Tournaments determined by three and five voters

Abstract

The Kemeny median problem asks for a linear order minimizing the total pairwise disagreement with $m$ given rankings of $n$ options; it is NP-hard for every even $m\ge 4$ and every odd $m\ge 7$, while $m=3$ and $m=5$ remain open. Weighting each arc of the majority tournament by its margin reduces the problem to minimum-weight feedback arc set (FAS). The fewest voters inducing a tournament is its McGarvey number, and its predictability $\hat{I}{\pm }^{\ast }(T)$ is the largest supermajority threshold at which $T$ is inducible. We refute three conjectures on inducibility. (i) In any tournament, every minimum FAS is a minimal hitting set of the directed 3-cycles, strengthening a theorem of Milosz, Hamel and Pierrot; both of their conjectures fail: the 3-cycle extension for all odd $m\ge 5$, and the equality $\mathrm{FAS}={\mathrm{HS}}_3$ at $n=11$. (ii) The threshold conjecture proposed by Shepardson and Tovey fails for $m=3$, exactly on the boundary (predictability $=2/3$). (iii) For $m=5$ it fails strictly: the Paley tournament on 43 vertices, with predictability $181/301>3/5$, is not the majority of any 5 voters, making it the first explicit tournament of modest size beyond the reach of five voters.

29 pages, 7 figures

Topics & keywords