The majority that goes in a circle

A ballot in this field is a ranking: one candidate above another above another, no ties and nothing left out. Every voter hands in one, and every one of them is transitive — not because voters are careful, but because a ranking is a list, and a list cannot put A above B, B above C and C above A. Transitivity is not a property a ballot might happen to fail. It is what makes the marks on it a ballot.

The obvious thing to do with a stack of them is to take the candidates two at a time and let the majority decide each pair. The obvious expectation is that the verdicts fit together.

Nothing in the ingredients is strange #

Three groups, three rankings, each of them a perfectly ordinary list. The first group prefers A, then B, then C. The second prefers B, then C, then A. The third prefers C, then A, then B. Nobody has ranked a candidate twice, left one out, or expressed anything a ranking cannot express — the generator checks each ballot is a permutation before it draws anything.

Now read the matrix. A beats B sixty-seven to thirty-three. B beats C sixty-eight to thirty-two. C beats A sixty-five to thirty-five. Every one of those is a landslide, decided by more than the margin most people would call decisive, and taken together they say that A is better than B is better than C is better than A.

The three groups are near enough the same size, but that is a decoration rather than the cause. The pairwise majority verdicts do not come apart because the electorate is finely balanced; they come apart because each pair is decided by a different majority. The sixty-seven who put A above B are not the sixty-eight who put B above C. Each pair convenes its own coalition, and no coalition is answerable to any other.

This is the whole difficulty in one sentence. Transitivity is a property of a single list. Pairwise majority is an operation applied one pair at a time, and there is no reason built into it for the answers to cohere. Transitivity is not fragile here and nothing has broken it; it is simply not preserved by the operation being applied to it.

The tournament, and the fact that it closes #

The natural picture of the pairwise verdicts throws away the margins’ sizes and keeps their directions: draw one node per candidate and one arrow from the winner of each pair to the loser. What is left is a directed graph in which every pair of nodes is joined exactly once — a tournament.

The cyclic order the figure draws the candidates in is not typed in. Every ordering of the candidates is tried, and the drawing uses one whose consecutive arcs all point forward, so that walking round the polygon is literally following the majority. Existence of such an ordering is the property being pictured: a majority cycle is exactly a tournament in which some ordering has every consecutive arc pointing forward, and a tournament with a candidate who beats everybody admits no such ordering at all.

Which is why the mode refuses. Hand it a profile whose majorities settle down and it will not draw a polygon; it stops and names the candidate who beats everybody. A picture of a cycle that is not there would be a picture of nothing, and the refusal is the same discipline that makes an exhaustive search worth reporting — a search that can only ever succeed has not been tested.

The vocabulary is worth fixing here, since three more essays will lean on it. A preference profile is the whole stack of ballots. A voting rule is any function from a preference profile to a verdict. A Condorcet winner is a candidate who beats every other head to head, and a Condorcet cycle is what this tournament has instead of one. The discovery on this page is that a Condorcet winner may simply not exist, however sensible every ballot is.

That vocabulary is also the whole of what this field takes as input, and it is worth being blunt about the boundary at the start of it. Preferences go in and a verdict comes out. The candidates are letters and the voters are numbered, because nothing in any argument here would change if they were called anything else, and the moment a candidate is a real body and a voter a real person every claim on the page acquires an empirical burden it cannot discharge. Nothing is measured, nothing is sampled, and no figure is drawn from anything observed. What replaces observation is exhaustion: a claim about a finite space of profiles is settled by building the space and deciding every member of it, which is precisely what the right-hand half of the picture above is.

Most profiles are perfectly well behaved #

It would be easy to leave the impression that pairwise majority is a shambles. It is not, and saying so is what turns the count in the next section into a finding rather than an alarm. The profile at the top of this page is a counterexample to an expectation, and a counterexample is worth nothing at all until the expectation it kills has been stated fairly.

Here the three pairwise verdicts fit together without effort. B beats both others, and A beats C, so the majority relation ranks B above A above C — a perfectly good ranking, produced by exactly the operation that failed a moment ago on a profile of the same size.

Notice also the small tension already visible in this well-behaved case: the largest single block of voters puts A first, and the majority relation puts B first. That is not a failure of anything; it is two different voting rules answering two different questions, and it is the subject of the next essay rather than this one.

