How few voters any majority needs

The majority that goes in a circle ended with a theorem stronger than the paradox it began from. Take any set of candidates and decide, for every pair, which one should win their head-to-head vote — arbitrarily, perversely, with as many cycles as desired. Then there is a set of voters, each holding a perfectly sensible ranking of the candidates, whose majorities produce exactly that pattern. David McGarvey proved it in 1953. Pairwise majority imposes no structure at all on its output.

That settles whether. It leaves open how many — and the answer is surprisingly small.

The figure lists every essentially different pattern of head-to-head results among five candidates — there are twelve, once candidates are relabelled — and for each one the smallest electorate found to produce it. One of them, the pattern in which the candidates beat one another in a straight line, comes from a single voter who ranks them in that line. All eleven others, including the most tangled, come from three voters. McGarvey’s recipe would have used twenty.

The recipe, two voters to a contest #

McGarvey’s construction is worth seeing in full, because its waste is what the rest of the essay removes.

For a single desired result — say A beats B — write down two voters. The first ranks A first, B second, and the remaining candidates after them in some fixed order. The second ranks the remaining candidates first, in the reverse of that order, and then A, then B. On the contest between A and B both voters prefer A, so A gains two votes. On any contest between two of the remaining candidates the two voters disagree, and cancel. On a contest between A or B and one of the others, one voter has A or B in front and the other has it behind, and they cancel again. So the pair of voters tips exactly one contest by exactly two votes and leaves every other untouched.

Do this for every one of the $\binom n2$ contests and the pattern is built, each contest won by exactly two. The cost is $n(n-1)$ voters: twelve for four candidates, twenty for five, nearly a million for a thousand. The figure’s pattern includes the three-way cycle of the majority that goes in a circle, with a fourth candidate who beats the cycle’s first member and loses to the other two; twelve voters produce it, every contest decided by two.

Three voters are already a cycle #

The smallest case shows that the recipe’s waste is large from the start.

For three candidates in a cycle the recipe uses six voters. Condorcet’s own example uses three: one voter ranks A, B, C; one ranks B, C, A; one ranks C, A, B. Each contest is won two to one, and the majority goes round in a circle. Three voters are exactly enough for a cycle, and one voter is never enough, since a single voter’s ranking is a straight line. That is the whole story for three candidates: the two possible patterns are the line, which needs one voter, and the cycle, which needs three.

Why never two? With an even number of voters a contest can tie, and a pattern of head-to-head results is only a pattern if every contest has a winner; so an electorate producing a strict pattern either has an odd number of voters or has no ties by luck. Two voters who disagree on any pair tie it. So the candidates for the minimum are one voter and three.

Four and five candidates, searched completely #

For four candidates the patterns can be listed by hand, and for five by machine.

A pattern of head-to-head results on $n$ candidates is a tournament: every pair joined by an arrow from winner to loser. There are $2^{\binom n2}$ of them — $64$ for four candidates, $1{,}024$ for five — and once candidates are relabelled, four and twelve essentially different ones. The search behind the figures does two things exhaustively. It runs through all $2^{\binom n2}$ tournaments to find the essentially different ones, confirming the counts four and twelve. Then it runs through every single ranking and every set of three rankings — for five candidates, $120$ rankings and nearly three hundred thousand sets of three — and records which tournament each produces.

The result is that every tournament on four or five candidates is produced by one voter or three. Five candidates cannot force a larger electorate. The general question is when it first becomes necessary to go beyond three, and the searched answer, found by Dustin Shepardson and Craig Tovey in 2009, is that the smallest tournaments three voters cannot produce have eight candidates.

That is already far below the recipe. McGarvey needs twenty voters for five candidates; three do. The recipe was designed to make the proof one line long, not to be economical.

Five candidates, every one beating two #

The most symmetric pattern on five candidates is the one in which each candidate beats the next two round a circle and loses to the two before it: A beats B and C, B beats C and D, and so on round to E, which beats A and B. Every candidate wins exactly two contests and loses two. It is the pattern with win counts $2, 2, 2, 2, 2$ at the top left of the first figure, and it has no winner of any kind — no Condorcet winner, no candidate ahead on contests won, and a symmetry that carries any candidate to any other.

Three voters produce it. The search finds, for instance, the rankings

