Elections in which every Condorcet winning set has four candidates

Condorcet's paradox says that an election may have no candidate whom a majority prefers to every rival, so one can instead elect a small committee that no outside candidate beats. Five candidates are known to suffice in every election, and it is conjectured that three always do. The task is to refute that conjecture, or to prove it.

Problem

There are $n$ voters and $m$ candidates, and each voter ranks all candidates strictly. A set $S$ of candidates is a Condorcet winning set if, for every candidate $c \notin S$, fewer than half of the voters rank $c$ above every member of $S$. Equivalently, for each outsider $c$, a strict majority of voters prefers some member of $S$ to $c$. Supersets of Condorcet winning sets are again Condorcet winning sets.

Task. Find an election in which no set of three candidates is a Condorcet winning set, so that every Condorcet winning set has at least four members; or prove that every election has a Condorcet winning set of size at most three.

Background

Elkind, Lang and Saffidine introduced Condorcet winning sets as a committee-level answer to Condorcet's paradox. They showed that sets of size two may not exist, while sets of size logarithmic in the number of candidates always do [1]. Charikar, Lassota, Ramakrishnan, Vetta and Wang proved at STOC 2025 that six candidates always suffice, whatever the numbers of voters and candidates [2], and they conjecture that three suffice. The question sits between social choice and combinatorics: it asks how much majority support a tiny committee can always guarantee.

What is known

• Size 2 is not always enough (Elkind, Lang and Saffidine, 2015) [1].
• Size 6 always suffices (Charikar, Lassota, Ramakrishnan, Vetta and Wang, 2025) [2], improved to size 5 by Nguyen, Song and Lin [3].
• So the smallest size that always suffices is 3, 4 or 5.

What would count as progress

• An explicit election (a list of $n$ rankings of $m \ge 4$ candidates) in which every 3-set $S$ is beaten by some outsider whom at least half of the voters rank above all of $S$. Checking runs over the $\binom{m}{3}$ triples and $m$ challengers, which is instant for moderate sizes.
• Epoch scores submissions with its own verifier: a solution is the $n \times m$ matrix of rankings, and the verifier checks every 3-candidate committee.
• A proof that four candidates always suffice would already improve the known bound; a proof that three suffice would confirm the conjecture.

References

1. E. Elkind, J. Lang and A. Saffidine, Condorcet winning sets, Social Choice and Welfare 44 (2015), 493–517. doi:10.1007/s00355-014-0853-4
2. M. Charikar, A. Lassota, P. Ramakrishnan, A. Vetta and K. Wang, Six candidates suffice to win a voter majority, STOC 2025, 1590–1601. doi:10.1145/3717823.3718235 (arXiv:2411.03390)
3. T. Nguyen, H. Song and Y.-S. Lin, A few good choices, 2025. arXiv:2506.22133

Source

Imported from FrontierMath: Open Problems, condorcet-winning-sets, curated by Epoch AI. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.