摘要翻译：
Gibbard-Satterthwaite定理指出，至少三个备选方案中的每一个非独裁选举规则都可以被战略性地操纵。我们证明了Gibbard-Satterthwaite定理的一个定量版本：单个随机选民的随机操纵对于三个备选方案中的任何选举规则来说，都将以不可忽略的概率成功，而这三个备选方案远不是独裁统治，也不是在其范围内只有两个备选方案。
---
英文标题：
《A Quantitative Version of the Gibbard-Satterthwaite Theorem for Three
  Alternatives》
---
作者：
Ehud Friedgut, Gil Kalai, Nathan Keller, and Noam Nisan
---
最新提交年份：
2011
---
分类信息：

一级分类：Mathematics        数学
二级分类：Combinatorics        组合学
分类描述：Discrete mathematics, graph theory, enumeration, combinatorial optimization, Ramsey theory, combinatorial game theory
离散数学，图论，计数，组合优化，拉姆齐理论，组合对策论
--
一级分类：Computer Science        计算机科学
二级分类：Artificial Intelligence        人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--
一级分类：Mathematics        数学
二级分类：Probability        概率
分类描述：Theory and applications of probability and stochastic processes: e.g. central limit theorems, large deviations, stochastic differential equations, models from statistical mechanics, queuing theory
概率论与随机过程的理论与应用：例如中心极限定理，大偏差，随机微分方程，统计力学模型，排队论
--

---
英文摘要：
  The Gibbard-Satterthwaite theorem states that every non-dictatorial election rule among at least three alternatives can be strategically manipulated. We prove a quantitative version of the Gibbard-Satterthwaite theorem: a random manipulation by a single random voter will succeed with a non-negligible probability for any election rule among three alternatives that is far from being a dictatorship and from having only two alternatives in its range.
---
PDF链接：
https://arxiv.org/pdf/1105.5129