A split nobody can walk away from

The order everybody arrives in asked what each member of a group is owed and got a unique answer out of four conditions. This asks a different question with the same data — not what is deserved but what can be held — and the answer is a region rather than a point, and sometimes there is no answer at all.

A division is stable — in the core — when no group of players could do better by walking out and earning on their own. That is not a fairness criterion. It is an enforceability criterion, and the two come apart quickly.

Every split is a point, every threat is a line #

Three shares adding to nine are three numbers with one constraint, so they form a two-dimensional set, and the natural picture is a triangle: each corner is everything to one player, each edge is a split leaving one player out, and every interior point is a division.

A coalition’s demand is that its members’ shares add to at least what the coalition could earn alone. Adding two of three coordinates is a linear operation, so the demand cuts the triangle with a straight line and keeps one side of it. Three pairs make three cuts, and the singletons make three more — although for a game where nobody earns anything alone, those three are the triangle’s own edges and remove nothing.

So the core is an intersection of half-planes: a polytope, and in the three-player case a polygon. What it looks like is decided by arithmetic, and the figures find it by sweeping every split on a fine lattice and keeping the ones no coalition can beat.

Nothing survives #

The interesting case is the one where the cuts leave nothing at all.

Three people are to divide one unit, and any two of them can take the whole unit by outvoting the third. Consider any proposed division. Some player is getting at most a third, so the other two are getting at least two thirds between them — but those two can take the whole unit, so they will. Whatever is proposed, some pair does better by leaving.

The arithmetic is a single line. Each of the three pairs demands one, so the three demands add to three; but each player’s share is counted in exactly two of the three demands, so the demands add to twice the total, which is two. Three is not less than or equal to two, and there is nothing to discuss.

That is Bondareva and Shapley’s condition in its smallest instance: a core exists exactly when no balanced family of coalitions demands more in total than the whole group is worth. The figure decides emptiness by that condition and draws the sweep beside it, and the two are required to agree — a sweep that found nothing would otherwise be indistinguishable from a sweep that was too coarse.

A core that is a single point #

Between “a region” and “nothing” there is a case worth its own figure, because it is the one where the core says something a fairness rule would not.

A pair of gloves is worth one; two left gloves are worth nothing. Suppose the right-hand holder is offered anything less than the whole unit. Then one of the left-hand holders is getting something, and the right-hand holder can go to the other left-hand holder and offer them a fraction more than they are currently getting — which is available, because the two of them can earn the whole unit between them. So no division except everything-to-the-right-glove is stable.

The Shapley value for this game is a sixth, a sixth and two thirds. Most people asked to divide the proceeds would produce something in that neighbourhood, and it is not stable: the scarce player can always break it. The core and the value are answering different questions and the glove game is where the difference becomes visible rather than theoretical.

Reading the region #

The shaded region in the hero figure is worth walking round, because every one of its edges is a threat and every corner is two threats at once.

The three partners earn nine, and the pairs earn six, four and two. The first pair’s demand — that the first two partners get at least six between them — is the same as saying the third partner gets at most three, which is a line parallel to the edge where the third partner gets nothing. The second pair’s demand caps the second partner at five, the third’s caps the first at seven.

So the core here is the set of splits in which nobody takes too much, with the three ceilings coming from what the other two could earn without them. That is the general shape of a core in a game with worthless singletons: not a floor under each player, but a ceiling, set by what the rest of the group can do alone.

The ceilings are three, five and seven, and they add to fifteen against a total of nine — which is the slack that makes the region two-dimensional. Tighten the pair values and the ceilings drop; when they add to less than the total, nothing is left, which is the counting argument of the previous section written for a general three-player game.

What the core is good at #

The core has an obvious weakness — it is often empty, and often huge — and one considerable strength, which is that when it is a single point, that point is worth knowing.

The pattern recurs across the field. Deferred acceptance produces a matching no pair wants to break, which is a core-style condition on a structure with no numbers in it at all; and the set of stable matchings is a lattice with two extremes, which is a shape rather than a point for the same reason.

The connection to duality is closer than it looks. The core is defined by linear inequalities, so asking whether it is empty is a linear programming feasibility question, and the answer is given by the dual: the core is empty exactly when a combination of coalition demands, with non-negative weights that assign every player a total of one, exceeds the group’s worth. That combination is what balanced means, and the Bondareva–Shapley theorem is the duality theorem specialised.

That is a satisfying place for the theory to land. The condition looks combinatorial, arrives from a completely different direction, and turns out to be an instance of the same equality between two numbers that runs through the rest of the field.

Two ideas of stability, and a third #

It is worth setting the core against the other stability notions this field has already met, because the word is doing different work in each and the differences are instructive.

