Given a coalitional form game (X, v) we seek to construct a value Φ(X, v) ∈ Rn for the game,
where the component Φi(X, v) denotes the payoff to player i. This can be interpreted as a measure
of the power of player i in the game, since it indicates their contribution to the grand coalition,
were one to form.
An example of such a value is the Shapley value, constructed as follows. Given a permutation
π ∈ Sn (i.e., a bijection from X to X) we can consider the players as forming the coalition one by
one, in accordance with the ordering created by π. Thus the coalition is built by considering first
the coalition consisting of Player π(1), then of players π(1) and π(2), and so on. By superadditivity,
the value at each step either increases or remains constant, so we may assign to each player a nonnegative
payoff equal to this increase. Let pi
π denote the set of players who joined the coalition
before Player i. Therefore piπ = {j|π(j) < π(i)}. Then the value of Player i to the coalition is given by v(piπ ∪ {i}) - v(pi
π).
However, it is unlikely that the payoff constructed in this way will be independent of the ordering
π. Thus we consider the value of a player to be their
average contribution to the formation of a
coalition; where any ordering of players is equally likely. That is,
Φi(X, v) =
(1/n!) ΣSn v(piπ ∪ {i}) - v(pi
π)
since the size of Sn is the number of permutations of the set of players X, namely n!, and for
any given permutation we may determine Player i's contribution by the method in the previous
paragraph.
Part of A survey of game theory- see project homenode for details and links to the print version.