$$A\,B\,C\,D\,E, \qquad C\,D\,E\,A\,B, \qquad E\,B\,D\,A\,C.$$

Check one contest: A against B. The first two voters rank A above B; the third ranks B above A; A wins two to one, as it should. Check another: E against A, which E should win. The first voter ranks A above E, the second and third rank E above A; E wins two to one. All ten contests come out the same way, each by two votes to one.

Nothing about the three rankings looks strange. The first is alphabetical; the second is the alphabet started at C; the third is a jumble. Each voter is perfectly consistent, and the majority is as inconsistent as a five-candidate pattern can be. A committee of three, meeting to rank five proposals, could produce this table with no one acting oddly, and every rule that reads the table would then face a perfect tie of symmetry that no principle can break.

Why the number must grow #

Three voters cannot suffice forever, and the reason is counting.

An electorate of $k$ voters casts $k$ rankings, and there are $n!$ rankings of $n$ candidates, so at most $(n!)^k$ different electorates exist, and at most that many different tournaments can come out of them. There are $2^{\binom n2}$ tournaments to produce. So producing all of them needs

$$(n!)^k \ge 2^{\binom n2}, \qquad k \ge \frac{\binom n2 \ln 2}{\ln n!} \approx \frac{n \ln 2}{2 \ln n}.$$

The floor grows, but slowly: $3$ voters at ten candidates, $10$ at a hundred, $59$ at a thousand. McGarvey’s recipe grows like the square of $n$. Richard Stearns showed in 1959 that $n + 1$ voters suffice when $n$ is even and $n + 2$ when it is odd — the recipe’s quadratic replaced by a line — and in 1964 Paul Erdős and Leo Moser showed that the true requirement grows like $n/\log n$, the same rate as the counting floor up to a constant factor.

So the counting argument, crude as it is, gets the growth right. A tournament on $n$ candidates contains about $n^2/2$ bits of information — one per contest — and each voter supplies about $\log_2 n!$, roughly $n \log_2 n$ bits, so about $n/(2\log_2 n)$ voters are needed to supply it; Erdős and Moser showed that a constant times that many are enough. What is not known is the constant.

Where the numbers come from #

The history runs in the same direction as the numbers. David McGarvey’s paper of 1953, in Econometrica, was a single page, and its construction was designed only to show existence. Richard Stearns took up the question of economy in 1959, in a note in the American Mathematical Monthly titled “The voting problem”, and brought the electorate down from quadratic to linear in the number of candidates. Paul Erdős and Leo Moser, in 1964, titled their paper “On the representation of directed graphs as unions of orderings”, which is the same problem stated without voters: a tournament is to be written as the majority of a few linear orders, and the question is how few.

The information count above is the reason the answer has the shape it does. A voter’s ranking of $n$ candidates is one of $n!$ possibilities and so carries about $\log_2 n! \approx n \log_2 n$ bits; a tournament is one of $2^{\binom n2}$ possibilities and so carries about $n^2/2$ bits. It is the same bookkeeping the rate a noisy channel allows does for messages: to transmit a message of so many bits through symbols of so many bits each, a certain number of symbols is unavoidable. Erdős and Moser showed that majority voting is an efficient enough code that a constant multiple of that number is also enough.

The hard patterns are the typical ones #

The counting argument has a sharper reading than a floor. It does not merely say that some tournament needs many voters; it says that almost all of them do. Electorates of $k$ voters can produce at most $(n!)^k$ tournaments, so when $k$ is somewhat below the floor, the tournaments they produce are a vanishing fraction of all $2^{\binom n2}$. A tournament chosen by tossing a coin for every contest is therefore, with probability tending to one, among the expensive ones.

That runs against intuition in an instructive way. The patterns that look most pathological — the perfectly symmetric circle of the previous section, cycles nested in cycles — are highly structured, and structure is cheap: three voters produced the symmetric circle. The patterns that genuinely need a large electorate are the ones with no structure at all, the tables that look like noise. The expensive tables are the random ones, because a random table has too much information in it to be packed into a few rankings.

