1 of 24

Extensive Form Games��

​

Roman Sheremeta, Ph.D.

Professor, Weatherhead School of Management

Case Western Reserve University

1

2 of 24

Outline�

  • Experiment #6
  • Review
  • Dynamic games of complete and perfect information
  • Examples:
    • Entry game
    • Sequential-move matching pennies
  • Extensive-form representation
  • Game tree

​

2

3 of 24

Experiment #6: �Centipede Game

  • Veconlab login:

​

  • Class experiment:
    • 2-stage centipede game
    • 6-stage centipede game

​

​

3

4 of 24

Review:�A Normal-Form Game

  • DEFINITION: A strategic normal-form game consists of:

​

    • A set of players

{Player 1, Player 2, ... Player n}

​

    • For each player, a set of actions

S1, S2, …, Sn

​

    • For each player, payoffs (preferences) over the set of action profiles

ui(s1, s2, ...sn), for all s1∈S1, s2∈S2, ..., sn∈Sn.

​

4

5 of 24

Review:�A Normal-Form of Matching Pennies

  • Set of players: {Player 1, Player 2}
  • Sets of strategies: S1 = S2 = {Head, Tail}
    • Payoff functions: u1(H, H)=-1, u1(H, T)=1, u1(T, H)=1, u1(H, T)=-1,� u2(H, H)=1, u2(H, T)=-1, u2(T, H)=-1, u2(T, T)=1
    • The normal-form of a game can also be represented as a matrix or a table

5

-1 , 1

1 , -1

1 , -1

-1 , 1

Player 1

Player 2

Tail

Head

Tail

Head

6 of 24

Extensive-Form Game�

  • The two representations of the rules of a game are
    • Normal-form
    • Extensive-form

​

  • The extensive-form is represented as a game tree
    • A game tree starts from a root: one of the players has to make a choice
    • The variable choices available to this player are represented as branches emanating from the root
    • Each branch may split into further branches
    • The payoffs are written at the end of the tree where the game terminates

​

6

7 of 24

Sequential-Move Matching Pennies: Extensive-Form Game

  • Each of the two players has a penny
    • Player 1 first chooses either Head or Tail
    • After observing Player 1’s choice, Player 2 chooses either Head or Tail
    • If two pennies match then Player 2 wins Player 1’s penny
    • Otherwise, Player 1 wins Player 2’s penny

7

Player 1

Player 2

H

T

-1, 1

1, -1

H

T

Player 2

1, -1

-1, 1

H

T

8 of 24

Sequential-Move Matching Pennies: Strategies

  • A strategy has to specify what to do at each information set (each decision node)

​

  • What are the strategies available for player 1?
    • H
    • T

8

Player 1

Player 2

H

T

-1, 1

1, -1

H

T

Player 2

1, -1

-1, 1

H

T

9 of 24

Sequential-Move Matching Pennies: Strategies

  • What are the strategies available for player 2?
    • H(if H)H(if T)
    • H(if H)T(if T)
    • T(if H)H(if T)
    • T(if H)T(if T)

​

​

9

Player 1

Player 2

H

T

-1, 1

1, -1

H

T

Player 2

1, -1

-1, 1

H

T

10 of 24

Sequential-Move Matching Pennies: Strategies

  • To avoid confusion, we will use the following notation for Player 2’s strategies:
    • HH’
    • HT’
    • TH’
    • TT’

​

​

10

Player 1

Player 2

H

T

-1, 1

1, -1

H

T

Player 2

1, -1

-1, 1

H’

T’

11 of 24

Sequential-Move Matching Pennies: Strategies

  • A pair of strategies, one for player 1 and one for player 2, determines the way in which the game is played:
    • (H, TT’) means that player 1 plays H and player 2 follows by T
    • (T, TH’) means that player 1 plays T and player 2 follows by H’

​

11

Player 1

Player 2

H

T

-1, 1

1, -1

H

T

Player 2

1, -1

-1, 1

H’

T’

12 of 24

Sequential-Move Matching Pennies: Normal-Form Representation

  • Set of players: {Player 1, Player 2}
  • Sets of strategies: S1 = {H, T} S2 = {HH’, HT’, TH’, TT’}
    • Payoff functions: u1(H,HH’)=-1, u1(H,TT’)=1, u1(T,HH’)=1, u1(T,TT’)=-1 u1(H,HT’)=-1, u1(H,TH’)=1, u1(T,HT’)=-1, u1(T,TH’)=1�u2(H,HH’)=1, u2(H,TT’)=-1, u2(T,HH’)=-1, u2(T,TT’)=1 u2(H,HT’)=1, u2(H,TH’)=-1, u2(T,HT’)=1, u2(T,TH’)=-1

