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> .