The corners are the orders of arrival

Two answers to the question of how a group should share what it earns have run side by side through this collection without meeting. A split nobody can walk away from asked for the splits no coalition can beat by leaving, drew them as a region of a triangle, and found that the region can be empty. The order everybody arrives in lined the players up, paid each what it added when it arrived, averaged over every order, and got one split — always, whatever the game.

The two rules are built from different materials. The core is a set cut out by inequalities, one per coalition; the average is a point assembled from orders of arrival. Nothing in either definition refers to the other. And yet for a large and natural family of games they turn out to be two descriptions of one object, with the orders of arrival sitting exactly at the corners of the core.

The game in the figure is as simple as a game can be. A group is worth the square of its size: one player alone earns $1$, any two together $4$, all three $9$. Take the order $A, B, C$. $A$ arrives into nothing and adds $1$; $B$ arrives to find $A$ and lifts the value from $1$ to $4$, adding $3$; $C$ arrives to find two and lifts it from $4$ to $9$, adding $5$. The split is $(1, 3, 5)$. The other five orders give the other five arrangements of those three numbers, and the six points they mark on the triangle are the corners of a regular hexagon — which is precisely the region no coalition can beat.

When arriving later is worth more #

The property that makes this happen is about marginal contributions, and it can be read straight off a table.

A game is convex when every player adds at least as much to a bigger group as to a smaller one it contains: for any player $i$ and groups $S \subseteq T$ not containing $i$,

$$v(T \cup \{i\}) - v(T) \;\ge\; v(S \cup \{i\}) - v(S).$$

The name comes from the same shape of inequality in the curves that lie below their chords, read on groups rather than numbers: the increments grow. The idea it captures is economies of scale. A newcomer is worth more to an established group than to a small one — a shared machine is better used, a larger network reaches more people, a joint venture has more to build on.

For the squared-size game every row of the table reads $1, 3, 3, 5$: nothing alone beyond one’s own unit, three to a partner, five to a pair. The increments grow, weakly, along every row, and that is the whole of the check. It is a finite list of comparisons — for three players, each player against each of its possible groups and their enlargements — and the figure makes every one of them.

Shapley’s theorem, checked #

Lloyd Shapley proved in 1971 that convexity is enough to make the two rules meet completely:

In a convex game, the core is exactly the convex hull of the splits given by the orders of arrival.

Three things follow at once. The core is never empty, since it contains every order’s split. Every corner of the core is an order’s split, so the core can be listed by enumerating orders. And the average over all orders — the Shapley value — is an average of points in a convex region, so it lies in the region: in a convex game, the average split is one no coalition can beat.

The reason one inclusion holds is short enough to give. Take an order and its split, and any coalition $S$. List $S$’s members in the order they arrived. The first adds to whoever was already there at least what it would add to nobody; the second adds at least what it would add to the first alone; and so on, because each member joined a group containing all of $S$’s earlier members and convexity says joining a bigger group is worth at least as much. Adding up, $S$’s members receive at least $v(S)$ in total. So no coalition can beat any order’s split, and those splits lie in the core. That the core has no other corners is the harder half, and the figures check it rather than prove it: for each game the core’s corners are computed exactly, as intersections of its boundary lines, and compared with the orders’ splits one by one.

Every other rule agrees too #

Convexity does more than reconcile two rules. It collapses the whole sequence of stability notions that the core’s failures forced into existence.

The objection nobody can make louder was invented for games whose core is empty: when no split survives every objection, pick the one whose loudest complaint is quietest. An objection one player makes to another weakened the test further, to pairwise threats balanced against pairwise counter-threats, and then to objections that can merely be answered. Each weakening produced a larger set, nested round the core, so that something survives in games where the core offers nothing.

In a convex game none of that is needed, and Michael Maschler, Bezalel Peleg and Shapley showed in 1972 that none of it changes the answer. The kernel of a convex game is a single point and it is the nucleolus; the bargaining set, the loosest of the three, shrinks to exactly the core. The notions that were built to disagree with the core, because the core could be empty, agree with it when it is not only non-empty but generated by orders.

And the five weighings cannot fail. The balancedness test certifies an empty core by finding a family of coalitions whose weighted demands exceed the whole; in a convex game any such family’s demand is at most what an order of arrival pays out, since each order already satisfies every coalition. The certificate of emptiness has nothing to find, which is Shapley’s theorem seen from the other side.

