论文标题
对战略性社会决策方案的condorcet一致性和效率的轻松概念
Relaxed Notions of Condorcet-Consistency and Efficiency for Strategyproof Social Decision Schemes
论文作者
论文摘要
社会决策计划（SDSS）绘制了一组选民的偏好，而不是一组$ m $替代品的概率分布的替代品。 Gibbard对策略性SDSS的开创性表征意味着没有战略范围的Condorcet扩展，并且只有随机独裁统治才能满足后效率和策略性的范围。后者被称为随机独裁定理。我们通过分别针对Condorcet获奖者的概率和帕累托主导替代方案的概率引入下限来放松孔司的一致性和事后效率。然后，我们证明，分配概率与Copeland分数成比例的SD是唯一可以保证Condorcet获胜者至少2/m的匿名，中立和策略的SDS。此外，即使放弃匿名性和中立性，也没有任何策略防护SD可以超过此界限。其次，我们证明了Gibbard随机独裁统治定理的连续加强：我们在帕累托主导的替代方案上施加的可能性较小，接近随机独裁统治的距离是由此产生的SDS。最后，我们表明，唯一的匿名，中立和策略性的SDSS可以最大程度地提高Condorcet获奖者的可能性，同时最大程度地减少帕累托主导的替代方案的可能性是统一的随机独裁统治和随机谷物规则的混合物。
Social decision schemes (SDSs) map the preferences of a group of voters over some set of $m$ alternatives to a probability distribution over the alternatives. A seminal characterization of strategyproof SDSs by Gibbard implies that there are no strategyproof Condorcet extensions and that only random dictatorships satisfy ex post efficiency and strategyproofness. The latter is known as the random dictatorship theorem. We relax Condorcet-consistency and ex post efficiency by introducing a lower bound on the probability of Condorcet winners and an upper bound on the probability of Pareto-dominated alternatives, respectively. We then show that the SDS that assigns probabilities proportional to Copeland scores is the only anonymous, neutral, and strategyproof SDS that can guarantee the Condorcet winner a probability of at least 2/m. Moreover, no strategyproof SDS can exceed this bound, even when dropping anonymity and neutrality. Secondly, we prove a continuous strengthening of Gibbard's random dictatorship theorem: the less probability we put on Pareto-dominated alternatives, the closer to a random dictatorship is the resulting SDS. Finally, we show that the only anonymous, neutral, and strategyproof SDSs that maximize the probability of Condorcet winners while minimizing the probability of Pareto-dominated alternatives are mixtures of the uniform random dictatorship and the randomized Copeland rule.
