Past exam of the computer science course of the University of Oxford / 2018 / Computational game theory / 3

For an $n$-player transferable utility game with $v(\varnothing )=0$, the Shapley value isIt averages player $i$'s marginal contribution over uniformly random orders of all players. Exactly $|S|!(n-|S|-1)!$ of the $n!$ permutations put precisely $S$ before $i$. For a cooperative cost game, apply the same linear formula to the cost function; the result represents payments instead of distributed benefits.

Take three players and define the simple cooperative gameIt is a superadditive coalitional game: two disjoint coalitions cannot both have value one because each would need player 1. If one has value one, their union does too; if neither does, the desired inequality is immediate.

The vector $(1,0,0)$ belongs to the core of a cooperative game. More strongly, it is the unique core vector: singleton constraints give nonnegative coordinates, efficiency gives sum one, and the value-one coalitions $\{1,2\}$ and $\{1,3\}$ force $x_3=x_2=0$.

In a random player ordering, player 1 is pivotal unless it comes first, giving Shapley value $2/3$. Player 2 is pivotal only in order $1,2,3$, and player 3 only in order $1,3,2$. ThusThe coalition $\{1,2\}$ receives only $5/6<1$, so the Shapley value is outside the core. This proves that superadditivity and nonempty core do not imply Shapley stability.

Put $c(\varnothing )=0$. For nonempty coalitions, the runway required by a union is the longer of the two required runways, soThe inequality uses nonnegative costs and also holds when either coalition is empty. Thus the cost function is subadditive, in particular for the stated disjoint coalitions. A subadditive cost game becomes a superadditive coalitional game after changing signs to $v=-c$.

Choose one plane requiring the longest runway and assign it the entire cost $c(N)$; assign every other plane zero. These nonnegative payments sum to $c(N)$. Any coalition containing that chosen plane also requires the whole longest runway, so its payment is exactly its standalone cost. Any coalition without it pays zero, which is at most its nonnegative standalone cost.

Hence this payment vector is in the cost core, proving the desired sharing always exists. This is an existence certificate, not a fairness assertion. If there are no planes, the empty allocation has total zero. The Shapley value of an airport game gives a more symmetric sharing rule and also lies in the core of this cooperative cost game.

Decompose the required runway into successive layers. The first layer has cost $s$ and is needed by all four planes. The next costs $2s$ and is needed by the three medium-or-long planes. The final layer costs $4s$ and is needed only by the longest plane.

For each layer, the first requiring plane in a uniformly random ordering contributes its entire cost. Each of its requiring planes has equal probability of being first. By linearity of the Shapley value, divide each layer cost equally among those requiring it. The payments are thereforeThey sum to $7s=c(N)$. The equality of the two medium payments follows from their identical runway requirements; the random-order argument proves the amounts, not just their equality.

Remove any plane types with zero count, retaining the increasing order of the remaining lengths; if none remain, return the empty allocation. For the retained types put $s_0=0$ and $N_i={\sum }_{\ell =i}^k{n}_{\ell }$. Then every plane of type $j$ has Shapley valueCompute suffix counts $N_i$ in a backward pass. In a forward pass, accumulate $A\leftarrow A+\lambda (s_i-s_{i-1})/N_i$ and output $A$ as the common payment for type $i$.

For correctness, layer $i$ costs $\lambda (s_i-s_{i-1})$ and is required by exactly $N_i$ planes. A particular requiring plane is earliest among these in a random ordering with probability $1/N_i$. Its expected marginal contribution to the layer is therefore that layer's cost divided by $N_i$. Summing the layers it requires proves the formula. This is the Shapley value of an airport game.

The two passes use $O(k)$ arithmetic operations. If every individual payment must be explicitly listed, add the unavoidable $O(|N|)$ output work. For counts given in binary, the compact per-type output is polynomial in the input size; expanding an exponentially large number of identical entries need not be. With integer lengths and rational $\lambda$, all fractions can be computed exactly with polynomial bit complexity: a common denominator divides a product of at most $k$ suffix counts, whose bit length is $O(k\log |N|)$, in addition to the input denominator of $\lambda$. For arbitrary real $\lambda$, the same rational factors give symbolic multiples of it.