Five weighings and the question is closed

A split nobody can walk away from draws the triangle of ways to divide what a group earns, cuts it with one straight line per coalition, and reports what is left. For the three-player majority game nothing is left, and the essay says so — but a search that returns nothing is a weak kind of evidence. A region can be a single point that no sweep lands on.

There is a way to settle the question that does not search at all.

What a family of coalitions can be weighed against #

The core is the set of splits $x$ with $x(S) \ge v(S)$ for every coalition $S$ and $x(N) = v(N)$: every group gets at least what it could earn alone, and the whole is handed out.

Now take several coalitions and give each a positive weight. Multiply each coalition’s constraint by its weight and add them up. The result is a single inequality, and it is a consequence of the core’s constraints — so if it is false, no split satisfies them all.

The left-hand side of the sum is $\sum_S \lambda_S\, x(S)$, and the trick is to choose the weights so that this collapses. Each player $i$ appears once in the sum for every coalition containing it, so the coefficient of $x_i$ is $\sum_{S \ni i} \lambda_S$. Choose the weights so that every player’s coefficient is exactly one and the left-hand side becomes $x(N) = v(N)$, a known number. The inequality reads

$$v(N) \;\ge\; \sum_S \lambda_S\, v(S),$$

with no unknowns in it at all.

A family of coalitions with such weights is called balanced. Every balanced family gives one inequality among the game’s own numbers, and if any of them fails, the core is empty. That is the easy half of the theorem, and it is the half that produces certificates.

The five families, and why there are five #

For three players the balanced families can be listed. Any partition of the players is balanced with every weight one, since each player is in exactly one block: the three singletons, or one pair with the leftover player, in three ways. That is four. And the three pairs at a half: each player is in two pairs, $\tfrac12 + \tfrac12 = 1$.

There are no others worth testing. A family containing a coalition whose weight can be lowered to nothing without breaking the balance is not doing anything the smaller family does not; among families of at most three coalitions with weights of small denominator, an exhaustive search finds exactly those five, and the figures run that search rather than quoting the list.

Five inequalities, and the theorem is that they are enough. If all five hold, the core is not empty — which is the hard half.

Reading the failing family as a story #

The inequality that fails is arithmetic, and it is worth saying what it means before treating it as algebra, because the meaning is the reason the theorem convinces.

Three people, a pound, and any two of them can take it. The failing family is the three pairs, each at weight a half. Read the weights as time: suppose the three pairs each form for half the available time, so that every person is working exactly all of the time — half with one partner and half with the other. In that arrangement each pair earns its pound for the half of the time it exists, so the total earned is three halves of a pound.

But the three of them together can only earn one pound. So the arrangement earns more than the grand coalition can, and a split that satisfied every pair would have to hand out at least what that arrangement earns. The weights are not a bookkeeping device; they are a schedule, and a balanced family is a way for everybody to be fully employed in overlapping groups.

That reading explains the name and the condition together. Balanced means every player fully occupied, the demand is what the schedule earns, and the theorem says a stable split exists exactly when no schedule beats the whole group working together. A game where some overlapping arrangement outperforms the grand coalition is a game where cooperation on the largest scale is not the best use of the players, and the core’s emptiness is the formal shadow of that.

It also says which games are safe. If the value function is such that merging always pays at least as much as splitting — superadditive is not enough, and the right condition is exactly balancedness — then the whole group is the most productive arrangement and something stable exists. The three-shop game is of that kind, and the majority game is not: two of the three earn as much as all three, so a third person is a passenger, and passengers are what make a core empty.

The hard half is a duality #

Why should a finite list of consequences be sufficient? The reason is that the core is defined by linear inequalities, and a system of linear inequalities that has no solution has a reason for having none: some positive combination of the constraints contradicts itself. That is Farkas’ lemma, and it is the same statement as the equality of a linear program and its dual.

Set it up as a program. Minimise $x(N)$ subject to $x(S) \ge v(S)$ for every coalition $S$. The core is non-empty exactly when that minimum is at most $v(N)$ — a split handing out $v(N)$ and satisfying every coalition exists precisely then, since any cheaper solution can be topped up. The dual program maximises $\sum_S \lambda_S v(S)$ over non-negative weights with $\sum_{S \ni i} \lambda_S = 1$ for every player, which is to say over balanced families. Duality says the two numbers are equal.

