Sharing a cost that is not the sum of its parts

Every game on this ladder so far has had a value to be shared out. Turn the sign over and the same machinery divides a bill.

The situation is common and the difficulty is specific. Several parties need one thing, they need it to different extents, and the cost of serving them together is less than the sum of the costs of serving them apart. There is a saving, and the question is whose it is.

The game #

Write $c(S)$ for the cost of serving the group $S$. Here $c(S)$ is the largest requirement in $S$, and $c(\emptyset) = 0$.

$$c(A) = 3,\quad c(B) = 6,\quad c(C) = 12,$$

$$c(AB) = 6,\quad c(AC) = 12,\quad c(BC) = 12,\quad c(ABC) = 12.$$

The saving is real: serving all three costs twelve, and serving them separately costs twenty-one.

The rule is unchanged from the bottom of this ladder. A user’s share is the average, over all orders of arrival, of what they add to the cost — and what somebody adds is the increment over what has already been provided. In the order $A, B, C$: the first pays $3$, the second pays $6 - 3 = 3$, and the third pays $12 - 6 = 6$. In the order $C, B, A$: the first pays $12$ and the other two pay nothing.

Averaged over all six orders, the shares are $1$, $2\frac{1}{2}$ and $8\frac{1}{2}$, adding to twelve.

The closed form, which this family has #

For a general game the average over orders is what has to be computed and the rung below is about how expensive that is. For this family it collapses to something anybody could apply by hand.

Sort the requirements: $c_1 \le c_2 \le \dots \le c_n$. Think of the capacity as built in layers: the first layer runs from $0$ to $c_1$ and is needed by everybody; the second runs from $c_1$ to $c_2$ and is needed by all but the first user; and so on.

Each layer is divided equally among the users who need it. So

$$\phi_i = \frac{c_1}{n} + \frac{c_2 - c_1}{n - 1} + \dots + \frac{c_i - c_{i-1}}{n - i + 1}.$$

For the example: the layer from $0$ to $3$ is split three ways, giving $1$ each. The layer from $3$ to $6$ is split two ways, giving $1\frac{1}{2}$ each to $B$ and $C$. The layer from $6$ to $12$ is $C$’s alone, giving $6$. Totals $1$, $2\frac{1}{2}$, $8\frac{1}{2}$ — which is what the enumeration gave.

That is a considerable reduction: $n!$ orders become $n$ layers, and the answer can be computed on paper. The collapse is not luck. It happens because the cost depends on a coalition only through its largest member, so most of the $n!$ orders contribute identically and the average has few distinct terms.

More users, and what stays true #

The layer reading does not depend on there being three of anything, and the general case is worth seeing because the shares stop looking like anything obvious while the rule stays the same.

Three properties survive every case and are worth stating as the family’s summary.

The smallest user pays $c_1/n$ and no more. Their requirement is the bottom layer and they are in no layer above it, so their share is that layer split $n$ ways — as little as any rule respecting the shares adding up could charge.

The largest user pays everything above the second-largest requirement, plus a share of everything below. Their contribution is the only one that includes the top layer whole.

The shares are increasing in the requirements. Somebody needing more never pays less, which is the property that makes the division defensible without any theory at all, and it follows immediately from the layers because a larger requirement means membership in more of them.

None of the three is automatic. Splitting the total equally violates the first and the third; charging each their standalone cost violates the shares adding up; charging in proportion to requirement satisfies all three and fails additivity, and is the fourth column of the independence figure in a different costume.

Why the sign change changes nothing, and one thing it does #

The rule is unchanged because the four conditions are unchanged in substance.

Efficiency becomes the shares pay the bill exactly, with no subsidy from outside and no surplus collected. Symmetry becomes two users with the same requirements pay the same. The null-player condition becomes a user who adds nothing to the cost of any group pays nothing — a user whose requirement is already met by everybody else’s. Additivity becomes the bill for two independent facilities is the sum of the two bills.

All four are as reasonable in this reading as in the other, and the uniqueness theorem applies verbatim. Nothing about the argument used the sign of the numbers.

One thing does change, and it changes direction rather than substance. A coalition in a gain game objects to receiving less than it could earn alone; a coalition in a cost game objects to paying more than it could pay alone. So every inequality defining the core, the nucleolus and the excess reverses.

That is why the figures in this essay use the orderings and the conditions and not the core views: those are written for a value shared out, and pointing them at a bill would draw the region on the wrong side of every line. The generator refuses them for this game and says so, which is the right behaviour for a family asked to draw something it was not written for.

What a different rule would give #

The division is one answer and it is worth seeing the alternatives on the same numbers, because the comparison is what an argument about a bill actually looks like.

For requirements of three, six and twelve, with a joint cost of twelve:

Equal shares is indefensible here and the reason is sharp: the smallest user pays four and would pay three alone, so that user is better off leaving. A division a party can improve on by walking away is not a division of a joint cost; it is a subsidy.

Proportional looks reasonable and undercharges the largest user. It charges nobody more than they would pay alone, so it survives the walking-away test — and it charges the smallest user $1\frac{5}{7}$ for a layer that costs three shared three ways, which is $1$. The extra is a subsidy to the largest user, hidden inside a rule everybody finds intuitive.

The average over orders is the one that makes each layer’s split explicit, and the reason it charges the largest user more is that the top layer is nobody else’s business.

