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 $\alpha^{*}(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.