Game Theory
Lecture 4

 

Games

1. Games

  • Usually two players

  • Rules

    • Timing

    • Action available to players

    • Information available

    • Outcome – action taken by a player

    • Payoffs

  • Types of Games

    • Static game – each player moves once

    • Dynamic game – players move sequentially

    • Perfect information – all players know the entire history when time to move

    • Complete information – players know their payoffs and the payoffs for rivals

      • Players can predict action by others

    • Incomplete information – players know their payoffs, but not payoffs of their rivals

  • Equilibrium – “solution to the game”

    • Out of all strategies, an equilibrium is the route that players will take

    • Assumptions

      • Rationality – players maximize payoff

      • Common knowledge – players know structure of game

2. Strategies

  • You have the game below for two players: Row player and Column player

  C1 C2 C3
R1 10, 3 7, 10 5, 7
R2 20, 7 15, 12 10, 6
R3 7, 7 6, 14 9, 5
  • Payoffs - the first number in each cell is the payoff to the Row player, while the second number is the payoff to the column player

    • The bottom right cell has 9, 5

      • Row players gets a 9 payoff, while column player gets a 5 payoff

    • Row player has three strategies, R1, R2, and R3

    • Column player has three strategies, C1, C2, and C3

    • The payoff is denoted by p, i.e. the profit

  • Strictly dominant strategy – can player i maximize his payoff , regardless of the other player

  • p i(S i, S -i) > p i(S i’, S -i)

  • Notation

    • S i is the best strategy for player i

    • S -i is the rival’s strategy

    • S i’ is a strategy for player i

  • Dominant strategy

    • Row player selects R2

    • Column player selects C2

  • Thus, the payoff is 15 for the row player and 12 for the column player

    • End up in the cell R2 C2

3. Prisoner’s Dilemma

  • Most common example in game theory

  • Applied to many situations in economics

  • Setup

    • Two criminals commit a crime together

    • Police arrest both at the same time

  Criminal 2

Criminal 1

Rat Clam

Rat

-2, -2 -0.5, -5

Clam

-5, -0.5 -1, -1
  • Payoff is years in prison

    • Payoffs are negative, because criminals want to avoid them

    • Payoff is a punishment

  • Cell 4: This would be best outcome for both criminals, because each spend a year in prison

  • Police: If one tells, he gets a half year in prison, while the other criminal gets 5 years

    • Both rat on each other

    • We end up in Cell 1, where each criminal gets 2 years in prison

    • Rat is the dominant strategy

  • What happens if both criminals are in the mafia?

    • The mafia has a strict code: death to all rats

    • The new payoff is below:

  Criminal 2

Criminal 1

Rat

Clam

Rat

death, death death, -5

Clam

-5, death -1, -1

4. Nash Equilibrium – a strategy profile, so every player’s strategy is the best response to strategies of the other players

  • Also works for games that do not have any dominant strategies

  • Example: Prisoner’s dilemma with no dominant strategies

  Criminal 2
Criminal 1 Rat Clam
Rat -2, -2 -0.5, -5
Clam -5, -0.5 0, 0
  • Trick

    • If column player chooses “Rat”, what should the row player do?

      • Row player also “Rats”

      • Given if row player “rats,” what is the best strategy for the column player?

      • Column player also “rats”

    • Row and column players selected the same cell

    • Thus, a Nash equilibrium is Rat-Rat

  • Do this trick again

    • If column player chooses “Clam”, what should the row player do?

      • Row player also “Clams”

      • Given if row player “clams,” what is the best strategy for the column player?

      • Column player also “clams”

    • Row and column players selected the same cell

    • Thus, a Nash equilibrium is Clam-Clam

  • Problem – we have two Nash equilibria

    • Is one Nash equilibrium preferable to the others?

    • Yes, the Clam-Clam strategy

5. Battle of the Sexes

  • Male-female dating

  • They are planning an activity; payoffs is utility

  Woman
Man Football Ballet
Football 10, 1 0, 0
Ballet 0, 0 1, 10
  • If the woman chooses football, what is the man’s best strategy?

    • The man chooses football

    • If the man chooses football, what is the woman’s best strategy?

    • The woman also chooses football

    • A Nash equilibrium is Football-Football

  • If the woman chooses ballet, what is the man’s best strategy?

    • The man chooses ballet

    • If the man chooses ballet, what is the women’s best strategy?

    • She also chooses ballet

    • A Nash equilibrium is Ballet-Ballet

  • This game has two Nash equilibria and one equilibrium is not preferable to another

