Simultaneous Games

Context

• In most real-life situations, economic agents do not operate in isolation. Their gains and losses depend not only on their own choices but also on the choices of others.

• Markets are typical examples of economic situations where social interactions matter.
  • How can we study social interactions in economics?
  • How do economic agents compete and coordinate with each other?
  • What are the social dilemmas that arise in such situations?

Course Structure Overview

Lecture Structure and Learning Objectives

Structure

• Street Fighter Mechanics (Case Study)
• Basic Concepts
• Examples with pure strategy equilibria
• Examples with mixed strategy equilibria
• Current Field Developments

Learning Objectives

• Explain why social interactions can lead to social dilemmas.
• Explain how game theory models social interactions.
• Describe the concept of equilibrium in models with interactions.
• Illustrate the concept of pure strategy equilibrium in static settings.
• Illustrate the concept of mixed strategy equilibrium in static settings.

Street Fighter Mechanics

• Street Fighter II: The World Warrior is a fighting game released in 1991.

• It was originally released in arcade.
• It reestablished the arcade competition from high score chasing to one-vs-one play.
• It inspired competitive video game tournaments in the early 2000s.
• Today the e-sports market is valued at more than a billion dollars.
• Why was Street Fighter II so successful?

Command Grab

Neutral Jump

Normal Grab and Anti-Air

Throw Technical

Social Dilemmas

• For some social interactions, individual interests do not always work in favor of society as a whole.

• Individual producers' interests suggest using cheap, brown instead of more expensive, green technologies.
• However, if all producers act in this way, pollution increases and the lives of everyone become worse off.
• A social dilemma is a situation in which actions taken independently by agents pursuing their individual objectives result in inferior outcomes to other outcomes that are feasible if agents coordinate.

Social Interactions

• Game theory is the main apparatus used for examining social interactions.

• A game is a description of a social interaction specifying
  • the players (who is participating?),
  • the feasible actions (when is someone playing? What can she do?)
  • the information (what is known by players when making their decisions?)
  • the payoffs (what is the outcome for each possible combination of actions?)

Common knowledge

• In the games that we will examine, the utilities and the choices of players are common knowledge.
• Common knowledge is information that is known and understood in the same way by all the players of a game.
• There is an element of infinite recursion in the idea of common knowledge.

• The agents of a game have common knowledge of a property \(P\) when they all know \(P\), they all know that they know \(P\), they all know that they all know that they know \(P\), etc.

Actions and Strategies

• Each player in a game has one or more decisions to make.

• A single choice made at a particular decision node is called an action.
• The collection of all actions of a player in a game is called a pure strategy (or simply strategy when it is understood from context that it is pure).
• In games where a player has a single decision to make, her actions and strategies coincide.

Representations of Games

• Games can be represented in various ways.
• The representations are not always interchangeable.
• Some games admit only certain representations. Others can be represented in multiple ways.
• Each representation has certain advantages.

Normal Form

• Simple games can be represented using a table documenting the primitives of the game.
• This representation is called the normal form of a game.

Extensive Form

• The extensive form of a game is a representation in terms of a tree.

• The extensive form depicts more information than the normal form:

  • It illustrates the order in which the players act.
  • It illustrates the information available to each player.

Information Set

• If a player has the same information at two (or more) nodes, the nodes are connected with a dotted line.
• An information set is a collection of decision nodes that the player making decisions cannot distinguish at the time of decision.
• The player knows that she is located at one of the nodes of the information set, but she does not know which one of them.

Best Responses

• Given a player’s strategy, what is the best strategy with which the other player can respond?
• A best response strategy is a strategy that maximizes a player’s payoff for given strategies of the remaining players of the game.
• The best response mapping is an association that gives the strategies that maximize a player’s payoff for each combination of strategies of the remaining players of the game.
• \(B_{A}(Left) = \{ Bottom\}\), \(B_{A}(Right) = \{ Bottom\}\)
• \(B_{B}(Top) = \{ Left\}\), \(B_{B}(Bottom) = \{ Left\}\)

Dominant Strategies

• On some occasions, a player can choose a strategy that makes her better off irrespective of the strategies chosen by other players.
• A strategy that, for all strategies other players can choose, gives a higher payoff to a player compared to every other strategy available to her is called a dominant strategy.
• \(Left \succ_{B} Right\)

Nash Equilibria

• A collection of strategies, one for each player, such that each strategy constitutes a best response to the remaining players' strategies is called a Nash equilibrium.
• In short but less accurate, a Nash equilibrium is a collection of mutual best responses.
• Intuitively, a Nash equilibrium is a collection of strategies from which no one has an incentive to deviate.
• \(NE = \left\{ \left\{ Bottom, Left \right\} \right\}\)

Do Nash equilibria predict the outcome of games?

