Solution

ID: past-exam-of-the-msc-in-advanced-computer-science-course-of-the-university-of-oxford/2021/computational-game-theory/4/b/solution

cannot have an induced subgraph game representation. is represented by a weighted triangle with edge weights , , , and has Shapley value vector .
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 these weights would have to be , making the grand coalition worth , whereas its actual value is . 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 , the stated weighted graph triangle has grand coalition value 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 , 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 , 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 has a different incident-weight total.

New to topics? Read the docs here!