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

If the core is nonempty, it is exactly the singleton allocation $p_j=v(\{j\})$ for every $j$. Take any $p$ in the core of a cooperative game and write $p(C)={\sum }_{j\in C}{p}_j$. Core membership gives efficiency of the imputation, $p(N)=v(N)$, and the coalition inequalitiesUsing the given complementary-coalition equality in this constant-sum cooperative game, the second inequality yieldsCombining upper and lower bounds gives $p(C)=v(C)$ for every coalition $C$. In particular,Since this holds for any core member and at least one exists by hypothesis, the displayed allocation is in the core and is its only member. The argument also shows why nonemptiness is restrictive: it forces $v(C)={\sum }_{j\in C}v(\{j\})$ for every coalition, so the characteristic function of a coalitional game must be additive. No superadditive coalitional game or monotonicity assumption is needed.

In an induced subgraph game, players are graph vertices and a coalition receives the sum of the weights of graph edges whose two endpoints lie in it. Therefore each two-player coalition determines the corresponding edge weight. For $G_1$ these weights would have to be $2,6,3$, making the grand coalition worth $2+6+3=11$, whereas its actual value is $15$. No other edge weights can repair that discrepancy without changing a two-player coalition's value. Even a convention allowing vertex weights would not help: its singleton values force all such weights to zero.

For $G_2$, the stated weighted graph triangle has grand coalition value $2+3+3=8$ and reproduces all three pair values. Empty and singleton coalitions contain no graph edges, so their values are zero. This verifies all eight coalitions and supplies the complete representation.

To compute the Shapley value, reveal players in a uniformly random permutation. An edge's weight contributes to an endpoint's marginal contribution precisely when the other endpoint appeared earlier. Each endpoint is later with probability $1/2$, independently of where the third player appears. Linearity of the expected value therefore splits each edge weight equally between its two endpoints:The values sum to $8=v_2(N)$, as required by the Shapley value's efficiency property. This is the general Shapley value of an induced subgraph game formula, not an assumption that all three players are symmetric: player $3$ has a different incident-weight total.

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.