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 (*u*–*u**)(*v*–*v**) 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**= (*x*_{1},*x*_{2}, ...,*x*_{n}) such that*x*_{i}≥*V*({*i*}) for all*i*, and ∑*x*_{i}=*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.

## No comments:

## Post a Comment