So the largest demand any balanced family can make is the cheapest way to satisfy everybody, and the core is non-empty exactly when that number does not exceed $v(N)$. The five families are the extreme points of the dual’s feasible region, and a linear function over a polytope is maximised at a vertex — which is why checking five is checking all of them.

That is the whole of the Bondareva–Shapley theorem, proved twice independently in 1963. It is a statement about games whose content is a statement about linear programs, and the translation is the work.

What a satisfied certificate does and does not prove #

One family failing settles the question. One family holding settles nothing: the majority game satisfies four of its five. So the certificate is asymmetric in exactly the way an impossibility proof usually is — a single witness refutes, and confirming needs every case.

That asymmetry is the reason the theorem is worth having in both directions. Run the five and one fails: the core is empty, and the failing family is a one-line proof anybody can check. Run the five and all hold: the core is non-empty, and nothing has been produced except the knowledge that a split exists. Finding one is a separate computation — the sweep, or a vertex enumeration.

The case where a certificate is exactly met #

A balanced family can be satisfied exactly, and when it is, the core is a single point. The reason is that equality in the summed inequality forces equality in every constraint the sum used: if $\sum \lambda_S x(S) = \sum \lambda_S v(S)$ and each $x(S) \ge v(S)$ with $\lambda_S > 0$, then every one of those constraints is tight. So every coalition in the family gets exactly what it could earn alone, which pins the split down.

The glove game is the standing example. Two left gloves and one right; a pair is worth one and two lefts nothing. The pair family asks for $\tfrac12(0 + 1 + 1) = 1$, and there is one. So the core is the single point giving everything to the right glove — which is the split the nucleolus also chose, and the harshness that essay defends is now visible as a geometric fact rather than a verdict: there is no room for any other answer.

Tight, satisfied and violated are three different verdicts and the figures report which. A game whose tightest certificate has slack has a core with interior; one whose tightest is exactly met has a core that is a point or a face; one whose tightest fails has no core at all. The number to look at is the slack, and it is a single subtraction.

How empty an empty core is, from the same list #

The objection nobody can make louder records that the majority game’s core is “empty by a third” and computes the third by minimising the largest complaint over a grid of splits. The certificates give the same number by arithmetic.

Relax every coalition’s demand by $\varepsilon$: ask for $x(S) \ge v(S) - \varepsilon$ instead. Summing a balanced family with weights $\lambda$ now gives $v(N) \ge \sum \lambda_S v(S) - \varepsilon \sum \lambda_S$, so the family is satisfiable once

$$\varepsilon \;\ge\; \frac{\sum \lambda_S v(S) - v(N)}{\sum \lambda_S}.$$

The smallest $\varepsilon$ that satisfies every family at once is the largest of those ratios, and it is the least core value. For the majority game the pair family gives $(\tfrac32 - 1) / \tfrac32 = \tfrac13$, and every other family gives something negative. So the first stage of the nucleolus’s cascade — which that essay describes as a minimisation over a grid — is a maximum over five fractions.

That the same expression reads both ways is worth stating plainly. When the core is empty the number is positive and says how much relaxation is needed. When the core is non-empty the number is negative and says how much the demands could be raised before it vanishes. A single quantity, and its sign is the verdict — which is what the certificate list buys over a search, since a search that finds a region cannot say how nearly it failed to.

The four-player case, and what changes #

Three players is where the triangle can be drawn and five certificates is where the list can be printed, so it is worth saying what both look like one step up, because the change is in the list and not in the theorem.

For four players there are fourteen non-empty proper coalitions and the minimal balanced families number a few dozen — the partitions, of which there are fifteen, plus families mixing sizes: the four triples at a third each, pairs and triples at mixed weights, and the six pairs in three matched sets. Every one of them is still a schedule, every one still gives one inequality, and the theorem is unchanged.

What changes is that printing them stops being useful. A table of forty rows is not a picture and is not read; a linear program with fourteen constraints is solved in microseconds and reports which constraints are binding, which is the same information in a usable shape. So the certificate view is the right one for three players and for proofs, and the program view is the right one for computation — and the theorem is what says the two agree.

The other thing that changes is that a core can be a face rather than a point or a region with interior. With three players a tight certificate pins the split down completely; with four it can leave a segment, because the tight constraints need not determine all four shares. Tightness bounds the core’s dimension rather than fixing it, which is a statement the triangle cannot illustrate and the arithmetic states without trouble.

