Vote Until Two of You Agree: Mechanisms with Small Distortion and Sample Complexity
Vote Until Two of You Agree: Mechanisms with Small Distortion and Sample Complexity
复制标题
投票直到你们两个同意：失真小且样本复杂的机制
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Lirong Xia
中科院分区：
文献类型：
--
作者：
Stephen Gross;Elliot Anshelevich;Lirong Xia
为了设计具有理想效用特性、规范特性以及低样本复杂度的社会选择机制，我们提出了一种名为“2 - 一致”的新随机机制。该机制向随机选民询问他们的首选方案，直到至少有两名选民意见一致，此时它将该方案选为获胜者。我们证明，尽管它简单且样本复杂度低，但当备选方案数量不多时，“2 - 一致”机制在度量空间上实现了近乎最优的扭曲，并且满足匿名性、中立性、事后帕累托效率、非常强的随机占优参与性，并且近似真实。我们进一步表明，对于有决定性主体的更多数量的备选方案，“2 - 一致”机制也能很好地发挥作用。
To design social choice mechanisms with desirable utility properties, normative properties, and low sample complexity, we propose a new randomized mechanism called 2-Agree. This mechanism asks random voters for their top alternatives until at least two voters agree, at which point it selects that alternative as the winner. We prove that, despite its simplicity and low sample complexity, 2-Agree achieves almost optimal distortion on a metric space when the number of alternatives is not large, and satisfies anonymity, neutrality, ex-post Pareto efficiency, very strong SD-participation, and is approximately truthful. We further show that 2-Agree works well for larger number of alternatives with decisive agents.