A core is a rare thing to find at random

A split nobody can walk away from defined the core of a cooperative game: a division of what all the players earn together such that no group of them could earn more by leaving. Five weighings and the question is closed then showed how to decide whether such a division exists. Olga Bondareva and Lloyd Shapley proved, independently in the 1960s, that the core is non-empty exactly when a certain list of inequalities holds — one for each minimal balanced family of coalitions — and for three players the list has five entries.

That essay ended by noting that the list grows, and that nobody has a formula for how fast. This one counts it for up to five players, and then asks a question the theorem makes easy to answer: if the values of the coalitions are picked at random, how often does a core exist at all?

A certificate is a way of weighing coalitions #

The idea behind the list is worth restating, because everything below counts it. Suppose a division $x$ gives each player $x_i$, with $\sum x_i = v(N)$, the value of everyone together. It lies in the core when every coalition $S$ gets at least what it could earn alone, $x(S) \ge v(S)$. Now pick some coalitions and positive weights $\lambda_S$ for them, chosen so that every player’s weights add up to exactly one — a balanced family. Adding the core conditions with those weights gives

$$\sum_S \lambda_S\, v(S) \le \sum_S \lambda_S\, x(S) = \sum_i x_i = v(N),$$

because each player’s share is counted with total weight one. So if any balanced family has a weighted sum exceeding $v(N)$, no division can satisfy all its coalitions at once, and the core is empty. The family is a certificate of emptiness. Bondareva and Shapley’s theorem is the converse: if no balanced family over-claims, the core is not empty — the statement two numbers that have to meet is the general form of, linear-programming duality, applied to the core’s inequalities.

Only the minimal balanced families are needed: those whose coalitions’ membership vectors are linearly independent, so that the balancing weights are unique. Every other balanced family is a mixture of minimal ones, and its inequality follows from theirs.

Counting the certificates #

The minimal families can be found by brute force for small numbers of players. A family of linearly independent vectors in $n$ dimensions has at most $n$ members, so it suffices to take every set of at most $n$ proper coalitions, solve the $n$ balance equations — one per player — for the weights, and keep the sets whose solution is unique and positive.

For four players there are fourteen proper coalitions, and the search over sets of at most four of them finds forty-one minimal families. Fourteen are partitions — the four ways to split off one player, the three ways into two pairs, the six ways into a pair and two singles, and the split into singletons — and the other twenty-seven are not partitions at all: three pairs and a triple with weights one half each, the four triples at one third each, and families mixing all three sizes with weights of a half or a third. Each is a different way of asking several groups at once to share what they claim.

The counts are $1$, $5$, $41$ and $1{,}291$ for two to five players, which agree with the values in the literature, where they were first obtained by Bezalel Peleg’s method of building the families for $n + 1$ players from those for $n$. For six players the count runs into the hundreds of thousands. The number of proper coalitions goes $2, 6, 14, 30$; the number of certificates goes $1, 5, 41, 1{,}291$. Each new player doubles the coalitions and multiplies the ways of weighing them against each other by more than thirty.

This is why the list is a theorem rather than an algorithm. Nobody decides whether a large game has a core by checking its certificates; they solve the linear programme directly, with one constraint per coalition, and the certificates are what that programme’s dual would return if the answer were no. But for up to five players the list is short enough to use, and it turns a question about a polytope into a question about inequalities that can be checked in a single pass.

Random games, and the certificate that kills them #

With the list in hand, a game picked at random can be tested in microseconds. The model in the hero figure is the simplest one with a single parameter. Everyone together earns $1$. A single player earns nothing alone. Every other coalition earns an independent random amount, uniformly between nought and $c$. Small $c$ means coalitions short of everyone are worth little; $c = 1$ means a pair might, on its own, earn as much as all the players together.