An equilibrium is stable against a single player changing what they do. Nobody can improve by deviating alone, and nothing is said about what two players could achieve by deviating together. That is a much weaker requirement, and it is why equilibria almost always exist while cores frequently do not.

A stable matching is stable against a pair deviating: no man and woman both prefer each other to their assigned partners. That is exactly a core condition on coalitions of size two, and the reason a stable matching always exists is that in that setting the larger coalitions never add a demand the pairs have not already made.

The core asks for stability against every coalition at once, which is the strongest of the three and the reason it is the one that can fail. Each step up in what a deviating group is allowed to be — one player, a pair, any subset — removes more divisions, and the majority game is where the third step removes them all.

There is a fourth position worth naming, and it is the one the field usually ends up in: relax what counts as an objection. A coalition might be required not merely to improve on its members’ shares but to survive a counter-objection from another coalition, and the set of divisions surviving that weaker test — the bargaining set — is never empty. Every solution concept past the core is some version of this manoeuvre.

Where it fails, and what it needs #

Emptiness is common. Any game where a majority can take everything has an empty core, which covers a large fraction of the situations the theory was built to describe. The response in the literature has been a family of weaker notions — the bargaining set, the kernel, the nucleolus — each of which is non-empty by construction and each of which is harder to justify.

Size is common too. At the other extreme, a game where the coalitions demand very little has a core almost as large as the whole triangle, and “the core” then rules out almost nothing.

It says nothing about which point. When the core is a region, every point of it is equally stable and the theory has no preference. Combining the two ideas — asking for the Shapley value when it happens to be in the core, and something else when it is not — is a rule, but not one with a characterisation behind it.

Nothing here scales without effort. Deciding whether a division is in the core means checking every coalition, of which there are $2^n$. Deciding whether the core is empty is a linear program with a variable per player and a constraint per coalition, which is exponentially large in the number of players even though it is polynomial in its own size. Both are stated as facts about the instance, in the way this field states every count, rather than as claims about how such a thing should be computed.

And the threats have to be credible. The whole construction assumes a coalition can leave and collect its value, which is a strong assumption about what the players can do. Where leaving costs something, or where the remaining players could retaliate, the numbers change and so does the region.

Where it came from #

The idea is in von Neumann and Morgenstern’s 1944 book, though not under that name and not as the primary object — their theory of “stable sets” was the intended solution concept, and the core appears as a technical device inside it. Gillies named and studied it in 1953, the same year Shapley’s paper appeared, and the two have been read as a pair ever since.

The emptiness question was settled independently by Bondareva in 1963 and Shapley in 1967, both by linear programming duality. It is a good example of a result that had to wait for a technique rather than for an idea: the condition is not something anybody would guess, and it falls out of the dual in a few lines once duality is available.

The three-player majority game is older than any of it. It is the game von Neumann analysed first, in 1928, and the observation that no division of the pound is safe is the observation that started cooperative game theory rather than a curiosity discovered inside it. Everything since has been an attempt to say something useful about it.

The word core itself carries an assumption worth noticing. It suggests something central and small, and the object is frequently neither — it is a face of the simplex in some games and absent in others. The name is from the intended picture rather than from the theorem.

What the pictures cannot show #

Every game drawn here has three players, so every core is a polygon in a triangle. With four players the simplex is a tetrahedron and the core is a three-dimensional polytope; with ten it is a region in nine dimensions with up to a thousand faces, and nothing about the pictures indicates that the complexity is in the number of coalitions rather than in the geometry.

The shaded regions are found by sweeping a lattice, which is why they are drawn as a cloud of points under a hull rather than as an exact polygon. That is an honest depiction of what was computed, and it means a core of zero area — a single point or a segment — appears at whatever resolution the lattice provides. The emptiness verdict is not taken from the sweep for exactly this reason.

And the empty core is drawn as a triangle with four sample splits marked and the objecting coalition named at each. That is four instances of a claim about infinitely many splits. The claim is proved in the prose by the counting argument, and the figure is a demonstration rather than the proof.

The ladder from here #

Below: the order everybody arrives in, which answers the other question about the same data, and nobody has a reason to run away, where stability is defined on a matching and always exists. Sideways: two numbers that have to meet, whose duality theorem is what decides emptiness, and envy-free up to one item, where a fairness condition is relaxed until it can always be met. Above: the nucleolus, the bargaining set, market games and the theorem that their cores are never empty.

What is worth carrying away #

Two questions that sound like one — what is fair and what will hold — have different answers, different shapes of answer, and different failure modes. The first has a unique answer and no guarantee anybody would accept it; the second has a set of answers and no guarantee the set is inhabited.

The glove game is the smallest place both are visible at once, and it is worth remembering as the standing counterexample to the assumption that a good division is one that survives. What survives there is a division nobody would propose, and what would be proposed does not survive.