Counting the whole space #

A single counterexample settles that cycles are possible. It says nothing whatever about how common they are, and the temptation at that point is to reach for an adjective — rare, pathological, a curiosity. The house habit is to reach for a count instead.

Fix three candidates and three voters. Each voter’s ballot is one of the six orderings, and the voters are independent, so the number of profiles is $6 \times 6 \times 6 = 216$. That is small enough to build entirely, and the figure above does: every profile assembled, its pairwise majorities computed, and its Condorcet winner sought. Twelve of the 216 have none. Nothing was sampled, nothing was estimated, and nothing was quoted from anywhere.

The count is then taken a second way, by a different question. With an odd electorate and three candidates, no pair can end level, so “there is no candidate beating both others” and “the three margins form a Condorcet cycle” are the same condition — and the generator counts the three-way cycles directly and requires the two numbers to agree. Two routes to a figure a caption is about to print is the minimum this collection is willing to accept, and it is the same insurance that counting one object twice buys everywhere else.

Twelve in two hundred and sixteen is 5.6%: not an epidemic, and not a curiosity either. Roughly one profile in eighteen. Anyone whose intuition said vanishingly rare has had the same experience as anyone meeting the birthday count for the first time, and for the same structural reason — the space is larger than it feels and the bad region is spread thinly through all of it rather than huddled in a corner.

What an even electorate does to the count #

Change the size of the space and the proportion moves, but the first way it moves is a trap worth walking into deliberately.

Two thirds of the two-voter profiles have no Condorcet winner, which sounds far worse than the three-voter figure and is a different phenomenon entirely. With two voters, any pair they disagree about splits one against one. Nobody wins it. So nobody beats everybody, and the count of profiles without a Condorcet winner picks all of those up — correctly, because that is what it was asked, and misleadingly, if it is read as a count of cycles.

At four voters the space is $6 \times 6 \times 6 \times 6 = 1296$ and the proportion without a Condorcet winner is 55.6%. Again ties, not circles. The honest comparison is between odd electorates, where no pair can be level and the two questions coincide, and there the proportion moves gently upward rather than lurching: three voters give 5.6%, and a sweep of the five-voter profiles — 7,776 of them, too many to give each its own cell, so no figure on this page draws it — gives 6.9%.

That is a small enough drift to be worth stating carefully. It rises, it rises slowly, and every number in that sentence came from building the space rather than from a formula.

Four candidates, and a bigger circle #

Nothing about the failure needs three candidates. With four, the majority can run round a square, and there are more pairs for it to run round.

The four-candidate space is bigger in the way that spaces of permutations always are: each voter now has twenty-four possible ballots rather than six, so two voters already give $24 \times 24 = 576$ profiles and three voters give more than the one-cell-per-profile grid can hold. The exhaustion this field runs on has a horizon, and it is a low one.

What the four-candidate picture adds is a warning about the shape of the failure. With three candidates and an odd electorate, no Condorcet winner means one three-way cycle and nothing else. With four, the majority relation can fail in several structurally different ways at once — a four-cycle, a three-cycle with a fourth candidate hanging off it, and combinations of both — and “there is no Condorcet winner” stops being a description of what went wrong and becomes merely the report that something did.

The generalisation, and it is worse than it looks #

The natural next question is how bad a majority tournament can get, and the answer is the strongest statement on this page.

Every tournament whatever is the pairwise majority tournament of some preference profile. Take any set of candidates, orient every pair however is liked — arbitrarily, maliciously, at random — and there is a profile of transitive individual rankings whose pairwise majorities produce exactly that directed graph. This is McGarvey’s theorem, from 1953, and its construction is disarming: for any single ordered pair, a small block of voters can be written down whose net effect on the majority relation is to tip that one pair and cancel out everywhere else. Stack one such block per pair and the tournament is built to order.

So pairwise majority imposes no structure at all on its own output. Whatever coherence a majority relation happens to have is a property of the preference profile that produced it, never a guarantee of the operation. Every counterexample this anchor will need, at every rung, is therefore available somewhere in the space of profiles; the work is finding it, not wondering whether it is there.

