A chain of majorities leads anywhere

The simplest model of politics is a line. Every voter has a favourite place on it, from left to right, and prefers whichever of two proposals lies nearer that favourite. On that line, majority voting behaves impeccably. Whichever way the positions fall, the middle voter’s favourite beats every rival by a majority, so that a vote between any two proposals always moves the outcome towards the same place, and there is no way to set an agenda that leads anywhere else. Whatever else goes wrong with a cycle of majorities, it cannot go wrong here.

Add one more dimension. Suppose every proposal is a point in a plane, with a tax rate on one axis and a defence budget on the other, and each voter again simply prefers whichever point is nearer. The result is one of the sharpest theorems in the study of voting and one of the most unsettling. Almost always, every point in the plane can be beaten by a majority, and worse, starting anywhere, a sequence of majority votes can reach any other point at all, no matter how bad. Richard McKelvey proved this in 1976. What the theorem can and cannot mean is measured by a much later construction: a small circle called the yolk.

The middle of a line #

To see what is lost, first see what is there. On a line, take the median voter $m$. A rival to $m$’s position lies on one side, and $m$ and every voter on the other side prefer $m$’s position to it. That is a majority, however the rival is chosen. So the median cannot be beaten, and this is Duncan Black’s theorem of 1948.

The proof uses just one fact: a single voter divides a line into two sides that each hold at most half of the voters. Nothing in it mentions distance. It extends to any set of preferences that are “single-peaked” in some order, and this is the condition that elsewhere rescues a whole class of voting rules from strategic manipulation. It is also the theoretical basis of the idea that parties converge towards the centre, as sellers on a street do for an analogous reason.

There is an obvious candidate for the middle of a plane, and it fails too. The point nearest in total to all the voters minimises the sum of distances and has a tidy characterisation by balanced unit vectors, and a majority can still beat it, because a majority cares about who is closer and not by how much. Taking the median of each coordinate separately fails the same way, as well as depending on the choice of axes. Arrow’s four conditions warned that no rule can have everything, and here the failure is concrete and spatial, since the Condorcet winner that most of the common rules try to find simply is not there.

In the plane, no voter divides the others into balanced sides, since a point does not separate a plane at all. What does separate it is a line, and a line through two voters may or may not leave a balanced split. That is the object that matters from here on. A median line is one for which a majority of voters lie on or beyond it in each direction. If a proposal sits on one side of a median line, then its mirror image, reflected across that line and very slightly pulled back, is closer to everyone on the far side and on the line itself, and that is a majority. So every median line that does not pass through a proposal gives a rival that beats the proposal.

What it takes to be unbeatable #

It follows that a point can be unbeatable only if every median line passes through it. Charles Plott found the exact form of that condition in 1967: apart from one voter who may sit at the point itself, the other voters must come in exactly opposed pairs, each pair on a line through the point.

The left-hand arrangement has this balance. For each direction of movement away from the centre, one member of each pair moves further away from their ideal, and they are joined by the voter at the centre. That is three of five. It is genuinely stable, and any point away from it loses. Now move one voter by the smallest amount. The lines through the centre no longer pass through their pairs, and the middle picture shows what follows: a narrow sliver of the plane now beats the centre. The sliver is thin, but its existence is the entire change. The condition cannot survive any generic perturbation, so stable points in two dimensions exist on a set of voter positions of measure nought. A stable outcome in the plane is a coincidence, in the same way that three lines meeting in a point are a coincidence, and it would never occur by chance.

The hero picture shows what happens instead. For any given proposal, each voter’s preferred set is a disc through it. These discs overlap in petals, and every point of a petal beats the proposal. The petals touch at the proposal, so there are winning rivals arbitrarily close by, and also winning rivals some distance away. In this example the win set has area 1.84, against a spread of voters only about three units wide. The picture is typical, and this one proposal could be replaced by any other.

Walking the group #

