Past exam of the MSc in advanced computer science course of the University of Oxford / 2021 / Computational game theory / 4 / c / i / Solution

The core is the singleton $\{(1/2,1/2,1/2,1/2)\}$. Here the characteristic function of a coalitional game is $v(C)=\lfloor |C|/2\rfloor$, the two-person instance of the core of the miners game calculation.

Let $x$ be in the core. Efficiency requires $x_1+x_2+x_3+x_4=2$, and every pair coalition requires $x_i+x_j\ge 1$. Summing the six pair inequalities counts each coordinate three times, giving $3{\sum }_i{x}_i\ge 6$. Efficiency makes this an equality; since every individual slack is nonnegative, all six pair inequalities must be equalities. In particular $x_1+x_2=x_1+x_3=x_1+x_4=1$ forces $x_2=x_3=x_4$, and comparison with $x_2+x_3=1$ gives every $x_i=1/2$.

Conversely, for the uniform allocation every coalition satisfiesand its total is $2=v(N)$. It is therefore a core member, completing both existence and uniqueness. In particular, a three-player coalition receives $3/2\ge 1$; the pair constraints are the tight ones.