Six Candidates Suffice to Win a Voter Majority
Preprint
Abstract
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{\alpha}{1 - \ln \alpha} \geq \frac{2}{k + 1}$, then there always exists a committee of size $k$ such that less than an $\alpha$ fraction of the voters prefer an alternate candidate. These are the first nontrivial positive results that apply for all $k \geq 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.
Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- The Condorcet dimension of metric spacesOperations Research Letters, 2025
- Multi-Winner Voting with Approval Preferences2023
- Axiomatic characterization of committee scoring rulesJournal of Economic Theory, 2019
- Properties of multiwinner voting rulesSocial Choice and Welfare, 2017
- Extending Tournament SolutionsProceedings of the AAAI Conference on Artificial Intelligence, 2014
- How to choose a non-controversial list with k namesSocial Choice and Welfare, 2007
- The Bipartisan Set of a Tournament GameGames and Economic Behavior, 1993
- An Analysis of Simple Voting Systems for Electing CommitteesSIAM Journal on Applied Mathematics, 1981
- Majority committeesJournal of Economic Theory, 1981
- Condorcet Social Choice FunctionsSIAM Journal on Applied Mathematics, 1977