So far, this says only that majority rule has no resting place. Cycles of three alternatives have been known to do that since Condorcet, and the probability of a cycle has been computed under many assumptions. What McKelvey showed in 1976 is qualitatively different. It is not only that a cycle exists; the top cycle is the whole plane. For any two points $a$ and $b$, there is a sequence $a = x_0, x_1, \ldots, x_k = b$ in which a majority prefers each $x_{i+1}$ to $x_i$.

The proof can be run as an algorithm, using reflections across median lines. A reflection is a majority step, computed as in the shadow of a point on a line and doubled, and each step can move further out from the middle by choosing the line for which the far side is farthest. Keep doing this. Eventually the current point is so far away that any reasonable target, even one quite poor, is closer to a majority of voters, and that makes the target a winning proposal for the last step.

This calculation was run on these five voters, with every vote counted by distances. Starting at the centre of the voters, it takes seven votes to reach the target. Along the way the chain goes as far as about 5 units from the centre, in spite of the fact that the voters themselves sit within about 1.8 of it. Every one of the five voters prefers the starting point to the target. So a group of five reasonable people, voting honestly at each step on a pair of alternatives and choosing the one each of them prefers, has moved by majority rule from an outcome they all preferred to one they all prefer less. Pareto efficiency is lost entirely along the way. A dictator at the head of the table could do the same thing, with the only power being control of the order in which proposals come up. William Riker later made this into a theory about what politics is. He argued that the theorem shows that the outcome of a vote depends on institutions and agendas, so that voting by itself could not reveal a will of the people in any meaningful sense.

The circle that measures it #

If the theorem were the end of the matter, legislatures would produce arbitrary results, and in practice they do not. So there has to be something that the theorem is not seeing, and in 1986 McKelvey himself found how to measure it. He defined the yolk as the smallest circle meeting every median line.

If all median lines passed through one point, the yolk would have radius nought, and that point would be Plott’s unbeatable one. So the radius $r$ measures exactly how far the group is from having a stable point, and this is a number computable from the positions of the voters. For the five voters here, there are five median lines, the diagonals of the pentagon, and $r = 0.4877$.

The yolk gives a bound that the theorem lacks. A single reflection across a median line moves a point $x$ to a distance from the yolk’s centre $c$ of at most $|x - c| + 2r$. This follows from the triangle inequality, since the line passes within $r$ of $c$. John Ferejohn, McKelvey and Edward Packel used this in 1984 to show that a whole agenda has limited speed: each vote can move the outcome at most $2r$ further from the centre. The chain above was checked at every step against this limit, and every step obeys it. In these five voters, that bound is large: the voters’ spread is about three times $r$, so that a chain can get away in a few steps. It is the bound’s dependence on $r$ that tells the rest of the story.

Other constructions lie inside the yolk’s range as well. The uncovered set, the proposals that are not beaten by a majority both directly and through every other point, is a natural prediction for what can emerge from sophisticated voting, and Nicholas Miller showed it to be the outcome set of a certain sort of agenda. McKelvey proved that it lies within $4r$ of the yolk’s centre. So a group with a small yolk has only a small central region which it can reasonably end up in. Outcomes outside that are reachable only through a long sequence of votes, each of which has to be won by a majority that can see what it is doing.

What happens to the yolk in a large group #

The natural question then is how large $r$ is for many voters. The median lines of a random cloud of voters almost pass through one point, since any line splitting a large round cloud into halves must pass close to its centre. So $r$ ought to shrink. Computing it for voters drawn from a round normal cloud bears this out.

The mean radius is 0.28 at five voters, 0.20 at 25, 0.11 at 101 and 0.063 at 401. Craig Tovey proved in the early 1990s that the yolk’s radius tends to nought for voters drawn from a suitably centred distribution, at a rate of about one over the square root of $n$. So in a large electorate each vote can move the outcome by only a tiny amount. The chaos theorem is still literally true. But to reach a distant point requires a number of votes that grows with the size of the electorate, each of which is a tiny step away, and so the effective instability has nearly vanished.