Orders that land on the same corner #

Convexity allows the increments to grow weakly, and when some of them stay level, different orders produce the same split and the core has fewer corners than there are orders.

The three shops earn $1$, $2$ and $3$ alone, $5$, $6$ and $7$ in pairs, and $10$ together. Each shop adds the same amount to any group that is not empty — $A$ adds $3$, $B$ adds $4$, $C$ adds $5$ — so the only thing an order decides is who arrives first and collects its stand-alone value instead. Six orders, three first arrivals, three splits: $(1, 4, 5)$ when $A$ is first, $(3, 2, 5)$ when $B$ is, $(3, 4, 3)$ when $C$ is. The core is the triangle they span, and it is small, because the game has little to fight over — every pair’s claim is nearly what the three produce together.

The average now counts each corner twice, and it is still the plain average of three points, $(7/3, 10/3, 13/3)$. The Shapley value is the average of the orders, not of the corners; in a convex game the two coincide only when every corner is reached by the same number of orders, which symmetry arranges for the squared-size game and nothing arranges in general.

Where convexity fails #

The three partners of the first essay on the core make the contrast. Any two of them earn something together — $6$, $4$ or $2$ depending on the pair — and all three earn $9$.

$B$ adds $6$ to $A$ alone but only $5$ to the pair $A$ and $C$, since $A$ and $C$ already earn $4$ and all three earn $9$. $C$ adds $4$ to $A$ but only $3$ to $A$ and $B$. Joining a bigger group is worth less than joining a smaller one, and in those places the game has diseconomies of scale: $A$ and $B$ are a strong pair, and a third partner dilutes them.

The consequences are exactly the ones the theorem’s failure predicts. In the two orders where $A$ arrives first, $A$ adds nothing to an empty group and gets nothing, and neither split survives: $(0, 6, 3)$ gives $A$ and $C$ three between them where they could earn four, and $(0, 5, 4)$ gives $A$ and $B$ five where they could earn six. Both fall outside the core. And the core has a corner that no order produces at all, $(1, 5, 3)$, where two coalitions’ constraints meet without any arrival sequence leading there. The core is no longer the outline of the orders; it is a region that some orders miss and that has corners of its own.

Convexity is sufficient and not necessary, and this game shows how much room that leaves. The core here is large and non-empty, and the average, $(4, 3, 2)$, lies inside it — by good fortune rather than by theorem. A game can fail convexity and still have its average in its core; what it loses is the guarantee.

The game where every order lands on a corner of the triangle #

The majority game, where any two of three players can take a pound, is the extreme case.

In any order, the first player adds nothing, the second completes a majority and adds the whole pound, and the third adds nothing. So every order hands everything to the player who happens to arrive second, and the six orders land on the three corners of the triangle, two on each. Their outline is the whole triangle. The core, as the first essay on it found, is empty.

This is convexity failing as badly as it can: $A$ adds $1$ to $B$ and $0$ to the pair $B$ and $C$ — the most a player can add, and then nothing. The orders’ splits are as far from the core as the triangle allows, because each of them is a split in which two players receive nothing and together could take the whole pound. The outline of the orders always contains the core — that inclusion holds for every game, and was proved by Robert Weber — and in the majority game the containment is as loose as it can be, the whole triangle around an empty set.

The hexagon is a solid everybody has already met #

The hexagon in the first figure is not a coincidence of three players, and what it is in general is the surprising part.

For any game in which a group’s worth depends only on its size — $v(S) = f(|S|)$ — each order’s split pays the $k$-th arrival $f(k) - f(k-1)$, so the orders’ splits are all the rearrangements of one list of numbers. When $f$ grows faster and faster, the game is convex, and its core is the convex hull of every rearrangement of that list. That solid has a name: the permutohedron. In three dimensions, for four players, it is the truncated octahedron, with twenty-four corners — one for each order of four players — six square faces and eight hexagonal ones.

The core’s own description, as the splits no coalition can beat, then reads: a list of numbers adding to $f(n)$ whose every $k$ entries add to at least $f(k)$. That is a classical characterisation of the permutohedron in terms of partial sums, due to Richard Rado in 1952 — so Shapley’s theorem, specialised to a group worth a function of its size, is Rado’s theorem, one statement read as economics and as geometry. The permutohedron is to orderings what the solid whose corners are triangulations is to ways of cutting a polygon: a polytope whose corners are a family of combinatorial objects and whose edges are single moves between them — here, swapping two neighbours in the queue.

