display | more...

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.

Log in or register to write something here or to contact authors.