# Six Candidates Suffice to Win a Voter Majority

arXiv: https://arxiv.org/abs/2411.03390 · HTML: https://mlsanity.com/paper/2411.03390/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Nov 2024.

## Built on by (most cited first, 3 of 3)

- [LLMs Judge Themselves: A Game-Theoretic Framework for Human-Aligned Evaluation](https://mlsanity.com/paper/2510.15746/) (2025)
- [Asymptotic Universal Alignment: A New Alignment Framework via Test-Time Scaling](https://mlsanity.com/paper/2601.08777/) (2026)
- [MILP the Gap: An Automated Reasoning Approach to Condorcet's Paradox](https://mlsanity.com/paper/2604.19851/) (2026)

## Abstract (arXiv)

A cornerstone of social choice theory is Condorcet's paradox which says that in an election where n voters rank m candidates it is possible that, no matter which candidate is declared the winner, a majority of voters would have preferred an alternative candidate. Instead, can we always choose a small committee of winning candidates that is preferred to any alternative candidate by a majority of voters? Elkind, Lang, and Saffidine raised this question and called such a committee a Condorcet winning set. They showed that winning sets of size 2 may not exist, but sets of size logarithmic in the number of candidates always do. In this work, we show that Condorcet winning sets of size 6 always exist, regardless of the number of candidates or the number of voters. More generally, we show that if fracα1 - ln α ≥ frac2k + 1, then there always exists a committee of size k such that less than an α fraction of the voters prefer an alternate candidate. These are the first nontrivial positive results that apply for all k ≥ 2. Our proof uses the probabilistic method and the minimax theorem, inspired by recent work on approximately stable committee selection. We construct a distribution over committees that performs sufficiently well (when compared against any candidate on any small subset of the voters) so that this distribution must contain a committee with the desired property in its support.