Editing Coordination game

{{Short description|Simultaneous game found in game theory}}
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 equilibrium|Nash equilibria]] in which players choose matching strategies. Figure 1 shows a 2-player example. 

{| class="wikitable" style="background:white;color:maroon;text-align:center;float:right;"  
|     style="background:white; border:1px solid white;" colspan="2" rowspan="2"|      ||  style="background:White; color:black; border:1px solid white;  font-weight:bold;" align="center" colspan="2"| Player 2     <tr>
|     style="color:cadetblue;"|Left||style="color:cadetblue;"|Right<tr>
|     style="background:white; color:black; border:1px solid white; font-weight:bold;"  valign="center" rowspan="2"|Player 1 || style="color:cadetblue;" align="left"|Up || 2,4  || 1,3<tr>
|     style="color:cadetblue;" align="left"|Down || 1,3  || 2,4<tr>
| style="background:white; border:1px solid white;"  colspan="4"|    <tr>
| style="background:white; border:1px solid white;"  colspan="4"|    <tr>
|  style="background:white; border:1px solid white;" align="left" colspan="4"|  &nbsp;Figure 1: Payoffs for a Coordination Game (Player 1, Player 2)  <tr>
  |}

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|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 efficiency|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.<ref>{{Cite web|title=Assurance Game - P2P Foundation|url=https://wiki.p2pfoundation.net/Assurance_Game#:~:text=Definition,to%20Cooperate%20as%20well.%22|access-date=2021-04-23|website=wiki.p2pfoundation.net}}</ref> 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.<ref>{{Cite web|title=Assurance game - Game Theory .net|url=https://www.gametheory.net/dictionary/Games/AssuranceGame.html|access-date=2021-04-23|website=www.gametheory.net}}</ref> 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]].<ref>{{Cite web|title=Definition of Coordination Game {{!}} Higher Rock Education|url=https://www.higherrockeducation.org/glossary-of-terms/coordination-game|access-date=2021-04-23|website=www.higherrockeducation.org}}</ref>

{| style="margin:auto;"
|-
| [[File:Pure Coordination.png|center|frame|Fig. 2 ''Pure Coordination'']]
| [[File:Contribute, Defect.png|center|frame|Fig.3 ''Assurance Game'']]
|-
| [[File:Battle of the Sexes.png|center|frame|Fig. 4 ''Battle of the Sexes'']]
| [[File:Stag Hunt.png|center|frame|Fig. 5 ''Stag Hunt'']]
|}

This is different in another type of coordination game commonly called [[Battle of the sexes (game theory)|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.<ref>{{Cite web|title=Game theory II: Battle of the sexes {{!}} Policonomics|url=https://policonomics.com/lp-game-theory2-battle-of-the-sexes/|access-date=2021-04-26|language=en-US}}</ref>

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.<ref>{{Cite web|title=Game theory II: Battle of the sexes {{!}} Policonomics|url=https://policonomics.com/lp-game-theory2-battle-of-the-sexes/|access-date=2021-04-23|language=en-US}}</ref> 

=== Voluntary standards ===

In [[social sciences]], a voluntary standard (when characterized also as [[De facto standard|''de facto'' standard]]) is a typical solution to a coordination problem.<ref name="Ulmann">{{cite book|author=Edna Ullmann-Margalit|title=The Emergence of Norms|url=https://archive.org/details/emergenceofnorms0024ullm|date=1977|publisher=Oxford University Press|isbn=978-0-19-824411-0|url-access=registration}}</ref> 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. <br/>In contrast, an obligation standard (enforced by law as "''[[de jure]]'' standard") is a solution to the [[prisoner's dilemma|prisoner's problem]].<ref name="Ulmann" />

== Mixed strategy Nash equilibrium ==

Coordination games also have [[mixed strategy]] [[Nash equilibrium|Nash equilibria]]. In the generic coordination game above, a mixed Nash equilibrium is given by probabilities p&nbsp;= (d-b)/(a+d-b-c) to play Up and 1-p to play Down for player 1, and q&nbsp;= (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).

[[File:Letter Coordination Game.png|left|Fig 6. ''Coordination Game'' |thumb]]


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 [[best response#Coordination games|reaction correspondences]] for 2×2 coordination games are shown in Fig. 7.
[[Image:Reaction-correspondence-stag-hunt.jpg|150px|thumbnail|Figure 7 - [[best response|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 [[Payoff dominance|higher payoffs]], be [[Salience (neuroscience)|naturally more salient]], [[wikt:fairness|may be more fair]], or may be [[Risk dominance|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.<ref>{{Cite journal|last1=Bortolotti|first1=Stefania|last2=Devetag|first2=Giovanna|last3=Ortmann|first3=Andreas|date=2016-01-01|title=Group incentives or individual incentives? A real-effort weak-link experiment|url=http://econpapers.repec.org/article/eeejoepsy/v_3a56_3ay_3a2016_3ai_3ac_3ap_3a60-73.htm|journal=Journal of Economic Psychology|volume=56|issue=C|pages=60–73|issn=0167-4870|doi=10.1016/j.joep.2016.05.004|url-access=subscription}}</ref>

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|stag-hunt]] games.<ref>{{Cite journal|last1=Devetag|first1=Giovanna|last2=Ortmann|first2=Andreas|date=2006-08-15|title=When and Why? A Critical Survey on Coordination Failure in the Laboratory|ssrn=924186|location=Rochester, NY|publisher=Social Science Research Network}}</ref>

== Other games with externalities ==

Coordination games are closely linked to the economic concept of [[externality|externalities]], and in particular [[network externality|positive network externalities]], the benefit reaped from being in the same [[network (mathematics)|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 (game)|Chicken]] (also known as [[Hawk-Dove game]]). Using the payoff matrix in Figure 1, a game is an anti-coordination game if B&nbsp;&gt;&nbsp;A and C&nbsp;&gt;&nbsp;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&nbsp;&gt;&nbsp;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 (California)|U.S. Route 101]] or [[Interstate 280 (California)|Interstate 280]] from [[San Francisco, California|San Francisco]] to [[San Jose, California|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&nbsp;&gt;&nbsp;B, C&nbsp;&lt;&nbsp;D, while a&nbsp;&lt;&nbsp;b, c&nbsp;&gt;&nbsp;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 ==

* [[Collective action]]
* [[Consensus decision-making]]
* [[Cooperative game theory|Cooperative game]]
* [[Coordination failure (economics)]]
* [[Equilibrium selection]]
* [[Non-cooperative game]]
* [[Self-fulfilling prophecy]]
* [[Strategic complements]]
* [[Social dilemma]]
* [[Supermodular]]
* [[General equilibrium#Uniqueness|Uniqueness or multiplicity of equilibrium]]

== References ==
{{Reflist|refs=Science Direct, "Coordination Game". www.sciencedirect.com/topics/computer-science/coordination-game}}

Other suggested literature:

* [[Russell W. Cooper (economist)|Russell Cooper]]: ''Coordination Games'', Cambridge: Cambridge University Press, 1998 ({{ISBN|0-521-57896-5}}).
* [[Avinash Dixit]] & [[Barry Nalebuff]]: ''[[Thinking Strategically: The Competitive Edge in Business, Politics, and Everyday Life]]'', New York: Norton, 1991 ({{ISBN|0-393-32946-1}}).
* Robert Gibbons: ''Game Theory for Applied Economists'', Princeton, New Jersey: Princeton University Press, 1992 ({{ISBN|0-691-00395-5}}).
* [[David Kellogg Lewis]]: ''Convention: A Philosophical Study'',  Oxford:  Blackwell, 1969 ({{ISBN|0-631-23257-5}}).
* Martin J. Osborne & [[Ariel Rubinstein]]: ''A Course in Game Theory'', Cambridge, Massachusetts: MIT Press, 1994 ({{ISBN|0-262-65040-1}}).
* [[Thomas Schelling]]: ''The Strategy of Conflict'', Cambridge, Massachusetts: Harvard University Press, 1960 ({{ISBN|0-674-84031-3}}).
* [[Thomas Schelling]]: ''Micromotives and Macrobehavior'', New York: Norton, 1978 ({{ISBN|0-393-32946-1}}).
<!-- going to cited-refs * Edna Ullmann-Margalit: ''The Emergence of Norms'', Oxford Un. Press, 1977. (or Clarendon Press 1978). -->
* Adrian Piper: [https://www.jstor.org/stable/2185102 review of 'The Emergence of Norms']{{subscription required}} in The Philosophical Review, vol. 97, 1988, pp.&nbsp;99–107.
* Bortolotti, Stefania; Devetag, Giovanna; Ortmann, Andreas (2016-01-01). [http://econpapers.repec.org/article/eeejoepsy/v_3a56_3ay_3a2016_3ai_3ac_3ap_3a60-73.htm "Group incentives or individual incentives? A real-effort weak-link experiment"].''Journal of Economic Psychology''. '''56''' (C): 60–73. [[International Standard Serial Number|ISSN]] [https://www.worldcat.org/issn/0167-4870 0167-4870]
* 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.
{{Game theory}}

[[Category:Non-cooperative games]]