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 = (x1, x2, ..., xn)
such that xi ≥ V({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.
No comments:
Post a Comment