Paper Info
Title
Computing with Voting Trees.
Abstract
A central challenge in social choice theory arises from the fact that there is no fair way to deterministically select a winner in an election among more than two candidates; the only definite collective preferences are between individual pairs of candidates. Combinatorially, one may summarize this information with a graph-theoretic tournament on n vertices (one per candidate), placing an edge from u to v if u would beat v in an election between only those two candidates (no ties are permitted). One well-studied procedure for selecting a winner is to specify a binary tree whose leaves are labeled by the candidates and evaluate it by running pairwise elections between the pairs of leaves, sending the winners to successive rounds of pairwise elections which ultimately terminate with a single winner. This structure is called a 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 returns a vertex of maximum out-degree in the given tournament. Perhaps surprisingly, the best previously known voting tree could only guarantee a returned out-degree of at least log(2) n, despite the fact that every tournament has a vertex of degree at least n-1/2. In this paper, we present three constructions, the first of which substantially improves this guarantee to Theta(root 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.
Year
DOI
Venue
2012
10.1137/130906726
SIAM JOURNAL ON DISCRETE MATHEMATICS
Keywords
DocType
Volume
tournament,voting tree,social choice theory
Journal
28
Issue
ISSN
Citations 
2
0895-4801
0
PageRank 
References 
Authors
0.34
1
3
Name
Order
Citations
PageRank
Jennifer Iglesias162.94
Nathaniel Ince200.34
Po-Shen Loh313318.68