  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.
