Cooperative game theory

Last updated

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). [1]

Contents

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. [2] [3]

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 , called the grand coalition, and a characteristic function [4] 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, 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 satisfying . In this setting, players must accomplish some task, and the characteristic function 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.

Harsanyi dividend

The Harsanyi dividend (named after John Harsanyi, who used it to generalize the Shapley value in 1963 [5] ) 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 of coalition in game is recursively determined by

An explicit formula for the dividend is given by . The function is also known as the Möbius inverse of . [6] Indeed, we can recover from by help of the formula .

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 of player in game is given by summing up a player's share of the dividends of all coalitions that she belongs to, .

Duality

Let be a profit game. The dual game of is the cost game defined as

Intuitively, the dual game represents the opportunity cost for a coalition of not joining the grand coalition . A dual profit game can be defined identically for a cost game . 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 ( Bilbao 2000 ).

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.

Properties for characterization

Superadditivity

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:

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 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 few relations among the above axioms have widely been recognized, such as the following (e.g., Peleg, 2002, Section 2.1 [8] ):

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.

Existence of Simple Games [11]
TypeFinite Non-compFinite ComputableInfinite Non-compInfinite Computable
1111NoYesYesYes
1110NoYesNoNo
1101NoYesYesYes
1100NoYesYesYes
1011NoYesYesYes
1010NoNoNoNo
1001NoYesYesYes
1000NoNoNoNo
0111NoYesYesYes
0110NoNoNoNo
0101NoYesYesYes
0100NoYesYesYes
0011NoYesYesYes
0010NoNoNoNo
0001NoYesYesYes
0000NoNoNoNo

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.

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: [13]

Solution concepts

The main assumption in cooperative game theory is that the grand coalition will form. [14] The challenge is then to allocate the payoff 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 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

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 be a game and let , be two imputations of . Then dominates if some coalition satisfies and . In other words, players in prefer the payoffs from to those from , and they can threaten to leave the grand coalition if is used because the payoff they obtain on their own is at least as large as the allocation they receive under .

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

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.

Properties

  • 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 players. In such sets at least of the discriminated players are excluded ( Owen 1995 , p. 240).

The core

Let be a game. The core of is the set of payoff vectors

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

The core of a simple game with respect to preferences

For simple games, there is another notion of the core, when each player is assumed to have preferences on a set of alternatives. A profile is a list of individual preferences on . Here means that individual prefers alternative to at profile . Given a simple game and a profile , a dominance relation is defined on by if and only if there is a winning coalition (i.e., ) satisfying for all . The core of the simple game with respect to the profile of preferences is the set of alternatives undominated by (the set of maximal elements of with respect to ):

if and only if there is no such that .

The Nakamura number of a simple game is the minimal number of winning coalitions with empty intersection. Nakamura's theorem states that the core is nonempty for all profiles of acyclic (alternatively, transitive) preferences if and only if is finite and the cardinal number (the number of elements) of is less than the Nakamura number of . A variant by Kumabe and Mihara states that the core is nonempty for all profiles of preferences that have a maximal element if and only if the cardinal number of is less than the Nakamura number of . (See Nakamura number for details.)

The strong epsilon-core

Because the core may be empty, a generalization was introduced in ( Shapley & Shubik 1966 ). The strong -core for some number is the set of payoff vectors

In economic terms, the strong -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 for leaving. Note that 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 -core will be non-empty for a large enough value of and empty for a small enough (possibly negative) value of . Following this line of reasoning, the least-core, introduced in ( Maschler, Peleg & Shapley 1979 ), is the intersection of all non-empty strong -cores. It can also be viewed as the strong -core for the smallest value of that makes the set non-empty ( Bilbao 2000 ).

The Shapley value

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 )

The kernel

Let be a game, and let be an efficient payoff vector. The maximum surplus of player i over player j with respect to x is

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 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 , but player j is immune to player i's threats if , 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 ).

The nucleolus

Let be a game, and let be a payoff vector. The excess of for a coalition is the quantity ; that is, the gain that players in coalition can obtain if they withdraw from the grand coalition under payoff and instead take the payoff .

