Coordination game

Last updated

A coordination game is a type of simultaneous game found in game theory. It describes the situation where a player will earn a higher payoff when they select the same course of action as another player. The game is not one of pure conflict, which results in multiple pure strategy Nash equilibria in which players choose matching strategies. Figure 1 shows a 2-player example.

Contents

Player 2
LeftRight
Player 1Up2,41,3
Down1,32,4
 Figure 1: Payoffs for a Coordination Game (Player 1, Player 2)

Both (Up, Left) and (Down, Right) are Nash equilibria. If the players expect (Up, Left) to be played, then player 1 thinks their payoff would fall from 2 to 1 if they deviated to Down, and player 2 thinks their payoff would fall from 4 to 3 if they chose Right. If the players expect (Down, Right), player 1 thinks their payoff would fall from 2 to 1 if they deviated to Up, and player 2 thinks their payoff would fall from 4 to 3 if they chose Left. A player's optimal move depends on what they expect the other player to do, and they both do better if they coordinate than if they played an off-equilibrium combination of actions. This setup can be extended to more than two strategies or two players.

Examples

A typical case for a coordination game is choosing the sides of the road upon which to drive, a social standard which can save lives if it is widely adhered to. In a simplified example, assume that two drivers meet on a narrow dirt road. Both have to swerve in order to avoid a head-on collision. If both execute the same swerving maneuver they will manage to pass each other, but if they choose differing maneuvers they will collide. In the payoff matrix in Fig. 2, successful passing is represented by a payoff of 8, and a collision by a payoff of 0. In this case there are two pure Nash equilibria: either both swerve to the left, or both swerve to the right. In this example, it doesn't matter which side both players pick, as long as they both pick the same. Both solutions are Pareto efficient. This game is called a pure coordination game . This is not true for all coordination games, as the assurance game in Fig. 3 shows.

An assurance game describes the situation where neither player can offer a sufficient amount if they contribute alone, thus player 1 should defect from playing if player 2 defects. However, if Player 2 opts to contribute then player 1 should contribute also. [1] An assurance game is commonly referred to as a “stag hunt” (Fig.5), which represents the following scenario. Two hunters can choose to either hunt a stag together (which provides the most economically efficient outcome) or they can individually hunt a Rabbit. Hunting Stags is challenging and requires cooperation. If the two hunters do not cooperate the chances of success is minimal. Thus, the scenario where both hunters choose to coordinate will provide the most beneficial output for society. A common problem associated with the stag hunt is the amount of trust required to achieve this output. [2] Fig. 5 shows a situation in which both players (hunters) can benefit if they cooperate (hunting a stag). As you can see, cooperation might fail, because each hunter has an alternative which is safer because it does not require cooperation to succeed (hunting a hare). This example of the potential conflict between safety and social cooperation is originally due to Jean-Jacques Rousseau. [3]

Fig. 2 Pure Coordination Pure Coordination.png
Fig. 2 Pure Coordination
Fig.3 Assurance Game Contribute, Defect.png
Fig.3 Assurance Game
Fig. 4 Battle of the Sexes Battle of the Sexes.png
Fig. 4 Battle of the Sexes
Fig. 5 Stag Hunt Stag Hunt.png
Fig. 5 Stag Hunt

This is different in another type of coordination game commonly called battle of the sexes (or conflicting interest coordination), as seen in Fig. 4. In this game both players prefer engaging in the same activity over going alone, but their preferences differ over which activity they should engage in. Assume that a couple argues over what to do on the weekend. Both know that they will increase their utility by spending the weekend together, however the man prefers to watch a football game and the woman prefers to go shopping. [4]

Since the couple want to spend time together, they will derive no utility by doing an activity separately. If they go shopping, or to football game one person will derive some utility by being with the other person, but won’t derive utility from the activity itself. Unlike the other forms of coordination games described previously, knowing your opponent’s strategy won’t help you decide on your course of action. Due to this there is a possibility that an equilibrium will not be reached. [5]

