# Cooperative game

In game theory, a cooperative game is a game where groups of players ("coalitions") may enforce cooperative behaviour, hence the game is a competition between coalitions of players, rather than between individual players. An example is a coordination game, when players choose the strategies by a consensus decision-making process.

Recreational games are rarely cooperative, because they usually lack mechanisms by which coalitions may enforce coordinated behaviour on the members of the coalition. Such mechanisms, however, are abundant in real life situations (e.g. contract law).

## Mathematical definition

A cooperative game is given by specifying a value for every coalition. Formally, the game (coalitional game) consists of a finite set of players $N$ , called the grand coalition, and a characteristic function $v:2^{N}\to \mathbb {R}$ from the set of all possible coalitions of players to a set of payments that satisfies $v(\emptyset )=0$ . The function describes how much collective payoff a set of players can gain by forming a coalition, and the game is sometimes called a value game or a profit game. The players are assumed to choose which coalitions to form, according to their estimate of the way the payment will be divided among coalition members.

Conversely, a cooperative game can also be defined with a characteristic cost function $c:2^{N}\to \mathbb {R}$ satisfying $c(\emptyset )=0$ . In this setting, players must accomplish some task, and the characteristic function $c$ represents the cost of a set of players accomplishing the task together. A game of this kind is known as a cost game. Although most cooperative game theory deals with profit games, all concepts can easily be translated to the cost setting.

### Duality

$v^{*}(S)=v(N)-v(N\setminus S),\forall ~S\subseteq N.\,$ Intuitively, the dual game represents the opportunity cost for a coalition $S$ of not joining the grand coalition $N$ . A dual profit game $c^{*}$ can be defined identically for a cost game $c$ . A cooperative game and its dual are in some sense equivalent, and they share many properties. For example, the core of a game and its dual are equal. For more details on cooperative game duality, see for instance Template:Harv.

### Subgames

$v_{S}(T)=v(T),\forall ~T\subseteq S.\,$ In other words, we simply restrict our attention to coalitions contained in $S$ . Subgames are useful because they allow us to apply solution concepts defined for the grand coalition on smaller coalitions.

## Properties for characterization

Characteristic functions are often assumed to be superadditive Template:Harv. This means that the value of a union of disjoint coalitions is no less than the sum of the coalitions' separate values:

### Monotonicity

Larger coalitions gain more: $S\subseteq T\Rightarrow v(S)\leq v(T)$ . This follows from superadditivity if payoffs are normalized so singleton coalitions have value zero.

### Properties for simple games

A coalitional game $v$ is 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. In other areas of mathematics, simple games are also called hypergraphs or Boolean functions (logic functions).

• The Nakamura number of a simple game is the minimal number of winning coalitions with empty intersection. According to Nakamura's theorem, the number measures the degree of rationality; it is an indicator of the extent to which an aggregation rule can yield well-defined choices.

A few relations among the above axioms have widely been recognized, such as the following (e.g., Peleg, 2002, Section 2.1):

• If a simple game is weak, it is proper.
• A simple game is dictatorial if and only if it is strong and weak.

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.

Existence of Simple Games
Type Finite Non-comp Finite Computable Infinite Non-comp Infinite Computable
1111 no yes yes yes
1110 no yes no no
1101 no yes yes yes
1100 no yes yes yes
1011 no yes yes yes
1010 no no no no
1001 no yes yes yes
1000 no no no no
0111 no yes yes yes
0110 no no no no
0101 no yes yes yes
0100 no yes yes yes
0011 no yes yes yes
0010 no no no no
0001 no yes yes yes
0000 no no no no

The restrictions that various axioms for simple games impose on their Nakamura number are also studied extensively. In particular, a computable simple game without a veto player has a Nakamura number greater than 3 only if it is proper and non-strong.

## Relation with non-cooperative theory

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 α-effective game associates with each coalition the sum of gains its members can 'guarantee' by joining forces. By 'guaranteeing', it is meant that the value is the max-min, e.g. the maximal value of the minimum taken over the opposition's strategies.
• The β-effective game associates with each coalition the sum of gains its members can 'strategically guarantee' by joining forces. By 'strategically guaranteeing', it is meant that the value is the min-max, e.g. the minimal value of the maximum taken over the opposition's strategies.

## Solution concepts

