• 検索結果がありません。

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

N/A
N/A
Protected

Academic year: 2017

シェア "Lec7 最近の更新履歴 yyasuda's website"

Copied!
16
0
0

読み込み中.... (全文を見る)

全文

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

参照

関連したドキュメント

where N p and N s are the number of turns for primary side and reference output, respectively, V o is the output voltage, V F is the diode (D R ) forward voltage drop and V sense

A by-product of BCM is that the boost converter runs with variable switching frequency that depends primarily on the selected output voltage, the instantaneous value of the input

A side effect of BCM is that the boost converter runs with variable switching frequency that depends primarily on the selected output voltage, the

During the turn-off transient, boost inductor current changes the path from MOSFET to output diode and before the output diode turns on; a minor voltage peak can be shown at

 Register addresses are assigned for an individual IP. This device has different addresses for Decoder, PCM0 input, PCM0 output, PCM1 input, and PCM1 output..

ON Semiconductor products are not designed, intended, or authorized for use as a critical component in life support systems or any FDA Class 3 medical devices or medical devices with

In addition, a complete list of all device types supplied from this process is included to aid in cross reference searches and the selection of preferred device

The output voltage is indirectly sensed by sampling the transformer winding voltage (V SH ) around the end of diode current discharge time, as illustrated in Figure 4..