Cooperative game theory

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:

${\displaystyle v(S\cup T)\geq v(S)+v(T)}$ whenever ${\displaystyle S,T\subseteq N}$ satisfy ${\displaystyle S\cap T=\emptyset }$.

Larger coalitions gain more:

${\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".[7]

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 simple game W is monotonic if any coalition containing a winning coalition is also winning, that is, if ${\displaystyle S\in W}$ and ${\displaystyle S\subseteq T}$ imply ${\displaystyle T\in W}$.
• A simple game W is proper if the complement (opposition) of any winning coalition is losing, that is, if ${\displaystyle S\in W}$ implies ${\displaystyle N\setminus S\notin W}$.
• A simple game W is strong if the complement of any losing coalition is winning, that is, if ${\displaystyle S\notin W}$ implies ${\displaystyle N\setminus S\in W}$.
  • If a simple game W is proper and strong, then a coalition is winning if and only if its complement is losing, that is, ${\displaystyle S\in W}$ iff ${\displaystyle N\setminus S\notin W}$. (If v is a coalitional simple game that is proper and strong, ${\displaystyle v(S)=1-v(N\setminus S)}$ for any S.)
• A veto player (vetoer) 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 W is weak (collegial) if it has a veto player, that is, if the intersection ${\displaystyle \bigcap W:=\bigcap _{S\in W}S}$ 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. (Dictator games in experimental economics are unrelated to this.)
• A carrier of a simple game W is a set ${\displaystyle T\subseteq N}$ such that for any coalition S, we have ${\displaystyle S\in W}$ iff ${\displaystyle S\cap T\in W}$. 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 (even if N is infinite).
• 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[8]):

• 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[9] has been made (Kumabe and Mihara, 2011[10]), 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.[12] 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.

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 ${\displaystyle v}$ be a game and let ${\displaystyle x}$, ${\displaystyle y}$ be two imputations of ${\displaystyle v}$. Then ${\displaystyle x}$ dominates ${\displaystyle y}$ if some coalition ${\displaystyle S\neq \emptyset }$ satisfies ${\displaystyle x_{i}>y_{i},\forall ~i\in S}$ and ${\displaystyle \sum _{i\in S}x_{i}\leq v(S)}$. In other words, players in ${\displaystyle S}$ prefer the payoffs from ${\displaystyle x}$ to those from ${\displaystyle y}$, and they can threaten to leave the grand coalition if ${\displaystyle y}$ is used because the payoff they obtain on their own is at least as large as the allocation they receive under ${\displaystyle x}$.

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.

• A stable set may or may not exist (Lucas 1969), and if it exists it is typically not unique (Lucas 1992). Stable sets are usually difficult to find. This and other difficulties have led to the development of many other solution concepts.
• A positive fraction of cooperative games have unique stable sets consisting of the core (Owen 1995, p. 240).
• A positive fraction of cooperative games have stable sets which discriminate ${\displaystyle n-2}$ players. In such sets at least ${\displaystyle n-3}$ of the discriminated players are excluded (Owen 1995, p. 240).

Let ${\displaystyle v}$ be a game. The core of ${\displaystyle v}$ is the set of payoff vectors

