Three splits that answer every other

Three people have a pound, and any two of them can agree to take it. If A, B and C split it evenly, A and B can walk off together with fifty pence each, which both prefer to thirty-three. If they then split it half and half between A and B, C can offer A sixty pence and keep forty, and both A and C prefer that. There is no end to it. The core — the set of splits no group can beat by leaving — is empty for this game, and the reason is simple arithmetic: each pair demands the whole pound, and the three pairs together demand three pounds out of one.

The later answers to that emptiness each picked one split and defended it: the nucleolus by quieting the loudest objection, the kernel by balancing objections between players. John von Neumann and Oskar Morgenstern, who wrote the book that started the subject in 1944, proposed something different and older. Their answer to “how will the pound be split?” was not a split. It was a set of splits, with a particular relation to one another and to everything outside.

When one split beats another #

The relation is domination. A split $x$ dominates a split $y$ if there is a group of players who all get strictly more under $x$ than under $y$, and who could guarantee themselves $x$’s shares on their own — their shares under $x$ add up to no more than the group is worth. The group would rather have $x$, and can enforce it.

In the three-player majority game only pairs matter. A single player can guarantee nothing, so cannot enforce anything; the three together cannot all be strictly better off, since the total is fixed. So $x$ dominates $y$ exactly when two of the players each get more under $x$. Any pair can take the whole pound, so affordability never binds.

The figure shows the relation around one split. Every point of the triangle is a way of dividing the pound, with each corner giving everything to one player. The splits that beat the marked one sit in three wedges, one for each pair: the wedge where both A and B gain, the wedge where both A and C gain, and the wedge where both B and C gain. The splits it beats are the mirror image. And a good many splits neither beat it nor are beaten by it — in particular, every split along the three lines through it on which one player’s share is unchanged, since a pair can only win if both of them strictly gain.

Domination is not a ranking. It is not transitive — $x$ can beat $y$ and $y$ beat $z$ while $x$ does not beat $z$ — and it has cycles, which is the pound game’s instability in another form. The even split is beaten by half-and-half between A and B, which is beaten by sixty-forty between A and C, which is beaten by a split favouring B and C, and so on round.

Around the even split the picture is symmetric, and it makes the problem plain. The even split looks like the obvious fair answer, and a large part of the triangle beats it. If a solution has to be a split that nothing beats, there is none: the core is the set of undominated splits, and it is empty.

A set that defends itself #

Von Neumann and Morgenstern replaced “a split that nothing beats” by two requirements on a set $V$ of splits:

• internal stability: no split in $V$ dominates another split in $V$;
• external stability: every split outside $V$ is dominated by some split in $V$.

The idea is a standard of behaviour. A society that has settled on $V$ never faces an objection from inside it that the society itself would endorse — no accepted split is beaten by another accepted one — and any proposal outside the standard can be answered by an accepted split that some pair prefers and can enforce. They called such a set a solution. It is now called a stable set.

For the pound game the natural candidate is the three splits that give half each to two players and nothing to the third. None of the three beats another: comparing half-and-half for A and B with half-and-half for A and C, A is equal, B does better under the first and C under the second, so no pair gains under either. And every other split is beaten by one of them. A split not among the three gives less than a half to at least two players — if two players each had a half or more, the third would have nothing and the split would be one of the three — and those two both do strictly better under the half-and-half split between them.

The picture shows how the triangle divides. Near each corner, one player has more than a half, and the other two are both below it: exactly one of the three splits beats such a point, the one favouring the two underpaid players. In the middle, where all three are below a half, all three splits beat it. The colours cover everything, and that is external stability, checked split by split.

What the solution predicts is not a split but a pattern: two players will form a pair and divide the pound equally, and the third will get nothing. Which pair forms, the solution does not say. That is a strength or a weakness depending on what a solution is for, and von Neumann and Morgenstern were explicit that they meant it as a description of stable social arrangements rather than a prediction of one outcome.

A solution for every share below a half #

The three half-and-half splits are not the only stable set. Von Neumann and Morgenstern found others in the same game, and they are very different in character.

Fix a share $c$ for C, less than a half. Consider every split in which C gets exactly $c$ and A and B divide the remaining $1 - c$ in any way at all: a line across the triangle parallel to the side where C gets nothing.

No point of such a line beats another. Two points on it give C the same share, so no pair containing C can strictly gain, and A and B cannot both gain because they are dividing the same amount. That is internal stability, and it holds for any $c$.

External stability is where the half comes in. A split giving C more than $c$ gives A and B together less than $1 - c$, so a point on the line gives both of them more, and they prefer it. A split giving C less than $c$ can be beaten through a pair containing C: C would prefer $c$, and C’s partner has to gain as well, which is possible provided that partner is currently getting less than $1 - c$. Both A and B could only be at $1 - c$ or more if $1 - c$ were at most a half. So when $c$ is below a half, one of them can always be bought, and the line beats everything off it.

These are the discriminatory stable sets. Each one describes a society in which C is treated in a fixed, conventional way — given a fixed share, perhaps nothing — while A and B bargain freely over the rest. There is one for every value of $c$ from zero up to (but not including) a half, so the pound game has infinitely many solutions, and in each of them C’s treatment is a matter of convention that the mathematics does not determine.

Five candidates, tested #

The definition is precise enough to check any proposed set mechanically, and the table does that for five.

The even split alone is internally stable — a set of one split cannot beat itself — and fails badly outside, leaving almost two hundred splits it does not beat; one of them gives A nothing, B a third and C two thirds, and the even split cannot beat it because B is no better off and A and C cannot both gain. The three all-to-one splits fail worse still: a split giving everything to one player is beaten only by splits that help the other two, and each all-to-one split helps only its own player.

