L3. Dynamic Games of Complete Information

TOC

1. Games of Perfect Information 1.1 Definition 1.2 Backwards Induction 1.3 Stackelberg Model of Duopoly 2. Games of Imperfect Information 2.1 Definition 2.2 Bank Runs 3. Extensive-form Representation 3.1 Definition 3.2 Information Set 3.3 Strategy 4. Subgame-Perfect Nash Equilibrium 4.1 Subgame 4.2 Application: Sequential Bargaining Game

1. Games of Perfect Information

1.1 Definition

Consider a two-player and two-stage game

Player 1 chooses an action L or R

Player 2 observes player 1’s action and then chooses an action L’ or R’

Each path (a combination of two actions) in the following tree is followed by two payoffs: the first for player 1 and the second for player 2.

Fig. Extensive-form representation using a game tree

The above game is an example of dynamic games of complete and perfect information. This type of games takes the following form:

Player 1 chooses an action from the feasible set

Player 2 observes and then chooses an action from the feasible set

Payoffs are and

Note that

may depend on the action , i.e.

Some action may even end the game, so that is an empty set (i.e., no choice of player 2)

The action is perfectly observed by player 2.

Some key features of dynamic games of complete and perfect information:

the moves occur in sequence

all previous moves are observed before the next move is chosen

the players’ payoffs from each combination of moves are common knowledge

To solve this type of games, we use backwards induction

1.2 Backwards Induction

In the second stage, player 2 observes the action (say ) chosen by player 1 in the first stage, and then chooses an action by solving

Assume this optimization problem has a unique solution denoted by which player 2’s best response to player 1’s action .

In the first stage, knowing player 2’s best response, player 1’s problem becomes

Assume it also has a unique solution, denoted by .

We call the backwards-induction outcome of the game.

Note that is determined by maximizing , and . However, may not maximize . Consider the following game

. The backwards-induction outcome is . However, given , the best response of player 1 is not .

1.3 Stackelberg Model of Duopoly

Consider a dominant firm moving first and a follower moving second. The game is played as follows:

Firm 1 chooses a quantity

Firm 2 observes and then chooses a quantity

The payoff of firm is the profit

where and

Using Backwards induction to solve the game.

First, find function for firm 2, i.e., for any given , find that solves

where

Then we have

is the same as that in the Cournot model.

Second, firm 1 knows and solves

where

Clearly, for , firm 1’s profit is always negative. Thus we only need to solve

which leads to the following first-order condition

The optimal choice of firm 1 is

The market price is

Firms’ profits and the total profit are

Cournot model v.s. Stackelberg model

2. Games of Imperfect Information

2.1 Definition

Consider the following simple two-stage game:

Player 1 and 2 simultaneously choose actions and from the feasible sets and , respectively.

Player 3 and 4 observe the outcome of the first stage , and then simultaneously choose actions and from the feasible sets and , respectively.

The game differs from the two-stage game with perfect information, since there are simultaneous moves within each stage.

We solve this game by using the idea of backwards induction. For each given , player 3 and 4 try to find the Nash equilibrium in stage 2. Assume the second-stage game has a unique Nash equilibrium . Then, player 1 and player 2 play a simultaneous-move game with payoffs

Suppose is the unique Nash equilibrium of this simultaneous-move game, then

is the subgame-perfect outcome of the two-stage game.

2.2 Bank Runs

Two investors have each deposited $5 millions in a bank, the bank has invested these deposits in a long-term project. If the bank is forced to liquidate its investment before the project matures, a total of $8 millions can be recovered. If the bank allows the investment to reach maturity, the project will pay out a total of $16 millions. There are two dates at which the investors can make withdrawals at the bank: Date 1 is before the bank’s investment matures and Date 2 is after. Suppose there is no discounting.

Players’ payoffs on date 1:

Players’ payoffs on date 2:

Using Backwards induction,

At date 2, in the unique Nash equilibrium, both withdraw and each obtains $8.

At date 1, they play the following game:

There are two pure-strategy NE of this game:

Both withdraw and each obtains $4

Both don’t and each obtains $8

Therefore, there are 2 subgame-perfect outcomes of the original two-stage game:

Both withdraw on date 1 to obtain $4 ⇒ the case of bank run

Both don’t withdraw on date 1 but do on date 2, and obtain $8.

3. Extensive-form Representation

3.1 Definition

Normal-form Representation of Games

In static games, we consider normal-form representation to describe a game. The normal-form representation of a game specifies

the players in the game

the strategies available to each player

the payoff received by each player for each combination of strategies that could be chosen by the players

Extensive-form Representation of Games

In dynamic games, we need to use extensive-form representation, it specifies:

the players in the game

when each player has the move

what each player can do at each of his or her opportunities to move

what each player knows at each of his or her opportunities to move

the payoffs received by each player for each combination of moves that could be chosen by the players

Note the second to the fourth describe strategies of each player in detail.

We use game trees for extensive-form representations, an example is shown as below

In this example, the game tree begins with a decision node for player 1, which is also the initial node of the game. After player 1’s choice (L or R) is made, player 2’s decision node is reached. And player 2 needs to decide whether to choose L’ or R’. A terminal node is reached after player 2’s move (i.e., the game ends), and payoffs of players are realized.

3.2 Information Set

A dynamic game of complete and perfect information is a game in which the players move in sequence, all previous moves are observed before the next move is chose, and payoffs are common knowledge. Such games can be easily represented by a game tree.

For games with imperfect information, some previous moves are not observed by the player with the current move. To present this kind of ignorance of previous moves and to describe what each player knows at each of his/her move, we introduce the notion of a player’s information set.

Definition

An information set for a player is a collection of decision nodes satisfying:

The player needs to move at every node in the information set

