Tournaments determined by three and five voters

Abstract

Pairwise majority has been studied since Ramon Llull in the 13th century and Condorcet in the 18th. A tournament records, for each pair of alternatives, which one a majority of voters prefers. A committee of $m$ voters produces only some tournaments; let $N(m)$ be the smallest number of alternatives on which some tournament cannot arise from any $m$ voters. Only $N(3)=8$ is known. We refute three conjectures. Every minimum feedback arc set of a tournament is a minimal set of arcs meeting every cyclic triangle, strengthening a theorem of Milosz, Hamel and Pierrot on Kemeny medians of three voters, and both of their conjectures fail. The third, going back to a question of Shepardson and Tovey, is that $m$ voters produce every tournament of predictability at least $(m+1)/(2m)$, predictability being the largest $\alpha$ for which some electorate produces the tournament with every majority backed by a fraction $\alpha$ of the voters. It fails for three voters: up to isomorphism, exactly 1,013 tournaments on ten alternatives have predictability $2/3$ yet arise from no three voters, none on fewer alternatives does, and failures occur only at the threshold. For five voters we show $12\le N(5)\le 38$ and give the first explicit tournament of moderate size that no five voters produce, the Paley tournament on 43 alternatives; its predictability exceeds $3/5$, so the conjecture fails even strictly above the threshold. A companion paper narrows the bounds to $13\le N(5)\le 22$. Public code reproduces every computation.

arXiv comment31 pages, 18 figures; v2: revised; companion paper: arXiv:2609.13924