​

12

​

​

Player 2

​

​

HH’

HT’

TH’

TT’

Player 1

H

-1 , 1

-1 , 1

1 , -1

1 , -1

T

1 , -1

-1 , 1

1 , -1

-1 , 1

13 of 24

Extensive-Form Game�

  • DEFINITION: An extensive-form game consists of:

​

    • A set of players

{Player 1, Player 2, ... Player n}

​

    • A history of plays

H

​

    • A set of actions at each history of plays

S1(H), S2(H), ..., Sn(H)

​

    • For each player, payoffs (preferences) over the set of histories of plays

ui(s1,s2,...sn) for all s1∈S1(H), ..., sn∈Sn(H)

13

14 of 24

Extensive-Form Game�

  • The extensive-form representation of a game specifies:
    • Who moves when and what action choices are available?
    • What do players know when they move?
    • What payoffs players receive for each combination of moves?

​

  • In the extensive-from game, a strategy for a player is a complete plan of actions
    • It specifies a feasible action for the player in every node in which the player might be called on to act

​

​

14

15 of 24

Game Tree�

    • A game tree of an extensive-form game:
      • A set of players
      • A set of nodes
      • A set of edges such that each edge connects two nodes
      • A unique path that connects nodes
      • Payoffs are at the bottom

​

​

15

Player 1

Player 2

H

T

-1, 1

1, -1

H

T

Player 2

1, -1

-1, 1

H’

T’

Path

Nodes

Edges

Players

Payoffs

16 of 24

Game Tree�

    • A game tree of an extensive-form game:
      • Any node other than a terminal node represents some player
      • For a node other than a terminal node, the branches that connect it with its successors represent the actions available to the player represented by the node

​

16

Player 1

Player 2

H

T

-1, 1

1, -1

H

T

Player 2

1, -1

-1, 1

H’

T’

Terminal Nodes

Actions

17 of 24

Entry Game�

  • Entry game:
    • An incumbent monopolist faces the possibility of entry by a challenger
    • The challenger may choose to enter in (In) or stay out (Out)
    • If the challenger enters, the incumbent can choose either to accommodate (A) or to fight (F)
    • The payoffs are common knowledge

​

​

17

Challenger

In

Out

Incumbent

A

F

1, 2

2, 1

0, 0

18 of 24

Entry Game:�Normal-Form

  • Challenger’s strategies
    • In
    • Out

​

  • Incumbent’s strategies
    • Accommodate (if challenger plays In)
    • Fight (if challenger plays In)

​

​

​

​

18

​

Incumbent

​

​

Accommodate

Fight

Challenger

In

2 , 1

0 , 0

Out

1 , 2

1 , 2

19 of 24

Nash Equilibrium�

  • The set of Nash equilibria in a dynamic extensive-form game of complete information is the set of Nash equilibria of its static normal-form representation

​

  • How to find the Nash equilibria in a dynamic game of complete information?
    • Construct the normal-form of the dynamic game of complete information
    • Find the Nash equilibria in the normal-form

​

​

​

19

20 of 24

Entry Game: �Nash Equilibrium

  • What are the Nash equilibria?
    • (In, Accommodate)
    • (Out, Fight)

​

  • Does the second Nash equilibrium make sense?
    • How does the challenger know that the incumbent will choose to Fight if the challenger chooses Out?
    • The extensive-form game does not allow incumbent to commit to Fight in case of challenger’s entry
    • Therefore, Fight is a non-creditable threat!

​

​

​

20

​

Incumbent

​

​

Accommodate

Fight

Challenger

In

2 , 1

0 , 0

Out

1 , 2

1 , 2

21 of 24

Subgame Perfect Nash Equilibrium�

  • We need to remove non-reasonable Nash equilibria

​

  • Subgame Perfect Nash equilibrium is a refinement of Nash equilibrium that removes non-reasonable Nash equilibria or non-creditable threats

​

​

​

21

22 of 24

Subgame Perfect Nash Equilibrium�

  • Next Time!

23 of 24

Thank you!

​

Roman Sheremeta, Ph.D.

Professor, Weatherhead School of Management

Case Western Reserve University

23

24 of 24

References�

  • Watson, J. (2013). Strategy: An Introduction to Game Theory (3rd Edition). Publisher: W. W. Norton & Company. (Chapters 2 & 14)

​

24