6. Zero Sum Game – one player gains, while the other player loses

  • Stealing

  • Gambling

  Column Player
Row Player A B
A -1, 1 3, -3
B 0, 0 -2, 2
  • If the column player selects A, what should the row player do?

    • The row player selects B

    • If the row player selects B, what should the column player do?

    • The column player selects B

    • Different cells, thus no Nash equilibrium

  • If the column player selects B, what should the row player do?

    • The row player selects A

    • If the row player selects A, what should the column player do?

    • The column player selects A

    • Different cells, thus no Nash equilibrium

  • This example has no pure Nash equilibrium

    • This is a strictly competitive game

7. A more complicated game

  C1 C2 C3
R1 3, 6 2, 2 1, 10
R2 5, 7 6, 8 9, 1
R3 5, 1 8, 3 10, 15
  • The Nash equilibrium is (R3, C3)

8. Another example


C1 C2 C3 C4
R1 3, 5 3, 10 1, 3 10, 7
R2 0, 0 5, 2 5, 6 4, 1
R3 5, 8 20, 19 4, 5 3, 4
R4 10, 9 4, 3 2, 0 9, 6
  • The Nash equilibria are (R4, C1), (R3, C2), and (R2, C3)

9. Mixed Strategies

  • No Nash equilibrium exists

  • If two players play the game over and over again, a player can randomly select a strategy part of the time that maximizes its payoffs

  • Two players, McDonalds and Burger King

    • A player can charge a high price or low price

    • The profits are the payoffs

  Burger King
McDonald's High Price Low Price
High Price 40, 30 30, 35
Low Price 35, 25 32, 20
  • If Burger King chooses the High Price, its expected payoff is:

payoff = 30 P m + 25 (1 - P m)

  • P m is the probability that McDonald's chooses the high price, while 1 - P m is the probability McDonald's chooses the low price

  • If Burger King chooses the Low Price, its expected payoff is:

payoff = 35 P m + 20 (1 - P m)

  • Burger King wants to maximize its payoffs after it keeps playing this game

  • Set the two payoffs equal to each other, and solve for the probability, P m

30 P m + 25 (1 - P m) = 35 P m + 20 (1 - P m)

P m = 0.5

  • Thus, McDonald's should charge a high price for half the time, and a low price for the other half

  • Similarly, McDonald's has the payoff, which is:

payoff = 40 P B + 30 (1 - P B) = 35 P B + 32 (1 - P B)

P B = 2 / 7

  • P B is the probability that Burger King chooses the high price

  • Burger King should charge high prices 2/7 of the time, and low prices for 5/7 of the time

10. Sequential Games - one player makes a move, and then the other player

  • Could change the nature of the game

  • Two methods to solve these games

    • Backward induction - start at the last game, and work backwards

      • Example: We have two people: Ben and Jerry

      • Their profit is the payoff

A sequential game with market entry

  • If Ben chooses "to stay out," then Jerry can be aggressive or maintain current price

    • If Jerry chooses to be aggressive, then Ben "stays out" of the market

      • The top payoff is a Nash equilibrium

    • If Jerry chooses to maintain current price, then Ben enters the market

  • If Ben chooses "to enter" market, then Jerry will maintain current price

    • If Jerry chooses to maintain current price, then Ben enters the market

      • The bottom is a Nash equilibrium

  • We could put this into a matrix below

    • The Nash equilibria is shaded in green

  Jerry
Ben Aggressive Maintain current price
Stay out 0, 1 0, 1
Enter -0.5, -1 1, 0
  • Another example

    • Payoffs are profits

    • Backwards induction works for this problem

    • However, it is easy to solve by putting into a matrix

A sequential game with market entry

  • What makes this example odd is it is missing a cell

  • Monopoly would never choose to fight entry

  • Nash equilibrium is green

    • New firm enters market

    • Monopoly continues to maximize profits

  Monopoly
New Firm Fight entry Continue to max profit
Stay out   0, 80
Enter 0, 10 30, 50

Extra Problems in Game Theory

1. Some students have difficulty understanding game theory. I present more examples. As you probably noticed, an interaction between two or more parties where each party has a choice can be structured as a game theory problem.

Example 1: The government provides a public good.

  • Game Setup – Two people
    • Each person has a maximum reservation price of $150 for the public good.
  • The costs for government to supply public good is $150.
    • If both people contribute, then the cost is $75 each.
    • If one person contributes, then the cost is $150.
  • The payoffs are the amount a person keeps after paying for public good, and are shown below.