That the two middle rows agree is not a coincidence: for this cost function, scaling stand-alone costs to the bill is proportional charging, because the stand-alone cost is the requirement.

The subadditivity that makes the question exist #

Nothing in this essay would be worth doing if the joint cost were the sum of the separate ones, and the property that makes it interesting has a name.

A cost function is subadditive when serving two disjoint groups together costs no more than serving them separately: $c(S \cup T) \le c(S) + c(T)$. The capacity game is subadditive, dramatically — serving all three costs twelve where separate service costs twenty-one — and the nine that is saved is what the division is about.

Subadditivity is the whole reason for a cooperative theory. If costs added, every user would pay their own and there would be no question; the saving is what has to be attributed, and there is no fact of the matter about whose it is until a rule is chosen.

The gain-side mirror image is superadditivity: a group earns at least what its parts earn separately. Every game on this ladder’s earlier rungs has it, and it is the standing assumption of the subject — the surplus over what the parts could manage is what a value divides.

The stronger property this family has is concavity, which is subadditivity applied at every scale: each additional user adds no more to a large group’s cost than to a small one’s. Concavity is what makes the value enforceable here, and it is much stronger than subadditivity — the glove game is superadditive and not convex, which is exactly why its value sits outside the core.

Does anybody actually accept it? #

A division nobody would accept is an arithmetic exercise, so it is worth asking whether the shares here can be enforced.

For this family, yes, and cleanly. No group of users pays more together than it would pay alone: the layers a group is charged for are exactly the layers below its own largest requirement, shared with others, so the group’s total is at most the cost of serving it alone. The division is in the core, always, for every set of requirements.

That is a much stronger position than the general case. The glove game is the standing example where the average over orders is outside the core and cannot be enforced. Here the two answers agree, and a split nobody can walk away from is the right frame for why: the reason is structural, and it is that the cost function is concave in the coalition — each additional user adds no more than they would have added to a smaller group — and for concave cost games the average over orders is always in the core.

So this family is the good case in every respect: the value has a closed form, it is in the core, and the closed form has an interpretation anybody can follow. That combination is rare and is why the family is the standard teaching example.

What the layers say that the average does not #

The closed form is worth more than its cheapness, because it makes the division defensible in a way the average is not.

A share is the average of what a user adds over every order of arrival is correct and is a hard sentence to accept from somebody presenting a bill. Everybody pays an equal share of the capacity everybody needs, and the extra capacity one user alone needs is theirs is the same number and is nearly self-evident.

That is a general point about characterisations. The value of a closed form is often rhetorical rather than computational: the same quantity, expressed so that its fairness is visible, is a different object in a negotiation. The layer form is why this family’s answer is used in practice and the general Shapley value mostly is not.

The layer reading also makes the comparisons obvious. The smallest user pays $c_1/n$, which is as little as any rule could charge; the largest pays everything above the second-largest requirement, which is as much as any rule could charge. Both extremes are forced, and everything between them is an equal split of a shared layer.

Where else the sign is turned over #

Three neighbours, all of them the same manoeuvre.

Dividing a saving rather than a cost. Given the separate costs and the joint cost, the saving is a gain game and can be divided by the same rule. The two divisions agree — sharing the bill by the value and sharing the saving by the value give the same final payments — which is a small theorem and a reassuring one.

Duality. What a constraint is worth is the shadow price of a resource in a linear programme, and it answers the same question from the other side: not what does each party owe, but what would one more unit be worth. The two are related and not the same, and the difference is that a shadow price is a derivative at the optimum while a value is an average over arrival orders; the two numbers that have to meet is the other half of that story.

Attribution. The prediction-attribution use the rung below describes is a cost game as often as a gain game, and the same sign symmetry applies. Nothing in the estimator cares.

What the picture cannot show #

The figure lists six orders for three users, which is the whole enumeration. At ten users it is three and a half million rows and the closed form is the only thing available — so the picture demonstrates the definition on a case where the closed form is not needed, and the closed form on a case where the definition suffices.

The layer figure shows the closed form agreeing with the average on one set of requirements, and the collapse is a claim about every set. The agreement is checked at every drawn placement rather than argued in general, which is the usual position: the identity is a short calculation and the figure is evidence that the calculation was done right.

And it cannot show that the division is in the core, which is the claim making it enforceable. That would need the core drawn for a cost game, with every inequality reversed — which the family refuses, deliberately, rather than reflecting a picture written for the other sign.

Where the ladder goes next #

This is the top of the ladder as it stands, and above it: cost games with more structure than a single largest requirement — trees, networks, sequences — each of which has its own closed form and its own interpretation; and the general theory of concave games, where the average over orders is always enforceable.

One debt. The theorem that a concave cost game’s value lies in the core is quoted and not proved. The figure checks it by exhaustion for the capacities it draws — every one of the seven coalitions is required to pay no more together than it would alone — which is a verification rather than a proof; the proof is short and is a genuinely satisfying use of the marginal vectors, since each of them is a vertex of the core and the value is their average.

What turning the sign over showed #

Dividing a bill and dividing a surplus are the same problem, and the same four conditions pick out the same rule.

What the cost reading adds is a family where the average collapses to something legible: layers of capacity, each shared equally among the users who need it. That the collapse happens at all is a fact about the cost function rather than about the rule — and it is worth looking for, because a closed form is not merely cheaper to compute than an average over $n!$ orders. It is easier to defend, and a division that cannot be defended is not a division anybody will accept.