Game Theory, Lecture 6

Slides Multi-stage Games with Observable Actions A Finitely Repeated Game with Multiple Static Equilibria A Finitely Repeated Game with a Unique Static Equilibrium The One-Stage-Deviation-Principle Total 13 10 3 13 39 Time 30 20 5 30 85

Multi-Stage Games with Observed Actions Multi-stage game with observed actions: Game that can be divided into stages and where At each stage all the players move simultaneously. Before a new stage starts the players observe what happened on the previous stages.

Multi-Stage Games with Observed Actions It includes the case where only a subset of players moves (the set of actions of the players that dont play is do nothing). At stage k players will play an action profile

a k = (a1k , a2k ,..., aIk )

Multi-Stage Games with Observed Actions At the start of stage k everyone knows the history of the game until stage k: hk = (a0, a1,, ak-1). To define strategies we specify a function from information sets to the set of actions. At the start of stage k we are at an information set and each player knows everything that happened before in the game, that is, he knows hk.

Multi-Stage Games with Observed Actions A pure-strategy si for player i defines what action player i should take at each stage k and for any possible history of the game up to stage k, with k = 0, 1,,K . Hence, a pure-strategy is a sequence of actions for any 1 k K possible contingency: si = ( si ,..., si ,..., si ) where

si0 : H 0 A0 , .......... , sik : H k Ak , ... ...... , siK : H K A K

Multi-Stage Games with Observed Actions Mixed strategies specify probability mixtures over the actions in each stage for any given contingency. The payoff of player i, ui , is a function of the terminal history hK+1 (i.e., of the entire sequence of actions from the initial stage 0 through the terminal stage K) to the real numbers. Usually, the payoffs of a multi-stage game are the k k discounted sum of the payoffs at each stage, g i ( a ):

ui = k =0 k g ik (a k )
K

Multi-Stage Games with Observed Actions The game might have a finite or infinite number so stages (horizon), that is, K might be infinity. If the game has an infinite horizon we assume that the property Continuity at Infinity of Payoffs (CIP) holds. This property says that stage game payoffs that happen in a distant future are relatively unimportant. It is satisfied if (i) overall payoffs are a discounted sum of per-period payoffs, and (ii) the per-period payoffs are bounded.
7

Multi-Stage Games with Observed Actions Example 1:

1 st

R L

R L

2 nd R

Multi-Stage Games with Observed Actions Example 2: Any dynamic game of perfect information is also a multi-stage game
1 L L R 2 R

1 st 2 nd

Multi-Stage Games with Observed Actions Many of the application of game theory to economics, political science and biology use multi-stage games with observed actions. A stage does not correspond necessarily to a period: A period might have one or more stages; A stage can have only one period.

10

Multi-Stage Games with Observed Actions Consider Rubinstein-Stahls bargaining model: A pie of size 1 is to be split between two players. In periods 0, 2, 4,.. player 1 proposes a sharing rule (x1,1-x1) that player 2 can accept or reject. If player 2 accepts any offer the game ends, if he rejects then he can propose a sharing rule (x2,1-x2) in the subsequent period that 1 can accept or reject. If player 1 accepts one of 2s offers the game ends, if he rejects then 1 can make an offer in the subsequent period.
11

Multi-Stage Games with Observed Actions Example 3:

x
2 A R 2

1st stage

2nd stage

x
A

1 R

1 per 2 per

12

Multi-Stage Games with Observed Actions We can classify multi-stage games into subclasses:

Multi-stage games

Repeated games Non-repeated games

Finite horizon Infinite horizon Finite horizon Infinite horizon

13

Multi-Stage Games with Observed Actions A repeated game has the property that the same stage game is played again and again. For example, repeated play of the PD game or of MP game. We will see that repeated games are good do describe situations where players interact many times (repeated interaction). The Rubinstein-Stahl game can be classified as a nonrepeated game with an infinite horizon.
14

A Finitely Repeated Game with Multiple Static Equilib. Consider the multi-stage game corresponding to two repetitions of the stage game (let =1, no discounting).
1\2 U M D L 0,0 4,3 0,6 M 3,4 0,0 0,0 R 6,0 0,0 5,5

15

A Finitely Repeated Game with Multiple Static Equilib. The PSNE of the stage game are (M,L) and (U,M). The MSNE is (1,2)=((3/7,U;4/7,M;0,D),(3/7, L;4/7,M;0,R)). which leads to payoffs of (12/7,12/7)(1.71,1.71).
1\2 U M D L 0,0 4,3 0,6 M 3,4 0,0 0,0 R 6,0 0,0 5,5

The efficient payoff (5,5) is not attainable by a NE.

A Finitely Repeated Game with Multiple Static Equilib.

What are the SPE of the two-stage repeated game?

17

A Finitely Repeated Game with Multiple Static Equilib. Applying the solution concept of SPE we know that first we need to find the Nash equilibria of the second stage subgame. Since the second stage-subgame is the static game its equilibria are: (M,L), (M,L), and (1,2). These are the only possible pairs of actions that can be played in the second stage.

18

A Finitely Repeated Game with Multiple Static Equilib. What will be the actions played in the first stage? Well, if players play a NE of the static game in the first stage there will be no unilateral incentives to deviate in the first-stage. We already know that players will play a NE in the second-stage so we found several SPE.

19

A Finitely Repeated Game with Multiple Static Equilib. All combinations of the static equilibria: (M,L) and (M,L) (M,L) and (U,M) (M,L) and (1,2) (U,M) and (U,M) (U,M) and (M,L) (U,M) and (1,2) (1,2) and (1,2) (1,2) and (M,L) (1,2) and (U,M)
20

A Finitely Repeated Game with Multiple Static Equilib. Are there more SPE? For example, is there are SPE where it is possible to support the play of (5,5) in the first stage of the game? Lets see

