Cooperative game
Encyclopedia
In game theory
Game theory
Game theory is a mathematical method for analyzing calculated circumstances, such as in games, where a person’s success is based upon the choices of others...

, a cooperative game is a game where groups of players ("coalitions") may enforce cooperative behaviour, hence the game is a competition between coalitions of players, rather than between individual players. An example is a coordination game
Coordination game
In game theory, coordination games are a class of games with multiple pure strategy Nash equilibria in which players choose the same or corresponding strategies...

, when players choose the strategies by a consensus decision-making
Consensus decision-making
Consensus decision-making is a group decision making process that seeks the consent, not necessarily the agreement, of participants and the resolution of objections. Consensus is defined by Merriam-Webster as, first, general agreement, and second, group solidarity of belief or sentiment. It has its...

 process.

Recreational games are rarely cooperative, because they usually lack mechanisms by which coalitions may enforce coordinated behaviour on the members of the coalition. Such mechanisms, however, are abundant in real life situations (e.g. contract law).

Mathematical definition

A cooperative game is given by specifying a value for every coalition. Formally, the game (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, and the game is sometimes called a value game or a profit game. The players are assumed to choose which coalitions to form, according to their estimate of the way the payment will be divided among coalition members.

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.

Duality

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


Intuitively, the dual game represents the opportunity cost
Opportunity cost
Opportunity cost is the cost of any activity measured in terms of the value of the best alternative that is not chosen . It is the sacrifice related to the second best choice available to someone, or group, who has picked among several mutually exclusive choices. The opportunity cost is also the...

 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
Core (economics)
The core is the set of feasible allocations that cannot be improved upon by a subset of the economy's consumers. 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...

 of a game and its dual are equal. For more details on cooperative game duality, see for instance .

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.

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 if payoffs are normalized so singleton coalitions have value zero.

Properties for Simple games

A coalitional game is 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.
In other areas of mathematics, simple games are also called hypergraph
Hypergraph
In mathematics, a hypergraph is a generalization of a graph, where an edge can connect any number of vertices. Formally, a hypergraph H is a pair H = where X is a set of elements, called nodes or vertices, and E is a set of non-empty subsets of X called hyperedges or links...

s or Boolean functions (logic 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 (opposition) 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 imples.
    • If a simple game is proper and strong, then a coalition is winning if and only if its complement is losing, that is, iff . (If is a colitional simple game that is proper and strong, for any .)

  • A veto player (vetoer) in a simple game is a player that belong to all winning coalitions. Supposing there is a veto player, any coalition not containing a veto player is losing. A simple game is weak (collegial) 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. (Dictator game
      Dictator game
      The dictator game is a game in experimental economics, similar to the ultimatum game. Experimental results offer evidence against the rationally self-interested individual concept of economic behavior, though precisely what to conclude from the evidence is controversial.-Description:In the...

      s in experimental economics are unrelated to this.)

  • 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 (even if is infinite).

  • The Nakamura number
    Nakamura number
    In cooperative game theory and social choice theory, the Nakamura number measures the degree of rationalityof preference aggregation rules , such as voting rules....

    of a simple game is the minimal number of winning coalitions with empty intersection. The number measures the degree of rationality; it is an indicator of the extent to which an aggregation rule can yield well-defined choices.

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 α-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 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:
  • 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 .
  • Computational ease: The solution concept can be calculated efficiently (i.e. in polynomial time with respect to the number of players .)
  • 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
Imputation (game theory)
In fully cooperative games players act efficiently when they form a single coalition, the grand coalition. The focus of the game is to find acceptable distributions of the payoff of the grand coalition. Distributions where a player receives less than it could obtain on its own, without cooperating...

. Most solution concepts are imputations.

The stable set

The stable set of a game (also known as the von Neumann-Morgenstern solution ) was the first solution proposed for games with more than 2 players. Let be a game and let , be two imputations
Imputation (game theory)
In fully cooperative games players act efficiently when they form a single coalition, the grand coalition. The focus of the game is to find acceptable distributions of the payoff of the grand coalition. Distributions where a player receives less than it could obtain on its own, without cooperating...

 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
Imputation (game theory)
In fully cooperative games players act efficiently when they form a single coalition, the grand coalition. The focus of the game is to find acceptable distributions of the payoff of the grand coalition. Distributions where a player receives less than it could obtain on its own, without cooperating...

 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.

Properties

  • A stable set may or may not exist , and if it exists it is typically not unique . 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
    Core (economics)
    The core is the set of feasible allocations that cannot be improved upon by a subset of the economy's consumers. 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...

     .
  • A positive fraction of cooperative games have stable sets which discriminate players. In such sets at least of the discriminated players are excluded .

The core

Let be a game. The core
Core (economics)
The core is the set of feasible allocations that cannot be improved upon by a subset of the economy's consumers. 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...

 of is the set of payoff vectors


In words, the core is the set of imputations
Imputation (game theory)
In fully cooperative games players act efficiently when they form a single coalition, the grand coalition. The focus of the game is to find acceptable distributions of the payoff of the grand coalition. Distributions where a player receives less than it could obtain on its own, without cooperating...

 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
    Core (economics)
    The core is the set of feasible allocations that cannot be improved upon by a subset of the economy's consumers. 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...

     of a game may be empty (see the Bondareva-Shapley theorem
    Bondareva-Shapley theorem
    In game theory, the Bondareva–Shapley theorem describes a necessary and sufficient condition for the non-emptiness of the core of a cooperative game. 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 with non-empty cores are called balanced.
  • If it is non-empty, the core does not necessarily contain a unique vector.
  • The core
    Core (economics)
    The core is the set of feasible allocations that cannot be improved upon by a subset of the economy's consumers. 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...

     is contained in any stable set, and if the core is stable it is the unique stable set (see 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
Nakamura number
In cooperative game theory and social choice theory, the Nakamura number measures the degree of rationalityof preference aggregation rules , such as voting rules....

 for details.)

The strong epsilon-core

Because the core
Core (economics)
The core is the set of feasible allocations that cannot be improved upon by a subset of the economy's consumers. 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...

 may be empty, a generalization was introduced in . 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
Core (economics)
The core is the set of feasible allocations that cannot be improved upon by a subset of the economy's consumers. 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...

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

The Shapley value

The Shapley value is the unique payoff vector that is efficient, symmetric, additive, and assigns zero payoffs to dummy players. It was introduced by Lloyd Shapley
Lloyd Shapley
Lloyd Stowell Shapley is a distinguished American mathematician and economist. He is a Professor Emeritus at University of California, Los Angeles, affiliated with departments of Mathematics and Economics...

 . The Shapley value of a superadditive game is individually rational, but this is not true in general .

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 is 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
Imputation (game theory)
In fully cooperative games players act efficiently when they form a single coalition, the grand coalition. The focus of the game is to find acceptable distributions of the payoff of the grand coalition. Distributions where a player receives less than it could obtain on its own, without cooperating...

 
x that satisfy
  • , and


for every pair of players
i and j. Intuitively, player i has more bargaining power than player j with respect to imputation
Imputation (game theory)
In fully cooperative games players act efficiently when they form a single coalition, the grand coalition. The focus of the game is to find acceptable distributions of the payoff of the grand coalition. Distributions where a player receives less than it could obtain on its own, without cooperating...

 
x if , but player j is immune to player is threats if , because he can obtain this payoff on his own. The kernel contains all imputations
Imputation (game theory)
In fully cooperative games players act efficiently when they form a single coalition, the grand coalition. The focus of the game is to find acceptable distributions of the payoff of the grand coalition. Distributions where a player receives less than it could obtain on its own, without cooperating...

 where no player has this bargaining power over another. This solution concept was first introduced in .

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
Core (economics)
The core is the set of feasible allocations that cannot be improved upon by a subset of the economy's consumers. 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...

 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
Imputation (game theory)
In fully cooperative games players act efficiently when they form a single coalition, the grand coalition. The focus of the game is to find acceptable distributions of the payoff of the grand coalition. Distributions where a player receives less than it could obtain on its own, without cooperating...

, based on this ordering. This solution concept was first introduced in .

Although the definition of the nucleolus seems abstract, 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 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 for details.)

Convex cooperative games

Introduced by Shapley
Lloyd Shapley
Lloyd Stowell Shapley is a distinguished American mathematician and economist. He is a Professor Emeritus at University of California, Los Angeles, affiliated with departments of Mathematics and Economics...

 in , convex cooperative games capture the intuitive property some games have of "snowballing". Specifically, a game is convex if its characteristic function is supermodular
Supermodular
In mathematics, a functionf\colon R^k \to Ris supermodular iff + f \geq f + ffor all x, y \isin Rk, where x \vee y denotes the componentwise maximum and x \wedge y the componentwise minimum of x and y.If −f is supermodular then f is called submodular, and if the inequality is changed to an...

:


It can be shown (see, e.g., Section V.1 of ) that the supermodular
Supermodular
In mathematics, a functionf\colon R^k \to Ris supermodular iff + f \geq f + ffor all x, y \isin Rk, where x \vee y denotes the componentwise maximum and x \wedge y the componentwise minimum of x and y.If −f is supermodular then f is called submodular, and if the inequality is changed to an...

ity of is equivalent to


that is, "the incentives for joining a coalition increase as the coalition grows" , 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:
  • Supermodularity trivially implies superadditivity.
  • Convex games are totally balanced: The core
    Core (economics)
    The core is the set of feasible allocations that cannot be improved upon by a subset of the economy's consumers. 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...

     of a convex game is non-empty, and since any subgame of a convex game is convex, the core
    Core (economics)
    The core is the set of feasible allocations that cannot be improved upon by a subset of the economy's consumers. 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...

     of any subgame is also non-empty.
  • A convex game has a unique stable set that coincides with its core
    Core (economics)
    The core is the set of feasible allocations that cannot be improved upon by a subset of the economy's consumers. 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...

    .
  • The Shapley value
    Shapley value
    In game theory, the Shapley value, named in honour of Lloyd Shapley, who introduced it in 1953, is a solution concept in cooperative game theory. To each cooperative game it assigns a unique distribution of a total surplus generated by the coalition of all players...

     of a convex game is the center of gravity of its core
    Core (economics)
    The core is the set of feasible allocations that cannot be improved upon by a subset of the economy's consumers. 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...

    .
  • An extreme point
    Extreme point
    In mathematics, an extreme point of a convex set S in a real vector space is a point in S which does not lie in any open line segment joining two points of S...

     (vertex) of the core
    Core (economics)
    The core is the set of feasible allocations that cannot be improved upon by a subset of the economy's consumers. 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...

     can be found in polynomial time using the greedy algorithm
    Greedy algorithm
    A greedy algorithm is any algorithm that follows the problem solving heuristic of making the locally optimal choice at each stagewith the hope of finding the global optimum....

    : Let be a permutation
    Permutation
    In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...

     of the players, and let be the set of players ordered through in , for any , with . Then the payoff defined by is a vertex of the core
    Core (economics)
    The core is the set of feasible allocations that cannot be improved upon by a subset of the economy's consumers. 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...

     of . Any vertex of the core
    Core (economics)
    The core is the set of feasible allocations that cannot be improved upon by a subset of the economy's consumers. 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...

     can be constructed in this way by choosing an appropriate permutation
    Permutation
    In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...

     .

Similarities and differences with combinatorial optimization
Combinatorial optimization
In applied mathematics and theoretical computer science, combinatorial optimization is a topic that consists of finding an optimal object from a finite set of objects. In many such problems, exhaustive search is not feasible...

Submodular and supermodular
Supermodular
In mathematics, a functionf\colon R^k \to Ris supermodular iff + f \geq f + ffor all x, y \isin Rk, where x \vee y denotes the componentwise maximum and x \wedge y the componentwise minimum of x and y.If −f is supermodular then f is called submodular, and if the inequality is changed to an...

 set functions are also studied in combinatorial optimization
Combinatorial optimization
In applied mathematics and theoretical computer science, combinatorial optimization is a topic that consists of finding an optimal object from a finite set of objects. In many such problems, exhaustive search is not feasible...

. Many of the results in have analogues in , where submodular functions were first presented as generalizations of matroid
Matroid
In combinatorics, a branch of mathematics, a matroid or independence structure is a structure that captures the essence of a notion of "independence" that generalizes linear independence in vector spaces....

s. In this context, the core
Core (economics)
The core is the set of feasible allocations that cannot be improved upon by a subset of the economy's consumers. 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...

 of a convex cost game is called the base polyhedron, because its elements generalize base properties of matroid
Matroid
In combinatorics, a branch of mathematics, a matroid or independence structure is a structure that captures the essence of a notion of "independence" that generalizes linear independence in vector spaces....

s.

However, the optimization community generally considers submodular functions to be the discrete analogues of convex functions , because the minimization of both types of functions is computationally tractable. Unfortunately, this conflicts directly with Shapley's
Lloyd Shapley
Lloyd Stowell Shapley is a distinguished American mathematician and economist. He is a Professor Emeritus at University of California, Los Angeles, affiliated with departments of Mathematics and Economics...

 original definition of supermodular
Supermodular
In mathematics, a functionf\colon R^k \to Ris supermodular iff + f \geq f + ffor all x, y \isin Rk, where x \vee y denotes the componentwise maximum and x \wedge y the componentwise minimum of x and y.If −f is supermodular then f is called submodular, and if the inequality is changed to an...

 functions as "convex".

See also

  • Consensus decision-making
    Consensus decision-making
    Consensus decision-making is a group decision making process that seeks the consent, not necessarily the agreement, of participants and the resolution of objections. Consensus is defined by Merriam-Webster as, first, general agreement, and second, group solidarity of belief or sentiment. It has its...

  • Coordination game
    Coordination game
    In game theory, coordination games are a class of games with multiple pure strategy Nash equilibria in which players choose the same or corresponding strategies...

  • Intra-household bargaining
    Intra-household bargaining
    Intra-household bargaining refers to negotiations that occur between members of a household in order to arrive at decisions regarding the household unit....

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK