Lec7 最近の更新履歴 yyasuda's website

全文

(1)

ECO290E: Game Theory

Lecture 7: Dynamic Games and Backward Induction

(2)

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 11th, please let me

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

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

(3)

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.

(4)

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.

(5)

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.

(6)

Game Tree Analysis

(0,4)

(-1,-1)

(1,1)

Entrant

Monopolis

t

OUT

IN

WAR

ACC.

(7)

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

(8)

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.

(9)

Backward Induction Solution

( ,4)

(-1, )

( , )

Entrant

Monopolis

t

OUT

IN

WAR

ACC.

(10)

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

(11)

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

(12)

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!

(13)

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

(14)

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?

(15)

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).

(16)

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.

Updating...

参照

Updating...

Scan and read on 1LIB APP