TOC
1. Set up
In game theory, a cooperative game (or coalitional game) is a game with competition between groups of players (โcoalitionsโ) due to the possibility of external enforcement cooperative behavior (e.g. through contract law).
Those are opposed to non-cooperative games in which there is either no possibility to forge alliances or all agreements need to be self-enforcing (e.g. through credible threats).
Given a set of agents, a coalitional game defines how well each group (or coalition) of agents can do for itself. We are not concerned with how the agents make individual choices within a coalition or how they coordinate. Instead, we take the payoffs to a coalition as given.
- Traditional non-cooperative game theory: focuses on predicting individual playersโ actions and payoffs and analyzing equilibria.
- Cooperative game theory: focuses on predicting which coalitions will form, the joint actions that groups take and the resulting collective payoffs.
1.1 Coalitional Game
A coalitional game with transferable payoff (henceforth โcoalitional gameโ) consists of
- a finite set of players
- a function with
Every subset of is called a coalition, and is called the worth of the coalition . The function is called the characteristic function.
Note that is a payoff that may be distributed in any way among the members of .
Convention: if is a coalition, we will write
There are two questions to be solved:
- Which coalition will form
- How should that coalition divide its payoff among its members in order to be fair, stable, etc.
Super-additivity
A coalitional game is super-additive if
Super-additivity is justified when coalitions can always work without interfering with one another.
- The value of two coalitions will be no less than the sum of their individual values.
- It implies that the grand coalition (all agents in ) has the highest payoff.
Assumption: The coalitional games are super-additive.
A coalitional game is
- monotonic if implies
- cohesive if
for every partition of ;
Super-additive โ Monotonic and Cohesive.
2. Shapley Value
2.1 Definition & Properties
Shapleyโs idea: Members should receive payments or shares proportional to their marginal contributions.
Substitutes and Null Player
Two players and are substitutes in if for all containing neither or ,
Player is called a null player if
for all .
Shapley Value
Given a coalitional game where , the Shapley value is an -vector, denoted by
satisfying the following coditions:
- Symmetry condition: if and are substitutes in , then
- Substitutable agents should receive the same shares/payments
- Null player condition: if is a null player, then
- Null players should receive nothing
- Efficiency condition:
- Additicity condtion:
- If we can separate a game into two parts , then we should be able to decompose the payments
is interpreted as the power of player in the coalitional game , or what it is worth to to participate in the game .
Shapley Theorem
Shapley value is uniquely determined: (definition)
Let , then we have
Interpretation
Imagine the coalition being formed one player at a time, with each player demanding their contribution as a fair compensation. Then for each player take the average of this contribution over the possible different permutations in which the coalition can be formed.
2.2 Examples
Example: Two-person bargaining game
Since , we have .
For player 1, we have
Hence,
For player 2, we have
Hence,
For player 2, we can get by efficiency condition directly. Actually, 1 and 2 are substitutes, so .
Example: Three-person majority game
.
Since , we have , and .
For player 1, we have
Hence,
For player 2, we have
Hence,
For player 3, we can get by efficiency condition directly. Actually, 1, 2 and 3 are pairwisely substitutes, so .
Example: Market with two sellers and one buyer
, and for all other .
Since , we have , and .
For player 1, we have
Hence, .
For player 2, we have
Hence, .
For player 3, we can get by efficiency condition directly.
3. Core
3.1 Definition & Properties
The Shapley value defines a fair way of dividing the grand coalitionโs payment among its members. However, this analysis ignored questions of stability. That is, whether the agents will be willing to form the grand coalition given the way it will divide payments or they will prefer to form smaller coalitions. Actually, sometimes smaller coalitions can be more attractive for subsets of the agents, even if they lead to lower value overall.
Motivating example
A parliament is made up of four political parties, A, B, C, D, which have 45, 25, 15, and 15 representatives respectively. They are to vote on whether to pass a $100 million spending bill and how much of this amount should be controlled by each of the parties. A majority vote, that is, a minimum of 51 votes, is required in order to pass any legislation, and if the bill does not pass then every party gets zero to spend.
Shapley values: . While A cannot obtain more than 50 on its own, A and B have incentive to defect and divide the $100 million between them (e.g. ).
Definition
The core is a solution concept for coalitional games that requires that no set of players be able to break away and take joint action that makes all of them better off.
Let be a coalitional game, A vector of real numbers is an -feasible payoff vector if
We refer to an -feasible payoff vector as a feasible payoff profile.
The core of the coalitional game is the set of feasible payoff profiles for which there is no coalition and -feasible payoff vector for which for all .
Analogous to NE, except that it allows deviations by groups of agents.
Property
If is the core, then satisfies ()
- (individual rational) for all
- (group rational)
- is the set of feasible payoff profiles for which
for every coalition .
Proof of :
Suppose that satisfies
Assume is not in the core, that is, there exist a coalition and , such that
Then we have
โ contradiction
Proof of :
Suppose that does not satisfy
If , cannot be in the core.
Suppose, there is a coalition such that
where . For each , define
It is easily seen that and for all . Hence is not in the core.
The core is the set of payoff profiles satisfying a system of weak linear inequalities and hence is closed and convex.
3.2 Examples
Example: Two-person bargaining game
and .
is in the core iff: and .
Example: Three-person bargaining game
, and for all .
is in the core iff
The core is therefore the set
Example: Market with two sellers and a buyer
, and for all other .
is in the core iff
Hence the core is
Note the core allocation in this example differs considerably from the Shapley value . One can interpret that zero payoff to players 2 and 3 in the core allocation as the result of cutthroat competition between them.
Example: Three-person majority game
Suppose that three players can obtain one unit of payoff, any two of them can obtain 1 independently of the actions of the third, and each player alone can obtain nothing, independently of the actions of the remaining two players.
and for all .
For to be in the core, we need for all , and . There exists no satisfying these condition, so the core is empty.
Example: A majority game
A group of players, where is odd, has one unit to divide among its members. A coalition consisting of a majority of the players can divide the unit among its members as its wishes.
This situation is modeled by the coalitional game in which and
The game has an empty core by the following argument
- Assume that is in the core. If then so that . Since there are coalitions of size , we have
- On the other hand, we have
thus there is a contradiction.
3.3 Nonemptyness of Core
Denote by the set of all coalitions. Denote by the characteristic vector of is given by
The function is a bi-jection.
Balanced collection of weights
A collection of numbers in is a balanced collection of weights if for every player the sum of over all the coalitions that contain is 1:
Example 1: the collection in which and for all other is a balanced collection of weights.
Example 2: let , the collection in which if and otherwise is a balanced collection of weights:
So is the collection in which if and otherwise:
Balanced Game
A game is balanced if
for every balanced collection of weights.
Interpretation: each player has one unit of time, which he must distribute among all the coalitions of which he is a member. In order for a coalition to be active for the fraction of time , all its members must be active in for this fraction of time, in which case the coalition yields the payoff .
The condition is a feasibility condition: For every individual, the sum of its amounts of his time he spends with each coalition must equal exactly the amount of time he is endowed with. A game is balanced if there is no feasible allocation of time that yields the players more than .
Bondareva-Shapley theorem
A coalitional game has a non-empty core iff it is balanced.
Core v.s. Shapley Value
Core: based on coalitional threats โ each coalition must get at least what it can generate alone.
Shapley value: based on marginal contributions โ what does each player contribute to each possible coalition.
Loading Comments...