21

A Finitely Repeated Game with Multiple Static Equilib. Player 1: Play D in the first stage; If action profile (D,R) happened in stage 1, then play M in the second stage, otherwise play 1. Player 2: Play R in the first stage; If action profile (D,R) happened in stage 1, then play L in the second stage, otherwise play 2.
22

A Finitely Repeated Game with Multiple Static Equilib. Lets check if these strategies are a SPE. In the second stage players play (M,L) which is a NE of the static game, so no player wants to deviate. Can player 2 gain by deviating in the first stage given that 1 sticks to his strategy? Deviation payoff: u2(D,L)+u2(1,2)=6+12/7=54/7. No deviation payoff: u2(D,R)+u2(M,L)= 5+3=8=56/7.
23

A Finitely Repeated Game with Multiple Static Equilib. Since we have three NE in the stage game we can construct strategies where each player can use the NE actions of the stage game to punish or reward the rival in the second stage. This example shows that repeated play expands the set of equilibrium outcomes. This is not always the case.

24

A Finitely Repeated Game with a Unique Static Equilib. If there is a single Nash equilibrium of the stage game we cant support the play of other payoffs. Consider the PD repeated twice. The stage game is:
1\2 C D C 4,4 5,0 D 0,5 1,1
25

A Finitely Repeated Game with a Unique Static Equilib. In the second stage both player can only play D so we have (D,D). In the first stage no matter what they do today there is no consequence tomorrow, so they should just maximize their payoff today. The argument can be repeated for K stages, where K is finite.

26

A Finitely Repeated Game with a Unique Static Equilib.

Any time a stage game has a unique NE and the stage game is repeated a finite number of times, the only SPE of the finitely repeated game is repetition of the NE of the stage game.

27

The One-Stage-Deviation-Principle How do we check if a strategy profile is a SPE of a multistage game with observed actions? We only need to check if there is a profitable deviation from that strategy profile for each stage. This is called the one-stage-deviation principle.

28

The One-Stage-Deviation-Principle For multistage games with observed actions the following result holds: For a given combination of strategies of the opponents, a players strategy is optimal from any stage of the game if and only if there is no stage of the game from which the player can gain by changing his strategy there, keeping it fixed at all other stages.

29

The One-Stage-Deviation-Principle

Theorem 1: In a finite-horizon multi-stage game with observed actions, pure-strategy profile s is subgame perfect if and only if it satisfies the one-stage deviation condition that no player i can gain by deviating from s in a single stage and conforming to s thereafter.

30

The One-Stage-Deviation-Principle Intuition for result: We can always divide a two-stage deviation into two one-stage deviations. If we can show that there is no incentive to deviate in a one stage deviation, then a two stage deviation is also not profitable.

31

The One-Stage-Deviation-Principle Implication of result: To check if a strategy profile s is a SPE of a multistage game with observed actions we need to check for every stage, every player, and every history of the game, if a player can gain by deviating at that stage and conforming to the strategy s thereafter.

32

The One-Stage-Deviation-Principle Example:

1 B 2 R L R 1 R L R

1 st

(a, b) (c, d ) (e, f ) ( g , h)

(k , l ) (m, n) (o, p )

2 nd

Player 1s strategy: (A, L if A, R if B) Player 2s strategy: (R if 1 plays A, L if 1 plays B)

The One-Stage-Deviation-Principle This game has two possible histories at the end of the first stage: (A, do nothing) or (B, do nothing). For history (A, do nothing) we need to check: If 1 can gain by playing R instead of L given that 2 is playing R, that is, if g > e . If 2 can gain by playing L instead of R assuming that 1 is playing L in stage 2, that is, if b > f .
34

The One-Stage-Deviation-Principle For history (B, do nothing) we need to check: If 1 can gain by playing L instead of R given that 2 is playing L, that is, if i > k . If 2 can gain by playing R instead of L assuming that 1 is playing R in stage 2, that is, if p > l . Finally, we need to verify If 1 wants to play B instead of A in the first stage assuming that 2 plays his strategy, that is, if k > e .
35

The One-Stage-Deviation-Principle We can use this example to illustrate why we dont need to check for a two-stage deviation. In this game only player 1 can do a two stage deviation since player 2 plays only once. Suppose 1 does the following two-stage deviation (B, R if A, L if B) whereas player 2 sticks to his equilibrium strategy (R if 1 plays A, L if 1 plays B).

36

The One-Stage-Deviation-Principle Example:

1 B 2 R L R 1 R L R

1 st

(a, b) (c, d ) (e, f ) ( g , h)

(k , l ) (m, n) (o, p )

2 nd

Player 1s strategy: (B, R if A, L if B) Player 2s strategy: (R if 1 plays A, L if 1 plays B)

The One-Stage-Deviation-Principle The payoff of 1 in his equilibrium strategy is e. The payoff of 1 in the two-stage deviation is i. For the two-stage deviation not to be profitable we must have i<e. For history (B, do nothing), 1 can NOT gain by playing L instead of R given that 2 is playing L when i < k . In the first stage 1 can NOT gain by playing B instead of A, assuming 2 plays his equilibrium strategy when k< e . Thus, i < k and k< e imply i< e .
38

The One-Stage-Deviation-Principle What happens if the horizon is infinite? Maybe a player can gain by some infinite sequence of deviations, even though he cannot gain by a singledeviation in any subgame. This possibility is excluded by the CIP property.

39

The One-Stage-Deviation-Principle

Theorem 2: In an infinite-horizon multi-stage game with observed actions that is continuous at infinitey, purestrategy profile s is subgame perfect if and only if it satisfies the one-stage deviation condition that no player i can gain by deviating from s in a single stage and conforming to s thereafter.

40