Tournaments that cannot be represented by five voters orders found
Tournaments not inducible by five voters
Discrete Mathematics
Summary
The paper explores a type of mathematical structure called a tournament, which can sometimes be represented by a group of voters ranking options in order. When five voters rank these options, some tournaments cannot be matched exactly by their majority preferences. The authors improved the known smallest size of such a tournament and provided new examples using clever search algorithms and proof techniques. They also created verified computer proofs to confirm these results, making them reliable and reproducible.
What this means in practice
- •For voting system designers: Identify limitations of small-voter majority models to better design voting rules that avoid representational failures.
- •For combinatorial optimization engineers: Use specialized search and proof techniques to verify complex properties in preference aggregation problems that general solvers cannot handle efficiently.
Authors
Leonid Chindelevitch, Ararat Harutyunyan
Abstract
A tournament T is k-inducible if there are k linear orders on its vertex set such that, for every arc $i \to j$ of T, a majority of the orders rank i above j. For odd k, let N(k) be the least order at which some tournament is not k-inducible. Only N(3) = 8 is known exactly; for N(5) the best bounds were $12 \le N(5) \le 38$, from our previous paper [2], which also gave the first explicit example of moderate order, the Paley tournament $P_{43}$. Results. A bespoke search algorithm improves both ends: $13 \le N(5) \le 23$. The upper bound comes from proving that $P_{23}$ is not 5-inducible, the case Bachmeier et al. [1] reported they could not decide, their SAT solver not having terminated within a cumulative six weeks; ours takes 22 hours on one laptop. The lower bound comes from an analysis at order 12. We also show that $P_{31}$ is not 5-inducible, while $P_{19}$ is 5-inducible but not with unit margin, that is, not by a profile in which every arc is carried by exactly three voters against two. Both $P_{19}$ and $P_{23}$ are arc-critical for their respective properties, whereas $P_{31}$ and $P_{43}$ are not vertex-critical: deleting a vertex leaves a tournament that is still not 5-inducible. Method. The search places one vertex at a time, always choosing the vertex with the fewest options left, and propagates the consequences. Together with the automorphisms of the tournament, this decides on a single laptop instances that neither integer programming nor a general-purpose SAT solver can settle. The refutations for $P_{19}$ and $P_{23}$ are certified as well: the search is split into independent subproblems, a SAT solver emits a machine-checkable proof for each, and a separate program rechecks every proof. All results, subject to two human-checked lemmas, are reproducible from https://github.com/Leonardini/TournamentsBeyond5Voters.