摘要翻译：
在社会选择、博弈论、政治学和公共选择等许多学科中，理解选举被打成平手的可能性是一个经典的话题。尽管有大量的文献和普遍认为联系是罕见的，但除了I.I.D.下几个简单的位置评分规则之外，人们对大型选举中联系有多罕见知之甚少。对选票的均匀分配，被称为社会选择中的公正文化(IC)。特别是，在Marchant于2001年明确提出在IC下建立k-way联系的可能性作为一个悬而未决的问题后，进展甚微。在一个比I.I.D.更普遍和更现实的模型下，我们给出了一个关于广泛的普遍研究的投票规则的开放问题的渐近回答。模型（特别是IC）--夏的平滑社会选择框架，受斯皮尔曼和滕的平滑复杂性分析的启发。在位置计分规则、基于边序的规则和基于多轮计分的淘汰规则下，我们证明了关于平分的光滑似然性的二分定理，这些规则包括常见的投票规则，如复数规则、Borda规则、veto规则、maximin规则、Copeland规则、排序对规则、Schulze规则、STV规则和Coombs规则作为特例。我们还在Preflib上对合成数据和真实世界秩数据进行了实验，对理论结果进行了补充。我们的主要技术工具是关于泊松多项式变量在多面体中的光滑似然性的改进的二分刻划，这是通过探索多面体的V-表示和矩阵表示之间的相互作用而证明的，可能是独立的兴趣。
---
英文标题：
《How Likely Are Large Elections Tied?》
---
作者：
Lirong Xia
---
最新提交年份：
2021
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Computer Science and Game Theory        计算机科学与博弈论
分类描述：Covers all theoretical and applied aspects at the intersection of computer science and game theory, including work in mechanism design, learning in games (which may overlap with Learning), foundations of agent modeling in games (which may overlap with Multiagent systems), coordination, specification and formal methods for non-cooperative computational environments. The area also deals with applications of game theory to areas such as electronic commerce.
涵盖计算机科学和博弈论交叉的所有理论和应用方面，包括机制设计的工作，游戏中的学习（可能与学习重叠），游戏中的agent建模的基础（可能与多agent系统重叠），非合作计算环境的协调、规范和形式化方法。该领域还涉及博弈论在电子商务等领域的应用。
--
一级分类：Economics        经济学
二级分类：Theoretical Economics        理论经济学
分类描述：Includes theoretical contributions to Contract Theory, Decision Theory, Game Theory, General Equilibrium, Growth, Learning and Evolution, Macroeconomics, Market and Mechanism Design, and Social Choice.
包括对契约理论、决策理论、博弈论、一般均衡、增长、学习与进化、宏观经济学、市场与机制设计、社会选择的理论贡献。
--
一级分类：Mathematics        数学
二级分类：Statistics Theory        统计理论
分类描述：Applied, computational and theoretical statistics: e.g. statistical inference, regression, time series, multivariate analysis, data analysis, Markov chain Monte Carlo, design of experiments, case studies
应用统计、计算统计和理论统计：例如统计推断、回归、时间序列、多元分析、数据分析、马尔可夫链蒙特卡罗、实验设计、案例研究
--
一级分类：Statistics        统计学
二级分类：Statistics Theory        统计理论
分类描述：stat.TH is an alias for math.ST. Asymptotics, Bayesian Inference, Decision Theory, Estimation, Foundations, Inference, Testing.
Stat.Th是Math.St的别名。渐近，贝叶斯推论，决策理论，估计，基础，推论，检验。
--

---
英文摘要：
  Understanding the likelihood for an election to be tied is a classical topic in many disciplines including social choice, game theory, political science, and public choice. Despite a large body of literature and the common belief that ties are rare, little is known about how rare ties are in large elections except for a few simple positional scoring rules under the i.i.d. uniform distribution over the votes, known as the Impartial Culture (IC) in social choice. In particular, little progress was made after Marchant explicitly posed the likelihood of k-way ties under IC as an open question in 2001.   We give an asymptotic answer to the open question for a wide range of commonly studied voting rules under a model that is much more general and realistic than i.i.d. models (especially IC) -- the smoothed social choice framework by Xia that was inspired by the celebrated smoothed complexity analysis by Spielman and Teng. We prove dichotomy theorems on the smoothed likelihood of ties under positional scoring rules, edge-order-based rules, and some multi-round score-based elimination rules, which include commonly studied voting rules such as plurality, Borda, veto, maximin, Copeland, ranked pairs, Schulze, STV, and Coombs as special cases. We also complement the theoretical results by experiments on synthetic data and real-world rank data on Preflib. Our main technical tool is an improved dichotomous characterization on the smoothed likelihood for a Poisson multinomial variable to be in a polyhedron, which is proved by exploring the interplay between the V-representation and the matrix representation of polyhedra and might be of independent interest.
---
PDF下载：
-->