论文标题
社会选择的平滑可能性
The Smoothed Possibility of Social Choice
论文作者
论文摘要
我们开发了一个框架，该框架利用Spielman和Teng的平滑复杂性分析来规避社会选择中的悖论和不可能的定理，这是由AI和ML提供支持的现代社会选择的动机。对于Condrocet的悖论，我们证明，随着代理数量的增加，悖论的平滑可能性要么以指数速度消失，要么根本不会消失。对于同时满足匿名性，中立性和共振性的不存在的不存在投票规则的不可能，我们表征了不可能消失的速度，即在多条件下快速或以指数级的速度。我们还提出了一种新颖的易于计算的胜利机制，该机制可在自然环境中最佳地保留匿名性和中立性。我们的结果说明了社会选择的平滑可能性 - 即使在最坏的情况下悖论和不可能的定理成立，它们在实践中可能并不是一个很大的关注点。
We develop a framework that leverages the smoothed complexity analysis by Spielman and Teng to circumvent paradoxes and impossibility theorems in social choice, motivated by modern applications of social choice powered by AI and ML. For Condrocet's paradox, we prove that the smoothed likelihood of the paradox either vanishes at an exponential rate as the number of agents increases, or does not vanish at all. For the ANR impossibility on the non-existence of voting rules that simultaneously satisfy anonymity, neutrality, and resolvability, we characterize the rate for the impossibility to vanish, to be either polynomially fast or exponentially fast. We also propose a novel easy-to-compute tie-breaking mechanism that optimally preserves anonymity and neutrality for even number of alternatives in natural settings. Our results illustrate the smoothed possibility of social choice -- even though the paradox and the impossibility theorem hold in the worst case, they may not be a big concern in practice.
