In this exercise, we present an algorithm for computing a solution concept. Given a coalitional game (N; v):
(a) Choose a coalition whose worth is not 0, and divide this worth equally among the members of the coalition (this is called the dividend given to the members of the coalition).
(b) Subtract the worth of this coalition from the worth of every coalition containing it, or equal to it. This defines a new coalitional function (where subtracting a negative number is understood to be equivalent to adding the absolute value of that number).
(c) Repeat this process until there are no more coalitions whose worth is not 0.
For example, consider the game (N; v) defined by the set of players N = {1, 2, 3}, and the coalitional function
v(1) = 6, v(2) = 12, v(3) = 18, v(1, 2) = 30, v(1, 3) = 60, v(2, 3) = 90, v(1, 2, 3) = 120.
The following table summarizes a stage of the algorithm in each row, and includes the coalitional function at the beginning of that stage, the chosen coalition (whose worth is not 0), and the payoff given to each player at that stage. The last line presents the sum total of all payoffs received by each player.
Prove the following claims:
(a) This process always terminates.
(b) The total payoffs received by the players are the Shapley value of the game (and are therefore independent of the order in which the coalitions are chosen).