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

Assume the standard empty-coalition normalization $v(\varnothing )=0$. A convex cooperative game has increasing marginal contributions: whenever $A\subseteq B$ and $i\notin B$,This follows from the supermodular inequality applied to $A\cup \{i\}$ and $B$. Fix a permutation $\pi$ of all players, let $P_i$ be the players preceding $i$, and form its marginal contribution vectorSumming along the full permutation is a telescoping sum, so ${\sum }_{i\in N}{m}_i^{\pi }=v(N)$. For an arbitrary coalition $S$, list its members in their induced order $i_1,\dots ,i_k$, and put $S_j=\{i_1,\dots ,i_j\}$. Since $S_{j-1}\subseteq P_{i_j}$, increasing marginal contributions giveThus every marginal contribution vector belongs to the core. The vector of Shapley values is exactly their uniform average over the $n!$ permutations, hence a convex combination. By the preceding part, that average is in the core. This proves that the Shapley value allocation belongs to the core of a convex cooperative game, including every coalition constraint. It is the result Shapley value belongs to the core of a convex game.