The reconciliation is one of the better outcomes in the theory of voting. McKelvey’s theorem is exact, and it applies at every size. It is an extreme statement about what an adversary with unlimited agenda control can reach using very long chains of votes, and about preferences so exact that a voter can be relied on to distinguish two proposals that are almost the same. Tovey also showed what happens if voters ignore very small differences, or if proposals carry a small cost: stable points then return, which he called an equilibrium with $\epsilon$-tolerance. So the chaos theorem and the observed stability are not really in conflict. Each answers a different question. The small-committee case is where the instability is real, and committees are indeed where agendas are fought over.

The reach of these pictures #

Everything drawn is two-dimensional. In higher dimensions, Plott’s condition is far stricter, and McKelvey and Norman Schofield showed that with enough dimensions, compared with the number of voters, no stable point can exist generically, for any smooth preferences. In two dimensions, a generic stable point never occurs for any odd number greater than one with these round preferences, but none of the figures can show that by itself; only the symmetric arrangement and its perturbations are drawn.

Euclidean preferences are also an assumption, and a strong one. Voters are assumed to weigh the two issues equally and to care only about distance. With tilted or elongated preference curves, the same theorems hold in forms that apply to a different geometry, but the numbers do not transfer. And real votes are not sequences of pairwise proposals chosen by anyone with perfect control. The chain in the figure says nothing about whether any actual committee would follow it. Each of its members would see where it was going, and a voter who refused the early steps would break the chain, which is what sophisticated voting means.

What was computed and what was quoted #

The win set and its area come from counting votes at each cell of a grid, with one picture element as the resolution, so the area is good to about a part in a hundred, and the thin slivers near small perturbations are underestimated by it. The median result on a line was checked at 360 rival positions. Plott’s central balance was checked on 400 test points spiralling out from the centre. Every vote in the chain was counted exactly from the distances, and the $2r$ bound was tested at each step.

The yolk was computed exactly as a small linear programme for each set of voters. The mean radii at each size are sample averages over random clouds, with sixty samples up to 101 voters and twelve above, so the last two points carry visible noise, and the slope is an impression rather than an estimate. The theorems of Black, Plott, McKelvey, Ferejohn, McKelvey and Packel, Miller, Tovey and Schofield are quoted, with their proofs given here only where they are short.

Still open: what a group actually chooses #

The mathematics of what majorities can do is largely settled. What remains is the part that is harder to state exactly. Laboratory experiments, starting with Morris Fiorina and Plott’s in 1978, show committees ending near the yolk’s centre with some scatter, though Plott’s condition did not hold; the outcomes are stable to a degree no theory of pairwise voting predicts. Later work has competed to explain this with bounded rationality, costs and deliberation, and no single rule of behaviour is accepted as the right predictor.

There is also a small precise question. How large is the yolk for an arbitrary set of $n$ points, in the worst case and for typical arrangements of a small number? There is a known upper bound relating it to the spread of the voters. The dependence on the shape of the distribution of voters is known in cases but not in general, and how the radius behaves in more dimensions, where the analogue of median lines is median hyperplanes and the analogue of the yolk is a smallest ball, is partly mapped. This resembles a question from another side of mathematics, since lines that leave half on each side has a similar structure, and there nobody knows even the exponent for how many such lines can exist.

One voter in the middle, or none #

On a line, one voter has a majority on each side and that voter’s position cannot be beaten; in a plane there is no such voter, every median line gives a majority move, and chains of such moves reach everywhere. That is the whole of the theorem of the theorem, and the second half follows from the geometry of reflections.

What rescues the theory is a number. The smallest circle meeting all the median lines bounds how far each vote can carry the outcome, and in a large group that circle is small. So the same reflections that lead to chaos in a committee of five lead to almost nothing in an electorate of millions. Majority rule’s instability was always real, and it is a matter of scale: seven votes were enough to walk five people to somewhere they disliked, and the circle says why that many, and why not so few when there are many more of them.