Cooperative game theory

In game theory, a cooperative game (or coalitional game) is a game with groups of players who form binding “coalitions” with external enforcement of cooperative behavior (e.g. through contract law). This is different from 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).
Cooperative games are analysed by focusing on coalitions that can be formed, and the joint actions that groups can take and the resulting collective payoffs.
A cooperative game is given by specifying a value for every coalition. Formally, the coalitional game consists of a finite set of players N {\displaystyle N} , called the grand coalition, and a characteristic function v : 2 N → R {\displaystyle v:2^{N}\to \mathbb {R} } from the set of all possible coalitions of players to a set of payments that satisfies v ( ∅ ) = 0 {\displaystyle v(\emptyset )=0} . The function describes how much collective payoff a set of players can gain by forming a coalition.
Cooperative game theory is a branch of game theory that deals with the study of games where players can form coalitions, cooperate with one another, and make binding agreements. The theory offers mathematical methods for analysing scenarios in which two or more players are required to make choices that will affect other players wellbeing.
Common interests: In cooperative games, players share a common interest in achieving a specific goal or outcome. The players must identify and agree on a common interest to establish the foundation and reasoning for cooperation. Once the players have a clear understanding of their shared interest, they can work together to achieve it.
Necessary information exchange: Cooperation requires communication and information exchange among the players. Players must share information about their preferences, resources, and constraints to identify opportunities for mutual gain. By sharing information, players can better understand each other's goals and work towards achieving them together.
Voluntariness, equality, and mutual benefit: In cooperative games, players voluntarily come together to form coalitions and make agreements. The players must be equal partners in the coalition, and any agreements must be mutually beneficial. Cooperation is only sustainable if all parties feel they are receiving a fair share of the benefits.
Compulsory contract: In cooperative games, agreements between players are binding and mandatory. Once the players have agreed to a particular course of action, they have an obligation to follow through. The players must trust each other to keep their commitments, and there must be mechanisms in place to enforce the agreements. By making agreements binding and mandatory, players can ensure that they will achieve their shared goal.
Let S ⊊ N {\displaystyle S\subsetneq N} be a non-empty coalition of players. The subgame v S : 2 S → R {\displaystyle v_{S}:2^{S}\to \mathbb {R} } on S {\displaystyle S} is naturally defined as
In other words, we simply restrict our attention to coalitions contained in S {\displaystyle S} . Subgames are useful because they allow us to apply solution concepts defined for the grand coalition on smaller coalitions.
Characteristic functions are often assumed to be superadditive (Owen 1995, p. 213). This means that the value of a union of disjoint coalitions is no less than the sum of the coalitions' separate values:
v ( S ∪ T ) ≥ v ( S ) + v ( T ) {\displaystyle v(S\cup T)\geq v(S)+v(T)} whenever S , T ⊆ N {\displaystyle S,T\subseteq N} satisfy S ∩ T = ∅ {\displaystyle S\cap T=\emptyset } .
Larger coalitions gain more:
S ⊆ T ⇒ v ( S ) ≤ v ( T ) {\displaystyle S\subseteq T\Rightarrow v(S)\leq v(T)} .
This follows from superadditivity. i.e. if payoffs are normalized so singleton coalitions have zero value.
A coalitional game v is considered simple if payoffs are either 1 or 0, i.e. coalitions are either "winning" or "losing".
Equivalently, a simple game can be defined as a collection W of coalitions, where the members of W are called winning coalitions, and the others losing coalitions. It is sometimes assumed that a simple game is nonempty or that it does not contain an empty set. However, in other areas of mathematics, simple games are also called hypergraphs or Boolean functions (logic functions).
A few relations among the above axioms have widely been recognized, such as the following (e.g., Peleg, 2002, Section 2.1):
More generally, a complete investigation of the relation among the four conventional axioms (monotonicity, properness, strongness, and non-weakness), finiteness, and algorithmic computability has been made (Kumabe and Mihara, 2011), whose results are summarized in the Table "Existence of Simple Games" below.
The restrictions that various axioms for simple games impose on their Nakamura number were also studied extensively. In particular, a computable simple game without a veto player has a Nakamura number greater than 3 only if it is a proper and non-strong game.
Let G be a strategic (non-cooperative) game. Then, assuming that coalitions have the ability to enforce coordinated behaviour, there are several cooperative games associated with G. These games are often referred to as representations of G. The two standard representations are:
The main assumption in cooperative game theory is that the grand coalition N {\displaystyle N} will form. The challenge is then to allocate the payoff v ( N ) {\displaystyle v(N)} among the players in some way. (This assumption is not restrictive, because even if players split off and form smaller coalitions, we can apply solution concepts to the subgames defined by whatever coalitions actually form.) A solution concept is a vector x ∈ R N {\displaystyle x\in \mathbb {R} ^{N}} (or a set of vectors) that represents the allocation to each player. Researchers have proposed different solution concepts based on different notions of fairness. Some properties to look for in a solution concept include:
An efficient payoff vector is called a pre-imputation, and an individually rational pre-imputation is called an imputation. Most solution concepts are imputations.
The stable set of a game (also known as the von Neumann-Morgenstern solution (von Neumann & Morgenstern 1944)) was the first solution proposed for games with more than 2 players. Let v {\displaystyle v} be a game and let x {\displaystyle x} , y {\displaystyle y} be two imputations of v {\displaystyle v} . Then x {\displaystyle x} dominates y {\displaystyle y} if some coalition S ≠ ∅ {\displaystyle S\neq \emptyset } satisfies x i > y i , ∀ i ∈ S {\displaystyle x_{i}>y_{i},\forall ~i\in S} and ∑ i ∈ S x i ≤ v ( S ) {\displaystyle \sum _{i\in S}x_{i}\leq v(S)} . In other words, players in S {\displaystyle S} prefer the payoffs from x {\displaystyle x} to those from y {\displaystyle y} , and they can threaten to leave the grand coalition if y {\displaystyle y} is used because the payoff they obtain on their own is at least as large as the allocation they receive under x {\displaystyle x} .
A stable set is a set of imputations that satisfies two properties:
Von Neumann and Morgenstern saw the stable set as the collection of acceptable behaviours in a society: None is clearly preferred to any other, but for each unacceptable behaviour there is a preferred alternative. The definition is very general allowing the concept to be used in a wide variety of game formats.
Let v {\displaystyle v} be a game. The core of v {\displaystyle v} is the set of payoff vectors
In words, the core is the set of imputations under which no coalition has a value greater than the sum of its members' payoffs. Therefore, no coalition has incentive to leave the grand coalition and receive a larger payoff.
For simple games, there is another notion of the core, when each player is assumed to have preferences on a set X {\displaystyle X} of alternatives. A profile is a list p = ( ≻ i p ) i ∈ N {\displaystyle p=(\succ _{i}^{p})_{i\in N}} of individual preferences ≻ i p {\displaystyle \succ _{i}^{p}} on X {\displaystyle X} . Here x ≻ i p y {\displaystyle x\succ _{i}^{p}y} means that individual i {\displaystyle i} prefers alternative x {\displaystyle x} to y {\displaystyle y} at profile p {\displaystyle p} . Given a simple game v {\displaystyle v} and a profile p {\displaystyle p} , a dominance relation ≻ v p {\displaystyle \succ _{v}^{p}} is defined on X {\displaystyle X} by x ≻ v p y {\displaystyle x\succ _{v}^{p}y} if and only if there is a winning coalition S {\displaystyle S} (i.e., v ( S ) = 1 {\displaystyle v(S)=1} ) satisfying x ≻ i p y {\displaystyle x\succ _{i}^{p}y} for all i ∈ S {\displaystyle i\in S} . The core C ( v , p ) {\displaystyle C(v,p)} of the simple game v {\displaystyle v} with respect to the profile p {\displaystyle p} of preferences is the set of alternatives undominated by ≻ v p {\displaystyle \succ _{v}^{p}} (the set of maximal elements of X {\displaystyle X} with respect to ≻ v p {\displaystyle \succ _{v}^{p}} ):
The Nakamura number of a simple game is the minimal number of winning coalitions with empty intersection. Nakamura's theorem states that the core C ( v , p ) {\displaystyle C(v,p)} is nonempty for all profiles p {\displaystyle p} of acyclic (alternatively, transitive) preferences if and only if X {\displaystyle X} is finite and the cardinal number (the number of elements) of X {\displaystyle X} is less than the Nakamura number of v {\displaystyle v} . A variant by Kumabe and Mihara states that the core C ( v , p ) {\displaystyle C(v,p)} is nonempty for all profiles p {\displaystyle p} of preferences that have a maximal element if and only if the cardinal number of X {\displaystyle X} is less than the Nakamura number of v {\displaystyle v} . (See Nakamura number for details.)
Because the core may be empty, a generalization was introduced in (Shapley & Shubik 1966). The strong ε {\displaystyle \varepsilon } -core for some number ε ∈ R {\displaystyle \varepsilon \in \mathbb {R} } is the set of payoff vectors
In economic terms, the strong ε {\displaystyle \varepsilon } -core is the set of pre-imputations where no coalition can improve its payoff by leaving the grand coalition, if it must pay a penalty of ε {\displaystyle \varepsilon } for leaving. ε {\displaystyle \varepsilon } may be negative, in which case it represents a bonus for leaving the grand coalition. Clearly, regardless of whether the core is empty, the strong ε {\displaystyle \varepsilon } -core will be non-empty for a large enough value of ε {\displaystyle \varepsilon } and empty for a small enough (possibly negative) value of ε {\displaystyle \varepsilon } . Following this line of reasoning, the least-core, introduced in (Maschler, Peleg & Shapley 1979), is the intersection of all non-empty strong ε {\displaystyle \varepsilon } -cores. It can also be viewed as the strong ε {\displaystyle \varepsilon } -core for the smallest value of ε {\displaystyle \varepsilon } that makes the set non-empty (Bilbao 2000).
The Shapley value is the unique payoff vector that is efficient, symmetric, and satisfies monotonicity. It was introduced by Lloyd Shapley (Shapley 1953) who showed that it is the unique payoff vector that is efficient, symmetric, additive, and assigns zero payoffs to dummy players. The Shapley value of a superadditive game is individually rational, but this is not true in general. (Driessen 1988)
Let v : 2 N → R {\displaystyle v:2^{N}\to \mathbb {R} } be a game, and let x ∈ R N {\displaystyle x\in \mathbb {R} ^{N}} be an efficient payoff vector. The maximum surplus of player i over player j with respect to x is
the maximal amount player i can gain without the cooperation of player j by withdrawing from the grand coalition N under payoff vector x, assuming that the other players in i's withdrawing coalition are satisfied with their payoffs under x. The maximum surplus is a way to measure one player's bargaining power over another. The kernel of v {\displaystyle v} is the set of imputations x that satisfy
for every pair of players i and j. Intuitively, player i has more bargaining power than player j with respect to imputation x if s i j v ( x ) > s j i v ( x ) {\displaystyle s_{ij}^{v}(x)>s_{ji}^{v}(x)} , but player j is immune to player i's threats if x j = v ( j ) {\displaystyle x_{j}=v(j)} , because he can obtain this payoff on his own. The kernel contains all imputations where no player has this bargaining power over another. This solution concept was first introduced in (Davis & Maschler 1965).
The Harsanyi dividend (named after John Harsanyi, who used it to generalize the Shapley value in 1963) identifies the surplus that is created by a coalition of players in a cooperative game. To specify this surplus, the worth of this coalition is corrected by subtracting the surplus that was already created by subcoalitions. To this end, the dividend d v ( S ) {\displaystyle d_{v}(S)} of coalition S {\displaystyle S} in game v {\displaystyle v} is recursively determined by
d v ( { i } ) = v ( { i } ) d v ( { i , j } ) = v ( { i , j } ) − d v ( { i } ) − d v ( { j } ) d v ( { i , j , k } ) = v ( { i , j , k } ) − d v ( { i , j } ) − d v ( { i , k } ) − d v ( { j , k } ) − d v ( { i } ) − d v ( { j } ) − d v ( { k } ) ⋮ d v ( S ) = v ( S ) − ∑ T ⊊ S d v ( T ) {\displaystyle {\begin{aligned}d_{v}(\{i\})&=v(\{i\})\\d_{v}(\{i,j\})&=v(\{i,j\})-d_{v}(\{i\})-d_{v}(\{j\})\\d_{v}(\{i,j,k\})&=v(\{i,j,k\})-d_{v}(\{i,j\})-d_{v}(\{i,k\})-d_{v}(\{j,k\})-d_{v}(\{i\})-d_{v}(\{j\})-d_{v}(\{k\})\\&\vdots \\d_{v}(S)&=v(S)-\sum _{T\subsetneq S}d_{v}(T)\end{aligned}}}
An explicit formula for the dividend is given by d v ( S ) = ∑ T ⊆ S ( − 1 ) | S ∖ T | v ( T ) {\textstyle d_{v}(S)=\sum _{T\subseteq S}(-1)^{|S\setminus T|}v(T)} . The function d v : 2 N → R {\displaystyle d_{v}:2^{N}\to \mathbb {R} } is also known as the Möbius inverse of v : 2 N → R {\displaystyle v:2^{N}\to \mathbb {R} } . Indeed, we can recover v {\displaystyle v} from d v {\displaystyle d_{v}} by help of the formula v ( S ) = d v ( S ) + ∑ T ⊊ S d v ( T ) {\textstyle v(S)=d_{v}(S)+\sum _{T\subsetneq S}d_{v}(T)} .
Harsanyi dividends are useful for analyzing both games and solution concepts, e.g. the Shapley value is obtained by distributing the dividend of each coalition among its members, i.e., the Shapley value ϕ i ( v ) {\displaystyle \phi _{i}(v)} of player i {\displaystyle i} in game v {\displaystyle v} is given by summing up a player's share of the dividends of all coalitions that she belongs to, ϕ i ( v ) = ∑ S ⊂ N : i ∈ S d v ( S ) / | S | {\textstyle \phi _{i}(v)=\sum _{S\subset N:i\in S}{d_{v}(S)}/{|S|}} .
Let v : 2 N → R {\displaystyle v:2^{N}\to \mathbb {R} } be a game, and let x ∈ R N {\displaystyle x\in \mathbb {R} ^{N}} be a payoff vector. The excess of x {\displaystyle x} for a coalition S ⊆ N {\displaystyle S\subseteq N} is the quantity v ( S ) − ∑ i ∈ S x i {\displaystyle v(S)-\sum _{i\in S}x_{i}} ; that is, the gain that players in coalition S {\displaystyle S} can obtain if they withdraw from the grand coalition N {\displaystyle N} under payoff x {\displaystyle x} and instead take the payoff v ( S ) {\displaystyle v(S)} . The nucleolus of v {\displaystyle v} is the imputation for which the vector of excesses of all coalitions (a vector in R 2 N {\displaystyle \mathbb {R} ^{2^{N}}} ) is smallest in the leximin order. The nucleolus was introduced in (Schmeidler 1969).
(Maschler, Peleg & Shapley 1979) gave a more intuitive description: Starting with the least-core, record the coalitions for which the right-hand side of the inequality in the definition of C ε ( v ) {\displaystyle C_{\varepsilon }(v)} cannot be further reduced without making the set empty. Continue decreasing the right-hand side for the remaining coalitions, until it cannot be reduced without making the set empty. Record the new set of coalitions for which the inequalities hold at equality; continue decreasing the right-hand side of remaining coalitions and repeat this process as many times as necessary until all coalitions have been recorded. The resulting payoff vector is the nucleolus.
Introduced by Shapley in (Shapley 1971), convex cooperative games capture the intuitive property some games have of "snowballing". Specifically, a game is convex if its characteristic function v {\displaystyle v} is supermodular:
It can be shown (see, e.g., Section V.1 of (Driessen 1988)) that the supermodularity of v {\displaystyle v} is equivalent to
that is, "the incentives for joining a coalition increase as the coalition grows" (Shapley 1971), leading to the aforementioned snowball effect. For cost games, the inequalities are reversed, so that we say the cost game is convex if the characteristic function is submodular.
Convex cooperative games have many nice properties:
Submodular and supermodular set functions are also studied in combinatorial optimization. Many of the results in (Shapley 1971) have analogues in (Edmonds 1970), where submodular functions were first presented as generalizations of matroids. In this context, the core of a convex cost game is called the base polyhedron, because its elements generalize base properties of matroids.
However, the optimization community generally considers submodular functions to be the discrete analogues of convex functions (Lovász 1983), because the minimization of both types of functions is computationally tractable. Unfortunately, this conflicts directly with Shapley's original definition of supermodular functions as "convex".
Corporate strategic decisions can develop and create value through cooperative game theory. This means that cooperative game theory can become the strategic theory of the firm, and different CGT solutions can simulate different institutions.