Following the observations made of the simple majority game, we now examine cooperative games, that is, ones in which players may enter into binding arrangements.
Each remains motivated by their individual utility payoff, and thus can be expected to only
enter an agreement that is personally beneficial to them. However, we will also allow for transferable
utility. That is, the participants in a coalition may redistribute the total return to the coalition
amongst themselves, rather than keeping to the individual returns prescribed by the game. In
effect, this allows for side payments from one player to another, to give the second an incentive
to join a coalition with the first. This, of course, assumes that the payoffs to each player are in
equivalent units, and represent a transferable commodity. In a genuine prisoner’s dilemma, for
instance, neither participant can accept jail time for the other; although mutual cooperation will
still arise as their best strategy.
We thus require two things: a rule for determining the return to any coalition; and a means to
decide which players will enter into the coalition. Broadly speaking, the payoffs to the coalitions
constitute the rules of the game, analogous to the payoff matrices/functions in strategic form games;
whilst the formation of coalitions represent the plays (strategies).
Definition: A finite n-player game in coalitional form (X, v) consists of the set of players X = {1, 2, . . . , n} and a characteristic function v : P(X) → R satisfying
- v(∅) = 0
- If S ∩ T = ∅ then v(S) + v(T) ≤ v(S ∪ T)
Here P(X) denotes the power set of X, that is, the set of all possible subsets, and thus the
characteristic function describes the payoff to any coalition that may form between the players.
Note that this is a set of size 2n. The first condition on v ensures that the empty coalition has no
value. This is a mathematical formality for later results, since a player cannot enter this coalition:
even if Player i shuns all the others, they will be in the coalition {i}. The second condition, known
as superadditivity, is considered a natual property: if two distinct coalitions work together, then
they should receive at least as much as they did by working independently.
It is an immediate consequence of the superadditivity that the greatest group return is achieved
by forming the grand coalition X consisting of all n players. However, it is not a given that the
grand coalition (or indeed any coalition) will form. Whilst v(X) ≥ v({i}), Player i would have to
be offered at least a return of v({i}) from the division of v(X) to be convinced to join. In particular,
if v({i}) < v(X)/n then the 'fair' payoff of equal distribution will not interest Player i. Thus the
determination of rules for allocation is not without subtlety.
Example Recall the Bimatrix game two finger morra. As a two player
game, there are four possible coalitions- ∅, {1}, {2} or {1, 2}. v(∅) = 0 is given, and since two finger
morra is zero-sum the value gives that v({1}) = 1/12 and v({2}) = -1/12. Interpreted directly,
v({1, 2}) is the total return to the coalition when, working together, the players are able to select
any entry in the bimatrix. Since the game is zero-sum, this is always zero (which can be verified
by inspection).
Notice that superadditivity holds, and the grand coalition offers a return of 0. Since Player 1
receives a payoff of 1/12 by not entering the grand coalition, Player 2 would have to offer a side
payment of at least 1/12 to entice Player 1 into a coalition. But it would be irrational for Player 2
to offer any more than 1/12 to create the coalition, since going it alone only costs him 1/12. Hence
the distribution within the grand coalition would be the same as if it did not form: players are
indifferent to the formation of a coalition, and the coalitional form precisely mimics the strategic
form. This motivates some additional definitions.
Definition: A game in coalitional form is said to be of constant-sum if v(S)+v(X\S) = v(X)
for all S ∈ P(X). If additionally v(X) = 0, the game is described instead as zero-sum.
Definition: A game in coalitional form is inessential if Σi v({i}) = v(X), where i runs from 1 to n. Otherwise, the
game is essential.
Example As a coalitional game, the Prisoner's dilemma as formulated in this series of writeups is given by v(∅) = 0, v({1}) = v({2}) = 1, v({1, 2}) = 6. Hence, the Prisoner's dilemma is an
essential coalitional game.
Corollary Any two person zero-sum game is inessential.
Part of A survey of game theory- see project homenode for details and links to the print version.