• Nash equilibria do not say how, why, or whether these strategies are reached in a game.
• The definition of Nash equilibria suggests that if they are reached, then there is no incentive for anyone to change her behavior.

Are Nash equilibria unique?

• Nash equilibria are not unique.
• Multiple situations in a game may constitute points from which no one wants to deviate.
• The payoffs of the players in different Nash equilibria can be significantly different.
• \(NE = \left\{ \left\{ Bottom, Left \right\}, \left\{ Top, Right \right\} \right\}\)

Are Nash equilibria necessarily Pareto efficient?

• No. Nash equilibria can be Pareto inefficient.
• A classic example is the prisoner’s dilemma.

The Grappler Game

• Back to the Street Fighter mechanics

• Is there no Nash equilibrium in this case?

Mixed strategies

• Pure strategies are collections of actions, one for each decision to be made.
• Sometimes the players prefer to choose strategies based on some randomization rule.
• Players can randomize by assigning the probabilities (weights) with which they use their pure strategies.
• A distribution over the player’s pure strategies is called a mixed strategy.

A Mixed Strategy Example

• The grappler has two pure strategies (\(Command\ Grab\) and \(Normal\ Grab\)).
• The mixed strategy \((p, 1-p)\) assigns probability \(p\) to choosing \(Command\ Grab\) and probability \(1-p\) to choosing \(Normal\ Grab\).

Existence of Nash Equilibria

• Finite games always have at least one Nash equilibrium in mixed strategies (Nash 1950).
• A finite game is a game in which the number of players, actions, and decision nodes are finite.

The Grappler Game’s Equilibrium

• The grappler performs a \(Command\ Grab\) with probability \(p\) and a \(Normal\ Grab\) with probability \(1-p\).
• The grappler chooses these probabilities so that it makes the defender indifferent between \(Neutral\ Jump\) and \(Tech\) (why?).

\[\underbrace{2p + (-2)(1-p)}_{\substack{\text{Expected payoff when}\\ \text{the defender chooses }\\ Neutral\ Jump}} = \underbrace{(-3)p + 0(1-p)}_{\substack{\text{Expected payoff when}\\ \text{the defender chooses }\\ Tech}} \implies p = \frac{2}{7}.\]

• Similarly the defender mixes \(Neutral\ Jump\) with \(q\) and \(Tech\) with \(1-q\), such that

\[\underbrace{(-2)q + 3(1-q)}_{\substack{\text{Expected payoff when}\\ \text{the grappler chooses }\\ Command\ Grab}} = \underbrace{2q + 0(1-q)}_{\substack{\text{Expected payoff when}\\ \text{the grappler chooses }\\ Normal\ Grab}} \implies q = \frac{3}{7}.\]

Rock Paper Scissors

• There is no pure strategy Nash equilibrium.
• However, there is a symmetric mixed strategy equilibrium in which both players randomize using \(\left(\frac{1}{3}, \frac{1}{3}, \frac{1}{3}\right)\).

Current Field Developments

• Game theory has a deep theoretical basis and a wide variety of applications.
• In the last 60 years, it grew to be one of the most active research areas in many sciences.
• Current game theory models in economics involve behavioral biases and cognitive limitations (e.g., rational inattention).
• Game theory is also used in political sciences to analyze topics ranging from voters' behavior to war conflicts.
• Computer science uses game theory concepts and tools to develop artificial intelligence agents.
• In biology, game theory has been used to describe some social aspects of evolutionary processes.

Concise Summary

• Social dilemmas are situations in which private actions can lead to inferior social outcomes.
• Social interactions can be analyzed using game theory.
• Social interaction settings can be either static or dynamic.
• Equilibria in social interaction settings are situations from which no one has an incentive to change her behavior.
• Such equilibria are not necessarily economically efficient.

Further Reading

• Watson (2008, chaps. 3, 4, 6, 9, 11)
• Belleflamme and Peitz (2010, sec. A.1)
• Varian (2010, secs. 29.1-4, 30.1-5)
• Nash (1950)

Mathematical Details

Mixed Strategies

Mixed strategies involve uncertainty about the realized payoffs that the players receive. Thus, for strategies of this type to be meaningful, the players should be able to determine their preferences over different uncertain scenarios that may occur. The uncertain scenarios are also called lotteries in the economic and business literature.

The most prominent way of forming preferences over lotteries is via the expected utility. Intuitively, the expected utility is a weighted average of the payoffs that may be realized when looking at a particular lottery, where the weights are determined by how likely is each payoff to occur.

Some Lottery Examples