The main assumption in cooperative game theory is that the grand coalition $N$ will form. The challenge is then to allocate the payoff $v(N)$ among the players in some fair 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\in \mathbb {R} ^{N}$ 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

A stable set is a set of imputations that satisfies two properties:

• Internal stability: No payoff vector in the stable set is dominated by another vector in the set.
• External stability: All payoff vectors outside the set are dominated by at least one vector in the set.

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.

### The core

$C(v)=\left\{x\in \mathbb {R} ^{N}:\sum _{i\in N}x_{i}=v(N);\quad \sum _{i\in S}x_{i}\geq v(S),\forall ~S\subseteq N\right\}.\,$ 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.

#### 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 Template:Harv for a proof.)

### The core of a simple game with respect to preferences

$x\in C(v,p)$ if and only if there is no $y\in X$ such that $y\succ _{v}^{p}x$ .

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)$ is nonempty for all profiles $p$ of acyclic (alternatively, transitive) preferences if and only if $X$ is finite and the cardinal number (the number of elements) of $X$ is less than the Nakamura number of $v$ . A variant by Kumabe and Mihara states that the core $C(v,p)$ is nonempty for all profiles $p$ of preferences that have a maximal element if and only if the cardinal number of $X$ is less than the Nakamura number of $v$ . (See Nakamura number for details.)

### The strong epsilon-core

Because the core may be empty, a generalization was introduced in Template:Harv. The strong $\varepsilon$ -core for some number $\varepsilon \in \mathbb {R}$ is the set of payoff vectors

$C_{\varepsilon }(v)=\left\{x\in \mathbb {R} ^{N}:\sum _{i\in N}x_{i}=v(N);\quad \sum _{i\in S}x_{i}\geq v(S)-\varepsilon ,\forall ~S\subseteq N\right\}.$ In economic terms, the strong $\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 $\varepsilon$ for leaving. Note that $\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 $\varepsilon$ -core will be non-empty for a large enough value of $\varepsilon$ and empty for a small enough (possibly negative) value of $\varepsilon$ . Following this line of reasoning, the least-core, introduced in Template:Harv, is the intersection of all non-empty strong $\varepsilon$ -cores. It can also be viewed as the strong $\varepsilon$ -core for the smallest value of $\varepsilon$ that makes the set non-empty Template:Harv.

### The Shapley value

{{#invoke:main|main}} 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 Template:Harv. The Shapley value of a superadditive game is individually rational, but this is not true in general. Template:Harv

### The kernel

Let $v:2^{N}\to \mathbb {R}$ be a game, and let $x\in \mathbb {R} ^{N}$ be an efficient payoff vector. The maximum surplus of player i over player j with respect to x is

$s_{ij}^{v}(x)=\max \left\{v(S)-\sum _{k\in S}x_{k}:S\subseteq N\setminus \{j\},i\in S\right\},$ 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$ 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_{ij}^{v}(x)>s_{ji}^{v}(x)$ , but player j is immune to player i's threats if $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 Template:Harv.

### The nucleolus

Although the definition of the nucleolus seems abstract, Template:Harv 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_{\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.

#### Properties

• Although the definition does not explicitly state it, the nucleolus is always unique. (See Section II.7 of Template:Harv for a proof.)
• If the core is non-empty, the nucleolus is in the core.
• The nucleolus is always in the kernel, and since the kernel is contained in the bargaining set, it is always in the bargaining set (see Template:Harv for details.)

## Convex cooperative games

Introduced by Shapley in Template:Harv, convex cooperative games capture the intuitive property some games have of "snowballing". Specifically, a game is convex if its characteristic function $v$ is supermodular:

$v(S\cup T)+v(S\cap T)\geq v(S)+v(T),\forall ~S,T\subseteq N.\,$ It can be shown (see, e.g., Section V.1 of Template:Harv) that the supermodularity of $v$ is equivalent to

$v(S\cup \{i\})-v(S)\leq v(T\cup \{i\})-v(T),\forall ~S\subseteq T\subseteq N\setminus \{i\},\forall ~i\in N;\,$ that is, "the incentives for joining a coalition increase as the coalition grows" Template:Harv, 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.

### Properties

Convex cooperative games have many nice properties:

### Similarities and differences with combinatorial optimization

Submodular and supermodular set functions are also studied in combinatorial optimization. Many of the results in Template:Harv have analogues in Template:Harv, 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 Template:Harv, 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".