= Shapley value of an airport game
{c}
{title2=$\phi_j=\lambda\sum_{i=1}^j\frac{s_i-s_{i-1}}{N_i}$}
Suppose the distinct required runway lengths are $0=s_0<s_1<\cdots<s_k$, with $n_i>0$ users of type $i$, constant cost $\lambda\geq0$ per unit length, and suffix counts $N_i=\sum_{\ell=i}^k n_\ell$. Then every type-$j$ user has the displayed <Shapley value>. For layer $i$, exactly $N_i$ users require it. The first of them in a uniformly random <permutation> contributes its entire cost $\lambda(s_i-s_{i-1})$. Each requiring user has <probability> $1/N_i$ of being first. <Linearity of the Shapley value> sums these expected <marginal contributions> across the layers that user needs.
The allocation lies in the cost <core>. Its payments sum to the full runway cost. For any <coalition> $S$, its total payment toward layer $i$ is $\lambda(s_i-s_{i-1})|S\cap R_i|/N_i$, where $R_i$ is the set of users requiring that layer. This is zero if $S$ needs no such layer, and at most the full layer cost otherwise. Summing gives $\sum_{j\in S}\phi_j\leq c(S)$. Suffix counts followed by prefix sums compute all distinct type payments in $O(k)$ arithmetic operations.
Back to article page