Consider the payoff set \[ U_{1} = \left\{10, 20, 15, 5, 30, 5 \right\} \] and suppose that we throw a fair dice (i.e., all faces have the same probability to appear) and take the \(i\text{-th}\) payoff when the face \(i=1,\dots,6\) is drawn. Since the dice is fair, the probability vector corresponding to each face is \[ P_{1} = \left(\frac{1}{6}, \frac{1}{6}, \frac{1}{6}, \frac{1}{6}, \frac{1}{6}, \frac{1}{6} \right). \] Then, the expected utility of this lottery can be calculated as \[ \mathbb{E}_{1} U_{1} = \left(\frac{10}{6} + \frac{20}{6} + \frac{15}{6} + \frac{5}{6} + \frac{30}{6} + \frac{5}{6} \right) = \frac{85}{6}, \] where the subscript in the expectation symbol \(\mathbb{E}_{1}\) indicates that we use the probability vector \(P_{1}\) to calculate the expecation. Typically, the subscript is omitted if the probability vector is understood from context.

The same idea applies when some of the payoffs are not positive. For instance, if the payoff set \[ U_{2} = \left\{10, -10, 15, 20, -10, 5 \right\} \] is combined with a fair dice, then the expected utility is \[ \mathbb{E}_{1} U_{2} = \left(\frac{10}{6} + \frac{-10}{6} + \frac{15}{6} + \frac{20}{6} + \frac{-10}{6} + \frac{5}{6} \right) = 5. \]

Finally, the probability vector is not restricted to having uniform individual probabilities. For example, consider a dice that is rigged so that the probability of getting 4, 5, or 6 is twice the probability of getting 1, 2, or 3, namely \[ P_{2} = \left(\frac{1}{9}, \frac{1}{9}, \frac{1}{9}, \frac{2}{9}, \frac{2}{9}, \frac{2}{9} \right). \] Then the expected utility of a lottery over the payoff set \(U_{1}\) is \[ \mathbb{E}_{2} U_{1} = \left(\frac{10}{9} + \frac{20}{9} + \frac{15}{9} + \frac{2\times5}{9} + \frac{2\times30}{9} + \frac{2\times5}{9} \right) = \frac{125}{9}. \]

Preferences over Lotteries

In the previous examples we have considered the three lotteries \(L_{1} = \left(\hat{u_{1}}, \hat{p_{1}}\right)\), \(L_{2} = \left(\hat{u_{2}}, \hat{p_{1}}\right)\), and \(L_{3} = \left(\hat{u_{1}}, \hat{p_{2}}\right)\). One way to think that agents formulate preferences over these lotteries is that they compare the expected utilities of the lotteries and they prefer lotteries with greater expected values. Thus, an expected utility maximizer would prefer \(L_{1}\) over \(L_{3}\), and \(L_{3}\) over \(L_{2}\).

Expected Utility

We can generalize the idea of expected utility for lotteries that have more than 6 potential outcomes with arbitrary probabilities in the following way. Suppose that we have a payoff set \[ U = \left\{u_{1}, u_{2}, \dots, u_{n} \right\} \] and a corresponding probability vector \[ P = \left\{p_{1}, p_{2}, \dots, p_{n} \right\}. \] The elements of the probability vector should be non-negative and sum up to one, namely \(p_{i} \ge 0\) for all \(i=1,\dots,n\) and \[ \sum_{i=1}^{n} p_{i} = 1. \] The probability vector is also called a (discrete) probability distribution in more advanced literature. Then, the expected utility is calculated as \[ \mathbb{E} U = \sum_{i=1}^{n} p_{i}u_{i} . \]

If all potential outcomes in \(U\) have the same probability, i.e., all the elements of the probability vector are equal to each other and equal to \(1/n\) (this is known as the uniform distribution), then the expected utility becomes \[ \mathbb{E} U = \frac{1}{n}\sum_{i=1}^{n} u_{i} , \] which is simply the (arithmetic) mean of the potential outcomes.

The Grappler Game’s Equilibrium

The Grappler has two pure strategies given by \[ \{ Command\ Grab, Normal\ Grab \}. \] She can assign a probability \(p\) to playing \(Command\ Grab\) and a probability \(1-p\) to \(Normal\ Grab\). In this case, her probability vector is \(\sigma = \left(p, 1-p\right)\). She would like to choose \(p\) such that she gets the highest expected utility when playing the game.

She can maximize her expected utility by choosing \(p\) so that she mixes up the Defender. This implies that \[ \mathbb{E} u_{D}(\sigma, Neutral\ Jump) = \mathbb{E} u_{D}(\sigma, Tech). \] If the above equality does not hold, then the Grappler has a profitable deviation and \(\sigma\) cannot be part of a Nash equilibrium. For example, if she chooses \(\sigma\) so that \(\mathbb{E} u_{D}(\sigma, Neutral\ Jump) < \mathbb{E} u_{D}(\sigma, Tech)\), then the Defender prefers to play \(Tech\) because he receives a greater payoff on average, which in turn implies that the Grappler would prefer to play \(Command\ Grab\) instead of \(\sigma\).