It also shows how the small cases mislead, and in which direction. For up to seven candidates three voters always suffice, and it would be natural to guess that some fixed small number suffices forever. Counting forbids it, but only late: sets of three rankings outnumber tournaments until about nineteen candidates — at seven candidates there are about two million tournaments against some $2 \times 10^{10}$ sets of three rankings — so counting alone cannot rule out three voters before then. The first tournaments that three voters cannot make appear at eight candidates, long before counting requires them. Structure fails before counting does: at eight candidates there are still tens of thousands of three-voter electorates for every tournament, and some tournaments are nevertheless missed, because the electorates crowd onto the same patterns rather than spreading over all of them.

What a small electorate can hide #

The smallness of the numbers has a consequence for anyone reading a real vote.

How often the majority goes in a circle found that under random voting, cycles become more common as candidates are added, and that for many candidates the head-to-head pattern is almost never a straight line. This essay says something complementary: no pattern is too strange for a tiny electorate. A committee of three, with three perfectly ordinary rankings, can produce a five-candidate pattern in which every candidate is beaten by someone who is beaten by someone it beats.

A related fact concerns strategy rather than sincerity. A lie that pays showed that a voter can sometimes gain by misreporting a ranking; the results here say that the table a manipulating voter aims for is always reachable by somebody’s sincere rankings, so a strange table never proves that anyone lied.

So the tangle in a head-to-head table is no evidence of irrational voters, or of many voters with different views. Three consistent people suffice. The inconsistency lives entirely in the aggregation, which is the point four conditions, and no rule that has all of them made about every aggregation rule at once.

It also bears on the rules of five rules and five winners, several of which read only the head-to-head table. A rule that depends only on the table — Copeland’s, which counts contests won, or the Schulze and ranked-pairs methods, which reason about margins — must be ready for any table at all, because any table can occur, and occur from a handful of voters.

Margins as well as winners #

McGarvey’s recipe controls more than who wins each contest: every contest is won by exactly two. Adding copies of a block raises one margin by two at a time and leaves the rest alone, so the recipe can produce any table of even margins, not only any pattern of winners. Adding one voter who ranks the candidates in any order changes every margin by one, so any table of margins with a common parity can be produced too.

Debord’s theorem of 1987 states this precisely: a table of head-to-head margins arises from some electorate exactly when all its entries have the same parity. The margins are therefore as unconstrained as the winners, and the rules that weigh margins — Kemeny’s, whose median ranking the nearest consistent verdict computed for judgements, and the Schulze method — face every possible input as well. How few voters a given table of margins needs is a harder question than for winners, because large margins need many voters no matter how they are arranged.

What the search and the bound cannot show #

The search covers only four and five candidates. For five it runs through every tournament and every electorate of one or three voters exhaustively, and finds that three always suffice; it does not extend to eight candidates, where the first tournaments needing more than three appear, because the sets of three rankings of eight candidates number about $10^{13}$.

The counting floor is a floor, not an answer. It shows that some tournament needs at least that many voters, without naming which. Erdős and Moser’s upper bound shows the floor is right up to a constant; the constant itself, and whether the worst tournaments are random-looking ones or specially structured ones, are what the figures cannot settle.

Rankings only. Every voter here holds a strict ranking. Allowing voters to be indifferent between candidates, or to approve of sets, changes the counting and the constructions.

Still open: the exact number for every size #

Let $f(n)$ be the fewest voters that produce every tournament on $n$ candidates. The figures and the literature give $f(n) = 3$ for $n$ from three to seven, and $f(n) \ge 5$ from eight on. Erdős and Moser give $f(n)$ between two constant multiples of $n/\log n$. The exact values of $f(n)$ beyond the smallest cases are not known, and neither is the limit of $f(n) \log n / n$, if it exists.

The difficulty is the one that makes many extremal questions hard: the lower bound is a counting argument that says a bad tournament exists without exhibiting one, and the upper bound is a construction that works for every tournament at once. Closing the gap needs either an explicit tournament that provably needs many voters — which no one has — or a construction that uses the counting argument’s budget almost exactly.

A pattern costs almost nothing #

The habit worth keeping is to ask not only whether something can happen but how much it costs.

McGarvey’s theorem says that any majority pattern can happen. Its proof spends two voters per contest, which suggests that strange patterns need large electorates. They do not. Three voters make every pattern on five candidates, and the worst patterns on a thousand candidates need only dozens, because each voter’s ranking carries almost as much information as the table of contests it helps to decide.