ProofAtlas

Social choice · majority tournaments · minimax

Condorcet Winning Sets

Collaboration beta

Can every election be represented by at most three candidates so that no outsider is preferred to all three by a strict majority? The size-three guarantee is open. Current external literature gives a general size-five guarantee.

∀finite elections∃S, |S|≤3: ∀c∉S, q(c,S)≤12 ?
Known results and sources
Definition-only schematic showing an outsider c compared with the set S={A,B,C} at the neutral threshold ≤ 1/2, above the open question of whether every finite election has a winning set of size at most three; no ballots or sample outcome are shown.
The strict size-three question asks whether some committee of at most three always defeats every outsider’s strict-majority challenge.

Research problem

Exact mathematical statement

Let voters give strict linear rankings of a finite candidate set CC. For S⊆CS\subseteq C and c∉Sc\notin S, let

q(c,S)=Prv[cis ranked above everys∈S].q(c,S)=\Pr_v[c\text{ is ranked above every }s\in S].

Is it true that every finite election has some SS with |S|≤3|S|\le3 such that q(c,S)≤12q(c,S)\le\tfrac12 for every c∉Sc\notin S? Equality is allowed: a counterexample must have every triple strictly overthrown.

Problem infographic

Problem at a glance

Problem-first explainer defining strict Condorcet winning sets, showing the open size-three question, the external size-five guarantee, and source-reported counterexample-conditional pair-shadow and candidate-bound deductions.
Current peer-reviewed work guarantees size five, while the size-three question remains open; under a hypothetical counterexample, the source derives winning pair shadows and a 19-candidate lower bound.

Current mathematical picture

Where work on Condorcet Winning Sets stands

Open problem

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

Useful failureAll-common-dominator relaxation

The source gives a random-tournament existence calculation where at least four common dominators force probability at least 4/7. Preserve one selected challenger per triple and exploit pair-shadow closure, exact ordering oracles, coalition cuts, or higher-order dependence.

Route status · Narrowed route
Main reductionFixed-selector minimax equivalence

The source proves the full conjecture equivalent to β(f)≤1/2 for every selector f.

Evidence posture · Source-reported route statement · dependencies incomplete
Priority open bridgeCompress a pair shadow to a winning triple.Task status · Ready to work on
Research-record correctionResearch-record correction

We corrected supporting details in the research record. The mathematical claims and their status did not change.

Reader-facing record corrected; mathematics unchanged

Work mapped so far

Condorcet Winning Sets in numbers

794retained lines of mathematical investigation794 in the current working snapshot
Argument development
607 · 76%
Explored or eliminated routes
64 · 8%
Computational analysis
23 · 3%
Open obligations
13 · 2%
Definitions and setup
87 · 11%
8selected mapped statements1routes investigated4open questions4contribution-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

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

13 selected steps

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

13 selected steps

Scroll horizontally to explore the route

Working route overview for Condorcet Winning SetsA selected map of recorded claims, active routes, useful failures, open questions, and their explicit relationships. Search, filter, zoom, or pan within this page.Does every finite election have a winning set of size at most three? — Depends on missing premiseDoes every finite electionhave a winning set of sizeat…Current reduction — Depends on missing premiseCurrent reductionFixed-selector minimax equivalence — Depends on missing premiseFixed-selector minimaxequivalenceAny counterexample has at least 19 candidates — Depends on missing premiseAny counterexample has atleast 19 candidatesClosing target — Depends on missing premiseClosing targetExact strict-overthrow convention — Depends on missing premiseExact strict-overthrowconventionPair shadows in a hypothetical counterexample — Depends on missing premisePair shadows in ahypothetical counterexampleThe order-19 exclusion is conditional — Depends on missing premiseThe order-19 exclusion isconditionalAll-common-dominator relaxation — stoppedAll-common-dominatorrelaxationCompress a pair shadow to a winning triple. — OpenCompress a pair shadow to awinning triple.Find a universal weighted minimax certificate. — OpenFind a universal weightedminimax certificate.Close expansion versus closure or find a counterexample. — OpenClose expansion versusclosure or find acounterexample.Full size-three conjecture unresolved — OpenFull size-three conjectureunresolved
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 routeAll-common-dominator relaxation

The source gives a random-tournament existence calculation where at least four common dominators force probability at least 4/7. Preserve one selected challenger per triple and exploit pair-shadow closure, exact ordering oracles, coalition cuts, or higher-order dependence.

Route status · Narrowed route

More ways to contribute

Open questions

Additional prepared tasks for exploring this research frontier.

4 featured tasks
01
Compress a pair shadow to a winning triple.Suggested move: Classify short cycles of the selected-overthrower map, attack |W(P)|=4, and show a minimal pair shadow cannot sustain all triple overthrowers.
Ready to work on
02
Find a universal weighted minimax certificate.Suggested move: Use pair-fiber cycles and the exact ordering oracle to build selector-dependent weights with maximum ranking score at most one half.
Ready to work on
03
Full size-three conjecture unresolved

