Matpic
mathematics, in pictures
Concept

Shapley value

The rule that gives each player the average of what they add to the group already present, taken over every order in which the players could arrive. Four conditions — efficiency, symmetry, a player who adds nothing getting nothing, and additivity — leave it as the only possibility.

Named by 11 essays across one field — each of them below, with the objects they name alongside it.

Every order of arrival for three partners, and what each player adds. A table with one row per order in which the players could arrive, giving what each adds to the group already present, and the average of each column as that player's share.

The order everybody arrives in

Three people jointly earn nine, and the question is what each is owed. Ask instead what each adds on walking into a room the others are already in, average that over every order they could have arrived in, and four modest conditions leave no other answer.

applied · Shapley value The quietest loudest complaint in any two of three decide. The triangle of all splits of what a three-player group is worth, with the split minimising the largest excess marked, the average split beside it, and the loudest complaint named.

The objection nobody can make louder

When no split of the winnings survives every group's objection, the core is empty and the question changes — which split makes the loudest objection as quiet as it can be? Sorting the complaints and minimising them in dictionary order picks exactly one split, always, whether or not the core exists.

applied · The core Drop one condition, and something else satisfies the rest. A column for each of the four conditions, holding a sharing rule that breaks that one and keeps the other three, with the split each rule gives on a stated four-player game.

None of the four conditions is spare

Four conditions pick out one sharing rule. The half that is usually shown is that they are enough; the other half is that each is needed — drop any one and a different rule satisfies the rest, so the list cannot be shortened.

applied · Shapley value Sampling the orders, and how fast the answer arrives. The largest error in the estimated shares against the number of orderings sampled, both on logarithmic axes, with the square-root rate drawn through the first point.

Too many orders to list

The rule is an average over every order the players could have arrived in. At seven players that is five thousand orders and at twenty it is more than there are seconds in the age of the universe — so the average is sampled, and the error falls at a rate that can be measured.

applied · Shapley value Every order of arrival for three users of one shared capacity, and what each player adds. A table with one row per order in which the players could arrive, giving what each adds to the group already present, and the average of each column as that player's share.

Sharing a cost that is not the sum of its parts

Three users need capacities three, six and twelve of one shared thing, and serving any group costs the largest of them. Averaging what each adds over every order of arrival divides the bill — and for this family the average collapses to a rule anybody could apply by hand.

applied · Shapley value Credit for one prediction, three ways of leaving an input out. Groups of bars, one group for each way of filling in the inputs that are not known, each bar one input's share of the difference between the prediction and the starting value.

What a missing input is worth

A model prices a house at 180 from its size, its garden and its bedrooms, and the question is how much of the price each input is responsible for. Make the inputs the players and the average over orders answers it — once somebody decides what the model says when an input is not known. Three reasonable decisions give bedrooms nothing, nothing, and sixteen, for a model that never reads them.

applied · Shapley value Shares on two triangles and a go-between. A network of players with each node labelled by its share of what the whole network earns, and its number of links beneath it.

Cutting a link costs both of its ends the same

Three players, any two of whom can earn 1 together — but only if they are linked. Link all three and each is due a third. Remove one link and the player holding both of the others is due two thirds. Averaging over orders on the game the network allows is the one rule under which breaking any link costs the two players it joined exactly the same, and it pays go-betweens more than their links.

applied · Shapley value The core of a group worth the square of its size: the outline of its six arrival orders. Splits of 9 among three players; core corners (1, 5, 3), (5, 1, 3), (1, 3, 5), (5, 3, 1), (3, 1, 5), (3, 5, 1); arrival-order splits (1, 3, 5), (1, 5, 3), (3, 1, 5), (5, 1, 3), (3, 5, 1), (5, 3, 1); average 3, 3, 3.

The corners are the orders of arrival

Line the players up, let each join in turn, and pay each what it adds on arrival: every order gives a split. When a newcomer always adds at least as much to a bigger group, those splits are exactly the corners of the core — so the core is never empty, it is the outline of the orders, and the average over all of them lies inside it. For a group worth the square of its size the outline is a hexagon whose corners are the six orderings of 1, 3 and 5.

applied · The core The cheapest tree for a remote user between two near ones, and each user paying for its own link. A source and 3 users with link costs source–A 2, source–B 9, source–C 2, A–B 1, B–C 1, A–C 2; the cheapest tree costs 4 and Bird's rule charges 2, 1, 1.

Each user pays for its own last link

Several users must be connected to a source, and the cheapest network that does it is a tree. Dividing its cost so that no group of users would rather build its own looks like a hard search, and it has a one-line answer: each user pays for the link that joins it to the tree on its way to the source. No group is ever overcharged — while the average over orders of arrival, the rule that settles so much else, can charge a pair more than its own connection costs.

applied · The core Luxembourg's votes and Luxembourg's power, 1958 to 1995. Paired bars for Luxembourg at five enlargements of the Council: vote share falling and power share rising from nothing in 1958 to 0.95% in 1973 and 3.02% in 1981.

A vote worth nothing until it was outnumbered

From 1958 to 1973 Luxembourg held one vote of seventeen in the Council of the European Communities and could never once change an outcome. When the Council grew, Luxembourg's share of the votes fell and its share of the power rose from nothing. Power is not a quantity a member holds; it is a property of the whole assembly, and changing the assembly moves it in directions nobody would guess.

applied · Shapley value What a left glove is worth as the market tips. For 20 players and L from 1 to 19: the core value of a left glove (1 below 10, any value at 10, 0 above) and the Shapley value, from 0.950 to 0.003.

One glove too many

Give some people left gloves and others right ones, and let any group sell the pairs it can make. If the two sides are equal, the core — the splits no group can beat by walking out — is every price at once. If one side has a single glove more, the core is one split: the scarce side takes the whole of every pair and the other side gets nothing, however large the market. The average over orders of arrival barely notices the difference, and the two rules disagree about almost everything a market is.

applied · The core

Named alongside it

The objects these essays reach for when they reach for this one.

Cooperative gameMarginal contributionCoalitionCoreExhaustive searchSymmetryFairnessCounterexampleEfficiencyImputationPermutationUniqueness

All concepts