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. 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, such as contract law.
Contents |
Mathematical treatment
A cooperative game is given by specifying a value for every coalition. Mathematically speaking, the game is a function <math> \nu \; : \; \mathcal{P}(N) \; \to \mathbb{R} </math> from the set of coalitions to a set of payments (the characteristic function). The function describes how much collective payoff a set of players can gain by forming a coalition. 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. It is assumed that the empty coalition gains nil.
Properties for characterization
Superadditivity
- Characteristic functions are often assumed to be superadditive.(Owen 1995, p. 213) This means that the joint value of disjoint coalitions is no less than the sum of their values: <math> \nu (A \cup B) \; \ge \; \nu (A) \; + \; \nu (B) </math> if <math>A\cap B = \emptyset</math>.
Monotonicity
- Larger coalitions gain more: <math> A \subseteq B \Rightarrow \nu (A) \le \nu (B) </math>. This follows from superadditivity if payoffs are normalized so singleton coalitions have value zero.
Simple games
A simple game is a special kind of cooperative game, where the payoffs are either 1 or 0, i.e. coalitions are either "winning" or "losing".
- A simple game is called proper, if the complement (opposition) of any winning coalition is losing. It is called strong, if <math> \nu (A) \; = \; 1 \; - \; \nu (N \setminus A) </math>; that is, a coalition is winning if and only if its complement is losing.
- A veto player in a simple game is a player who is included in all winning coalitions. That is, all coalitions not containing the veto player are losing.
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 for cooperative theory
A cooperative game describes payoffs given for coalitions. Players will only join a coalition if they expect to gain from it. So, in order to find what coalitions will actually be created, one needs to estimate both the relative power of different coalitions, as well as the strength of the different players within each coalition.
The stable set
The stable set of a game (also known as the von Neumann-Morgenstern solution (von Neumann & Morgenstern 1944)) is the first solution proposed for games with more than 2 players. A stable set satisfies two properties:
- Internal stability: No alternative in the stable set is dominated by another alternative in the set.
- External stability: All alternatives outside the set are dominated by at least one alternative 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 (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 <math>n-2</math> players. In such sets at least <math>n-3</math> of the discriminated players are excluded (Owen 1995, p. 240.).
The core
The core of a game is a set of vectors allocating payoffs to players, which preserve the following conditions:
- Efficiency: it is assumed that the players form the grand coalition (a coalition containing all players), and so the sum of individual payoffs should equal the value of the grand coalition.
- Strategic stability or balance: no coalition can earn more by defecting from the grand coalition. E.g. no coalition has a value greater than the sum of its members' payoffs.
Note that the core of a game may be empty.
Shapley's value
The kernel
Is a vector allocating payoffs to players which is:
- Efficient
- Personally reasonable
Some examples of recreational cooperative games
One example is "Stand Up", where a number of individuals sit down, link arms (all facing away from each other) and attempt to stand up. This objective becomes more difficult as the number of players increases. Another is the counting game, where the players, as a group, attempt to count to 20 with no two participants saying the same number twice. In a cooperative version of volleyball, the emphasis is on keeping the ball in the air for as long as possible. Similar games are played with cage balls[1]. Role-playing games are the most common form of recreational cooperative game, where coalition forming (and sometimes coalition disintegration) are an intrinsic part of the game. In such games, the players, who act through persons called "characters", usually strive toward intertwined goals. However, each character has his or her own ambitions, and ultimately, individual goals. Hence conflict between groups of characters often occurs in these games. Cooperative board games are rare, the most famous example perhaps being Reiner Knizia's game Lord of the Rings. Another example is the Days Of Wonder game Shadows Over Camelot. However, many card games and board games can exhibit cooperative behaviour, usually where a group of weak players join forces to halt the progress of a leading player. An example is Diplomacy, a board game in which the forming and breaking of coalitions is the main strategic aspect of play.
References
- Lucas, William F. (1969). "The Proof That a Game May Not Have a Solution". Transactions of the American Mathematical Society 136: 219-229.
- Lucas, William F. (1992), "Von Neumann-Morgenstern Stable Sets", 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).
- Osborne, M.J. and Rubinstein, A. (1994) A Course in Game Theory, MIT Press (see Chapters 13,14,15)
- Owen, Guillermo (1995), Game Theory (3rd ed.), San Diego: Academic Press, ISBN 0-12-531151-6
- von Neumann, John & Morgenstern, Oskar (1944), Theory of Games and Economic Behavior, Princeton: Princeton University Press
See also
External links
- Cooperative Games - Ultimate Camp Resource- Cooperative Games and activities for various ages and activity levels.
