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.