Skip to content

Tournament solutions — the theory of the win-loss graph

Throw away everything about an election except who beat whom head-to-head. No margins, no first choices, no scores — just arrows. What's left is a tournament: a complete directed graph. A tournament solution is a rule for picking the winners out of that graph, and there is a whole academic literature on it, because the graph can cycle and then "the best" has no obvious meaning. This page is the map: what the field is, why it exists, and exactly how much of it touches Ranked Robin, STAR and Approval.

→ Related: what a method reads — the C1/C2/C3 tiers this page is the C1 half of · the math behind Condorcet · the Smith set · cycle resolution — what the C2 methods do with the margins tournament solutions discard · Level: 301 · deep dive

Runnable: Tournament solutions, counted — five defensible winners from a three-ballot election, both engines agreeing.

"Is this graph theory or voting theory?" — genuinely both, and that's the point

It's voting theory that has been completely translated into graph theory, so thoroughly that the papers read like combinatorics. Every concept has two names:

Voting theory says Graph theory says
Copeland score (head-to-head wins) outdegree of the vertex
Condorcet winner vertex with an arrow to everyone (a source)
the pairwise-results table adjacency matrix M(T)
top cycle / Smith set top strongly connected component
uncovered set (Landau set) the kings of the tournament — its center
Slater's rule minimum feedback arc set (NP-hard)
Markov set essentially PageRank on the win graph
bipartisan set support of the Nash equilibrium of a zero-sum game

The graph theory is where the answers come from; the voting theory is where the questions come from — which set of candidates a democratic society should regard as the legitimate winners. Neither half is decoration. And it means a fact proved about tournaments is a fact about elections, which is why this literature can be unusually crisp about things voting arguments usually hand-wave.

Why the field exists: majority rule eats its own tail

Start from the most appealing democratic primitive there is: A is socially better than B if more people prefer A to B. May's theorem says that for two candidates this is essentially the only sensible rule. So the pairwise "beats" relation looks like bedrock.

It isn't transitive. A beats B, B beats C, C beats A — the Condorcet paradox — and then there is no maximal element at all. "Elect the best" has no referent. Tournament solutions are the response: give up on maximality, and define a replacement. Each one is a different answer to "what should 'best' mean when 'beats' goes in circles."

Two structural facts frame everything else:

  • McGarvey's theorem (1953). Every complete pairwise pattern is realizable — for any tournament you can draw, some electorate produces exactly it (with at most m(m−1) voters; later improved to about m/log m). So there is no hidden regularity to exploit. The graph can be as perverse as you like, and real voters can produce it. This is also why the runnable cases in this library can be built at all: draw the graph you want to teach, then find the ballots.
  • A "tournament" assumes no pairwise ties. With an odd number of voters and complete ballots, every head-to-head has a winner. Real elections tie, and then the object is a weak tournament, where these rules become generalizations with no canonical extension — the chapter spends a whole section on it. Worth knowing before quoting a theorem at a real election. Our own pairwise report is a For / Equal Support / Against table, which is strictly richer than a tournament and richer than margins.

The solutions, coarse to fine

All of them agree — trivially — whenever a Condorcet winner exists: every one returns just that candidate. They only differ in a cycle, which is the recurring theme of this whole subject.

Solution Picks Cost
Top cycle (Smith set) the smallest group that beats everyone outside it linear
Uncovered set everyone who reaches every rival in ≤ 2 steps — "I beat you, or I beat someone who beat you" polynomial
Banks set the tops of the maximal transitive sub-tournaments NP-complete
Bipartisan set the support of the win-graph game's unique Nash equilibrium polynomial (LP)
Copeland set most head-to-head wins ← this one is Ranked Robin linear
Slater set the tops of the closest linear orderings (fewest arrows reversed) NP-hard
Markov set who wins most often in a stay-at-the-table tournament (≈ PageRank) polynomial

Two things a newcomer should take from that table. First, "how hard is it to compute" varies wildly and doesn't track how sensible the rule is — Banks and Slater are both intellectually respectable and both intractable, while Copeland is linear-time. Second, most of these return a set, not a winner. That's not a failure; irresoluteness is the normal state here. Getting to one name takes a further rule — usually information from outside the graph, or a lot, though a tie between exactly two candidates can be settled by an arrow the graph already contains, which is the fine distinction the next section turns on.