What this does not settle #

It does not scale. The dual has one variable per coalition, so $2^n - 2$ of them, and the vertices of its feasible region are the minimal balanced families — of which there are five for three players, dozens for four, and a number nobody has a formula for in general. Checking every certificate is therefore not a practical algorithm; what is practical is solving the linear program, which is the same thing without enumerating the vertices.

It does not produce a split. The theorem is an existence statement and its proof is a duality, so it hands over a number and not an allocation. The fleet’s own worked example of that distinction is the assignment polytope, where knowing the vertices are whole is separate from finding one.

And it says nothing about which split to choose. A non-empty core is usually a region with many points in it, and the core does not prefer any of them. Choosing needs a further rule, which is what the nucleolus and the averaging rule are, and the two disagree.

What the pictures cannot show #

Every game drawn here has three players, because three shares that add to a fixed total are a triangle and four are a tetrahedron. The certificate list is short for the same reason the triangle is drawable, and both stop at three.

The sweeps are the check rather than the argument. A lattice of sixty-one by sixty-one splits keeps the ones no coalition beats, and the figures require the count to be consistent with the certificate verdict — but a core small enough to slip between lattice points would show as zero kept and the certificates satisfied, which is exactly the disagreement the check is written to catch. When the two disagree the resolution is too coarse for the game, not the theorem wrong.

And the duality is not drawn at all. That the largest balanced demand equals the cheapest satisfying split is a theorem about two linear programs, its proof is a separating argument in a space of six dimensions, and no triangle contains it. The figures compute both sides for the games they draw; the equality in general is the algebra above.

Still open: how many certificates a game needs #

The five families are the minimal balanced ones for three players, and the number for larger games grows in a way nobody has pinned down. The count of minimal balanced families on $n$ players is known for small $n$ by computation and has no known formula, and the same is true of the number of facets a core can have.

The related question with more at stake is computational. Deciding whether a core is non-empty is a linear program with exponentially many constraints, which is tractable when the game’s values have enough structure to be described compactly and is hard in general. For several natural classes of game the question is known to be hard, for others there are fast algorithms exploiting the structure, and the boundary between the two is not drawn. That is the same shape of question as the one about computing the nucleolus for structured games, and it has the same answer so far: the structure decides, and which structures suffice is open.

Where the same certificate turns up elsewhere #

The pattern — a family of constraints with weights, summed into one inequality with no unknowns — is not confined to this subject, and recognising it is worth more than the theorem.

Hall’s condition is an instance. A set of jobs can be filled by distinct people unless some group of jobs has too few candidates, and too few is a count of one side against the other — which is the summed inequality with every weight one, over the family of jobs in the group. The theorem that the single obstruction is the only one is the statement that those certificates are sufficient, and it has the same proof shape: the problem is a linear program in disguise, and infeasibility has a short reason.

The apportionment paradoxes are the other side of the same coin. Two out of three and never all three shows three conditions that cannot hold together, and the proof is an exhibited example rather than a weighted sum — because the conditions there are not linear inequalities on a single unknown vector, so no Farkas argument is available and a witness has to be constructed by hand.

Which of the two shapes a subject has is decided by whether its constraints are linear, and that is worth checking early. A subject whose impossibilities come with short certificates is one where the failing case can always be exhibited compactly; a subject whose impossibilities need a constructed counterexample is one where each is its own piece of work. This one is of the first kind, and the five families are what that looks like at the smallest size worth drawing.

What a certificate is worth #

A search and a certificate answer the same question and hand over different things. The search hands over an example when it succeeds and silence when it fails. The certificate hands over a proof when it fails and silence when it succeeds. The two are complementary rather than competing, and a subject that has both is in much better shape than one with either.

What makes the certificate available here is that the core is cut out by linear inequalities, and linear inequalities are the one kind of constraint for which infeasibility always has a short reason. That is Farkas’ lemma, it is the same fact as linear programming duality, and it is the reason this subject and that one keep meeting.

The habit worth carrying is narrower and more useful than the theorem. When a search for a solution comes up empty, ask what combination of the constraints contradicts itself — because if the constraints are linear there is one, it is short, and it is a far better answer than a report that nothing was found.