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

Write $x(S)={\sum }_{i\in S}{x}_i$. The core of a cooperative game isTake any $x,y\in C(v)$ and $\alpha \in [0,1]$, and form the convex combination $z=\alpha x+(1-\alpha )y$. Its total payoff is $z(N)=\alpha v(N)+(1-\alpha )v(N)=v(N)$. For every coalition $S$,Hence $z$ remains in the core. The core is a convex set, even when the transferable utility game is not a convex cooperative game. An empty core is a convex set vacuously; the argument does not claim nonemptiness. Geometrically, the same conclusion follows because the constraints intersect an affine hyperplane with closed half-spaces.

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.

Yes. Use the simple cooperative game in which a coalition wins exactly when it contains at least two players. In every permutation, precisely the second arrival changes a losing coalition into a winning one. Each player is second in two of the six permutations, so each Shapley value is $2/6=1/3$. This constructs the required vector while verifying that singleton coalitions lose and the grand coalition wins.

No. In a simple cooperative game, a player's marginal contribution along any permutation is zero or one. With three players there are six equally likely permutations, so every Shapley value is an integer multiple of $1/6$, by the Shapley value denominator in a simple game. But $6(5/12)=5/2$ and $6(3/12)=3/2$ are not integers. The vector sums to one, but fails this necessary denominator condition.

Yes. Give players $1,2,3$ weights $1,1,2$, respectively, and let the quota be three. This weighted voting game is a simple cooperative game whose minimal winning coalitions are $\{1,3\}$ and $\{2,3\}$. In orders $123,132,213,231$, player 3 supplies the winning marginal contribution. In order $312$ player 1 does, and in order $321$ player 2 does. Averaging the six marginal contribution vectors gives exactly $(1/6,1/6,4/6)$ as the vector of Shapley values.

No. The denominator test from part ii is satisfied here, so a stronger obstruction is needed. Put $a_i=v(\{i\})$ and $b_{ij}=v(\{i,j\})$. In a three-player simple cooperative game, the Shapley value formula gives, for distinct $i,j,k$,Subtract the corresponding expression for ${\varphi }_j$:Each coalition value is zero or one, so this difference must be an integer multiple of $1/2$. This is the obstruction from pairwise Shapley differences in a three-player simple game. The proposed first two coordinates differ by $1/6$, which is not an integer multiple of $1/2$. Therefore the vector cannot occur, even though each coordinate separately passes the $1/6$ denominator test.