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

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.

The core is empty. Efficiency would require $x_1+x_2+x_3=v(N)=1$. Each two-player coalition has value $1$, so core membership would also requireAdding gives $2(x_1+x_2+x_3)\ge 3$, contradicting efficiency, which makes the left side $2$. Thus no allocation can meet all coalition demands. The obstruction uses only pair coalitions and the grand coalition; imposing individual rationality cannot remove it. The equal allocation $(1/3,1/3,1/3)$ is efficient but gives each pair only $2/3<1$, so symmetry does not supply a core allocation.