There is a genuine surprise sitting next door, in a field that looks unrelated. A conditionally convergent series is built out of terms that individually behave impeccably, and yet rearranging them reaches any total that is asked for — the value is not a property the terms carry but an artefact of the order they are aggregated in. The two theorems have the same shape. Well-behaved parts, an aggregation that looks as though it must preserve the good behaviour, and a proof that the aggregate can be made to be anything. In both cases the error was in expecting an operation to inherit a property of its inputs, and in both cases the correction is the same: the property belonged to the parts and was never handed on.

What the grid cannot show #

The right half of the tournament figure is one cell per profile, filled where no Condorcet winner exists, and it is worth being exact about what that settles.

It settles the three-voter, three-candidate case completely. All 216 profiles were built, each was decided on its own, and the twelve cyclic ones were then counted a second way. There is no sampling anywhere and no appeal to anything outside the picture, which is the whole reason the drawing is a report of a decision rather than an illustration of one.

It settles nothing about larger electorates. The claim that a Condorcet cycle is available at every size, or that the proportion of profiles carrying one approaches some particular number, is quantified over infinitely many profiles, and no grid of cells decides a claim like that — for exactly the reason a finite model settles an independence question and not a truth. Three sizes are drawn here and a fourth was swept off the page; the pattern across them is suggestive and is not a proof.

What is known, and is not established by anything on this page, is that under the assumption that all profiles are equally likely, the proportion of three-candidate profiles with no Condorcet winner rises with the number of voters towards a limit of about 8.8%. Guilbaud computed it in 1952. The assumption doing the work there is the one about the space, not about the arithmetic: it supposes that every ordering is as likely as every other and that voters are independent, which is a modelling choice and would need defending. Nothing in this field defends it, because defending it would mean reaching for observed preferences, and observed anything is outside the line this field is drawn on.

One more thing the picture declines to say. How much work it takes to build 216 profiles, or 1296, or a space with a hundred candidates in it, is a question about cost, and cost belongs to another site in this collection rather than to this one. The counts here are facts about a particular exhaustion, never bounds on anything.

Condorcet, Llull, and a result found twice #

The cycle carries Condorcet’s name from his Essai of 1785, where the three-voter example appears in essentially the form drawn at the top of this page. He was clear about what it meant: a pairwise procedure that everyone would call fair can return a verdict that is not a ranking, and no amount of care from the voters prevents it.

He was not first. Ramon Llull described the pairwise comparison of candidates in the thirteenth century, in manuscripts that were lost and rediscovered only in the 1990s, and the rediscovery showed he had understood both the method and the trouble it runs into. That is a five-hundred-year gap between a result and its second discovery, over a space small enough to check by hand — much as the two hundred and fifty-six syllogistic forms were argued over for two thousand years while the exhaustion that settles them fits on a page.

The other thing worth noticing about the history is how late the counting is. Exhibiting the cycle took Condorcet a paragraph in 1785. Asking what proportion of profiles contain one waited until the middle of the twentieth century, and the answer arrived as a limit computed by hand rather than as a space built and walked. Building the space is a modern habit, of a piece with proofs that check every case, and it answers a question the classical method could only approach from a distance.

Where the ladder goes #

This anchor has three more rungs and each one takes the same failure a step further in.

If the majority relation can fail to be a ranking, then any voting rule that always returns an answer must be doing something other than following pairwise majorities. Five reasonable rules on one profile return five different candidates, which is the next rung, and the natural response — write down the conditions a rule ought to satisfy and find one that has them all — is the rung after that. The search fails, and it fails for reasons this page has already exhibited in miniature.

And once no rule can be entirely satisfactory, the question shifts from what a rule returns to what a voter has reason to submit — a lie that pays, found by writing out every ballot one voter could hand in and checking each.

All four rungs run on the move that deleting a city to leave a graph made respectable: state the object exactly, throw away everything the argument does not use, exhaust the finite space that is left, and report what the exhaustion found. Six people at a party is the closest relative — a complete graph whose every edge has been given one of two colours, and a claim about what such a decoration cannot avoid. A majority tournament is the same complete graph with its edges given directions instead, and the claim here is the mirror image of Ramsey’s: this decoration can avoid nothing, because it can be anything at all.