## ECO290E: Game Theory

Lecture 7: Dynamic Games and Backward Induction

## Information on Midterm ^{}

### The coverage of the midterm exam is what we have

### covered in Lectures 1 - 6.

### The exam is take-home, which will be posted on

### March 9 (Sun) morning via gateway.

### You have to bring your answer at the beginning of the

### morning lecture on March 11 (Tue).

If you cannot attend the lecture on 11^{th}, please let me

know in advance. Otherwise, I will NOT accept ANY late submission.

### The midterm counts about 1/3 of the entire grade.

## Review of Lecture 5

### Indifference property in mixed strategy NE.

If a player chooses more than one strategy with positive

probability, she must be indifferent among such pure strategies: choosing any of them generate same expected payoff.

### Pure strategy is a special case of mixed strategy:

### assigning a strategy probability 1.

### Any finite game has a Nash equilibrium, possibly in

### mixed strategies.

## Dynamic Game

Each dynamic game can be described (in detail) by extensive-form.

Its formal definition will be given in Lecture 7.

Often expressed by a “game tree”.

Dynamic games can also be analyzed in normal form (or, strategic form).

A strategy in dynamic games is a complete action plan which prescribes how the player will act in each possible

contingencies in future.

## Entry and Predation

There are two firms in the market game: a potential entrant and a monopoly incumbent.

First, the entrant decides whether or not to enter this monopoly market.

If the potential entrant stays out, then she gets 0 while the monopolist gets a large profit, say 4.

If the entrant enters the market, then the incumbent must choose whether or not to engage in a price war.

If he triggers a price war, then both firms suffer (receive -1).

If he accommodates the entrant, then both firms obtain modest profits, say 1 each.

## Game Tree Analysis

**(0,4)** ^{
}

**(-1,-1)** ^{
}

**(1,1)** ^{
}

**Entrant** ^{
}

**Monopolis**

**t** ^{
}

**OUT** ^{
}

**IN** ^{
}

**WAR** ^{
}

**ACC.** ^{
}

## Normal (Strategic)-Form Analysis

Is (O, PW) a reasonable NE?

** Monopolist **
**Entrant **

**Price War ** **Accommodate **

**In ** ** -1 **

** -1 **

** 1 **
** 1 **

**Out ** ** 4 **

** 0 **

** 4 **
** 0 **

## Lessons

### Dynamic games often have multiple Nash equilibria,

### and some of them do not seem plausible since they

### rely on non-credible threats.

### By solving games from the back to forward, we can

### erase those implausible equilibria.

⇒_{ }

### Backward Induction

### This idea will lead us to the refinement of NE, the

### subgame perfect Nash equilibrium.

Formal definition will be given in Lecture 7.

## Backward Induction Solution

**( ,4)** ^{
}

**(-1, )** ^{
}

**( , )** ^{
}

**Entrant** ^{
}

**Monopolis**

**t** ^{
}

**OUT** ^{
}

**IN** ^{
}

**WAR** ^{
}

**ACC.** ^{
}

## Sequential Battle of the Sexes

What happens if Wife makes decision first, and Husband
decides after observing Wife’s action?^{
}

** Husband **
**Wife **

** Musical ** ** Soccer **

**Musical ** ** 1 **
**3 **

** 0 **
**0 **

**Soccer ** ** 0 **
**0 **

** 3 **
**1 **

## Normal-Form Analysis ^{}

There are three Nash equilibria:

(M, MM’), (M, MS’), (S, SS’) => Do they look reasonable?

Backward induction selects (M, MS’).^{
}

** H **

**W** ^{
}

**M, M’** ^{
} **M, S’** ^{
} **S, M’** ^{
} **S, S’** ^{
}

**Musical** ^{
} ** 1 **

**3** ^{
}

** 1 **

**3** ^{
}

** 0 **

**0** ^{
}

** 0 **

**0** ^{
}

**Soccer** ^{
} ** 0 **

**0** ^{
}

** 3 **

**1** ^{
}

** 0 **

**0** ^{
}

** 3 **

**1** ^{
}

## Strategy and Outcome ^{}

Strategy in dynamic game = Complete plan of actions

What each player will do in every possible chance of move.

Even if some actions will not be taken in the actual play, players specify all contingent action plan.

Outcome = Combination of actions in the play

Actions that each player takes in the actual play.

Not specify contingent actions that will not be reached in the actual play.

To derive/understand rational (backward induction) play,
we need to look at strategy, rather than outcome!^{
}

## Centipede Game ^{}

## 1 P 2 P 1 P 2 P 1 P 2 P 25.60

## 6.40

## T

## T T T T T

## 0.40 0.20 1.60 0.80 6.40 3.20

## 12.80

## 0.10 0.80 0.40

^{3.20 }

## 1.60

## Counting Game: Not 21 ^{}

### Two players count series of numbers (from 1 to 21)

### in turn.

Each player must count at least one, but at most three numbers.

The player who ends up declaring 21 loses, and the other wins.

Does the first or the second player have a winning strategy?

If so, what does winning strategy look like?

How is the analysis changed if the last number is different from 21?

## Zermelo’s Theorem ^{}

### In any finite two-person game in which

1._{ } players have strictly opposing interests,

2._{ } the players move alternatively,

3._{ } chance does not affect the decision making process,

4._{ } the game cannot end in a draw,

### one of the two players must have a winning strategy .

In these cases, one player is guaranteed “win” regardless of how her opponent will play, e.g., “Not 21.”

In principle, the complicated game such as chess has a
winning strategy (or both players are guaranteed draw).^{
}

## Further Exercises ^{}

Find the conditions under which backward induction works, i.e., pins down the unique outcome.

If this is too difficult, construct a counter example that backward induction does not work.

Consider the sequential version (one player moves first) of prisoner’s dilemma and coordination game, and solve them by backward induction.

Construct a dynamic game to which Zeomelo’s theorem
can be applied, and derive the winning strategy.^{
}