Past exam of the mathematics course of the University of Cambridge / 2010 / iii / Paper 35 / 5

A coalitional game with transferable utility has a finite player set $N$ and a characteristic function of a coalitional game $v:2^N\to \mathbb{R}$, normalized by $v(\varnothing )=0$. The value $v(S)$ is the total payoff the coalition $S$ can secure and redistribute among its members.

An imputation is an efficient, individually rational payoff vector:The core of a cooperative game consists of imputations satisfying every coalition constraint:A coalition assigned less than its characteristic value can leave and make every member better off, by sharing the positive surplus. Conversely a coalition with no such surplus cannot improve every member's payoff simultaneously. This explains the stability represented by the core of a cooperative game.

It is useful to prove the general core of the miners game calculation when $r$ miners carry one unit: $v(S)=\lfloor |S|/r\rfloor$, with $r\ge 2$. Individual rationality gives $x_i\ge 0$, and efficiency gives ${\sum }_i{x}_i=q:=\lfloor n/r\rfloor$.

If $n<r$, the grand coalition value is zero and the only core allocation is zero. If $n\ge r$, every $r$-person coalition must receive at least one. Sum these inequalities over all $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$ such coalitions. Each player appears $\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)$ times, soIf $r$ does not divide $n$, then $rq<n$, a contradiction. Thus the core of a cooperative game is empty in these cases.

If $n=r$, every proper coalition has value zero. The core is exactly the simplex of nonnegative allocations with total one. If $n$ is a multiple of $r$ with $n\ge 2r$, the averaged inequality is equality. Since each $r$-person coalition sum is at least one, every such sum equals one. For any two players $i,j$, choose $r-1$ other players and compare the two resulting $r$-person coalition sums. They imply $x_i=x_j$. Hence $x_i=1/r$ for all players. This vector belongs to the core because $|S|/r\ge \lfloor |S|/r\rfloor$ for every coalition.

For two miners per lump, therefore,In particular the even case has a small-group exception at $n=2$.

For three miners per lump, the same proof givesThus divisibility controls the existence of a stable allocation once enough miners are present, while exactly one possible lump leaves freedom to divide its value.

Let $L$ be the set of left-shoe owners and $R$ the right-shoe owners. This is the glove game with pair price ten, so its characteristic function of a coalitional game isAll singleton values are zero. Write ${\ell }_i\ge 0$ for left-owner payoffs and $r_j\ge 0$ for right-owner payoffs. Efficiency gives total $10\min (a,b)$, and each mixed pair imposes ${\ell }_i+r_j\ge 10$.

Suppose $a<b$. Removing any right owner leaves at least $a$ right shoes, so the complement coalition still has value $10a$. Its core inequality and efficiency imply $r_j\le 0$. Thus every right owner receives zero. The pair constraints then force ${\ell }_i\ge 10$, and their total is $10a$, so every left owner receives ten. Conversely this allocation gives each coalition $10|S\cap L|$, at least its value, so it is in the core. The argument is symmetric when $a>b$.

When $a=b=k$, sum all $k^2$ mixed-pair inequalities. Their total left side is $k$ times the grand-coalition payoff, namely $10k^2$. Hence every inequality is equality: ${\ell }_i+r_j=10$ for every pair. Fixing one right owner shows all left payoffs are the same $\theta$, and fixing one left owner shows all right payoffs are $10-\theta$. Individual rationality gives $0\le \theta \le 10$. Such allocations are sufficient: for a coalition with $u$ left owners and $v$ right owners,as is seen by subtracting the right side and factoring either $\theta (u-v)$ or $(10-\theta )(v-u)$.

The core of a glove game is thereforePayoffs are in pounds. The parameter in the balanced case is common to all owners of a given shoe type.