Decision Sciences & Systems
Technical University of Munich

Felix Fischer (TU Berlin): Impartial Selection and the Power of Up to Two Choices

Tuesday, 22 December 2015 14:00
DSS Seminarraum (01.10.033)

We study mechanisms that select members of a set of agents based on nominations by other members and that are impartial in the sense that agents cannot influence their own chance of selection. Prior work has shown that deterministic mechanisms for selecting any fixed number of agents are severely limited, whereas randomization allows for the selection of a single agent that in expectation receives at least 1/2 of the maximum number of nominations. The bound of 1/2 is in fact best possible subject to impartiality, and we show that it can also be achieved deterministically by sometimes but not always selecting a second agent. We further show a separation between randomized mechanism that make exactly two or up to two choices, and give upper and lower bounds on the performance of mechanisms allowed more than two choices. (Joint work with Antje Bjelde and Max Klimm.)


All Dates

  • Tuesday, 22 December 2015 14:00

Powered by iCagenda

Decision Sciences & Systems (DSS), Department of Informatics (I18), Technische Universität München, Boltzmannstr. 3, 85748 Garching, Germany
©2002-2018 DSS All Rights Reserved
Impressum, Privacy Policy, Copyright Information and Disclaimer