Voluntary standards

In social sciences, a voluntary standard (when characterized also as de facto standard) is a typical solution to a coordination problem. [6] The choice of a voluntary standard tends to be stable in situations in which all parties can realize mutual gains, but only by making mutually consistent decisions.
In contrast, an obligation standard (enforced by law as " de jure standard") is a solution to the prisoner's problem. [6]

Mixed strategy Nash equilibrium

Coordination games also have mixed strategy Nash equilibria. In the generic coordination game above, a mixed Nash equilibrium is given by probabilities p = (d-b)/(a+d-b-c) to play Up and 1-p to play Down for player 1, and q = (D-C)/(A+D-B-C) to play Left and 1-q to play Right for player 2. Since d > b and d-b < a+d-b-c, p is always between zero and one, so existence is assured (similarly for q).

Fig 6. Coordination Game Letter Coordination Game.png
Fig 6. Coordination Game


In the generic coordination game in Fig. 6, a mixed Nash equilibrium is given by the probabilities:

p = (d-b)/(a+d-b-c),

to play Option A and 1-p to play Option B for player 1, and

q = (D-C)/(A+D-B-C),

to play A and 1-q to play B for player 2. If we look at Fig 1. and apply the same probability equations we obtain the following results:

p = (4-3) / (4+4-3-3) = ½ and,

q = (2-1) / (2+2-1-1) = ½

The reaction correspondences for 2×2 coordination games are shown in Fig. 7.

Figure 7 - Reaction correspondence for 2x2 coordination games. Nash equilibria are at points where the two players' correspondences cross Reaction-correspondence-stag-hunt.jpg
Figure 7 - Reaction correspondence for 2x2 coordination games. Nash equilibria are at points where the two players' correspondences cross

The pure Nash equilibria are the points in the bottom left and top right corners of the strategy space, while the mixed Nash equilibrium lies in the middle, at the intersection of the dashed lines.

Unlike the pure Nash equilibria, the mixed equilibrium is not an evolutionarily stable strategy (ESS). The mixed Nash equilibrium is also Pareto dominated by the two pure Nash equilibria (since the players will fail to coordinate with non-zero probability), a quandary that led Robert Aumann to propose the refinement of a correlated equilibrium.

Coordination and equilibrium selection

Games like the driving example above have illustrated the need for solution to coordination problems. Often we are confronted with circumstances where we must solve coordination problems without the ability to communicate with our partner. Many authors have suggested that particular equilibria are focal for one reason or another. For instance, some equilibria may give higher payoffs, be naturally more salient, may be more fair, or may be safer. Sometimes these refinements conflict, which makes certain coordination games especially complicated and interesting (e.g. the Stag hunt, in which {Stag,Stag} has higher payoffs, but {Hare,Hare} is safer).

Experimental results

Coordination games have been studied in laboratory experiments. One such experiment by Bortolotti, Devetag, and Andreas Ortmann was a weak-link experiment in which groups of individuals were asked to count and sort coins in an effort to measure the difference between individual and group incentives. Players in this experiment received a payoff based on their individual performance as well as a bonus that was weighted by the number of errors accumulated by their worst performing team member. Players also had the option to purchase more time, the cost of doing so was subtracted from their payoff. While groups initially failed to coordinate, researchers observed about 80% of the groups in the experiment coordinated successfully when the game was repeated. [7]

When academics talk about coordination failure, most cases are that subjects achieve risk dominance rather than payoff dominance. Even when payoffs are better when players coordinate on one equilibrium, many times people will choose the less risky option where they are guaranteed some payoff and end up at an equilibrium that has sub-optimal payoff. Players are more likely to fail to coordinate on a riskier option when the difference between taking the risk or the safe option is smaller. The laboratory results suggest that coordination failure is a common phenomenon in the setting of order-statistic games and stag-hunt games. [8]

Other games with externalities

