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. The problem is important not only as a fundamental problem in probability theory and statistics, but also because of its critical roles in many other important issues such as indecisiveness of voting, strategic voting, privacy of voting, voting power, voter turn out, etc. 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 [Mar01] 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 including IC--the smoothed social choice framework [Xia20], which was inspired by the celebrated smoothed complexity analysis [ST09]. We prove dichotomy theorems on the smoothed likelihood of ties under a large class of voting rules. 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.
翻译:在许多学科,包括社会选择、游戏理论、政治学和公众选择中,了解选举被捆绑的可能性是一个古典话题。 这个问题不仅作为概率理论和统计中的根本问题而重要,而且因其在许多其他重要问题中的关键作用,例如投票的不精确性、战略投票、投票隐私、投票权、选民退出等等。 尽管有大量文献和关于联系很少的共同信念,但除了在社会选择中被称为不偏颇文化(IC)的投票统一分配(i.d.)之下的少数简单立场评分规则外,在大型选举中很少知道联系有多罕见。 特别是,在三月[Mar01]之后,在许多其他重要问题中,它显然使K-way关系成为了2001年的开放问题。 尽管我们从大量文献和共同研究的众多的投票规则的开放性问题中,我们在一个比i.d.d.包括IC-平稳的社会选择框架[Xia20]在内的一些独立候选人统一分配规则,在社会选择中被称为不偏倚文化(IC)的一个根本问题。 在三月[Mar01]之后,几乎没有取得什么进展。