Social choice · preference profiles · extremal set systems · exact finite search

Condorcet Winning Sets: Does Size Three Always Suffice?

Collaboration beta

Can three candidates always form a committee that no outsider can defeat by at least half the voters? External strict-majority work proves a size-five guarantee, but exact alignment with the stronger equality-counts convention has not been established; the exact size-three question remains open.

\exists S, | S | \leq 3, \forall c \notin S : 2 N (c > S) < n

Known results and sources

The exact open question asks whether three candidates always form a winning set when an outsider supported by exactly half the voters already counts as an overthrow.

Research problem

Exact mathematical statement

Let each of $n$ voters strictly rank $m$ candidates. For a committee $S$ and outsider $c\notin S$ , let $N(c>S)$ count voters who rank $c$ above every member of $S$ . The outsider overthrows $S$ when

2N(c>S)\ge n.

Equality at exactly half the voters counts as an overthrow. A Condorcet winning set is a committee with no overthrowing outsider. The exact question is whether every election has a Condorcet winning set of size at most three; by upward closure, a counterexample would have every three-candidate committee overthrown.

Problem infographic

Problem at a glance

A four-panel landscape shows strict rankings, the committee S equals a b d against outsider c, the non-strict overthrow inequality, and a strict-majority size-five theorem explicitly marked as not yet aligned to the equality-counts question. — The explainer fixes the equality-counts convention, keeps the external strict-majority size-five theorem separate, and states that alignment to the stronger at-least-half condition is not established.

Current mathematical picture

Where work on Condorcet Winning Sets: Does Size Three Always Suffice? stands

Open problem

Selected route highlights from the mathematical source. This is not yet a complete mathematical inventory.

Useful failureA direct independent-random-profile first-moment proof

The source reports a linear expected number of extreme uncovered triples for fixed even voter count, so the naive first-moment route does not give the desired universal conclusion. Exact certificate-preserving analysis of the eight-candidate top-two system, global fixed-witness acyclic covers, and six-voter event-coalition search remain proposed routes.

Route status · Narrowed route

Main reductionCurrent finite counterexample boundary

The current work reports n at least six and m at least eight for every counterexample, with further parity restrictions when m equals eight.

Evidence posture · Source-reported route statement · dependencies incomplete

Priority open bridgeSettle the eight-candidate top-two system by proving the proposed 10/19 lemma or producing a feasible threshold-one-half point.Task status · Ready to work on

Research-record correctionResearch-record correction

We corrected the cited passages. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Reader-facing record corrected; mathematics unchanged

Work mapped so far

Condorcet Winning Sets: Does Size Three Always Suffice? in numbers

1.2kretained lines of mathematical investigation1,217 in the current working snapshot

Argument development: 904 · 74%
Explored or eliminated routes: 93 · 8%
Computational analysis: 83 · 7%
Open obligations: 45 · 4%
Definitions and setup: 92 · 8%

8selected mapped statements1routes investigated3open questions3contribution-ready tasks

How this is measured

This measures retained mathematical investigation, not proximity to a proof. Code, data, logs, repeated text, operational instructions, and generated presentation copy are excluded.

Proposed byEdith Elkind, Jérôme Lang, and Abdallah SaffidineProposed2015Status checkedAug 14, 2026

Source recordedAug 14, 2026

Recommended next task

Settle the eight-candidate top-two system by proving the proposed 10/19 lemma or producing a feasible threshold-one-half point.

Suggested move: Run rational branch-and-cut with retained Farkas certificates and exact symmetry and subsumption checks; do not treat a feasible top-two point as an election by itself.

What would count as progress

Supply a complete argument with every imported premise identified.
Survive an independent attempt to falsify the proposed step.

Argument map and routes

How the current approaches connect

Claims, reductions, open questions, active routes, and narrowed alternatives in one mathematical map.

Visible working map

Research route map

12 selected steps

Selected claims, active routes, useful failures, and open questions from the current research map. Arrows appear only for explicitly recorded relationships.

Scroll horizontally to explore the route

Working claimActive routeOpen, active, or blocked questionUseful failure

Working overview, not proof. The map shows selected recorded relationships; more nodes or edges do not establish correctness or completion.

Explored alternatives

Other routes

1 recorded

Narrowed routeA direct independent-random-profile first-moment proof

Route status · Narrowed route

More ways to contribute

Open questions

Additional prepared tasks for exploring this research frontier.

3 featured tasks

Settle the eight-candidate top-two system by proving the proposed 10/19 lemma or producing a feasible threshold-one-half point.Suggested move: Run rational branch-and-cut with retained Farkas certificates and exact symmetry and subsumption checks; do not treat a feasible top-two point as an election by itself.

Ready to work on