The three axioms the literature actually argues about:

  • Monotonicity — gaining a win never costs you your place in the choice set. Nearly everything satisfies it. (This is a much weaker condition than monotonicity as we use it elsewhere.)
  • Stability — chosen from B and chosen from C if and only if chosen from B ∪ C. Demanding; fails for most solutions.
  • Composition-consistency — "choose the best from the best components," the strong form of clone-independence. Satisfied by the uncovered, Banks and bipartisan sets. Failed by Copeland, which is the interesting part for us.

What this has to do with Ranked Robin: everything

Ranked Robin is a tournament solution. It is the Copeland set — most head-to-head wins — the rule the chapter introduces as "perhaps the first idea that comes to mind." So this entire literature is the theory of the family Ranked Robin belongs to, and our engine already prints the object it operates on: the pairwise matrix in an RR report is M(T), and the win-loss column is the outdegrees.

Which means the literature's verdicts on Copeland land directly on Ranked Robin, and they're mixed — honestly, that's the value of reading it:

  • Copeland is monotonic, Condorcet-consistent, and linear-time. For a public method that has to be explained in one sentence and hand-counted, those are the properties that matter, and it's why Ranked Robin is the repo's practical recommendation.
  • Copeland is coarse. It ties easily in a cycle, because cycling candidates tend to share a win-loss record — already documented here, and the reason the refined methods exist.
  • Copeland fails composition-consistency, and even the weak version. This is the theoretical name for Ranked Robin's one real clone weakness, teaming — and it only bites in a cycle.
  • Copeland is not stable — it isn't even idempotent: applying it to its own output can shrink the set again.

And one sharp point that falls out of the runnable case, which we haven't stated anywhere else in the repo:

The moment Ranked Robin's tie-break reads a margin, it has stopped being a tournament solution — but that moment is one rung later than it looks. Margins are not in the tournament. Ranked Robin's published ladder is wins → 1st Degree → 2nd Degree → lot, and the 1st Degree asks for the greatest sum of win margins over the other finalists. With exactly two finalists that sum is a single match, so its sign is nothing but who beat whom — pure C1, an arrow the tournament already contains. With three or more finalists the same rung genuinely adds margins up, and the 2nd Degree (margins over the whole field) always does. So Ranked Robin is C1 through a two-way 1st Degree, and C2 from there on.

That is not a criticism — a rule that has to name one winner needs something, and margin is a defensible and deterministic something. But it does mean the C1 claim has to be made carefully, in both directions: "Ranked Robin is a C1 method" is not true all the way down, and "Ranked Robin leaves C1 as soon as there is a tie" is not true either. Two-way ties are the common case, and on those the ladder stays inside the graph.

This paragraph used to say something stronger and simpler, and it was wrong. Until 2026-08-19 the LH engine had no 1st Degree rung at all: it ranked tied candidates by total margin over the whole field — the 2nd Degree, applied in place of the first — so every tie left C1 immediately, and the page said so. Correcting the ladder changed the winner on 11 of the repo's 100 Ranked Robin cases, including the one worked below — every one of them a two-way tie whose head-to-head the old rung had overridden. The full story, and BetterVoting's opposite bug, are on the degrees page linked above.

The three-ballot election with five defensible winners

