Optimal Impartial Selection

Gio, 10/13/2016 - 12:01 / 13:00

207, Viale Romania, 32

Speaker: Max Klimm , Technische Universität Berlin

Optimal Impartial Selection.


A fundamental property of many interactions like the awarding of prizes, the election of heads of committees or the process of peer review is that one or more members of a set of agents are selected based on nominations from within the set. Since the agents act as voters and nominees at the same time it is desirable that a selection mechanism is impartial in the sense that the probability of selecting an agent is independent of the nominations cast by that agent. In graph theoretic terms, this leads to the interesting problem of selecting vertices with high in-degrees under the constraint that the selection probability of each vertex is independent of its outgoing edges. We give a randomized impartial mechanism that in expectation selects an agent with at least half the maximum number of nominations. This is best possible subject to impartiality and resolves a conjecture of Alon et al. Further results are given for the case where some agent receives many nominations, each agent casts at least one nomination, and more than one agent is selected.