The objection nobody can make louder

A split nobody can walk away from asks which divisions of a group’s winnings no subgroup can beat by walking out, and finds that for the three-player majority game — a pound, and any two of the three can take it — there are none. Any split gives some pair less than a pound between them, and that pair can do better alone.

That essay’s closing section names the question this one answers: when nothing survives, what is left to want?

Measuring a complaint #

Give each coalition a number saying how badly it is done by. For a coalition $S$ and a split $x$, the excess is

$$e(S, x) = v(S) - x(S),$$

what the coalition could get alone, less what the split gives it. A positive excess is a genuine grievance — the coalition would do better walking out. A negative one is a coalition doing better than it could alone, which is the normal state of affairs in a game worth playing.

The core is the set of splits where every excess is at most zero. When it is empty, some excess is positive at every split, and the question is which split makes the worst of them as small as possible.

That is not quite enough to pin down an answer. Minimising the largest excess often leaves a whole region tied, so the rule continues: among the splits achieving the smallest possible largest excess, minimise the second largest; among those, the third; and so on. Sorting each split’s excesses from loudest to quietest and comparing the sorted lists in dictionary order picks out exactly one split.

That split is the nucleolus.

Why one split and not several #

Three properties make the nucleolus worth defining rather than merely describing, and the first two are not obvious.

It always exists. The set of splits is a compact triangle and the sorted-excess map is continuous on it, so a minimum is attained. The lexicographic minimisation is then a finite sequence of minimisations over progressively smaller closed sets, each non-empty.

It is unique. Each stage cuts the surviving set down by an equality constraint, and the set of splits achieving a given largest excess is convex; a convex set on which the next excess is minimised shrinks to a point after enough stages. There is a proof of this that fits in a page and it is genuinely a theorem — nothing about a lexicographic rule guarantees a unique optimum in general.

It lies in the core whenever the core is not empty. If some split has every excess at most zero, then the smallest achievable largest excess is at most zero, so the nucleolus has every excess at most zero too, and is in the core. So the nucleolus does not replace the core; it extends it, agreeing wherever the core has something to say.

Computed exactly, and why that matters here #

Lexicographic minimisation is a sequence of linear programmes, and this field’s standing rule is that no comparison consults a tolerance. So the computation here is a search over splits with a fixed denominator, and every excess is multiplied through by that denominator so that every comparison is between whole numbers.

The cost is resolution and it is stated: the figures report the grid searched, and assert that the splits achieving the minimum lie within one grid step of each other. That last assertion is the one that matters. A search returning a cluster of minimisers a long way apart would mean the grid was too coarse to separate them, and reporting one of them as “the nucleolus” would be reporting an artefact.

The gloves game is the one that separates the two rules, and the separation is the point of including it. The order everybody arrives in derives the Shapley value from four conditions and finds it forced; the nucleolus satisfies some of those conditions and not others, and there is no contradiction because the two rules are answers to different questions.

Reading the majority game #

The three-player majority game is the standing example of an empty core, and it is worth following the nucleolus through it because every step can be checked by hand.

The value of any pair is 1; the value of a single player is 0; the value of all three is 1. Take a split $(x_1, x_2, x_3)$ adding to 1. The excess of the pair $\{1,2\}$ is $1 - x_1 - x_2 = x_3$, and similarly for the other pairs — so the three pair excesses are just the three shares, and the three singleton excesses are their negatives.

Minimising the largest of $x_1, x_2, x_3$ subject to their sum being 1 forces all three equal, at a third each. The largest complaint is a third, made simultaneously by all three pairs, and no split does better: making one pair happier means giving two players more, which means giving the third less, which makes a different pair’s complaint louder.

So the answer is the equal split, and the reason is a genuine argument rather than an appeal to symmetry — though symmetry would have given the same answer here, and does not in general. The gloves game is symmetric in the two left gloves and its nucleolus gives them equal shares of nothing; the game where symmetry would mislead is one where two players are interchangeable in the values but differently placed relative to a third, and no such game exists on three players.

What each rule is answering #

The Shapley value asks: what did each player contribute? It averages each player’s marginal contribution over every order of arrival, and its justification is a list of conditions that no other rule satisfies.

The nucleolus asks: what will nobody complain about? It ignores contribution entirely and minimises grievance.

On the gloves game the difference is stark and instructive. Shapley gives the two left gloves a sixth each because in some orders of arrival a left glove arrives to find a right one waiting and adds a whole unit. The nucleolus gives them nothing because they cannot threaten: a left glove walking out with nobody takes nothing, and the two together take nothing.

Contribution and threat are different quantities, and a game can make them disagree completely. Neither rule is wrong; they are measuring different things, and a reader who wants one number out of a game has to decide which question was being asked.

Four conditions and no rule is the standing warning against expecting these choices to be forced. There, four reasonable conditions on a voting rule turn out to be jointly unsatisfiable; here, two reasonable rules exist and disagree, which is the milder version of the same phenomenon.