That last connection has a practical side. Maximising a linear function over the core of a convex game is done by a greedy rule: sort the players by their weight in the function, let them arrive in that order, and read off the split. The corner reached is optimal. This is Jack Edmonds’s greedy algorithm for polymatroids, from 1970, and the orders of arrival are the reason it works — every corner is an order, so searching the corners is searching the orders, and the right order can be written down directly.

Where games like this come from #

Economies of scale are common, and so are the games that encode them, though they usually arrive as cost-sharing rather than as dividing a gain.

A shared facility is the standard case. When a group’s cost is set by the largest need among its members — a runway long enough for the largest plane, a pipe wide enough for the heaviest user — adding a member to a larger group costs at most what it costs to add them to a smaller one, since the larger group has already paid for more. That is convexity for costs, and sharing a cost that is not the sum of its parts works through the three-user version, where the average over orders reduces to a rule applied segment by segment: everybody who needs a stretch of runway shares that stretch equally. Shapley’s theorem guarantees what that essay found by computation — no group of users is charged more than it would pay alone.

Dividing an estate among creditors is another. When a debtor’s assets fall short of the total claimed, the value of a coalition of creditors is what is left for them after everyone outside the coalition has been paid in full, or nothing if that is negative. These bankruptcy games, introduced by Barry O’Neill in 1982, are convex: each extra creditor in a coalition removes a claim that would otherwise have been paid first, so late arrivals are worth more. Their cores are therefore never empty, and every order of arrival — first come, first served — is a corner of them.

Voting games are the exception. A group’s worth there jumps from nothing to everything at the moment it becomes a majority, which is the opposite of a steady increase, and the majority game above is what that looks like: convexity failing completely, every order landing on a corner of the triangle, and the core empty.

Three players, and not four #

Every core drawn here belongs to a three-player game, because the triangle of splits is the only picture in which a core can be seen whole. With four players the core is a solid in three dimensions and with more it cannot be drawn at all; the permutohedron for four players is described and not shown.

The theorem is checked, not proved, beyond the half given in words. For each game the core’s corners are computed exactly — as intersections of pairs of the six boundary lines, kept when they satisfy all six constraints — and compared with the orders’ splits. That establishes the equality for these five games. The general statement, for every convex game of any size, is Shapley’s; the argument above shows only that orders’ splits lie in the core, not that the core has no other corners.

Convexity is a strong condition and most games do not have it. The examples were chosen to show the theorem, its weak form and its failure, and nothing here measures how common convexity is among the games that arise. It is typical of cost-sharing for shared facilities, where larger groups spread fixed costs, and atypical of voting, where the majority game shows it failing completely.

Still open: whether every game has a stable set of splits #

The core is one answer to which splits are stable, and when it is empty the game theorists John von Neumann and Oskar Morgenstern had proposed another in 1944: a stable set, a set of splits none of which is beaten by another member of the set, and which together beat every split outside it. A game can have many stable sets or one. Shapley proved in the same 1971 paper that in a convex game the core itself is the only stable set — one more way in which convexity makes every rule agree.

For games in general it is not settled when a stable set exists. William Lucas found in 1968 a game with ten players that has none. Every game with four or fewer players has one: the three-player case was settled early, and the four-player case was proved by Olga Bondareva and her colleagues in 1979. For five players up to the sizes of the known counterexamples, whether a stable set always exists is not known.

Two rules that were one #

The habit worth keeping is the one the hexagon teaches.

Two definitions made from different materials — one cutting a region out of the triangle with inequalities, one building points from orders of arrival — turn out to describe the same object whenever a single condition on increments holds. The condition is checkable from a table, it has a plain meaning, economies of scale, and it converts a question that can fail, is the core empty?, into one that cannot, list the orders. When the increments grow, the orders are the corners, and the average of the orders, which was only ever defined as a fair-sounding average, inherits the core’s stability for free.

When the increments do not grow, the two rules separate, and the pictures show exactly how: orders that fall outside the core, corners no order reaches, and in the worst case a triangle of order-splits around an empty core. The distance between the two rules is a measure of how far the game is from having economies of scale.