Multiplayer cooperative games

From Simulace.info
Jump to: navigation, search

A multiplayer cooperative game, used in game theory, can be explained by distinguishing the words of the term. It’s a sort of a multiplayer game, which means that there are several players involved in the game, who may be independent opponents or teams. A cooperative game, also called a coalitional game or games with transferable utility, is a game in which external maintenance of cooperative behaviour makes it possible for the coalitions or groups of players to interact competitive. In general, multiplayer cooperative games are analysed in the field of cooperative game theory, which studies building and interactions of the groups.

Game theory

The framework of cooperative game theory focuses especially on 3 main themes. First of all it starts with predicting which teams the players will form which can be supported by the possibility of enforcing external behaviour, for example through contract law. In case of contract law is the agreement bound by law, but the agreement is voluntary arranged between the two or more parties. Secondly, after predicting the groups, we try to predict the actions they will take. The third and last prediction in the cooperative game is about the results and payoffs of the coalitions.

In general, we often analyse the cooperative games by approaching the non-cooperative game theory, which is much more used. In those games there is no possibility to form coalitions or the agreements need to be self-enforcing agreements, which means that the agreement only applies between the involved parties, there is no possibility for a third party to interfere. Nash equilibrium is the most common kind of a self-enforcing agreement and localizing these equilibriums, besides predicting actions and payoffs of individual players, is the main activity of non-cooperative games. Important to know is that approaching cooperative games by non-cooperative games is very common, but the converse isn’t possible. So this approach only holds in one direction. This is due to the subjects descript during the cooperative game: strategy, structure and payoffs of the groups. In a non-cooperative game the effects on the distribution of the payoffs within each group by the negotiating procedures is added. This makes the cooperative game a high-level approach, and the non-cooperative game not.

Solving cooperative games by the approach of non-cooperative is only possible if we make assumptions about the bargaining powers. These assumptions comprehend all the possible strategies made by the external compelling of cooperation. Insufficient availability of information or highly complex situations in the real world makes this approach too difficult to apply, which is where the cooperative game theory provides tools to solve the game.

In game theory, multiplayer cooperative games apply both zero-sum as non-zero-sum games.

Definition

Notations

There is a finite set of players: N = {1,...,n}, 2. There is a characteristic function that indicates what each coalition S of players can get (it is the sum of utilities of players in the coalition). Formally, the characteristic function is a function:

v : 2^N → ℜ+ .

This means that in general, in a game with N players, there are 2^N coalitions.

As usual in a multiplayer cooperative game, we assume that players within the same group may arrange to compensate each other through payments, we call that transferable utility. Superadditivity could be the case, in which the characteristic function is as follows:

If S1 ∩ S2 = ∅, then v(S1 ) + v(S2) ≤ v (S1 ∪ S2 ) .

The interpretation of v(S) is the amount of money or utility that the coalition can divide between its members. We also assume no externalities: for players that remain after forming groups, it is indifferent whether members of coalitions S1 and S2 group into a coalition S1 ∪ S2 or not. We can also have a look at the payoff of coalition S1 : it is v(S1), independently of which other coalitions form.

Example

Consider a coalition S = {P1,P3}, then is the counter coalition Sc = {P2}. Coalition S has four pure joint strategies : {(1, 1),(1, 2),(2, 1),(2, 2)}. For Sc, the strategies are 1 and 2. The bi-matrix is:

Table1.jpg

The maximum value for the coalition is called the characteristic function of S and it is denoted as v(S). In other words, members of S are guaranteed to gain a total payoff of at least v(S). Let us consider for S, pure joint strategy (1,2) is dominated by (1,1), pure joint strategy (2,2) is dominated by (2,1). We have

Table2.jpg

We solve this by approaching with the non-cooperative theory. Then we have v(S) = 4/3 and v(Sc) = -1/3. If we compute this in a similar way, we get ν({P1,P2}) = 1, ν({P3}) = 0, ν({P2,P3}) = 3/4, ν({P1}) = 1/4. The characteristic function for the grand coalition is simply the largest total payoff which the set of all players can achieve, it is easily seen that ν(P) = 1. Finally, by definition, the characteristic function of empty coalition is ν(∅) = 0.

Now we have to interpret these results to completely understand the cooperative game. By examining the characteristic function, we can speculate which coalitions are likely to form. Since P1 does better playing on his own than P2 or P3 playing on their own, P2 and P3 would bid against each other to try to entice P1 into a coalition. In exchange, P1 would demand a larger share of the total payoff to the coalition he joins and he would ask for more than 1/4 since he get that much on his own. On the other hand, if P1 demands too much, P2 and P3 might join together, excluding P1 and gain a total of 3/4.

Properties for characterization

Superadditivity

The value of a union of disjoint groups is no less than the sum of the groups’ separate values:

v(S ∪ T)>= v(S) + v(T) whenever S,T ⊆N satisfy S ∩ T .

