Cooperative game theory

In game theory, a cooperative or coalitional game is a game with groups of players who form binding "coalitions" with external enforcement of cooperative behavior. 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.
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.

Mathematical definition

A cooperative game is given by specifying a value for every coalition. Formally, the coalitional game consists of a finite set of players, called the grand coalition, and a characteristic function from the set of all possible coalitions of players to a set of payments that satisfies. The function describes how much collective payoff a set of players can gain by forming a coalition.

Key attributes

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.
Subgames

Let be a non-empty coalition of players. The subgame on is naturally defined as
In other words, we simply restrict our attention to coalitions contained in. Subgames are useful because they allow us to apply [|solution concepts] defined for the grand coalition on smaller coalitions.

Mathematical properties

Superadditivity

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

Monotonicity

Larger coalitions gain more:
This follows from superadditivity. i.e. if payoffs are normalized so singleton coalitions have zero value.

Properties for simple games

A coalitional game 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 of coalitions, where the members of 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.

A simple game is monotonic if any coalition containing a winning coalition is also winning, that is, if and imply.
A simple game is proper if the complement of any winning coalition is losing, that is, if implies.
A simple game is strong if the complement of any losing coalition is winning, that is, if implies.
* If a simple game is proper and strong, then a coalition is winning if and only if its complement is losing, that is, iff .
A veto player in a simple game is a player that belongs to all winning coalitions. Supposing there is a veto player, any coalition not containing a veto player is losing. A simple game is weak if it has a veto player, that is, if the intersection of all winning coalitions is nonempty.
* A dictator in a simple game is a veto player such that any coalition containing this player is winning. The dictator does not belong to any losing coalition.
A carrier of a simple game is a set such that for any coalition, we have iff. When a simple game has a carrier, any player not belonging to it is ignored. A simple game is sometimes called finite if it has a finite carrier.
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
:

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
, finiteness, and algorithmic computability
has been made,
whose results are summarized in the Table "Existence of Simple Games" below.

Type	Finite Non-comp	Finite Computable	Infinite Non-comp	Infinite Computable

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.

Relation with non-cooperative theory

Let G be a strategic 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 will form. The challenge is then to allocate the payoff among the players in some way. A solution concept is a vector 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:

Efficiency: The payoff vector exactly splits the total value:.
Individual rationality: No player receives less than what he could get on his own:.
Existence: The solution concept exists for any game.
Uniqueness: The solution concept is unique for any game.
Marginality: The payoff of a player depends only on the marginal contribution of this player, i.e., if these marginal contributions are the same in two different games, then the payoff is the same: implies that is the same in and in.
Monotonicity: The payoff of a player increases if the marginal contribution of this player increase: implies that is weakly greater in than in.
Computational ease: The solution concept can be calculated efficiently
Symmetry: The solution concept allocates equal payments to symmetric players,. Two players, are symmetric if ; 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. Mathematically, if and are games, the game simply assigns to any coalition the sum of the payoffs the coalition would get in the two individual games. An additive solution concept assigns to every player in the sum of what he would receive in and.
Zero Allocation to Null Players: The allocation to a null player is zero. A null player satisfies. In economic terms, a null player's marginal value to any coalition that does not contain him is zero.

An efficient payoff vector is called a pre-imputation, and an individually rational pre-imputation is called an imputation. Most solution concepts are imputations.