Combinatorics of Voting Trees
February 27, 2013
Given a set of candidates $\{1,\ldots,n\}$, define the tournament $T$ by
placing an edge from $i$ to $j$ if $i$ would beat $j$ in an election
between only those two candidates (no ties are permitted). One
well-studied procedure for selecting a winner is to run pairwise
elections, sending the winners to successive rounds of pairwise elections
which ultimately terminate with a single winner. This process is
represented by a binary tree whose leaves are labeled by the candidates
that are initially matched against each other, and this structure is
called a \emph{voting tree}.
Much research has investigated which functions on tournaments are computable in this way. Fischer, Procaccia, and Samorodnitsky quantitatively studied the computability of the Copeland rule, which selects a vertex of maximum out-degree in the given tournament. Perhaps surprisingly, the best previously known voting tree could only guarantee an out-degree of at least $\log_2 n$. In this paper, we present three constructions, the first of which substantially improves this guarantee, to $\Theta(\sqrt{n})$. The other two demonstrate the richness of the voting tree universe, with a tree that resists manipulation, and a tree which implements arithmetic modulo three.
Joint work with Po-Shen Loh and Nate Ince.
Much research has investigated which functions on tournaments are computable in this way. Fischer, Procaccia, and Samorodnitsky quantitatively studied the computability of the Copeland rule, which selects a vertex of maximum out-degree in the given tournament. Perhaps surprisingly, the best previously known voting tree could only guarantee an out-degree of at least $\log_2 n$. In this paper, we present three constructions, the first of which substantially improves this guarantee, to $\Theta(\sqrt{n})$. The other two demonstrate the richness of the voting tree universe, with a tree that resists manipulation, and a tree which implements arithmetic modulo three.
Joint work with Po-Shen Loh and Nate Ince.