The Math Behind Condorcet — Tournaments, the Smith Set, and Cycles¶
The "graduate seminar" companion to Ranked Robin. None of this is needed to run or advocate for a Condorcet election — Ranked Robin ("most head-to-head wins") is the practical, explainable method. But once you ask what is the structure of the pairwise results, you walk straight into graph theory, game theory, and a few famous impossibility theorems. Here's the map.
→ Companion: Ranked Robin vs. the Condorcet winner · cycle resolution · Condorcet topic hub · Level: 301 · deep dive — Curriculum 301.5 (limits & theory), 301.7 (Condorcet/Score/Runoff disagree)
The one mental shift: the pairwise matrix is a graph¶
Every pair of candidates has a head-to-head winner, so the pairwise results form a tournament — a complete directed graph where an arrow A→B means "A beats B one-on-one." Almost every Condorcet idea below is just a question about this graph. That's the key move: Condorcet methods are graph algorithms, not vote-counting tricks.
- A Condorcet winner is a node that points to everyone (beats all) — a source with no incoming arrows.
- A Condorcet loser points to no one.
- A cycle (A→B→C→A) means the "beats" relation is not transitive — the famous Condorcet paradox (Condorcet, 1785). Majority rule, applied pairwise, can contradict itself. This is a property of the voters' preferences, not a flaw in any one method.
There is a whole academic field about just this graph — rules that read the arrows and nothing else, Ranked Robin/Copeland among them. → Tournament solutions, with the uncovered/Banks/bipartisan/Slater/Markov sets, McGarvey's theorem, and a three-ballot election with five defensible winners.
When there's no single winner: the Smith and Schwartz sets¶
These generalize "the Condorcet winner" to the case where none exists.
- Smith set (a.k.a. top cycle): the smallest set of candidates who all beat everyone outside the set. If a Condorcet winner exists, the Smith set is just
{that winner}; in a cycle, it's the whole cyclic clump at the top. - Schwartz set: a slightly tighter cousin (always Schwartz ⊆ Smith); the two differ only when there are pairwise ties.
- A method is Smith-efficient if it always elects from the Smith set — a strong, desirable property (it implies Condorcet-efficiency).
The math to compute them is graph theory: the Smith set is the top strongly connected component of the dominance graph. You find it with standard algorithms — Tarjan's or Kosaraju's SCC, or by taking the transitive closure (Floyd–Warshall) and reading off the maximal candidates. "Find the Smith set" = "find the top SCC."
The concept, worked: The Smith set — the smallest club that beats everyone outside it — the club-membership walkthrough on a runnable 4-candidate election (a 3-cycle plus a dominated outsider), the Smith-efficiency scorecard, and ISDA.
The whole order, not just the winner¶
A pairwise matrix can be asked for an order of finish, not only a winner — and the same cycles that can leave "who won?" unanswered can leave "who came 2nd?" unanswered too.
- A Condorcet ranking (pairwise order) is an order in which every candidate sits above everyone they beat head-to-head. It exists exactly when the tournament is acyclic — a stronger condition than "a Condorcet winner exists," which only needs a source at the top. Ada beating everyone while Ben, Cara and Dave cycle below her gives a Condorcet winner and no Condorcet ranking.
- When no such order exists, the standard fallback is the Smith ranking: take the Smith set of the whole field, set it aside as the top tier, take the Smith set of what remains, and repeat. That ranks tiers rather than candidates, always exists, and collapses to the Condorcet ranking when there are no cycles at all.
- What our engine prints is neither of those by name — it's the Copeland ranking, the win–loss standings of a Ranked Robin report. That agrees with the Condorcet ranking whenever one exists, but under a cycle it is a different ordering with a different meaning: the standings answer "who beat the most rivals?", the Smith ranking answers "who is still in contention?" — and the two can disagree about everyone below first place (the Smith set page's fine print works a five-candidate case where the Copeland leaders are two of the four candidates still in contention).
The distinction matters most where the order is the product: shortlists, party lists, and any multi-winner rule that seats the top N of a ranking rather than running a fresh count per seat.
The cycle-resolving methods, mapped to their math¶
| Method | What it does | The math it is |
|---|---|---|
| Copeland / Ranked Robin | elect the most head-to-head wins | tournament scoring (simplest) |
| Minimax | elect whoever's worst loss is smallest | optimization over the matrix |
| Schulze (beatpaths) | strongest path of majorities between candidates | widest-path / max-min Floyd–Warshall |
| Ranked Pairs (Tideman) | lock in the biggest majorities, skipping any that make a cycle | greedy + cycle detection |
| Kemeny–Young | the ranking that disagrees with the fewest voters | median ranking under Kendall-tau distance — NP-hard |
| Maximal lotteries / bipartisan set | mixed Nash equilibrium of the "majority game" | game theory + linear programming (von Neumann minimax) |
The last row is the gem: treat the margin matrix as a symmetric zero-sum game and solve for its optimal mixed strategy. It connects voting directly to game theory, is solved by an LP, and is beautifully well-behaved (Condorcet-, Smith-, and clone-consistent). If you want one "wow" topic, it's maximal lotteries.
The load-bearing theorems¶
- Arrow's impossibility theorem — no rank-aggregation rule can satisfy a short list of obviously-fair conditions at once.
- Gibbard–Satterthwaite — every reasonable non-dictatorial method is manipulable; strategy-proofness is impossible. (This is why favorite-betrayal incentives exist.)
- McKelvey–Schofield chaos theorem — in 2+ spatial dimensions, when there's no Condorcet winner the top cycle can wander anywhere, so agenda-setting power becomes decisive.
- Probability of cycles — under random ("impartial culture") preferences, a 3-candidate Condorcet cycle occurs ~8.8% of the time with many voters, and the chance of no Condorcet winner climbs toward 1 as candidates increase. (Exactly why a random 6-candidate, 5-ballot sweep leaves the Condorcet column blank so often — see
tools_adam/random_star_divergence.py.)
What to learn, in order of payoff¶
- Graph / tournament theory — strongly connected components, top cycle, paths. Unlocks Smith, Schwartz, and Schulze immediately.
- Order & relation theory — transitivity, dominance, the majority relation.
- Game theory + linear programming — minimax, Nash equilibria → maximal lotteries (the deepest, prettiest corner).
- Probability / combinatorics — how often cycles actually occur.
- Complexity theory — NP-hardness of Kemeny; manipulation-complexity (Bartholdi–Tovey–Trick).
- Social choice theory — the umbrella that ties it together (Arrow, Gibbard–Satterthwaite, Sen).
The honest caveat¶
You need none of this to run or advocate for a Condorcet election. Ranked Robin (Copeland) — "whoever wins the most head-to-head matchups" — is the practical, teachable method, and it resolves cycles fine for real-world use (margin, then lot). The Smith/Schwartz/Schulze/maximal-lotteries machinery only matters when you care about edge-case cycle behavior or want provable theoretical properties. It's deep and genuinely fun — but it's the graduate seminar, not the voter pamphlet.