Convex Games

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 of 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).

Cooperative games are often analysed through the framework of cooperative game theory, which focuses on predicting which coalitions will form, the joint actions that groups take and the resulting collective payoffs. It is opposed to the traditional non-cooperative game theory which focuses on predicting individual players' actions and payoffs and analyzing Nash equilibria.

Cooperative game theory provides a high-level approach as it only describes the structure, strategies and payoffs of coalitions, whereas non-cooperative game theory also looks at how bargaining procedures will affect the distribution of payoffs within each coalition. As non-cooperative game theory is more general, cooperative games can be analyzed through the approach of non-cooperative game theory (the converse does not hold) provided that sufficient assumptions are made to encompass all the possible strategies available to players due to the possibility of external enforcement of cooperation. While it would thus be possible to have all games expressed under a non-cooperative framework, in many instances insufficient information is available to accurately model the formal procedures available to the players during the strategic bargaining process, or the resulting model would be of too high complexity to offer a practical tool in the real world. In such cases, cooperative game theory provides a simplified approach that allows the analysis of the game at large without having to make any assumption about bargaining powers.

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 $N$, called the ''grand coalition'', and a ''characteristic function'' $v : 2^N \to \mathbb$ 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''.

Conversely, a cooperative game can also be defined with a characteristic cost function $c: 2^N \to \mathbb$ 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.

Cooperative game theory definition

Cooperative game is a mandatory binding contract that can be reached by all parties on the basis of information exchange. Moreover, cooperative game is a mechanism to establish cooperative consciousness, mutual trust, restraint and commitment through negotiation and communication.

There are four main points:

1. Common interests

2. Necessary information exchange

3. Voluntariness, equality and mutual benefit

4. Compulsory contract

Harsanyi dividend

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 the surplus that is already created by subcoalitions. To this end, the dividend $d_v(S)$ of coalition $S$ in game $v$ is recursively determined by

$\begin d_v(\)&= v(\) \\ d_v(\)&= v(\)-d_v(\)-d_v(\) \\ d_v(\)&= v(\)-d_v(\)-d_v(\)-d_x(\)-d_v(\)-d_v(\)-d_v(\)\\ &\vdots \\ d_v(S) &= v(S) - \sum_d_v(T) \end$

An explicit formula for the dividend is given by $d_v(S)=\sum_(-1)^v(T)$. The function $d_v:2^N \to \mathbb$ is also known as the Möbius inverse of $v:2^N \to \mathbb$. Indeed, we can recover $v$ from $d_v$ by help of the formula $v(S) = d_v(S) + \sum_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 $\phi_i(v)$ of player $i$ in game $v$ is given by summing up a player's share of the dividends of all coalitions that she belongs to, $\phi_i(v)=\sum_/$.

Duality

Let $v$ be a profit game. The ''dual game'' of $v$ is the cost game $v^*$ defined as

: $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 .

Subgames

Let $S \subsetneq N$ be a non-empty coalition of players. The ''subgame'' $v_S : 2^S \to \mathbb$ on $S$ is naturally defined as

: $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

Superadditivity

Characteristic functions are often assumed to be superadditive . This means that the value of a union of disjoint