Past exam of the mathematics course of the University of Cambridge / 2007 / iii / Paper 40 / 4

In a transferable utility game, the characteristic function of a coalitional game assigns each coalition $S$ the total payoff $v(S)$ that its members can attain or guarantee together, normalized by $v(\varnothing )=0$. If disjoint coalitions $S,T$ can combine their separate strategies without interference, their union can secure both payoffs, givingThis is a superadditive coalitional game. The pooling assumption explains the intended assertion, but superadditivity is not automatic for an abstract characteristic function: the two-player values $v(\{1\})=v(\{2\})=v(\{1,2\})=1$, with empty value zero, are a counterexample. Thus the word “always” requires either that pooling assumption or a definition restricting the class of games to superadditive ones.

For the given bankruptcy game, the total deficit is $19-15=4$, so the coalition value is $({\sum }_{i\in S}{c}_i-4{)}_{+}$. Its computed values areIt is indeed superadditive: for disjoint claim sums $p,q\ge 0$, $(p+q-4{)}_{+}\ge (p-4{)}_{+}+(q-4{)}_{+}$. If both right-hand terms are positive the difference is $4$; if only one is positive, adding the other claim sum cannot reduce the value; if neither is positive the right side is zero.

A payoff allocation is Pareto efficient if no feasible allocation weakly increases every player's payoff and strictly increases at least one. Here feasibility requires total payment at most the available estate. The proposed payments haveAny such improvement would have total payment greater than $15$, which is impossible. Each payment is also between zero and its claim, and exceeds its singleton coalition value. Hence the allocation is an imputation and

The Shapley value is the expected marginal contribution of a player when the players join in uniformly random order. Equivalently,For three players, the weights for predecessor sets of sizes $0,1,2$ are $1/3,1/6,1/3$. Using the computed values,Thus

For an imputation $y$, the excess of a coalition is $e(S,y)=v(S)-{\sum }_{i\in S}{y}_i$. Arrange these excesses in decreasing order. The nucleolus is the imputation that lexicographically minimizes this ordered vector: minimize the largest complaint first, then the next largest among ties, and so on. The empty and grand-coalition excesses are fixed at zero for every efficient allocation, so they can be omitted without changing the lexicographic comparison.

For every efficient $y$ the three pair excesses have sumHence at least one pair has excess at least $-4/3$, and the largest proper-coalition excess is at least $-4/3$. At the proposed allocation all three pair excesses equal $-4/3$, while all three singleton excesses equal $-8/3$. It therefore attains the best possible largest proper-coalition excess.

Moreover, any allocation attaining this bound must have all three pair excesses equal $-4/3$, since they are individually at most that value and sum to $-4$. This forceswhose unique solution is $y=x$. It is already an imputation, so the first nonconstant lexicographic stage has a unique minimizer; there are no later choices to resolve. Therefore

The core of a cooperative game consists of efficient allocations satisfying ${\sum }_{i\in S}{x}_i\ge v(S)$ for every coalition, so no coalition can obtain a greater total payoff by leaving. Efficiency has already been checked. For singletons,For pairs,The empty constraint is automatic and the grand constraint is equality. Thus every core inequality holds andAll four assertions about this allocation are true, although their definitions impose different requirements.