${\displaystyle 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.

• 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 (Driessen 1988) for a proof.

For simple games, there is another notion of the core, when each player is assumed to have preferences on a set ${\displaystyle X}$ of alternatives. A profile is a list ${\displaystyle p=(\succ _{i}^{p})_{i\in N}}$ of individual preferences ${\displaystyle \succ _{i}^{p}}$ on ${\displaystyle X}$. Here ${\displaystyle x\succ _{i}^{p}y}$ means that individual ${\displaystyle i}$ prefers alternative ${\displaystyle x}$ to ${\displaystyle y}$ at profile ${\displaystyle p}$. Given a simple game ${\displaystyle v}$ and a profile ${\displaystyle p}$, a dominance relation ${\displaystyle \succ _{v}^{p}}$ is defined on ${\displaystyle X}$ by ${\displaystyle x\succ _{v}^{p}y}$ if and only if there is a winning coalition ${\displaystyle S}$ (i.e., ${\displaystyle v(S)=1}$) satisfying ${\displaystyle x\succ _{i}^{p}y}$ for all ${\displaystyle i\in S}$. The core ${\displaystyle C(v,p)}$ of the simple game ${\displaystyle v}$ with respect to the profile ${\displaystyle p}$ of preferences is the set of alternatives undominated by ${\displaystyle \succ _{v}^{p}}$ (the set of maximal elements of ${\displaystyle X}$ with respect to ${\displaystyle \succ _{v}^{p}}$):

${\displaystyle x\in C(v,p)}$ if and only if there is no ${\displaystyle y\in X}$ such that ${\displaystyle 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 ${\displaystyle C(v,p)}$ is nonempty for all profiles ${\displaystyle p}$ of acyclic (alternatively, transitive) preferences if and only if ${\displaystyle X}$ is finite and the cardinal number (the number of elements) of ${\displaystyle X}$ is less than the Nakamura number of ${\displaystyle v}$. A variant by Kumabe and Mihara states that the core ${\displaystyle C(v,p)}$ is nonempty for all profiles ${\displaystyle p}$ of preferences that have a maximal element if and only if the cardinal number of ${\displaystyle X}$ is less than the Nakamura number of ${\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 ${\displaystyle \varepsilon \in \mathbb {R} }$ is the set of payoff vectors

${\displaystyle 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 ${\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. Note that ${\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.[15] 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 ${\displaystyle v:2^{N}\to \mathbb {R} }$ be a game, and let ${\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

${\displaystyle 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 ${\displaystyle v}$ is the set of imputations x that satisfy

• ${\displaystyle (s_{ij}^{v}(x)-s_{ji}^{v}(x))\times (x_{j}-v(j))\leq 0}$, and
• ${\displaystyle (s_{ji}^{v}(x)-s_{ij}^{v}(x))\times (x_{i}-v(i))\leq 0}$

for every pair of players i and j. Intuitively, player i has more bargaining power than player j with respect to imputation x if ${\displaystyle s_{ij}^{v}(x)>s_{ji}^{v}(x)}$, but player j is immune to player i's threats if ${\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).

Let ${\displaystyle v:2^{N}\to \mathbb {R} }$ be a game, and let ${\displaystyle x\in \mathbb {R} ^{N}}$ be a payoff vector. The excess of ${\displaystyle x}$ for a coalition ${\displaystyle S\subseteq N}$ is the quantity ${\displaystyle v(S)-\sum _{i\in S}x_{i}}$; that is, the gain that players in coalition ${\displaystyle S}$ can obtain if they withdraw from the grand coalition ${\displaystyle N}$ under payoff ${\displaystyle x}$ and instead take the payoff ${\displaystyle v(S)}$.

Now let ${\displaystyle \theta (x)\in \mathbb {R} ^{2^{N}}}$ be the vector of excesses of ${\displaystyle x}$, arranged in non-increasing order. In other words, ${\displaystyle \theta _{i}(x)\geq \theta _{j}(x),\forall ~i<j}$. Notice that ${\displaystyle x}$ is in the core of ${\displaystyle v}$ if and only if it is a pre-imputation and ${\displaystyle \theta _{1}(x)\leq 0}$. To define the nucleolus, we consider the lexicographic ordering of vectors in ${\displaystyle \mathbb {R} ^{2^{N}}}$: For two payoff vectors ${\displaystyle x,y}$, we say ${\displaystyle \theta (x)}$ is lexicographically smaller than ${\displaystyle \theta (y)}$ if for some index ${\displaystyle k}$, we have ${\displaystyle \theta _{i}(x)=\theta _{i}(y),\forall ~i<k}$ and ${\displaystyle \theta _{k}(x)<\theta _{k}(y)}$. (The ordering is called lexicographic because it mimics alphabetical ordering used to arrange words in a dictionary.) The nucleolus of ${\displaystyle v}$ is the lexicographically minimal imputation, based on this ordering. This solution concept was first introduced in (Schmeidler 1969).

Although the definition of the nucleolus seems abstract, (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 ${\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.

• Although the definition does not explicitly state it, the nucleolus is always unique. (See Section II.7 of (Driessen 1988) 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 (Driessen 1988) for details.)

Convex cooperative games have many nice properties:

• Supermodularity trivially implies superadditivity.
• Convex games are totally balanced: The core of a convex game is non-empty, and since any subgame of a convex game is convex, the core of any subgame is also non-empty.
• A convex game has a unique stable set that coincides with its core.
• The Shapley value of a convex game is the center of gravity of its core.
• An extreme point (vertex) of the core can be found in polynomial time using the greedy algorithm: Let ${\displaystyle \pi :N\to N}$ be a permutation of the players, and let ${\displaystyle S_{i}=\{j\in N:\pi (j)\leq i\}}$ be the set of players ordered ${\displaystyle 1}$ through ${\displaystyle i}$ in ${\displaystyle \pi }$, for any ${\displaystyle i=0,\ldots ,n}$, with ${\displaystyle S_{0}=\emptyset }$. Then the payoff ${\displaystyle x\in \mathbb {R} ^{N}}$ defined by ${\displaystyle x_{i}=v(S_{\pi (i)})-v(S_{\pi (i)-1}),\forall ~i\in N}$ is a vertex of the core of ${\displaystyle v}$. Any vertex of the core can be constructed in this way by choosing an appropriate permutation ${\displaystyle \pi }$.

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

• Bilbao, Jesús Mario (2000), Cooperative Games on Combinatorial Structures, Kluwer Academic Publishers, ISBN 9781461543930

• Davis, M.; Maschler, M. (1965), "The kernel of a cooperative game", Naval Research Logistics Quarterly, 12 (3): 223–259, doi:10.1002/nav.3800120303

• Driessen, Theo (1988), Cooperative Games, Solutions and Applications, Kluwer Academic Publishers, ISBN 9789401577878

• Edmonds, Jack (1970), "Submodular functions, matroids and certain polyhedra", in Guy, R.; Hanani, H.; Sauer, N.; Schönheim, J. (eds.), Combinatorial Structures and Their Applications, New York: Gordon and Breach, pp. 69–87

• Lovász, László (1983), "Submodular functions and convexity", in Bachem, A.; Grötschel, M.; Korte, B. (eds.), Mathematical Programming—The State of the Art, Berlin: Springer, pp. 235–257

• Leyton-Brown, Kevin; Shoham, Yoav (2008), Essentials of Game Theory: A Concise, Multidisciplinary Introduction, San Rafael, CA: Morgan & Claypool Publishers, ISBN 978-1-59829-593-1. An 88-page mathematical introduction; see Chapter 8. Free online(subscription required) at many universities.

• Lucas, William F. (1969), "The Proof That a Game May Not Have a Solution", Transactions of the American Mathematical Society, 136: 219–229, doi:10.2307/1994798, JSTOR 1994798.

• Lucas, William F. (1992), "Von Neumann-Morgenstern Stable Sets", in Aumann, Robert J.; Hart, Sergiu (eds.), Handbook of Game Theory, Volume I, Amsterdam: Elsevier, pp. 543–590

• Luce, R.D. and Raiffa, H. (1957) Games and Decisions: An Introduction and Critical Survey, Wiley & Sons. (see Chapter 8).
• Maschler, M.; Peleg, B.; Shapley, Lloyd S. (1979), "Geometric properties of the kernel, nucleolus, and related solution concepts", Mathematics of Operations Research, 4 (4): 303–338, doi:10.1287/moor.4.4.303

• Osborne, M.J. and Rubinstein, A. (1994) A Course in Game Theory, MIT Press (see Chapters 13,14,15)
• Moulin, Herve (1988), Axioms of Cooperative Decision Making (1st ed.), Cambridge: Cambridge University Press, ISBN 978-0-521-42458-5

• Owen, Guillermo (1995), Game Theory (3rd ed.), San Diego: Academic Press, ISBN 978-0-12-531151-9

• Schmeidler, D. (1969), "The nucleolus of a characteristic function game", SIAM Journal on Applied Mathematics, 17 (6): 1163–1170, doi:10.1137/0117107.

• Shapley, Lloyd S. (1953), "A value for ${\displaystyle n}$-person games", in Kuhn, H.; Tucker, A.W. (eds.), Contributions to the Theory of Games II, Princeton, New Jersey: Princeton University Press, pp. 307–317

• Shapley, Lloyd S. (1971), "Cores of convex games", International Journal of Game Theory, 1 (1): 11–26, doi:10.1007/BF01753431, S2CID 123385556

• Shapley, Lloyd S.; Shubik, M. (1966), "Quasi-cores in a monetary economy with non-convex preferences", Econometrica, 34 (4): 805–827, doi:10.2307/1910101, JSTOR 1910101

• Shoham, Yoav; Leyton-Brown, Kevin (2009), Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations, New York: Cambridge University Press, ISBN 978-0-521-89943-7. A comprehensive reference from a computational perspective; see Chapter 12. Downloadable free online.

• von Neumann, John; Morgenstern, Oskar (1944), "Theory of Games and Economic Behavior", Nature, Princeton: Princeton University Press, 157 (3981): 172, Bibcode:1946Natur.157..172R, doi:10.1038/157172a0, S2CID 29754824

• Yeung, David W.K. and Leon A. Petrosyan. Cooperative Stochastic Differential Games (Springer Series in Operations Research and Financial Engineering), Springer, 2006. Softcover-ISBN 978-1441920942.
• Yeung, David W.K. and Leon A. Petrosyan. Subgame Consistent Economic Optimization: An Advanced Cooperative Dynamic Game Analysis (Static & Dynamic Game Theory: Foundations & Applications), Birkhäuser Boston; 2012. ISBN 978-0817682613