Impartial Selection and the Power of Up to Two Choices
Impartial Selection and the Power of Up to Two Choices
复制标题
公正的选择和最多两种选择的力量
DOI：
10.1145/3107922
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
S. Tamura
中科院分区：
文献类型：
--
作者：
S. Tamura
我们研究的机制是根据其他成员的提名来选择一组代理中的成员，并且从代理不能影响自己的选择机会的意义上来说，这种机制是公正的。先前的工作表明，用于选择任何固定数量 k 的代理人的确定性机制受到严重限制，并且无法提取 k 个最高提名代理人的提名的恒定比例。我们在这里证明，可以通过允许该机制有时但并不总是选择少于 k 个代理来规避这种不可能的结果。这种增加的灵活性还提高了随机机制的性能，为此，我们展示了精确做出两个或最多两个选择的机制之间的分离，并为允许两个以上选择的机制给出了上限和下限。
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 k of agents are severely limited and cannot extract a constant fraction of the nominations of the k most highly nominated agents. We prove here that this impossibility result can be circumvented by allowing the mechanism to sometimes but not always select fewer than k agents. This added flexibility also improves the performance of randomized mechanisms, for which we show a separation between mechanisms that make exactly two or up to two choices and give upper and lower bounds for mechanisms allowed more than two choices.