When the play of the game reaches a node in the information set, the player with the move does not know which node in the set has (or has not) been reached.

The second condition implies that player must have the same set of feasible actions at each decision node in an information set; Otherwise the player could infer from the set of actions available that some node(s) had or had not been reached. Besides, Any two nodes from different information sets of a player can be distinguished from each other.

Information Set: Perfect v.s. Imperfect

In an extensive-form game, a collection of decision nodes, which constitutes an information set, is connected by a dotted line. We can use information set to differentiate perfect and imperfect information, a game is

of perfect information if every information set is a singleton.

of imperfect information if there is at least one non-singleton information set.

Static games can be re-modeled as dynamic games and vice versa. Let’s consider a two-player simultaneous-move (static) game as follows:

Player 1 chooses

Player 2 does not observe player 1’s move but chooses an

Payoffs are and

We can use an information set to describe player 2’ ignorance of player 1’s actions. The above static game of complete information can be represented as a dynamic game of complete but imperfect information. Take prisoner’s dilemma as example:

the normal-form representation is

the extensive-form representation is

3.3 Strategy

Definition

A strategy for a player is a complete plan of actions. It specifies a feasible action for the player in every contingency in which the player might be called on to act.

For dynamic games with complete information, a player’s strategy is a function which assigns an action to each information set (not each decision node) belonging to the player.

An action and a strategy do not make a big difference in static games, while they do in dynamic games.

For example (perfect information)

Player 1 has 2 actions (and also 2 strategies): L and R. Player 2 has 2 actions: L’ and R’, but 4 strategies: .

means if player 1 plays , then player 2 plays ; and if player 1 plays , then player 2 plays .

For imperfect information example (prisoner’s delimma):

Both players have two actions and also two strategies: Defect and Confess.

In the Cournot model of duopoly, firm ’s action and strategy is the same, i.e. .

In the Stackelberg model, the action and strategy for firm 1 (the leader) is again . For firm 2, the action is but its strategy is a function for any .

4. Subgame-Perfect Nash Equilibrium

Problems of NE

Question:

What’s the normal-form representation of this game? What’s the NE?

The normal-form representation is shown as below

There are two NE: and

For , it seems okay and respects the spirit of backwards induction.

However, for , player 2 should choose not if player 1 chooses . One interpretation is player 2 can threat player 1. But this threat is non-creditable. The contradiction is due to ignorance of dynamic feature.

4.1 Subgame

To capture the dynamic feature, we consider subgames.

Definition

A subgame is an extensive-form game

begins at a decision node n that is a singleton information set (but is not the game’s initial node)

includes all the decision and terminal nodes following node n in the game tree (but no nodes that do not follow n)

does not cut any information sets, i.e., if a decision node n’ follows n in the game tree, then all other nodes in the information set containing n’ must also follow n, and so must be included in the subgame.

Strategy: Perfect Nash Equilibrium

Definition

A Nash equilibrium is subgame-perfect, or is said to be a subgame-perfect Nash equilibrium if the player’s strategies constitute a Nash equilibrium in every subgame.

It can be shown that any finite dynamic game of complete information has a subgame-perfect Nash equilibrium, perhaps in mixed-strategies. To find subgame-perfect Nash equilibria, we first need to find Nash equilibria in each subgame, then use backwards-induction to solve for the whole game.

For above example (*), there are two subgames. For NE

in the left subgame, the Nash equilibrium involves the player 2 choosing R’ (NE of left subgame)

in the right subgame, the Nash equilibrium involves the player 2 choosing L’ (NE of rigth subgame)

However, for NE , the NE is not the NE of right subgame (i.e. this Nash equilibrium is not subgame-perfect Nash equilibrium).

Note that

Equilibrium v.s. Outcome

An equilibrium is a collection of players’ strategies (strategy profile), while an outcome is a collection of players’ actions.

Consider the following two-stage game of complete and perfect information:

Player 1 chooses an action ;

Player 2 observes and then chooses an action ;

Payoffs are and .

The best response solves and sovles

The backwards-induction outcome is and the subgame-perfect Nash equilibrium is . Note that is an action while is a strategy for player 2.

In above example (*):

is the backwards-induction outcome

while is the subgame-perfect Nash equilibrium

In the Stackelberg model:

The backwards-induction outcome is , where and .

while the subgame-perfect NE is where

4.2 Application: Sequential Bargaining Game

Suppose players 1 and 2 are bargaining over one dollar. They discount payoffs received a period later by a discount factor , where . Consider the following three-period bargaining game:

In the first period, player 1 proposes for himself and for player 2. Player 2 either accepts the offer to end the game or rejects the offer to continue the game.

In the second period, player 2 proposes for player 1 and for himself. Player 1 either accepts the offer to end the game or rejects the offer to continue the game.

In the third period, player 1 receives a share of the dollar, leaving to player 2.

The game tree is shown as below

Let and . In general, in period , and are offered to players 1 and 2, the offers satisfy

The present value of payoff to player is if the bargaining is ended in period .

We can use backwards induction to solve the game

In the second period, player 2 is at the move

if player 2 were to make palyer 1 not accept, the payoff of player 2 is always .

if player 2 wants player 1 to accept, the best choice is , which results the payoff for player 2.

Since , the best choice of player 2 is where player 1 will accept.

In the first period, player 1 is at the move.

the payoff to player 2 in period 2 is , thus player 2 will accept player 1’s offer iff

If player 1 wants player 2 to accept, the best choice is , which results the payoff for player 1

If player 1 were to make player 2 not accept, the payoff if always , which is less than

Thus the best choice of player 1 is , where player 2 will accept.

The backwards-induction outcome of the three-period bargaining game:

Player 1 offers the settlement

Player 2 accepts the offer, and the game ends.