Coordination games are closely linked to the economic concept of externalities, and in particular positive network externalities, the benefit reaped from being in the same network as other agents. Conversely, game theorists have modeled behavior under negative externalities where choosing the same action creates a cost rather than a benefit. The generic term for this class of game is anti-coordination game. The best-known example of a 2-player anti-coordination game is the game of Chicken (also known as Hawk-Dove game). Using the payoff matrix in Figure 1, a game is an anti-coordination game if B > A and C > D for row-player 1 (with lowercase analogues b > d and c > a for column-player 2). {Down, Left} and {Up, Right} are the two pure Nash equilibria. Chicken also requires that A > C, so a change from {Up, Left} to {Up, Right} improves player 2's payoff but reduces player 1's payoff, introducing conflict. This counters the standard coordination game setup, where all unilateral changes in a strategy lead to either mutual gain or mutual loss.

The concept of anti-coordination games has been extended to multi-player situation. A crowding game is defined as a game where each player's payoff is non-increasing over the number of other players choosing the same strategy (i.e., a game with negative network externalities). For instance, a driver could take U.S. Route 101 or Interstate 280 from San Francisco to San Jose. While 101 is shorter, 280 is considered more scenic, so drivers might have different preferences between the two independent of the traffic flow. But each additional car on either route will slightly increase the drive time on that route, so additional traffic creates negative network externalities, and even scenery-minded drivers might opt to take 101 if 280 becomes too crowded. A congestion game is a crowding game in networks. The minority game is a game where the only objective for all players is to be part of smaller of two groups. A well-known example of the minority game is the El Farol Bar problem proposed by W. Brian Arthur.

A hybrid form of coordination and anti-coordination is the discoordination game, where one player's incentive is to coordinate while the other player tries to avoid this. Discoordination games have no pure Nash equilibria. In Figure 1, choosing payoffs so that A > B, C < D, while a < b, c > d, creates a discoordination game. In each of the four possible states either player 1 or player 2 are better off by switching their strategy, so the only Nash equilibrium is mixed. The canonical example of a discoordination game is the matching pennies game.

See also

Related Research Articles

An evolutionarily stable strategy (ESS) is a strategy that is impermeable when adopted by a population in adaptation to a specific environment, that is to say it cannot be displaced by an alternative strategy which may be novel or initially rare. Introduced by John Maynard Smith and George R. Price in 1972/3, it is an important concept in behavioural ecology, evolutionary psychology, mathematical game theory and economics, with applications in other fields such as anthropology, philosophy and political science.

In game theory, the Nash equilibrium, named after the mathematician John Nash, is the most common way to define the solution of a non-cooperative game involving two or more players. In a Nash equilibrium, each player is assumed to know the equilibrium strategies of the other players, and no one has anything to gain by changing only one's own strategy. The principle of Nash equilibrium dates back to the time of Cournot, who in 1838 applied it to competing firms choosing outputs.

The game of chicken, also known as the hawk-dove game or snowdrift game, is a model of conflict for two players in game theory. The principle of the game is that while the ideal outcome is for one player to yield, individuals try to avoid it out of pride, not wanting to look like "chickens." Each player taunts the other to increase the risk of shame in yielding. However, when one player yields, the conflict is avoided, and the game essentially ends.

In game theory, the best response is the strategy which produces the most favorable outcome for a player, taking other players' strategies as given. The concept of a best response is central to John Nash's best-known contribution, the Nash equilibrium, the point at which each player in a game has selected the best response to the other players' strategies.

In game theory, the centipede game, first introduced by Robert Rosenthal in 1981, is an extensive form game in which two players take turns choosing either to take a slightly larger share of an increasing pot, or to pass the pot to the other player. The payoffs are arranged so that if one passes the pot to one's opponent and the opponent takes the pot on the next round, one receives slightly less than if one had taken the pot on this round, but after an additional switch the potential payoff will be higher. Therefore, although at each round a player has an incentive to take the pot, it would be better for them to wait. Although the traditional centipede game had a limit of 100 rounds, any game with this structure but a different number of rounds is called a centipede game.

