Sunday, September 15, 2013

97. Cooperative Games

When the number of players in a game is large, the available information is usually inadequate for either an extensive-form approach or a strategic-form approach for analysis. In a many-player scenario, the players are likely to form coalitions for mutual benefit. So the notion of strategies of individual players is replaced by that of coalitions, and payoffs are replaced by the value of the coalition: It is expected that the coalition can guarantee its members a certain amount of benefit, called the value of the coalition.

In a coalitional form of a game, the process by which the coalition forms is not specified. For example, the players may be a number of parties in parliament. Each party has a strength determined by the number of seats it has in the parliament. The game describes which coalitions of parties can form a majority, but does not specify, for example, the negotiation process through which an agreement to vote en bloc is achieved.

Coalitional game theory is a subset of cooperative game theory, with transferable utility. There is a grand coalition involving all the members of the coalition, with some rule(s) for distribution among members the total payoff received by the grand coalition. For example, in the context of an economy, there is the important notion of the core of the economy. It is a set of payoffs to the players such that each coalition (as a part of the grand coalition) receives at least its value. There are principles that can result in a unique distribution of the payoff from the grand coalition.

Let us consider two-player cooperative games first. Let us plot along the x-axis the payoffs to player 1, and along the y-axis the payoffs to player 2. One can represent all the possible payoffs to the players by a subset S of points in the xy-plane. A popular theoretical model assumes that there is a special point (u*, v*) in the subset S, called the conflict point. If the two players cooperate, they can reach a fair point (u-, v-) in S as a mutually acceptable solution, but if they fail to agree they must receive the conflict-point payoff (u*, v*) (Owen1995).

Several axiomatic solutions to this problem have been suggested. Nash’s (1950, 1953) axioms for (u-, v-) were that:

1. It must lie in the feasible set S.
2. It must be Pareto-optimal, meaning that there can be no point in S that is better for both players.
3. It must be independent of irrelevant alternatives. This means that the elimination of a less desirable alternative cannot change the solution of the problem.
4. It must be covariant with linear changes of the utility scale. There are two kinds of cooperative games. The game may have transferable utility, or it may have non-transferable utility. Transferable utility is relevant when the players measure utility of the payoff in the same units and there is a means of exchange of utility, such as side payments.
5. It must be at least as symmetric as the set (S, u*, v*).

It was shown that, with these axioms, (u-, v-) is necessarily that feasible point (u, v) for which the product (uu*)(vv*) of the increment in utilities is a maximum, subject to u ≥ u*, v ≥ v*.

For n-player cooperative games, coalitions are usually the focus of attention, as also the bargaining within the coalitions. Such games are normally investigated in the characteristic function form. This function plays a role equivalent to that played by the payoff matrix in the characteristic form of games.

A coalition can be any nonempty subset S of the set N. The characteristic function V of the game is defined as one which assigns to each coalition S the set of outcomes that the members of that coalition can obtain by coming together, even against the concerted action of other players. If it can be assumed that the utility is transferable among members of a coalition, then V(S) is the maximum amount of utility that the coalition S can obtain and then distribute among its members.

An imputation is a vector x = (x1, x2, ..., xn) such that xiV({i}) for all i, and ∑xi = V(N). An imputation is an individually rational way of dividing the utility V(N).

Given two imputations x and y, x is said to dominate y if there is some coalition S which prefers x and is strong enough to enforce x.

In plural games the main problem is to choose some reasonable set of outcomes, preferably a unique outcome, from the set of all imputations. Stability and fairness are two possible criteria for making the choices.

The core

One can look for the set of all undominated imputations. This set is known as the core. It is somewhat like the competitive equilibrium of classical economic theory, and illustrates countervailing power.

The stable set

The core may not always be nonempty. von Neumann and Morgenstern (1944) therefore introduced the notion of stable sets. A set of imputations is said to be internally stable if no imputation in the set dominates another. A set is externally stable if any imputation not in the set is dominated by some imputation in the set. A stable set, also called a solution, is any set which is both internally and externally stable. This solution illustrates a form of social stability.

The value

The value form of solution illustrates fair division. It is a single-point solution for which one considers the combinatorics of all possible ways in which an individual could join a coalition of any size. We calculate the marginal worth of his contribution to any coalition, and then average over all the contributions. A value or expected worth is assigned to every player. Shapley (1953) stated four axioms for calculating the value, and derived an equation for the expected value, or power index.

1. Symmetry. If two players make the same contribution when any of them joins any coalition, they each obtain the same value.
2. Dummy player. The value of a player is zero if he contributes nothing, no matter which coalition he joins.
3. Efficiency. The sum of the values assigned to all the players is equal to the available utility V(N); no less, no more.
4. Additivity. If two separate games are considered jointly as if it is a single game, the values in the joint single game are simply the sums of the values in the separate games.

The Shapley power index has been used for analyzing power in voting situations.

The bargaining set

In a cooperative game, bargaining is involved for sharing the rewards of success. Consider a pair of players i, j in the game. A bargaining point is an imputation with the property that any objection that might be raised by i against j can be met by a counter-objection by j against i.

An objection consists of a coalition S including i but not j, and an imputation feasible for S that is preferred to the given imputation by every member of S.

A counter-objection consists of a different coalition T including j but not i, and an imputation that is weakly preferred to the objection of every member of T also in S, and is weakly preferred to the original imputation by every member of T not in S.

The bargaining set consists of those imputations such that to every objection there is a counter-objection.

Enough of formal game theory. From the next post onwards, I shall discuss coevolution of species, and the emergence of evolutionarily stable strategies, using the jargon of game theory where necessary.