Prisoner's Dilemma for tax evasion

(a) Identify the dominant strategies.

(b) Identify the Nash equilibriums if any.

Example 2: We have the battle between the sexes.

  • A man and woman are dating
    • One selects an activity and the other follows
    • The payoffs are the utility for each person
    • Joke – Man gets a utility of 5 when eating alone (Men love to eat!)

A simultaneous game between a man and a woman going on a date

(a) Identify the dominant strategies.

(b) Identify the Nash equilibriums if any.

(c) Identify the Preferable Nash equilibrium.

Example 3: You have the payoff matrix below:

  C1 C2 C3 C4
R1 0, 7 2, 5 7, 0 6, 6
R2 5, 2 3, 3 5, 2 2, 2
R3 7, 0 2, 5 0, 7 4, 4
R4 6, 6 2, 2 4, 4 10, 3

(a) Identify the dominant strategies.

(b) Identify the Nash equilibriums if any.

(c) Identify the Preferable Nash equilibrium.

Example 4: You have the payoff matrix below.

  Left Middle Right
Upper 5, 4 0, 1 0, 6
Middle 4, 1 1, 2 1, 1
Down 5, 6 0, 3 4, 4

(a) Identify the dominant strategies.

(b) Identify the Nash equilibriums if any.

(c) Identify the Preferable Nash equilibrium.

Example 5: We have a sequential game between the Cypress government and its citizens' bank deposits. The choices or strategies are:

  • The Cypress government wants to impose a tax on bank deposits as a means to pay for the EU bailout package. Its choice is to tax or not tax bank deposits.
  • The depositors have a choice. They can withdraw their deposits or keep funds at the bank.
  • The payoffs are millions of euros, which are defined as (gov. tax revenue, depositors' wealth).

A sequential game between the Cypress government and its depositors

Identify the Nash equilibriums if any

Example 6: We have a sequential game between the Greek government and the European Union (EU). The choices or strategies are:

  • The Greek government has a choice to withdraw from the Eurozone and reintroduce its currency.
  • The EU has a choice to grant or not grant a loan to the Greek government.
  • The payoffs are the change in GDP in millions of euros, which are defined as (Greece's GDP, EU's GDP).

A sequential game between the Greek government and the EU

Identify the Nash equilibriums if any

Example 7: We have a sequential game between a worker and a manager. Their choices are:

  • The manager has a choice to fire or not fire his employee.
  • The employee has a choice to arrive at work on time or clock in late.
  • The payoffs are utilities, which are defined as (worker's utility, manager's utility).

Sequential game between manager and worker

Identify the Nash equilibriums if any

Example 8: We have a sequential game between a driver and the police. Their choices are:

  • The driver has the choice to inform the police about his 4th Amendment rights, or consent to his car being searched.
  • The police can pull the driver out of the car and beat him mercilessly or the police can respect the driver's rights.
  • The payoffs are utilities, which are defined as (driver's utility, police's utility).

Sequential game between a driver and the police

Identify the Nash equilibriums if any

2. Solutions

Example 1: The dominant strategy for both players is not to contribute for the public good. Consequently, the Nash equilibrium is Doesn't contribute-Doen't contribute. As you guessed, people want benefits from their government but they do not want to pay for them.

Example 2: The players do not have any dominant strategies. The Nash equilibriums are Dinner-Dinner and Movie-Movie. The Movie-Movie is preferable because both parties experience greater utility.

Example 3: The players do not have any dominant strategies. The Nash equilibrium is R2C2, and no preferable Nash equilibrium exists. The game has only one Nash equilibrium.

Example 4: The Row player has a dominant strategy, Down, while the Column player has no dominant strategy. The Nash equilibriums are Middle-Middle and Down-Left. The preferable Nash equilibrium is the Down-Left because it yields a greater payoff.

Example 5: The Nash equilibrium is the government taxes bank deposits and the depositors withdraw their bank funds.

Example 6: The Nash equilibrium is the Greek government remains in the Eurozone and the EU grants loans to Greece.

Example 7: This game has two Nash equilibriums: The first is the worker arrives on time and manager does not fire. The second is the worker arrives late and the manager fires the worker.

Example 8: I apologize for this problem, but I thought it was good game-theory example to illustrate the deteriation of people's rights in the United States. The first Nash equilbrium is the driver informs the police of his right, and the police pull the driver from the car and beat him. The second Nash equilibrium is the driver allows the police to search his car and the police respect his rights.