Computing with voting trees

DOI10.1137/130906726zbMATH Open1298.05067arXiv1211.0515OpenAlexW2049195527MaRDI QIDQ3192156FDOQ3192156

Nathaniel Ince, Jennifer Iglesias, Po-Shen Loh

Publication date: 26 September 2014

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: The classical paradox of social choice theory asserts 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 complete 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(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.

Full work available at URL: https://arxiv.org/abs/1211.0515

Recommendations

• A new perspective on implementation by voting trees
• Voting procedures, complexity of
• A survey on the complexity of tournament solutions
• It is difficult to tell if there is a Condorcet spanning tree
• The computational difficulty of manipulating an election

zbMATH Keywords

social choice theorytournamentvoting tree

Mathematics Subject Classification ID

Applications of graph theory (05C90) Trees (05C05) Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35) Voting theory (91B12)

This page was built for publication: Computing with voting trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3192156)