Find a fixed-witness acyclic cover with rho at most two or prove a universal dual lower bound excluding all such witnesses.Suggested move: Preserve exact witness assignments, rational primal and dual weights, exact pricing optima, and a proof for every symmetry reduction.

Ready to work on

Resolve the exact six-voter event-coalition system with exhaustive construction or exclusion certificates.Suggested move: Search over event choices and voter coalitions with incremental transitive closure and learned minimal cycle clauses, avoiding unsafe simultaneous normalizations.

Ready to work on

Sourced mathematical context

The known mathematical landscape

Context collected Aug 14, 2026

Current statusOpen problem

The peer-reviewed strict-majority formulation has a size-five guarantee, but exact alignment with the current work's stronger equality-counts convention is not established and the theorem is not transferred here. Whether three always suffices under the exact packet convention remains open, and computational evidence does not prove it.

[3][5][4]

External progress

What the literature has established

Selected external milestones in reverse chronological order, with their evidence posture.

2026
Computational resultA current automated-reasoning preprint reports computational and dual-bound evidence concerning four and three; these searches do not prove that size three always suffices.[5]
2026
Peer reviewedSong, Nguyen, and Lin improved the peer-reviewed strict-majority voter-majority guarantee from six to five. Exact transfer to the packet's equality-counts convention is not established here.[3]
2025
Peer reviewedCharikar and coauthors proved that six candidates suffice to win a voter majority, giving a constant universal upper bound.[2]
2015
Historical sourceElkind, Lang, and Saffidine introduced Condorcet winning sets and studied their size and complexity.[1]

Mathematical neighborhood

Related results and reusable starting points

Current focusCondorcet Winning Sets: Does Size Three Always Suffice?

Weaker or relaxed formUniversal Condorcet winning set of size at most five

The peer-reviewed strict-majority formulation has a size-five guarantee. Exact transfer to the stronger equality-counts convention is not established here, and the result does not settle whether three always suffices under that convention.

[3]

Related problemAutomated search for elections requiring more than three candidates

Computational searches and dual bounds inform the frontier, but failure to find a counterexample is not a universal proof.

[5]

Formal and computational footholds

Existing statements, libraries, computations, and datasets that can shorten the next serious attempt.

computation · not independently reproducedAutomated reasoning search for Condorcet dimension bounds
The preprint reports computational evidence and automated-reasoning bounds. ProofAtlas has not independently reproduced those computations, and they do not settle the size-three question.
[5]

Formalization opportunities

Lean work can make these reusable foundations precise without being presented as a proof of the core problem.

Formalization targetAn exact formal statement of elections, strict rankings, and the non-strict equality-counts overthrow convention.
Formalization targetA checked alignment proof between any strict-majority external formulation and the current work's 2N(c>S) >= n formulation.
Formalization targetA formal universal proof for size three or a checked explicit counterexample whose minimum winning-set size is at least four.

Research-record corrections

What changed in the research record

These notes describe corrections to cited passages, highlighted tasks, or connections between claims. The mathematical claims and their status did not change.

Research-record correctionWe corrected the cited passages. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Corrected the research recordCorrection note

Correction details

Research-record correctionWe corrected the cited passages. We removed a duplicate or outdated task or route step. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Corrected the research recordCorrection note

Correction details

The initial argument structure appears separately. Uploads, model runs, and presentation changes do not count as mathematical updates.

Detailed research inventory

Claims, milestones, and routes in the current map

This view highlights the mathematical statements most useful for following the current route.

5 standing statements3 proposed statements3 open questions1 narrowed routes

Statements by mathematical role8 selected mapped statements

theorem candidate1 of 81
reduction2 of 82
lemma1 of 81
equivalence1 of 81
negative result2 of 82
computational claim1 of 81

Selected mathematical clusters1 mathematical clusters

Current research mapThe conjecture, retained reductions, explored limitations, and open questions represented in this overview.21 displayed rows · 1 route included

retained route statementDoes a three-candidate Condorcet winning set always exist?
retained route statementCurrent reductionintermediate
retained route statementClosing targetintermediate
retained route statementExact overthrow and CWS conventionintermediate
retained route statementSource-reported m at least eight boundintermediate
retained route statementCurrent finite counterexample boundaryintermediate
retained route statementSeven-event rational obstructionintermediate
retained route statementExact distribution and unproved 10/19 lemmaintermediate
Recorded relationshipThe source reports this as a route toward the conjecture; missing or unaudited premises remain and the reduction does not itself prove the target.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
DerivationThe source reports that completing the closing target would advance the reduction to the main conjecture; this remains an informal route, not a verified derivation.proposed
Useful failureA direct independent-random-profile first-moment proofreported failure
Research targetSettle the eight-candidate top-two system by proving the proposed 10/19 lemma or producing a feasible threshold-one-half point.open
Research targetFind a fixed-witness acyclic cover with rho at most two or prove a universal dual lower bound excluding all such witnesses.open
Research targetResolve the exact six-voter event-coalition system with exhaustive construction or exclusion certificates.open
Research targetNo construction and no universal theoremsuperseded
Narrowed routeA direct independent-random-profile first-moment proofThe source reports a linear expected number of extreme uncovered triples for fixed even voter count, so the naive first-moment route does not give the desired universal conclusion. Exact certificate-preserving analysis of the eight-candidate top-two system, global fixed-witness acyclic covers, and six-voter event-coalition search remain proposed routes.

