In
game theoryGame theory is a branch of applied mathematics that is used in the social sciences, most notably in economics, as well as in biology, engineering, political science, international relations, computer science, and philosophy...
,
coordination games are a class of games with multiple pure strategy
Nash equilibriaIn game theory, Nash equilibrium is a solution concept of a game involving two or more players, in which each player is assumed to know the equilibrium strategies of the other players, and no player has anything to gain by changing only his or her own strategy unilaterally...
in which players choose the same or
correspondingIn mathematics, a bijection, or a bijective function is a function f from a set X to a set Y with the property that, for every y in Y, there is exactly one x in X such that f = y and no unmapped element remains in both X and Y.Alternatively, f is bijective if it is a one-to-one correspondence...
strategiesA strategy is a plan of action designed to achieve a particular goal. The word strategy has military connotations, because it derives from the Greek word for general....
. Coordination games are a formalization of the idea of a
coordination problem, which is widespread in the
social sciencesThe social sciences are the fields of scientific knowledge and academic scholarship that study social groups and, more generally, human society. The social sciences initially were constituted of five fields: Jurisprudence and Amendment of the Law; Education; Health; Economy and Trade; Art...
, including
economicsEconomics is the social science that studies the production, distribution, and consumption of goods and services. The term economics comes from the Ancient Greek from + , hence "rules of the house"...
, meaning situations in which all parties can realize mutual gains, but only by making mutually consistent decisions. A common application is the
choiceDecision making can be regarded as an outcome of mental processes leading to the selection of a course of action among several alternatives. Every decision making process produces a final choice...
of technological
standardA technical standard is an established norm or requirement. It is usually a formal document that establishes uniform engineering or technical criteria, methods, processes and practices....
s.
For a classic example of a coordination game, consider the 2-player, 2-strategy game, with the payoff matrix shown on the right (Fig.
In
game theoryGame theory is a branch of applied mathematics that is used in the social sciences, most notably in economics, as well as in biology, engineering, political science, international relations, computer science, and philosophy...
,
coordination games are a class of games with multiple pure strategy
Nash equilibriaIn game theory, Nash equilibrium is a solution concept of a game involving two or more players, in which each player is assumed to know the equilibrium strategies of the other players, and no player has anything to gain by changing only his or her own strategy unilaterally...
in which players choose the same or
correspondingIn mathematics, a bijection, or a bijective function is a function f from a set X to a set Y with the property that, for every y in Y, there is exactly one x in X such that f = y and no unmapped element remains in both X and Y.Alternatively, f is bijective if it is a one-to-one correspondence...
strategiesA strategy is a plan of action designed to achieve a particular goal. The word strategy has military connotations, because it derives from the Greek word for general....
. Coordination games are a formalization of the idea of a
coordination problem, which is widespread in the
social sciencesThe social sciences are the fields of scientific knowledge and academic scholarship that study social groups and, more generally, human society. The social sciences initially were constituted of five fields: Jurisprudence and Amendment of the Law; Education; Health; Economy and Trade; Art...
, including
economicsEconomics is the social science that studies the production, distribution, and consumption of goods and services. The term economics comes from the Ancient Greek from + , hence "rules of the house"...
, meaning situations in which all parties can realize mutual gains, but only by making mutually consistent decisions. A common application is the
choiceDecision making can be regarded as an outcome of mental processes leading to the selection of a course of action among several alternatives. Every decision making process produces a final choice...
of technological
standardA technical standard is an established norm or requirement. It is usually a formal document that establishes uniform engineering or technical criteria, methods, processes and practices....
s.
For a classic example of a coordination game, consider the 2-player, 2-strategy game, with the payoff matrix shown on the right (Fig. 1).
If this game is a coordination game, then the following inequalities in payoffs hold for player 1 (rows): A > B, D > C, and for player 2 (columns): a > c, d > b. In this game the strategy profiles {Left, Up} and {Right, Down} are pure Nash equilibria, marked in gray. This setup can be extended for more than two strategies, where strategies are usually sorted so that the Nash equilibria are in the diagonal from top left to bottom right, as well as game with more than two players.
Examples
A typical case for a coordination game is choosing the side 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 swerve to the same side they will manage to pass each other, but if they choose different sides they will collide. In the payoff matrix in Fig. 2, "pass" is represented by a payoff of 10, and "collide" 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 efficientPareto efficiency, or Pareto optimality, is an important concept in economics with broad applications in game theory, engineering and the social sciences. The term is named after Vilfredo Pareto, an Italian economist who used the concept in his studies of economic efficiency and income distribution...
. This is not true for all coordination games, as the
pure coordination game in Fig. 3 shows. Pure (or common interest) coordination is the game where the players both prefer the same Nash equilibrium outcome, here both players prefer partying over both staying at home to watch TV. The {Party, Party} outcome
Pareto dominatesPareto efficiency, or Pareto optimality, is an important concept in economics with broad applications in game theory, engineering and the social sciences. The term is named after Vilfredo Pareto, an Italian economist who used the concept in his studies of economic efficiency and income distribution...
the {Home, Home} outcome, just as both Pareto dominate the other two outcomes, {Party, Home} and {Home, Party}.
This is different in another type of coordination game commonly called
battle of the sexesThe Battle of the Sexes is a two-player coordination game used in game theory. Imagine a couple that agreed to meet this evening, but cannot recall if they will be attending the opera or a football match. The husband would most of all like to go to the football game. The wife would like to go to...
(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. Player 1 prefers that they both party while player 2 prefers that they both stay at home.
Finally, the
stag huntIn game theory, the stag hunt is a game which describes a conflict between safety and social cooperation. Other names for it or its variants include "assurance game", "coordination game", and "trust dilemma". Jean-Jacques Rousseau described a situation in which two individuals go out on a hunt. ...
game in Fig. 5 shows a situation in which both players (hunters) can benefit if they cooperate (hunting a stag). However, 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 RousseauJean Jacques Rousseau was a major philosopher, writer, and composer of the eighteenth-century Enlightenment, whose political philosophy influenced the French Revolution and the development of modern political and educational thought.His novel, Emile: or, On Education, which he considered his most...
.
Mixed Nash equilibrium
Coordination games also have mixed strategy
Nash equilibriaIn game theory, Nash equilibrium is a solution concept of a game involving two or more players, in which each player is assumed to know the equilibrium strategies of the other players, and no player has anything to gain by changing only his or her own strategy unilaterally...
. In the generic coordination game above, a mixed Nash equilibrium is given by probabilities p = (d-c)/(d-c+a-b) to play Up and 1-p to play Down for player 1, and q = (D-C)/(D-C+A-B) to play Left and 1-q to play Right for player 2. Since d > c and d-c < a-b-c+d, p is always between zero and one, so existence is assured (similarly for q).
The reaction correspondences for 2×2 coordination games are shown in Fig. 6.
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 strategyIn game theory and behavioural ecology, an evolutionarily stable strategy is a strategy which, if adopted by a population of players, cannot be invaded by any alternative strategy that is initially rare...
(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 AumannRobert John Aumann is an Israeli/American mathematician and a member of the United States National Academy of Sciences. He is a professor at the Center for the Study of Rationality in the Hebrew University of Jerusalem in Israel...
to propose the refinement of a
correlated equilibriumIn game theory, a correlated equilibrium is a solution concept that is more general than the well known Nash equilibrium. It was first discussed by mathematician Robert Aumann . The idea is that each player chooses her action according to her observation of the value of the same public signal. A...
.
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 salientThe salience of an item – be it an object, a person, a pixel, etc. – is its state or quality of standing out relative to neighboring items...
,
may be more fairFairness or being fair may refer to:* Distributive justice* Equity * Fairness, absence of bias in specific realms:**** In American broadcasting, presentation of controversies in accord with the Fairness Doctrine...
, or may be
saferRisk dominance and payoff dominance are two related refinements of the Nash equilibrium 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...
. Sometimes these refinements conflict, which makes certain coordination games especially complicated and interesting (e.g. the
Stag huntIn game theory, the stag hunt is a game which describes a conflict between safety and social cooperation. Other names for it or its variants include "assurance game", "coordination game", and "trust dilemma". Jean-Jacques Rousseau described a situation in which two individuals go out on a hunt. ...
, in which {Stag,Stag} has higher payoffs, but {Hare,Hare} is safer).
Other games with externalities
Coordination games are closely linked to the economic concept of
externalitiesIn economics, an externality or spillover of an economic transaction is an impact on a party that is not directly involved in the transaction. In such a case, prices do not reflect the full costs or benefits in production or consumption of a product or service...
, and in particular positive network externalities, the benefit reaped from being in the same
networkIn graph theory, a network is a digraph with weighted edges. These networks have become an especially useful concept in analysing the interaction between biology and mathematics...
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
ChickenThe game of Chicken, also known as the Hawk-Dove or Snowdrift game, is an influential model of conflict for two players in game theory...
(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 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 280Interstate 280 is a 57 mile long north-south Interstate Highway in the San Francisco Bay Area of Northern California. It connects San Jose and San Francisco, running along just to the west of the cities of San Francisco Peninsula for most of its route.I-280 from its beginning at King Street...
from
San FranciscoSan Francisco is the fourth most populous city in California and the 12th most populous city in the United States, with a 2008 estimated population of 808,976. It is the eighth most densely populated city in the U.S. and is the financial, cultural, and transportation center of the larger San...
to
San JoseSan Jose or San José is the third-largest city in California and the tenth-largest in the United States. The county seat of Santa Clara County, it is located at the southern end of the San Francisco Bay Area, a region commonly referred to as Silicon Valley...
. 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 problemThe El Farol bar problem is a problem in game theory. Based on a bar in Santa Fe, New Mexico, it was created in 1994 by W. Brian Arthur.The problem is as follows: There is a particular, finite population of people. Every Thursday night, all of these people want to go to the El Farol Bar. However,...
proposed by
W. Brian ArthurWilliam Brian Arthur is an economist credited with influencing and describing the modern theory of increasing returns. He has lived and worked in Northern California for many years. He is a sought-after speaker on economics and complexity theory in technology and financial markets, and other...
.
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, D < C, 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 equilirium is mixed. The canonical example of a discoordination game is the
matching penniesMatching pennies is the name for a simple example game used in game theory. It is the two strategy equivalent of Rock, Paper, Scissors. Matching pennies, also called the Pesky Little Brother Game or Parity Game, is used primarily to illustrate the concept of mixed strategies and a mixed strategy...
game.
See also
- Cooperative game
A cooperative game is a game where groups of players may enforce cooperative behaviour, hence the game is a competition between coalitions of players, rather than between individual players...
- Non-cooperative game
In game theory, a non-cooperative game is a one in which players make decisions independently. Thus, while they may be able to cooperate, any cooperation must be self-enforcing....
- Equilibrium selection
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...
- Strategic complements
In economics and game theory, the decisions of two or more players are called strategic complements if they mutually reinforce one another, and they are called strategic substitutes if they mutually offset one another...
- Supermodular
In mathematics, a functionis supermodular iffor all x, y Rk, where x y denotes the componentwise maximum and x y the componentwise minimum of x and y....
- Uniqueness or multiplicity of equilibrium
- Consensus decision-making
Consensus decision-making is a group decision making process that not only seeks the agreement of most participants, but also the resolution or mitigation of minority objections. Consensus is usually defined as meaning both general agreement and the process of getting to such agreement...
- Self-fulfilling prophecy
A self-fulfilling prophecy is a prediction that directly or indirectly causes itself to become true, by the very terms of the prophecy itself, due to positive feedback between belief and behavior. Although examples of such prophecies can be found in literature as far back as ancient Greece and...