This theorem states that “in union, there is strength”. The disjoint coalitions are S and T. We can now proof that since each player uses the maximum solution method , a coalition guarantees that each player gain at least as much as if they do not form a coalition.

Resulting, if S1,…,Sk are pairwise disjoint coalitions (with k = number of coalitions), then

Table3.jpg

For any N-person game, v(P) ≥ (SUM) v ({Pi}).

A game in characteristic function form consists of a set P = {P1, . . . ,PN} of players, together with a function v, defined for all subsets of P, such that ν(∅) = 0, and such that the superadditivity holds, that is:

ν(S ∪ T ) ≥ ν(S) + ν(T ),

whenever S and T are disjoint coalitions of the players. An N−person game ν in characteristic function form is said to be inessential if v(P) = (SUM) v ({Pi}). In other words, if it is an inessential game, there is no point to form a coalition.

Example

The determinant is superadditive for nonnegative Hermitan matrices, for example if

A, B, element of Matn (C), matrix of the complex numbers, are nonnegative Hermitian, then det (A + B ) >= det (A) + det (B). this follows from the Minkowski determinant theorem.

Cohesiveness

A coalitional game <N,v> with transferable payoff is cohesive if we have

Table9.jpg

for very partition {S1, ..., SK} of N. Note: cohesiveness is a special case of the stronger assumption stated above, superadditivity. Cohesiveness guarantees that the equilibrium coalition is the one that should form. The worth of other coalitions will influence how v(N) will be divided among the players.

Monotonicity

Following from superadditivity, there is monotonicity: bigger groups gain more,

Table5.jpg

Solution concepts

Different solution concepts based on different notions of fairness are possible. Features we have to look for are the following:

-) Efficiency

-) Existence: the solution has to exist

-) Uniqueness: the solution has to be unique

-) Symmetry: the solution concept x allocates equal payments xi = xj to symmetric players i,j.

That is, we can exchange one player for the other in any coalition that contains only one of the players and not change the payoff.

-) Additivity: The allocation to a player in a sum of two games is the sum of the allocations to the player in each individual game.


The core

Definition

The core of a coalitional game with transferable payoff < N, v > is the set of feasible payoff profiles (xi) i∈N for which there is no coalition S and S-feasible payoff vector (yi)∈S such that yi > xi holds for all i ∈ S. For games with transferable payoff, the core is the set of feasible payoff profiles such that v(s) ≤ x(S) holds for all coalitions, S ⊆ N. Thus the core is the set of points in payoff space that satisfies a finite number of linear inequalities. The core is a closed, convex set.

Mathematical notation

The core of a game :

Table11.jpg

In words: the core is an allocation (x1 ,..., xn) , where xi is the payoff for player i, of total surplus v(N) , that satisfies:

1) It is feasible, ∑ xi ≤ v(N) .

2) A set of players S obtain at least what they would obtain forming a coalition S,∀ S , ∑i ∈S xi≥ v(S) (otherwise they would not accept the allocation and would blockade its formation).

Properties

-) The core of a game may be empty (see the Bondareva–Shapley theorem). Games with non-empty cores are called balanced.

-) If it is non-empty, the core does not necessarily contain a unique vector.

-) The core is contained in any stable set, and if the core is stable it is the unique stable set; see (Driessen 1988) for a proof.

Example

We describe the example of a three player majority game, so a typical multiplayer cooperative game.

Three players together can obtain $1 to share, any two players can obtain α, and one player by herself can obtain zero. Then v(N)=1, v({1, 2}) = v({1, 3}) = v({2, 3}) = α, v({1}) = v({2}) = v({3}) = v(∅)=0.

The core of this game is :

{(x1, x2, x3) ∈ R3+ : x1 + x2 ≥ α, x1 + x3 ≥ α, and x2 + x3 ≥ α}

If α > 2/3, the core is empty. If α = 2/3, the core is the single point, (1/3, 1/3, 1/3). If α < 2/3, the core has a continuum of points.

The Shapley Value

The Shapley value is the unique payoff vector that is efficient, symmetric, additive, and assigns zero payoffs to dummy players. It was introduced by Lloyd Shapley (Shapley 1953). The Shapley value of a superadditive game is individually rational, but this is not true in general.

Others

Other solution concepts are less used, but still worth to mention:

-) the stable set

-) the kernel

-) the nucleolus

References

https://en.wikipedia.org/wiki/Contract

https://en.wikipedia.org/wiki/Superadditivity

https://en.wikipedia.org/wiki/Cooperative_game_theory#

https://en.wikipedia.org/wiki/Multiplayer_game

http://www.uib.cat/depart/deeweb/pdi/hdeelbm0/arxius_decisions_and_games/Cooperative_game_theory.pdf

http://www.econ.ohio-state.edu/jpeck/gametheory/gameL10.pdf

http://www.cse.cuhk.edu.hk/~cslui/CSC6480/cooperative_game.pdf