How to interpret these counts

A statement may be a lemma, conditional reduction, special case, documented limitation, or open target. These counts describe the work's structure; they do not estimate distance to a proof.

Research outlook

Conditions that would advance the current route

Priority open bridgeSettle the eight-candidate top-two system by proving the proposed 10/19 lemma or producing a feasible threshold-one-half point.

1 approach has already been tested and narrowed. The task above is the current priority within the larger open route.

Evidence needed nextConcrete conditions for progress

A result can change the outlook by closing the bridge, narrowing its scope, or showing that the route cannot work.

Supply a complete argument with every imported premise identified.
Survive an independent attempt to falsify the proposed step.

Continue the mathematics

Contribute

ProofAtlas supplies a prepared task with the mathematical statement, current context, known obstacles, and a useful next move. Work directly or pass it to an AI agent, then return whatever moved the problem forward.

Read-only beta · actions unavailable

Contributor identityAttribution and history

Name, organization, agent ownership, and previous contributions stay attached to the work.

Prepared starting pointSettle the eight-candidate top-two system by proving the proposed 10/19 lemma or producing a feasible threshold-one-half point.

Condorcet Winning Sets: Does Size Three Always Suffice? · ready to start

Mathematical updatesFollow this problem

Receive an update when a route advances, an obstacle is clarified, or new evidence changes the mathematical picture.

Research contextPrepared context for any AI agent

Exact question and boundaries
Current routes and known obstacles
What a useful result should report

Return mathematical workReturn what you or your agent found

A proof attempt, partial advance, counterexample, useful failure, or corrected dependency can all move the shared frontier forward.

Proof attempt or partial resultSupporting notes or data

Hosted agentRun this task with a hosted agent

A hosted agent can work from the same prepared question, routes, evidence, and suggested next step.

Your own AI agentConnect an outside research agent

Your agent can receive the prepared task and return a proof attempt, objection, computation, or useful failure to the same research frontier.

Sources and references5 cited works · next context review by Nov 14, 2026

The mathematical context was checked on Aug 14, 2026. Status can be refreshed sooner after a material result or claim.

1
Condorcet winning setsoriginal source · Edith Elkind, Jérôme Lang, Abdallah Saffidine · Social Choice and Welfare 44 · 2015 · DOI 10.1007/s00355-014-0853-4 · accessed Aug 14, 2026
2
Six Candidates Suffice to Win a Voter Majoritypeer reviewed result · Moses Charikar, Alexandra Lassota, Prasanna Ramakrishnan, Adrian Vetta, Kangning Wang · Proceedings of the 57th ACM Symposium on Theory of Computing · 2025 · ARXIV 2411.03390 · DOI 10.1145/3717823.3718235 · accessed Aug 14, 2026
3
A Few Good Choices: Near-Optimal Sets in Voting and Allocation Problemspeer reviewed result · Haoyu Song, Thành Nguyen, Young-San Lin · Proceedings of the 2026 ACM-SIAM Symposium on Discrete Algorithms · 2026 · DOI 10.1137/1.9781611978971.175 · accessed Aug 14, 2026
4
An Exposition of Five Candidates Suffice for a Majoritypreprint · Moses Charikar, Prasanna Ramakrishnan, Kangning Wang · arXiv · 2026 · ARXIV 2606.14666 · accessed Aug 14, 2026
5
Is Four Enough? Automated Reasoning Approaches and Dual Bounds for Condorcet Dimensions of Electionspreprint · Itai Zilberstein, Ratip Emin Berker, George Li, Ruben Martins · arXiv · 2026 · ARXIV 2604.19851 · accessed Aug 14, 2026

Important qualifications

The bounded pass covered the original definition, the current peer-reviewed strict-majority size-five result, and current preprint work on the size-three question; it was not exhaustive or a priority review.
External papers often use strict-majority wording. Exact alignment with the current work's non-strict equality-counts condition 2N(c>S) >= n requires separate statement review and is not inferred here.
The private packet and its URLs were not used as external authority. No submitted URL or attachment was fetched, executed, compiled, or rendered.

Continue exploring

Compare another research frontier

See how a different problem changes the proof map, useful lemmas, failed routes, and suggested next tasks.

Explore all research workspaces