Impartial Selection and the Power of up to Two Choices

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 1i¾?/i¾?2 of the maximum number of nominations. The bound of 1i¾?/i¾?2 is in fact best possible subject to impartiality. We prove here that the same bound can also be achieved deterministically by sometimes but not always selecting a second agent. We then show a separation between randomized mechanisms that make exactly two or upi¾?to two choices, and give upper and lower bounds on the performance of mechanisms allowed more than two choices.