For three players the answer can be written exactly. The only certificates that can fail are the three partitions into a pair and a single — which need a pair to be worth more than everyone, impossible when $c \le 1$ — and the family of all three pairs at weight one half, which fails when the three pairs’ values add to more than two. So the core exists with the chance that three uniform numbers on $[0, c]$ add to at most two, an Irwin–Hall probability, and at $c = 1$ that is exactly five-sixths. The arithmetic is a picture: three uniform values are a random point in the unit cube, and the points whose coordinates add to more than two fill the corner cut off by the plane $x + y + z = 2$, a tetrahedron with three edges of length one meeting at right angles, whose volume is one-sixth. For smaller $c$ the cube shrinks and the plane cuts off less, and once $c \le 2/3$ it cuts off nothing. The simulation sits on the exact curve at every value of $c$.

For four players at $c = 1$ the share with a core is 6.6 per cent; for five, none of two thousand games has one. The collapse is not gradual in $c$: for five players the share falls from 99 per cent at $c = 0.44$ to 2 per cent at $c = 0.72$. Below a threshold there is a simple reason every game has a core. In any certificate, each coalition other than a single player has at least two members, and every player’s weights add to one, so the weights on those coalitions add to at most $n/2$. If no coalition is worth more than $2/n$ of the whole, no certificate can over-claim. That threshold is $2/3$, $1/2$ and $2/5$ for three, four and five players, and the figure’s curves leave one exactly there. Above it the certificates start to bite, and there are a great many of them.

Which certificate fails tells how the core is lost. In four-player games the culprit is overwhelmingly the plainest family there is: a split of the players into two pairs, whose values together exceed what all four earn. With pairs worth up to the whole, two disjoint pairs over-claim half the time, and there are three such splits, so a random game survives all three with chance about one eighth before any other certificate is consulted. The four triples at one third each — the family that looks most like an elaborate conspiracy — are the worst offender in 23 games out of 18,663. Small groups making modest claims that add up, not large groups making large ones, are what empty a random core.

Two partnerships that cannot both be paid #

The two-pair certificate has a plain reading, and it explains most of what the figures show. Split the four players into two partnerships, say $\{1, 2\}$ and $\{3, 4\}$. Any division of the whole pays the first partnership something and the second the rest, and if $v(12) + v(34) > v(N)$ then at least one of them is paid less than it could earn by itself and will walk away. No weights, no fractions: two groups, disjoint, each demanding more than the whole can spare for it.

With pair values uniform on $[0, 1]$, the sum of two independent values exceeds one with chance exactly one half. There are three ways to split four players into two pairs, and the three splits use six different pair values, so the three events are independent and the chance that all three splits are satisfied is $(1/2)^3 = 1/8$. That is an upper bound on the share of four-player games with a core: 12.5 per cent. The measured share is 6.6 per cent, so the other thirty-eight certificates, between them, remove about half of the games the pairs leave alone; among games that fail, the families mixing a pair with two triples are the next most frequent culprits after the pairs themselves.

The calculation also shows why the model matters. Under a model where a pair is worth at most half the whole, the two-pair certificate can never fail and the four-player picture changes completely. The core is fragile in proportion to what small coalitions can claim, and the uniform model, which lets a pair claim as much as everyone, is the harshest reasonable choice. The qualitative result — that cores become rarer as players are added, and quickly — survives gentler models, because the number of certificates grows whatever the values are, and each extra certificate is one more way to fail.

Checking a certificate list is not how cores are found #

For a reader who wants to decide whether a particular game has a core, the certificate list is the wrong tool beyond five players. The core is the set of divisions satisfying one inequality per coalition, a polytope in $n$ dimensions described by $2^n - 2$ inequalities and one equation, and whether it is empty is a single linear programme: maximise nothing, subject to all those inequalities. What a constraint is worth described how such a programme is solved, and its cost grows with the number of inequalities, $2^n$, not with the number of certificates, which grows much faster. The certificates are what the programme’s dual produces when the answer is no — a single minimal balanced family, with its weights, as a proof of emptiness that anyone can check by adding up.

That division of labour is general. A list of all possible certificates is a way of understanding a problem’s structure, and a search for one certificate is a way of solving it. For two to five players the list is small enough to read, and reading it shows which kinds of over-claim are possible; for larger games only the search is practical, and it finds the over-claim that applies to the game in hand without enumerating the ones that do not.

How empty an empty core is #