Matching pennies is the name for a simple game used in game theory. It is played between two players, Even and Odd. Each player has a penny and must secretly turn the penny to heads or tails. The players then reveal their choices simultaneously. If the pennies match, then Even keeps both pennies, so wins one from Odd. If the pennies do not match Odd keeps both pennies, so receives one from Even.

In game theory, a player's strategy is any of the options which they choose in a setting where the optimal outcome depends not only on their own actions but on the actions of others. The discipline mainly concerns the action of a player in a game affecting the behavior or actions of other players. Some examples of "games" include chess, bridge, poker, monopoly, diplomacy or battleship. A player's strategy will determine the action which the player will take at any stage of the game. In studying game theory, economists enlist a more rational lens in analyzing decisions rather than the psychological or sociological perspectives taken when analyzing relationships between decisions of two or more parties in different disciplines.

In game theory, the stag hunt, sometimes referred to as the assurance game, trust dilemma or common interest game, describes a conflict between safety and social cooperation. The stag hunt problem originated with philosopher Jean-Jacques Rousseau in his Discourse on Inequality. In the most common account of this dilemma, which is quite different from Rousseau's, two hunters must decide separately, and without the other knowing, whether to hunt a stag or a hare. However, both hunters know the only way to successfully hunt a stag is with the other's help. One hunter can catch a hare alone with less effort and less time, but it is worth far less than a stag and has much less meat. It would be much better for each hunter, acting individually, to give up total autonomy and minimal risk, which brings only the small reward of the hare. Instead, each hunter should separately choose the more ambitious and far more rewarding goal of getting the stag, thereby giving up some autonomy in exchange for the other hunter's cooperation and added might. This situation is often seen as a useful analogy for many kinds of social cooperation, such as international agreements on climate change.

In game theory, the battle of the sexes is a two-player coordination game that also involves elements of conflict. The game was introduced in 1957 by R. Duncan Luce and Howard Raiffa in their classic book, Games and Decisions. Some authors prefer to avoid assigning sexes to the players and instead use Players 1 and 2, and some refer to the game as Bach or Stravinsky, using two concerts as the two events. The game description here follows Luce and Raiffa's original story.

In game theory, strategic dominance occurs when one strategy is better than another strategy for one player, no matter how that player's opponents may play. Many simple games can be solved using dominance. The opposite, intransitivity, occurs in games where one strategy may be better or worse than another strategy for one player, depending on how the player's opponents may play.

In game theory, trembling hand perfect equilibrium is a type of refinement of a Nash equilibrium that was first proposed by Reinhard Selten. A trembling hand perfect equilibrium is an equilibrium that takes the possibility of off-the-equilibrium play into account by assuming that the players, through a "slip of the hand" or tremble, may choose unintended strategies, albeit with negligible probability.

In game theory, a repeated game is an extensive form game that consists of a number of repetitions of some base game. The stage game is usually one of the well-studied 2-person games. Repeated games capture the idea that a player will have to take into account the impact of their current action on the future actions of other players; this impact is sometimes called their reputation. Single stage game or single shot game are names for non-repeated games.

In game theory, a subgame perfect equilibrium is a refinement of a Nash equilibrium used in dynamic games. A strategy profile is a subgame perfect equilibrium if it represents a Nash equilibrium of every subgame of the original game. Informally, this means that at any point in the game, the players' behavior from that point onward should represent a Nash equilibrium of the continuation game, no matter what happened before. Every finite extensive game with perfect recall has a subgame perfect equilibrium. Perfect recall is a term introduced by Harold W. Kuhn in 1953 and "equivalent to the assertion that each player is allowed by the rules of the game to remember everything he knew at previous moves and all of his choices at those moves".

