Cooperative game

A non-strategic game (see Games, theory of), defined by a triple <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c0264501.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c0264502.png" /> is a (usually finite) set whose elements are called players, the subsets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c0264503.png" /> are called coalitions, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c0264504.png" /> is a real-valued function defined on the set of coalitions, called the characteristic function of the game, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c0264505.png" /> is a subset of vectors <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c0264506.png" /> (the components <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c0264507.png" /> correspond to player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c0264508.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c0264509.png" />) called the imputations. Cooperative games were first introduced by J. von Neumann, 1928, as a tool in the cooperative theory of (non-cooperative) games.

In the classical theory of cooperative games one takes:

<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645010.png" />

On the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645011.png" /> one introduces the binary relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645012.png" /> of dominance (preference) of the imputations with respect to the coalition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645013.png" />:

<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645014.png" />

<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645015.png" />

If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645016.png" /> for some <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645017.png" />, then one writes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645018.png" />. Notions of optimality of an imputation are formulated in terms of this relation of dominance.

A significant part of the contents of the theory of cooperative games consists of elaborating the notions of optimality, of proving their realizability for various special classes of cooperative games, and of actually discovering such realizations. Among the principles of optimality that have been developed in connection with cooperative games are the following: double (namely, internal and external) stability, realizable in the form of von Neumann–Morgenstern solutions (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645020.png" />-solutions, cf. Solution in game theory); undominated imputations (see Core in the theory of games); stability with respect to threats; stability in the sense of minimization of the greatest insufficiency (see Stability in game theory); fairness (see Shapley vector); etc.

The introduction of algebraic operations in the class of cooperative games leads to the calculus of cooperative games and to the investigation of interrelations between these operations and various principles of optimality. The different special classes of cooperative games described below have been given special attention.

A simple game is a cooperative game in which the characteristic function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645021.png" /> takes exactly two values (usually 0 and 1); here, coalitions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645022.png" /> on which the maximum value of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645023.png" /> is attained are called winning. A special case of simple games is a weighted majority game, in which a coalition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645024.png" /> is winning if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645025.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645026.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645027.png" />) and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645028.png" /> are certain constants.

A balanced game is a cooperative game whose characteristic function is such that

<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645029.png" />

if the family of coalitions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645030.png" /> and the non-negative numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645031.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645032.png" />) are such that

<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645033.png" />

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645034.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645035.png" /> and 0 otherwise. Balanced games and only they have a non-empty <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645037.png" />-core (cf. Core in the theory of games).

A convex game is a cooperative game whose characteristic function is such that for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645038.png" />,

<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645039.png" />

(*)

In a convex game the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645040.png" />-core is non-empty and coincides with the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645041.png" />-solutions. If a cooperative game is strictly convex (that is, the inequality (*) is strict), then the Shapley vector (value) is the centre of gravity of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645042.png" />-core.

A quota-game is a cooperative game with characteristic function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645043.png" /> for which there exists a vector <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645044.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645045.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645046.png" /> for any two players <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645047.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645048.png" />).

A market game is a cooperative game induced by a market, which is taken to be a system

<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645049.png" />

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645050.png" /> is the set of participants in the market (with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645051.png" /> commodities), <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645052.png" /> is the initial bundle of commodities of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645053.png" />-th participant and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645054.png" /> is the utility function of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645055.png" />-th participant defined on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645056.png" />. On the basis of such a market a cooperative game is constructed in which

<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645057.png" />

while the characteristic function is defined by

<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645058.png" />

The theory of classical cooperative games has undergone generalizations in various directions (see also Non-atomic game).

Games without side payments are non-strategic games defined by a triple <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645059.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645060.png" /> (in contrast to classical cooperative games) is a function that associates with each coalition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645061.png" /> a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645062.png" /> of vectors <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645063.png" /> satisfying the following conditions: 1) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645064.png" /> is closed and convex; 2) if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645065.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645066.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645067.png" />), then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645068.png" />; 3) if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645069.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645070.png" />; 4) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645071.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645072.png" />; and 5) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645073.png" /> if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645074.png" /> for some <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645075.png" />.

Dominance in a game without side payments is defined as follows: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645076.png" /> if there exists a non-empty coalition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645077.png" /> such that

<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645078.png" />

A game in partition function form is a non-strategic game defined by a set of players <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645079.png" /> and a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645080.png" /> that associates with each partition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645081.png" /> of the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645082.png" /> a vector <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645083.png" />. The maximal pay-off that the coalition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645084.png" /> itself can guarantee is defined by the formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645085.png" />. An imputation in a game in partition function form is defined as a vector <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645086.png" /> satisfying the conditions: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645087.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645088.png" />); <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645089.png" /> for some <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645090.png" />. An imputation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645091.png" /> dominates an imputation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645092.png" /> with respect to a coalition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645093.png" /> if: 1) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645094.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645095.png" />); 2) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645096.png" />; and 3) there exists a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645097.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645098.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026450/c02645099.png" />.

References

[1]	J. von Neumann, O. Morgenstern, "Theory of games and economic behavior" , Princeton Univ. Press (1953)
[2]	N.N. Vorob'ev, "The present state of the theory of games" Russian Math. Surveys , 25 : 2 (1970) pp. 81–140 Uspekhi Mat. Nauk , 25 : 2 (1970) pp. 103–107
[3]	I. Rosenmüller, "The theory of games and markets" , North-Holland (1981) (Translated from German)

References

[a1]	J.W. Friedman, "Oligopoly and the theory of games" , North-Holland (1977)
[a2]	J. Szép, F. Forgó, "Introduction to the theory of games" , Reidel (1985)