Now let be the vector of excesses of , arranged in non-increasing order. In other words, . Notice that is in the core of if and only if it is a pre-imputation and . To define the nucleolus, we consider the lexicographic ordering of vectors in : For two payoff vectors , we say is lexicographically smaller than if for some index , we have and . (The ordering is called lexicographic because it mimics alphabetical ordering used to arrange words in a dictionary.) The nucleolus of 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 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 ( 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

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

It can be shown (see, e.g., Section V.1 of ( Driessen 1988 )) that the supermodularity of is equivalent to

that is, "the incentives for joining a coalition increase as the coalition grows" ( Shapley 1971 ), 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 ( 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".

See also

Related Research Articles

In the mathematical discipline of set theory, forcing is a technique for proving consistency and independence results. It was first used by Paul Cohen in 1963, to prove the independence of the axiom of choice and the continuum hypothesis from Zermelo–Fraenkel set theory.

Shapley value

The Shapley value is a solution concept in cooperative game theory. It was named in honor of Lloyd Shapley, who introduced it in 1951 and won the Nobel Prize in Economics for it in 2012. To each cooperative game it assigns a unique distribution of a total surplus generated by the coalition of all players. The Shapley value is characterized by a collection of desirable properties. Hart (1989) provides a survey of the subject.

Vapnik–Chervonenkis theory was developed during 1960–1990 by Vladimir Vapnik and Alexey Chervonenkis. The theory is a form of computational learning theory, which attempts to explain the learning process from a statistical point of view.

Game theory is the branch of mathematics in which games are studied: that is, models describing human behaviour. This is a glossary of some terms of the subject.

In measure theory, an area of mathematics, Egorov's theorem establishes a condition for the uniform convergence of a pointwise convergent sequence of measurable functions. It is also named Severini–Egoroff theorem or Severini–Egorov theorem, after Carlo Severini, an Italian mathematician, and Dmitri Egorov, a Russian physicist and geometer, who published independent proofs respectively in 1910 and 1911.

In game theory, the core is the set of feasible allocations that cannot be improved upon by a subset of the economy's agents. A coalition is said to improve upon or block a feasible allocation if the members of that coalition are better off under another feasible allocation that is identical to the first except that every member of the coalition has a different consumption bundle that is part of an aggregate consumption bundle that can be constructed from publicly available technology and the initial endowments of each consumer in the coalition.

In game theory, folk theorems are a class of theorems describing an abundance of Nash equilibrium payoff profiles in repeated games. The original Folk Theorem concerned the payoffs of all the Nash equilibria of an infinitely repeated game. This result was called the Folk Theorem because it was widely known among game theorists in the 1950s, even though no one had published it. Friedman's (1971) Theorem concerns the payoffs of certain subgame-perfect Nash equilibria (SPE) of an infinitely repeated game, and so strengthens the original Folk Theorem by using a stronger equilibrium concept: subgame-perfect Nash equilibria rather than Nash equilibria.

In game theory, a game is said to be a potential game if the incentive of all players to change their strategy can be expressed using a single global function called the potential function. The concept originated in a 1996 paper by Dov Monderer and Lloyd Shapley.

In game theory, an epsilon-equilibrium, or near-Nash equilibrium, is a strategy profile that approximately satisfies the condition of Nash equilibrium. In a Nash equilibrium, no player has an incentive to change his behavior. In an approximate Nash equilibrium, this requirement is weakened to allow the possibility that a player may have a small incentive to do something different. This may still be considered an adequate solution concept, assuming for example status quo bias. This solution concept may be preferred to Nash equilibrium due to being easier to compute, or alternatively due to the possibility that in games of more than 2 players, the probabilities involved in an exact Nash equilibrium need not be rational numbers.

In game theory, a stochastic game, introduced by Lloyd Shapley in the early 1950s, is a dynamic game with probabilistic transitions played by one or more players. The game is played in a sequence of stages. At the beginning of each stage the game is in some state. The players select actions and each player receives a payoff that depends on the current state and the chosen actions. The game then moves to a new random state whose distribution depends on the previous state and the actions chosen by the players. The procedure is repeated at the new state and play continues for a finite or infinite number of stages. The total payoff to a player is often taken to be the discounted sum of the stage payoffs or the limit inferior of the averages of the stage payoffs.

The Bondareva–Shapley theorem, in game theory, describes a necessary and sufficient condition for the non-emptiness of the core of a cooperative game in characteristic function form. Specifically, the game's core is non-empty if and only if the game is balanced. The Bondareva–Shapley theorem implies that market games and convex games have non-empty cores. The theorem was formulated independently by Olga Bondareva and Lloyd Shapley in the 1960s.

In mathematics, a cardinal function is a function that returns cardinal numbers.

Linear production game is a N-person game in which the value of a coalition can be obtained by solving a linear programming problem. It is widely used in the context of resource allocation and payoff distribution. Mathematically, there are m types of resources and n products can be produced out of them. Product j requires amount of the kth resource. The products can be sold at a given market price while the resources themselves can not. Each of the N players is given a vector of resources. The value of a coalition S is the maximum profit it can achieve with all the resources possessed by its members. It can be obtained by solving a corresponding linear programming problem as follows.

In measure theory, or at least in the approach to it via the domain theory, a valuation is a map from the class of open sets of a topological space to the set of positive real numbers including infinity, with certain properties. It is a concept closely related to that of a measure, and as such, it finds applications in measure theory, probability theory, and theoretical computer science.

In decision theory and game theory, Wald's maximin model is a non-probabilistic decision-making model according to which decisions are ranked on the basis of their worst-case outcomes – the optimal decision is one with the least worst outcome. It is one of the most important models in robust decision making in general and robust optimization in particular.

In cooperative game theory and social choice theory, the Nakamura number measures the degree of rationality of preference aggregation rules, such as voting rules. It is an indicator of the extent to which an aggregation rule can yield well-defined choices.

Irrigation games are cooperative games which model cost sharing problems on networks. The irrigation game is a transferable utility game assigned to a cost-tree problem. A common example of this cost-tree problems are the irrigation networks. The irrigation ditch is represented by a graph, its nodes are water users, the edges are sections of the ditch. There is a cost of maintaining the ditch, and we are looking for the fair division of the costs among the users. The irrigation games are mentioned first by Aadland and Kolpin 1998, but the formal concept and the characterization of the game class is introduced by Márkus et al. 2011.

In game theory, an aggregative game is a game in which every player’s payoff is a function of the player’s own strategy and the aggregate of all players’ strategies. The concept was first proposed by Nobel laureate Reinhard Selten in 1970 who considered the case where the aggregate is the sum of the players' strategies.

In cooperative game theory, a hedonic game is a game that models the formation of coalitions (groups) of players when players have preferences over which group they belong to. A hedonic game is specified by giving a finite set of players, and, for each player, a preference ranking over all coalitions (subsets) of players that the player belongs to. The outcome of a hedonic game consists of a partition of the players into disjoint coalitions, that is, each player is assigned a unique group. Such partitions are often referred to as coalition structures.

In mathematics, a filter on a set informally gives a notion of which subsets are "large". Filter quantifiers are a type of logical quantifier which, informally, say whether or not a statement is true for "most" elements of . Such quantifiers are often used in combinatorics, model theory, and in other fields of mathematical logic where (ultra)filters are used.

References

  1. Shor, Mike. "Non-Cooperative Game - Game Theory .net". www.gametheory.net. Retrieved 2016-09-15.
  2. Chandrasekaran, R. "Cooperative Game Theory" (PDF).
  3. Brandenburger, Adam. "Cooperative Game Theory: Characteristic Functions, Allocations, Marginal Contribution" (PDF). Archived from the original (PDF) on 2016-05-27.
  4. denotes the power set of .
  5. Harsanyi, John C. (1982). "A Simplified Bargaining Model for the n-Person Cooperative Game". Papers in Game Theory. Theory and Decision Library. Springer, Dordrecht. pp. 44–70. doi:10.1007/978-94-017-2527-9_3. ISBN   9789048183692.
  6. Set Functions, Games and Capacities in Decision Making | Michel Grabisch | Springer. Theory and Decision Library C. Springer. 2016. ISBN   9783319306889.
  7. Georgios Chalkiadakis; Edith Elkind; Michael J. Wooldridge (25 October 2011). Computational Aspects of Cooperative Game Theory. Morgan & Claypool Publishers. ISBN   978-1-60845-652-9.
  8. Peleg, B. (2002). "Chapter 8 Game-theoretic analysis of voting in committees". Handbook of Social Choice and Welfare Volume 1. Handbook of Social Choice and Welfare. 1. pp. 395–423. doi:10.1016/S1574-0110(02)80012-1. ISBN   9780444829146.
  9. See a section for Rice's theorem for the definition of a computable simple game. In particular, all finite games are computable.
  10. Kumabe, M.; Mihara, H. R. (2011). "Computability of simple games: A complete investigation of the sixty-four possibilities" (PDF). Journal of Mathematical Economics. 47 (2): 150–158. arXiv: 1102.4037 . Bibcode:2011arXiv1102.4037K. doi:10.1016/j.jmateco.2010.12.003. S2CID   775278.
  11. Modified from Table 1 in Kumabe and Mihara (2011). The sixteen types are defined by the four conventional axioms (monotonicity, properness, strongness, and non-weakness). For example, type 1110 indicates monotonic (1), proper (1), strong (1), weak (0, because not nonweak) games. Among type 1110 games, there exist no finite non-computable ones, there exist finite computable ones, there exist no infinite non-computable ones, and there exist no infinite computable ones. Observe that except for type 1110, the last three columns are identical.
  12. Kumabe, M.; Mihara, H. R. (2008). "The Nakamura numbers for computable simple games". Social Choice and Welfare. 31 (4): 621. arXiv: 1107.0439 . doi:10.1007/s00355-008-0300-5. S2CID   8106333.
  13. Aumann, Robert J. "The core of a cooperative game without side payments." Transactions of the American Mathematical Society (1961): 539-552.
  14. Peters, Hans (2008). Game theory: a multi-leveled approach . Springer. pp.  123. doi:10.1007/978-3-540-69291-1_17. ISBN   978-3-540-69290-4.
  15. Young, H. P. (1985-06-01). "Monotonic solutions of cooperative games". International Journal of Game Theory. 14 (2): 65–72. doi:10.1007/BF01769885. ISSN   0020-7276. S2CID   122758426.

Further reading