Three voters, four candidates — one ranking, rotated (runnable; this is the chapter's own Figure 3.3, converted back into ballots):

A>B>C>D
B>C>D>A
D>A>B>C

A beats B and C; B beats C and D; C beats D; D beats A — so the top cycles and there is no Condorcet winner. Now every rule above, computed by pref_voting and cross-checked against the chapter's caption:

Solution Choice set
Top cycle / Schwartz {A, B, C, D} — everyone
Uncovered = Banks = bipartisan {A, B, D} — C is covered: B beats C and beats everything C beats, so C is strictly redundant
Copeland (= Ranked Robin) {A, B} — both win 2
Slater = Markov {A}

Five answers, three ballots, every one of them published and defended. And then our engine has to pick one:

Abridged for the lesson — the win–loss table and winner line only
Win–loss record — Copeland score = wins + ½·ties (highest score wins; ties broken by the Ranked Robin degrees, then lot order):
    #  Candidate  W–L–T  Copeland  Margin  vs finalists  Beats
    1  A          2–1–0         2      +1            +1  B, C
    2  B          2–1–0         2      +3            -1  C, D
    3  C          1–2–0         1      -3             —  D
    4  D          1–2–0         1      -1             —  A

Winner — Ranked Robin (RCV-RR): A
   *** 2 candidates tie for the most wins (A, B) — tied on the tally, not a cycle (some of them beat others head-to-head, but no loop closes). Resolved by the 1st Degree tiebreaker: A has the greatest sum of win margins over the other finalists (+1).

Read the two margin columns against each other, because the whole point of the rung is that they disagree. Margin is each candidate's margin summed over the whole field: B leads it, +3 to A's +1. vs finalists — printed only when there is a tie for the lead, and only for the tied candidates — is the same sum restricted to the tie, which for two finalists is one match: A beat B, so it reads +1 and −1. The 1st Degree asks the second question, so Ranked Robin elects A — and so do Slater and Markov.

Two things follow, and they pull in opposite directions. The cheerful one: on this election the tie-break consulted exactly one arrow of the tournament and nothing else, so Ranked Robin never left C1 here, and it landed where the two NP-hard rules land. The chastening one: B was this engine's answer until 2026-08-19, on the strength of that +3 — a total built partly out of B's matches with C and D, who were not in the tie at all. The five defensible winners in the table above were always a fact about the tournament; which of them our engine printed was, for a while, a fact about a bug. Full report → the runnable case.

If you arrived from the textbook picture, it is this election

Every write-up of this subject opens with the same drawing: four circles, six arrows, a caption reading A = {1, 2, 3, 4} and a list of ordered pairs. Wikipedia's Tournament solution leads with ≻ = {(1,2), (1,4), (2,4), (3,1), (3,2), (4,3)}, where (x, y) means x beats y. That is the tournament above, relabelled:

Figure vertex 3 1 2 4
Our candidate A B C D

Read the six pairs through that table and you get A>B, A>C, B>C, B>D, C>D, D>A — arrow for arrow, our matrix. So the choice sets in the figure's own numbers are: top cycle {1,2,3,4} · uncovered = Banks = bipartisan {1,3,4} (vertex 2 is the covered one) · Copeland {1,3} · Slater {3}.

And it could hardly be otherwise. There are exactly four tournaments on four vertices up to relabelling, and only one of them is strongly connected — the one where the top cycles. So the moment a four-candidate election has no Condorcet winner and no pairwise ties, it draws this picture. It isn't a chosen example; it's the smallest thing the field has to talk about, which is why everyone draws it. Three voters produce it — that's the file above, and uv run …/tournament_solutions_report.py prints the graph and all seven solutions from those three ballots.

And you can vote in it. The same profile — same four candidates, same six arrows, trees instead of letters — is a live public election: BV2270 8h4bvh (Alder = A, Birch = B, Cedar = C, Dogwood = D), minted for a different purpose and only later noticed to be this graph. Which makes it the cleanest demonstration on the page of what "the tournament doesn't decide it" costs in practice — and of what it doesn't, since the two tabulators that will name a winner now name the same one:

Who is counting Winner On what rung
BetterVoting (RankedRobin.ts) A (Alder) Copeland tie → head-to-head, and A beat B
LH (starvote_larry_hastings.py) A (Alder) Copeland tie → 1st Degree, which on two finalists is that head-to-head (A +1, B −1)
pref_voting (independent Copeland) declines returns the leader set {A, B}

BetterVoting's frozen export settles it with tieBreakType: "none" and the log line Alder preferred over Birch in runoff. — no random rung, no seed, derivable from the ballots by anyone.

This row is where the two engines used to disagree, and it was ours that was wrong. LH elected Birch here until 2026-08-19, on a total margin of +3 to Alder's +1 — margin Birch had run up against Cedar and Dogwood, who were not in the tie. That disagreement was written up at length as a difference of rule between two defensible engines; the page that did so is still worth reading for the shape of the argument, with the correction in mind. What survives of it: BetterVoting implements this rung only for a two-way tie and has nothing for three or more, so the engines still part company on a bigger tie — LH walks the 2nd Degree and then its published lot, BV goes straight to a seeded shuffle.

Worth noticing, and worth not over-reading: the cheap head-to-head rung lands on A — the same candidate Slater and Markov pick, after NP-hard work. That is a coincidence on this tournament, not a theorem; Copeland-plus-head-to-head is not Slater, and on a bigger graph they part company. But it is a fair reply to anyone who assumes the sophisticated rules and the practical ones are pulling in different directions.

What this has to do with STAR: less than you'd hope, and precisely so

STAR is not a tournament solution, and it has no Fishburn class at all — not "C3," not "beyond C2." The reason is stronger than "STAR uses different ballots":

Two score profiles can induce the identical ranked profile — hence the identical tournament, the identical margins, everything — and elect different STAR winners. (Worked, with ballots.)

A function must return the same answer on the same input. STAR's winner is not a function of the tournament, so there is nothing here for a tournament solution to classify. The whole apparatus — McGarvey, the uncovered set, composition-consistency, the NP-hardness results — simply doesn't reach STAR. Any table that assigns STAR a class is wrong, and hedging it ("roughly C3") is worse, because readers strip hedges.

That said, there is one real and rather elegant connection worth teaching:

STAR's runoff consults exactly one edge of the tournament. The scoring round uses cardinal information the graph doesn't contain to choose which head-to-head to read; then it reads that one arrow and obeys it.

So STAR isn't outside pairwise reasoning — it uses a single pairwise comparison, chosen by score. That's why STAR can be diagnosed in this language even though it can't be classified by it: when people say "STAR elected someone who loses a head-to-head," they mean STAR's chosen edge wasn't the graph's top, and our reports print the matrix that shows it. The Condorcet tiebreaker — Equal Vote's optional STAR add-on — is literally a mini Copeland run, i.e. a tournament solution used as a subroutine.

What this has to do with Approval: outside too, with one footnote

Approval's winner is the highest approval count, which the tournament does not determine — same story, same reason. Approval isn't in Fishburn's domain either, since that domain is ranked profiles.

The footnote a critic will find, so here it is: on the Brams–Fishburn dichotomous-preference domain — every voter splits the field into "acceptable" and "not," with no preferences inside either group — Approval is a genuine social choice function on preference profiles, and it is determined by the majority tournament, hence C1-like. That's a theoretical domain, not real approval ballots, where voters do have inner preferences they're compressing. Interesting; not a licence to put Approval in the C1 column.

Is any of this useful, or is it seminar furniture?

Honest answer: mostly the second, with three exceptions that are genuinely load-bearing.

  1. It names Ranked Robin's limits precisely. "Copeland fails composition-consistency and isn't idempotent" is a real, citable statement about the method this repo recommends, and it is better to say it ourselves than to be told it. It also pins where the limits aren't: monotonic, Condorcet-consistent, linear-time, and every one of these failures needs a cycle to fire.
  2. The uncovered set is the one concept with a plain-language payoff. "Nobody should win who is covered — beaten by someone who also beats everyone they beat" is an argument a normal person accepts on hearing, it is equivalent to being reachable-in-two-steps, and it is exactly the line between Pareto-optimal and not. If you take one idea from the chapter, take that one — it has its own page, with the three equivalent definitions, the Pareto theorem, the proof that Ranked Robin never elects a covered candidate, and a five-ballot election where STAR does.
  3. It disciplines claims. "Method X uniquely satisfies criterion Y" arguments are common in voting debates and often built to fit the method. This literature is where you learn how many mutually incompatible "reasonable" answers a single election admits — five, in a three-ballot example — which is a permanent inoculation against anyone claiming their rule is the answer.

What it is not good for: choosing a voting method for a real jurisdiction. Nothing in the chapter argues for a public method, and most of its refinements are unexplainable at a town-hall meeting or intractable to compute. Ranked Robin's case rests on being explainable and summable, not on winning an axiom scorecard.

Sources

  • Felix Brandt, Markus Brill & Paul Harrenstein, "Tournament Solutions," ch. 3 of the Handbook of Computational Social Choice (CUP 2016, free from co-editor Ariel Procaccia) — the source for this page: definitions, the axioms, Theorems 3.1–3.7, and Figures 3.1–3.5, two of which are runnable here. Lean: neutral / academic. Dense but self-contained.
  • Peter C. Fishburn, "Condorcet Social Choice Functions," SIAM J. Appl. Math. 33(3), 1977 — where C1 is defined, and one of two independent origins of the uncovered set. Lean: neutral.
  • David C. McGarvey, "A Theorem on the Construction of Voting Paradoxes," Econometrica 21(4), 1953. Lean: neutral.
  • The choice sets on this page are computed by tournament_solutions_report.py via Eric Pacuit & Wesley Holliday's pref_voting, and cross-checked against the LH engine's own Ranked Robin. Nothing here is asserted from memory.