The verification ledger lists the full conjecture as unresolved.

Suggested move: Resolve the exact source-reported obligation without treating it as an established negative result.
Ready to work on
04
Close expansion versus closure or find a counterexample.Suggested move: Prove the full-support transport violates a coalition cut or yields an exact closed subset, while separately maintaining certified searches for genuine size-four lower-bound elections.
Ready to work on

Sourced mathematical context

The known mathematical landscape

Context collected Aug 14, 2026
Current statusOpen problem

Whether every finite election has a strict-convention Condorcet winning set of size at most three remains open. SODA 2026 proves a general size-five guarantee. A 2026 primary search report states the known guarantee gap as lower bound three versus upper bound five and reports no election requiring more than three.

[2][3]
External progress

What the literature has established

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

  1. PreprintZilberstein, Berker, Li, and Martins described the remaining lower-three/upper-five gap, found no election requiring more than three in their searches, and proposed a conjecture implying a size-four bound.[3]
  2. Peer reviewedSong, Nguyen, and Lin proved that every election has a Condorcet winning set of size five, improving the preceding general bound of six.[2]
  3. Peer reviewedElkind, Lang, and Saffidine introduced and studied Condorcet winning sets as small committees robust to outside majority challenges.[1]
3 cited sources3 related results or reductionsReferences

Mathematical neighborhood

Related results and reusable starting points

Current focusCondorcet Winning Sets
Weaker or relaxed formUniversal Condorcet winning set of size five

The proved universal size-five guarantee is weaker than the open size-three guarantee sought here.

[2]
Related problem(t,alpha)-undominated sets

The (t,alpha)-undominated-set framework generalizes Condorcet winning sets, recovered at t=1 and alpha=1/2.

[2]
Weaker or relaxed formUniversal size-four Condorcet winning set

A new conjecture in the 2026 search report would imply size four, not size three, and remains unproved.

[3]

Formal and computational footholds

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

  • software · not independently reproducedAutomated election-search framework reported by Zilberstein et al.

    The preprint reports MILP search, symmetry breaking, subsampling, and constraint generation; ProofAtlas did not run or reproduce these computations.

    [3]

Formalization opportunities

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

  • Formalization targetA formal model of finite preference profiles, strict rankings, and majority comparison against a committee.
  • Formalization targetA formal proof of the minimax and pair-shadow reductions under the exact strict threshold convention.
  • Formalization targetMachine-checkable certificates for any claimed finite counterexample search or tournament classification.

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 supporting details in the research record. 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.

6 standing statements2 proposed statements4 open questions1 narrowed routes
Statements by mathematical role8 selected mapped statements
  • theorem candidate1 of 81
  • reduction2 of 82
  • lemma4 of 84
  • 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 every finite election have a winning set of size at most three?
  • retained route statementCurrent reductionintermediate
  • retained route statementClosing targetintermediate
  • retained route statementExact strict-overthrow conventionintermediate
  • retained route statementFixed-selector minimax equivalenceintermediate
  • retained route statementPair shadows in a hypothetical counterexampleintermediate
  • retained route statementAny counterexample has at least 19 candidatesintermediate
  • retained route statementThe order-19 exclusion is conditionalintermediate
  • 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 failureAll-common-dominator relaxationreported failure
  • Research targetCompress a pair shadow to a winning triple.open
  • Research targetFind a universal weighted minimax certificate.open
  • Research targetClose expansion versus closure or find a counterexample.open
  • Research targetFull size-three conjecture unresolvedopen
  • Narrowed routeAll-common-dominator relaxationThe source gives a random-tournament existence calculation where at least four common dominators force probability at least 4/7. Preserve one selected challenger per triple and exploit pair-shadow closure, exact ordering oracles, coalition cuts, or higher-order dependence.
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 bridgeCompress a pair shadow to a winning triple.

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
Prepared starting pointCompress a pair shadow to a winning triple.

Condorcet Winning Sets · 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

Can every election be represented by at most three candidates so that no outsider is preferred to all three by a strict majority? The size-three guarantee is open. Current external literature gives a general size-five guarantee.

  • 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 references3 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. 1
    Condorcet winning setsoriginal source · Edith Elkind, Jérôme Lang, Abdallah Saffidine · Social Choice and Welfare · 2015 · DOI 10.1007/s00355-014-0853-4 · accessed Aug 14, 2026
  2. 2
    A Few Good Choicespeer reviewed result · Haoyu Song, Thành Nguyen, Young-San Lin · Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms · 2026-01-07 · DOI 10.1137/1.9781611978971.175 · accessed Aug 14, 2026
  3. 3
    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-04-21 · ARXIV 2604.19851 · accessed Aug 14, 2026

Important qualifications

  • The collection focuses on the strict majority convention matching the governed source; equality-sensitive variants are excluded.
  • The 2026 search report is a preprint and its failure to find a larger example is computational evidence, not a proof that none exists.
  • The exact unreviewed source material’s embedded tournament computations and external classification dependency were not rerun or independently validated.

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

Expanded visual

Open original image