Substituting the expected utilities in the equilibrium equality gives \[ p 2 + (1-p) (-2) = p (-3) + (1-p) 0, \] from which we obtain \(p=2/7\), so the mixed strategy of the Grappler in the Nash equilibrium is \(\sigma=(2/7, 5/7)\).

The mixed strategy of the Defender in the Nash equilibrium is obtained via an analogous argument. The Defender chooses \(\xi=(q, 1-q)\) so that he mixes up the Grappler. This implies that \[ \mathbb{E} u_{G}(Command\ Grab, \xi) = \mathbb{E} u_{G}(Normal\ Grab, \xi), \] from which we get \[ q (-2) + (1-q) 3 = q 2 + (1-q) 0, \] and, finally, \(\xi=(3/7, 4/7)\).

The Rock Paper Scissors Equilibrium

The game is symmetric, so we only need to calculate the strategy of player A. Suppose that player A chooses Rock, Paper, and Scissors with probabilities \((p, q, r)\), where \(r=1-p-q\). Then, in any Nash equilibrium, the following should hold \[ p 0 + q 1 + r(-1) = p(-1) + q 0 + r 1 = p 1 + q (-1) + r 0. \] Substituting \(r=1-p-q\) results in \[ p + 2q -1 = 1 - 2p - q = p - q, \] from which we get the two equations \[ 3p + 3q = 2 \quad\text{ and }\quad 3p = 1. \] Thus \(p=q=r=1/3\).

Exercises

Group A

1. Consider the Bach or Stravinsky game (also known as Battle of the Sexes, which is outdated in current norms). A couple wishes to go to a music concert by either Bach or Stravinksy. One partner prefers Bach and the other Stravinsky. Nevertheless, their primary concern is to go out together.

   1. Find all the Nash equilibria.
   2. How do you interpret the objective of the players in this game?

   1. There are two pure Nash equilibria in this game, namely \((Bach, Bach)\) and \((Stravinsky, Stravinsky)\).

      There is also a mixed strategy equilibrium in which player \(A\) chooses \(Bach\) with \(p=\frac{2}{3}\) and \(Stravinksy\) with \(p=\frac{1}{3}\), while player \(B\) chooses \(Bach\) with \(q=\frac{1}{3}\) and \(Stravinksy\) with \(q=\frac{2}{3}\).

   2. The objective of the players is to coordinate. The players would like to choose the same action. Games of this type are called coordination games.

Group B

1. Consider the Hawk and Dove game. Two animals fight over a food source with a value of \(1\). Each animal can behave aggressively (like a Hawk) or peacefully (like a Dove). If both animals behave peacefully, they split the food. If only one animal behaves aggressively, it gets all the food. If both animals act aggressively, the value of the food source is reduced by \(c>0\) (lost in the fight), and the animals split the remainder equally.

   1. Write the normal form of the game.
   2. Find all the Nash equilibria for every value of the cost parameter \(c\).
   3. How do you interpret the equilibria of each case?

   1. The normal form of the game is as follows.

   2. We distinguish three cases based on the value of the parameter \(c\). For \(0<c<1\), the game has one pure strategy Nash equilibrium, in which both animals act aggressively, namely \(\{Hawk, Hawk\}\). For \(c>1\), the game has two pure strategy Nash equilibria. These are \(\{Dove, Hawk\}\) and \(\{Hawk, Dove\}\). The last case combines the pure strategy equilibria of the first and second cases. That is, for \(c=1\), the equilibria in pure strategies are \(\{Hawk, Hawk\}\), \(\{Dove, Hawk\}\), and \(\{Hawk, Dove\}\)

      To calculate the mixed equilibria, suppose that Animal \(A\) mixes its actions by choosing \(Dove\) with probability \(p\). In equilibrium, Animal \(B\) should be indifferent between choosing \(Dove\) and \(Hawk\), therefore, \[p\frac{1}{2} = p + (1-p)\frac{1}{2}(1 -c).\] Solving for \(p\) gives \[p = \frac{c-1}{c}.\] Thus, if \(c < 1\), there is no mixed strategy equilibrium. If \(c=1\), then \(p=0\), so, we essentially get one of the pure strategy equilibria of this case (namely \(\{Hawk, Hawk\}\)). Lastly, if \(c>1\), we get an additional mixed equilibrium.

   3. If \(c<1\), the cost of fighting is small, and the animals attempt to get the value for their own. This leads to a prisoners' dilemma type of game with a Pareto inefficient outcome. If \(c>1\), the cost of fighting is great enough to deter fighting. The animals then resort to playing a coordination game (Similar to Bach or Stravinksy).

References

References

Topic's Concepts

• finite game
• mixed strategy
• nash equilibrium
• dominant strategy
• best response mapping
• best response strategy
• information set
• extensive form
• normal form
• strategy
• pure strategy
• action
• common knowledge
• game
• social dilemma