The line holding C at $0.6$ fails for the reason the argument predicted. With C above a half, A and B share only $0.4$, and any split in which C gets less than $0.6$ and A and B each get at least $0.4$ is beaten by nothing on the line — the example is $(0.4, 0.4, 0.2)$. C cannot find a partner, because neither A nor B can be given more than what the line has to offer. Half-and-half between A and B is among the splits left unbeaten.

The test is exhaustive on the lattice but the lattice is not the triangle. For the lines, dominating points are sought on a lattice twice as fine, since beating a split requires strictly more for both members of a pair and a coarse lattice can leave no room between. The arguments above are what make the conclusions hold at every split rather than only at lattice points; the table checks that the arguments were not mistaken.

A standard, not a forecast #

The stable set is easy to misread as a weaker kind of prediction, and it is worth being exact about what it claims. It does not say that the pound will be split half and half between two players. It says that if the players have come to regard those three splits as the acceptable ones, then no objection to an acceptable split can be sustained from within the standard, and any split outside it will be answered.

That is closer to a description of an institution than of an outcome. The same game has a single-split answer that minimises the loudest objection, another that balances objections between individuals, and an average over orders of arrival; each returns the even split here, by symmetry. The stable sets return something else entirely — a pattern in which somebody is left out — and they return several such patterns, because they are describing which conventions could hold rather than computing a fair share.

The discriminatory solutions make the point sharply. A society in which C is always given a fixed ten pence, while A and B bargain over the rest, is stable in exactly the same sense as one in which some pair takes everything. Neither is fairer by the definition, and the definition was never meant to decide that. It is the same distance between a precise criterion and a choice that the four conditions on voting rules leave open, and that a rule on judgements leaves open when several consistent rules survive: the mathematics lists what is stable and leaves who is favoured to something outside it.

There is also a question of weight. In the pound game every player is equally strong, so the stable sets treat them symmetrically as a family, even when a single set singles one out. In a weighted vote the players are not equal, and a share of the votes is not a share of the power, so the pattern of who can be left out depends on the weights. The three-player pound, where nothing distinguishes the players, is the case in which the structure of the solutions shows most plainly.

When the core is the answer #

The stable set and the core are related, and the relation is simple. A split in the core cannot be dominated — any group that gains under the other split would be getting more than it is worth there, which the core forbids it from being short of — so every split in the core must be in every stable set, since nothing outside could beat it. The core is contained in every solution.

For convex games, where a player adds at least as much to a bigger group, the relation becomes equality. Lloyd Shapley proved in 1971 that in a convex game the core is a stable set, and therefore, since it is contained in every stable set, it is the only one.

The shop game is convex, and its core is a region, cornered at the splits given by the orders of arrival, inside the triangle of splits that give each shop at least what it earns alone. The check confirms Shapley’s theorem at this game: each of the sixty-three lattice splits outside the core is dominated by some split in the core, found on a lattice four times as fine; no core split dominates another. So for convex games the question “which split?” has one set-valued answer, the core, and the single-split answers — the nucleolus, the kernel, the average over orders of arrival and the charge for each user’s own last link in the network game — all lie inside it.

The pound game is the opposite extreme. Its core is empty, so the containment says nothing, and its solutions are many and very different from each other. Between those extremes lie most games.

What the lattice cannot show #

Everything drawn here is computed on a lattice of splits, and the lattice is a finite approximation of a continuous triangle. The domination tests are exact integer comparisons, and where strict inequalities need room the dominating splits are sought on a finer lattice; but the claims that a set is stable for every split, not merely every lattice split, rest on the short arguments given in the text.

The games are all three-player games, where only pairs can dominate and the pictures are triangles. With four or more players the domination relation involves every coalition, the space of splits is a higher-dimensional simplex, and stable sets can have shapes that no picture conveys. The majority game with three players was von Neumann and Morgenstern’s first example because it is the smallest in which the idea does anything, and it is not typical.

And stability is a property of sets, which makes it hard to compute. Checking that a given set is stable requires comparing every split outside it with the set; finding a stable set requires searching over sets of splits, an infinite search in any continuous game. Even for games with few players, describing all stable sets has turned out to be difficult, and for most games they are not known.

Still open: when does a solution exist #

Von Neumann and Morgenstern hoped every game would have at least one stable set. For more than twenty years nobody found a game without one, and for three players it is true: every three-player game has one. William Lucas found in 1968 a game with ten players that has none at all. Lucas and Rabie later found one with fourteen players that has neither a stable set nor a core, so that neither concept says anything.

Between the small cases and Lucas’s examples, the existence question is open. Every game with four or fewer players is known to have a stable set; for five players up to the sizes of the known counterexamples, whether every game has one is not known. It is a strange position for the concept that founded the subject: its definition is two lines long, and no general method is known for deciding whether a given game of eight players has a solution in its sense.

What a set of splits says #

The empty core of the pound game says that no split is safe. The stable sets say something more interesting: that a society can still be stable, if it settles on a standard that answers every proposal outside it and never argues with itself. The three half-and-half splits are one such standard, and a line holding one player at a fixed share is another. The mathematics finds all of them and does not choose among them, because the choice is a convention about who is left out and by how much.

That is the lesson the pound game has taught every approach to collective choice, in its own terms: when majorities can form freely, stability comes from what the participants agree not to propose, not from any particular division being unbeatable.