A core that does not exist can be missed by a little or by a lot, and the least core measures which. Relax every coalition’s claim by the same amount $\varepsilon$, so that a division need only give each coalition $v(S) - \varepsilon$; the least core is the set of divisions that work for the smallest $\varepsilon$ that makes any work, as the objection nobody can make louder used it on the way to the nucleolus. With the certificates the smallest $\varepsilon$ is a formula: each family gives a lower bound $(\sum \lambda_S v(S) - v(N))/\sum \lambda_S$, and $\varepsilon$ is the largest of them.

The three distributions move steadily to the right as players are added, and the median goes from $-0.085$ for three players to $0.194$ for four and $0.364$ for five. A random five-player game is not merely without a core: it would need every coalition to give up about a third of the whole before the claims could be reconciled. And the five-player distribution is narrower as well as further out, because with 1,291 certificates the worst one is reliably bad — the largest of many independent-looking excesses concentrates, as maxima do.

The structure that promises a core #

The positive results about cores are all about structure. The corners are the orders of arrival proved Shapley’s theorem that a convex game — one in which a player adds at least as much to a larger coalition as to a smaller one — always has a core, and a large one, whose corners are the marginal-contribution vectors of the orders of arrival. Market games have cores, as one glove too many and a market too large to bargain in used; so do the cost-sharing games of each user pays for its own last link. Each theorem names a structure, and the structure does the work.

The random games show how rare that structure is. None of twenty thousand random four-player games is convex — convexity is a family of inequalities, one for every pair of coalitions, and a random game satisfies each with a fair chance and all of them with almost none. A convex game built on purpose, whose coalitions are worth the square of their share of the players, has a core, which the figure checks. Superadditivity, the condition that two disjoint coalitions together are worth at least their sum and the one most often assumed of a cooperative game, is only slightly less rare — 128 games of the twenty thousand — and it promises nothing: fewer than half of the superadditive games have a core.

The contrast is with non-cooperative games, where a third of random games have no pure equilibrium and the remaining two-thirds do, with the share settling at a constant as the game grows. Equilibria survive randomness because each is a local condition on a single cell. A core is a global condition on every coalition at once, and the number of ways a random game can violate it grows faster than the number of coalitions.

What the random model assumes #

The figures use one model, and its choices matter. Coalition values are independent of one another, which is unrealistic in any application: a coalition’s value usually depends on its members, and a triple containing a valuable pair is usually valuable itself. Values are uniform up to $c$ regardless of the coalition’s size, which makes pairs as potent as triples; a model in which values grow with size, $v(S)$ uniform up to $c\,|S|/n$, gives pairs less power and cores more often, although the same collapse with the number of players appears in it at larger $c$. Neither model is a description of real cooperation. What both establish is a fact about the inequalities: the core is a demanding condition, it gets more demanding as players are added, and the theorems that guarantee one guarantee it by assuming structure that independent random values do not have.

The counts of certificates, by contrast, assume nothing. They are a property of the coalitions, not of any game, and the search that finds them checks itself: every family it keeps has unique positive weights, every player’s weights add up to one, and the totals match the values first computed by hand and by Peleg’s recursion.

Still open: how many certificates there are #

The sequence $1, 5, 41, 1{,}291$ continues into the hundreds of thousands for six players, and only a few further terms have ever been computed. There is no formula and no sharp asymptotic estimate: the families correspond to the vertices of a polytope in $2^n - 2$ coordinates, and counting the vertices of such polytopes is hard in general. The crude bounds are far apart — each family is a set of at most $n$ of the $2^n - 2$ coalitions, which caps the count, and recursive constructions from smaller families give many — and where the truth lies between them has not been determined.

A related question asks for the threshold. In the random model, the share of games with a core falls from one to nought as $c$ rises, and for five players most of the fall happens between a half and seven-tenths. Whether, as the number of players grows, the fall becomes a sharp step at a definite value of $c$ — and whether that value tends to one half, where the simple guarantee ends — is the kind of statement random graphs have taught probabilists to expect, and the bound $2/n$ above says that if such a step exists its position is not fixed by the simple argument, since the threshold for certainty falls with $n$ while the measured fall sits well above it. Nobody has proved a sharp threshold for cores.