Risk dominance and payoff dominance are two related refinements of the Nash equilibrium (NE) solution concept in game theory, defined by John Harsanyi and Reinhard Selten. A Nash equilibrium is considered payoff dominant if it is Pareto superior to all other Nash equilibria in the game. When faced with a choice among equilibria, all players would agree on the payoff dominant equilibrium since it offers to each player at least as much payoff as the other Nash equilibria. Conversely, a Nash equilibrium is considered risk dominant if it has the largest basin of attraction. This implies that the more uncertainty players have about the actions of the other player(s), the more likely they will choose the strategy corresponding to it.

Equilibrium selection is a concept from game theory which seeks to address reasons for players of a game to select a certain equilibrium over another. The concept is especially relevant in evolutionary game theory, where the different methods of equilibrium selection respond to different ideas of what equilibria will be stable and persistent for one player to play even in the face of deviations of the other players. This is important because there are various equilibrium concepts, and for many particular concepts, such as the Nash equilibrium, many games have multiple equilibria.

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.

<span class="mw-page-title-main">Simultaneous game</span>

In game theory, a simultaneous game or static game is a game where each player chooses their action without knowledge of the actions chosen by other players. Simultaneous games contrast with sequential games, which are played by the players taking turns. In other words, both players normally act at the same time in a simultaneous game. Even if the players do not act at the same time, both players are uninformed of each other's move while making their decisions. Normal form representations are usually used for simultaneous games. Given a continuous game, players will have different information sets if the game is simultaneous than if it is sequential because they have less information to act on at each step in the game. For example, in a two player continuous game that is sequential, the second player can act in response to the action taken by the first player. However, this is not possible in a simultaneous game where both players act at the same time.

In algorithmic game theory, a succinct game or a succinctly representable game is a game which may be represented in a size much smaller than its normal form representation. Without placing constraints on player utilities, describing a game of players, each facing strategies, requires listing utility values. Even trivial algorithms are capable of finding a Nash equilibrium in a time polynomial in the length of such a large input. A succinct game is of polynomial type if in a game represented by a string of length n the number of players, as well as the number of strategies of each player, is bounded by a polynomial in n.

The Berge equilibrium is a game theory solution concept named after the mathematician Claude Berge. It is similar to the standard Nash equilibrium, except that it aims to capture a type of altruism rather than purely non-cooperative play. Whereas a Nash equilibrium is a situation in which each player of a strategic game ensures that they personally will receive the highest payoff given other players' strategies, in a Berge equilibrium every player ensures that all other players will receive the highest payoff possible. Although Berge introduced the intuition for this equilibrium notion in 1957, it was only formally defined by Vladislav Iosifovich Zhukovskii in 1985, and it was not in widespread use until half a century after Berge originally developed it.

References

  1. ↑ "Assurance Game - P2P Foundation". wiki.p2pfoundation.net. Retrieved 2021-04-23.
  2. ↑ "Assurance game - Game Theory .net". www.gametheory.net. Retrieved 2021-04-23.
  3. ↑ "Definition of Coordination Game | Higher Rock Education". www.higherrockeducation.org. Retrieved 2021-04-23.
  4. ↑ "Game theory II: Battle of the sexes | Policonomics" . Retrieved 2021-04-26.
  5. ↑ "Game theory II: Battle of the sexes | Policonomics" . Retrieved 2021-04-23.
  6. 1 2 Edna Ullmann-Margalit (1977). The Emergence of Norms . Oxford University Press. ISBN   978-0-19-824411-0.
  7. ↑ Bortolotti, Stefania; Devetag, Giovanna; Ortmann, Andreas (2016-01-01). "Group incentives or individual incentives? A real-effort weak-link experiment". Journal of Economic Psychology. 56 (C): 60–73. doi:10.1016/j.joep.2016.05.004. ISSN   0167-4870.
  8. ↑ Devetag, Giovanna; Ortmann, Andreas (2006-08-15). "When and Why? A Critical Survey on Coordination Failure in the Laboratory". Rochester, NY: Social Science Research Network. SSRN   924186.{{cite journal}}: Cite journal requires |journal= (help)

Other suggested literature:

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.