What the nucleolus gives up #

It is not additive. Play two games at once and the nucleolus of the sum is generally not the sum of the nucleoli. The Shapley value is additive, and that is one of the four conditions it is forced by, so this is a real loss.

It is not easy to compute. For $n$ players there are $2^n - 2$ coalitions and the lexicographic minimisation is a sequence of linear programmes with that many constraints. There are efficient methods for structured games, and the general problem is hard.

It is not monotone in the values. Raise what one coalition is worth, leaving everything else alone, and a player in that coalition can end up with less. That is unsettling and it is a theorem: no rule that always lands in the core can be monotone in this sense, so the property has to be given up by anything with the core-extension property the nucleolus has.

It can be counter-intuitive on small examples. Giving the right glove everything looks harsh, and the harshness is the rule reporting the situation accurately: the two left gloves are in a bidding war they cannot win. Any rule that gave them something would have to be violating the core in a game whose core is exactly that single point.

When the core is empty, by how much #

There is a quantity between the core and the nucleolus that is worth naming, because it is what the first stage of the minimisation computes.

The least core is the set of splits achieving the smallest possible largest excess. When the core is non-empty that number is at most zero and the least core is a subset of the core; when the core is empty the number is positive, and it measures exactly how far from feasible the game is.

For the majority game the number is $1/3$: every split has some pair complaining by at least a third, and one split holds every complaint down to exactly that. So “the core is empty” is refined to “the core is empty by a third”, which is a statement with a size in it.

That refinement is the same move as several elsewhere on this site. The seat that vanishes when the house grows turns an impossibility into a measurement of how badly a rule can misbehave; here the impossibility of a core becomes a number saying how much every split must upset somebody.

And it gives the nucleolus a reading that does not mention dictionary order at all. The nucleolus is what is left after minimising the worst complaint and then breaking the remaining ties the same way — so the first stage is a natural quantity and the rest is the cascade needed to reach a single point.

Where it came from #

Schmeidler defined the nucleolus in 1969 and proved existence and uniqueness in the same paper. The definition was not the first attempt at a single-valued solution for games with empty cores — the bargaining set and the kernel came earlier, from Aumann, Maschler and Davis in the early 1960s — and the nucleolus is inside both, which is part of its appeal.

The lexicographic construction was not new as a technique; what was new was noticing that the excess vector is the right thing to sort. Earlier attempts minimised the largest excess alone and left large ties, and the tie-breaking cascade is the whole of Schmeidler’s contribution.

The word is Schmeidler’s too, chosen for the sense of a small central kernel — the nucleolus of a cell — and the naming was deliberate: the object sits inside the kernel, which sits inside the bargaining set.

The whole family belongs to a period in which the question “what is a fair division of this?” was being attacked from several directions at once, and the striking thing in retrospect is how few of the answers agree. Envy-free up to one item settles for a weakened condition because the strong one is unachievable; one cuts and the other chooses supplies a procedure rather than a formula; the Shapley value and the nucleolus supply formulas that disagree. The subject has no single answer and has several good ones, and being clear about which question each answers is most of what there is to know.

What the pictures cannot show #

Every game here has three players, because the triangle of splits is two-dimensional and can be drawn. Four players give a tetrahedron and five a simplex nobody can see, and the search over a grid becomes a search over a lattice in higher dimensions whose size makes exhaustion impossible at any useful resolution.

The grid resolution is stated and is a real limit. At sixtieths, a nucleolus with denominator 7 would not land on the grid at all, and the search would return the nearest point rather than the answer. The games drawn here have nucleoli with small denominators, which is a property of the games chosen rather than of the rule.

And the emptiness of the core is decided here by the sweep. A core too thin to contain a grid point looks exactly like an empty one from inside a search, which is why the sibling figure decides emptiness independently and requires the two to agree — a search that finds nothing has to be told apart from a search that could not have found anything.

The ladder from here #

Below: a split nobody can walk away from, which builds the core and finds it empty, and the order everybody arrives in, the other rule this is compared against. Sideways: four conditions and no rule, the standing example of reasonable conditions with no rule satisfying them, and three people and a trimmed piece, a division problem where a procedure rather than a formula is the answer. Above: the kernel and the bargaining set, the least core, balancedness and the Bondareva–Shapley theorem, and the computation of the nucleolus for structured games.

What is worth carrying away #

A rule that only works when a solution exists is not a rule; it is a test. The core is a test, and it fails on games as simple as three people deciding by majority.

The nucleolus is what a rule looks like when it is required to answer always. It gets there by changing the question from “is there a split nobody objects to?” to “which split makes the objections smallest?”, and the change is not a weakening — on games where the first question has an answer, the second picks one of them.

Sorting the complaints and minimising in dictionary order is the general recipe, and it appears wherever a problem has no feasible solution and one is wanted anyway. What it needs is a way of measuring how badly each constraint is violated; given that, the rest is mechanical, and the answer it produces is unique for a reason that has nothing to do with the subject.