Optimal impartial correspondences

Abstract We study mechanisms that select a subset of a set of agents based on nominations among them. The goal is to maximize the minimum number of nominations received by any selected agent, subject to an impartiality constraint that the selection of a particular agent must be independent of the nominations cast by that agent. For situations where each agent casts at most d nominations, we give a mechanism that selects at most $$d+1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>d</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> agents and only selects agents who receive a maximum number of nominations or the maximum number of nominations minus one. We then show that this is best possible in the sense that no impartial mechanism can only select agents receiving a maximum number of nominations, even without any restrictions on the number of selected agents. We finally establish the following trade-off between the maximum number of agents selected and the minimum number of nominations for any selected agent when there are no constraints on the number of nominations each agent can cast: when selecting at most k agents out of n , it is possible to only select agents that receive at least the maximum number of nominations minus $$\big \lfloor \frac{n-2}{k-1} \big \rfloor +1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mo>⌊</mml:mo> </mml:mrow> <mml:mfrac> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>-</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:mfrac> <mml:mrow> <mml:mo>⌋</mml:mo> </mml:mrow> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> .