L2. Static Games of Complete Information

TOC

1. Normal-form games 1.1 Motivating Examples 1.2 Definition 2. Concepts of strategies 2.1 Best response 2.2 Strictly dominated strategy 2.3 Strictly dominant strategy 2.4 Example 3. IESDS and Nash equilibrium 3.1 IESDS 3.2 Nash equilibrium 3.3 NE v.s. IESDS 4. Applications 4.1 Cournot Model of Duopoly 4.2 Bertrand Model of Duopoly 5. Mixed Strategies 5.1 Definition 5.2 Mixed Strategy Nash Equilibrium: two players 5.3 Examples 5.4 Mixed Strategy Nash Equilibrium: general setting

1. Normal-form games

1.1 Motivating Examples

Example 1: Prisoners’ Dilemma

Two suspects are arrested and charged with a crime. The police lack sufficient evidence to convict the suspects, unless at least one confesses.

The suspects are held in separate cells and told that:

if only one confesses, the confessor will go free while the person does not confess will surely be convicted and given a 9-month jail sentence

if both confess, each will be sent to jail for 6 month

finally, if neither confesses, both will be convicted of a minor offence and sentenced to jail for 1 month

Question: What should the suspects do?

Example 2: Battle of the Sexes

Suppose a couple wanted to meet this evening, but did not reach an agreement on whether to attend an opera or a football match. The husband would most of all like to go to the football game, while the wife would prefer the opera. Moreover, both would prefer to go to the same place rather than different ones.

Question: If they cannot communicate, where should they go?

1.2 Definition

The two motivating examples can be considered as static games of complete information. Static means one-shot while simultaneous means move. Complete information means that each player’s payoff function is common knowledge among all players. Such kind of games can be formalized by normal-form 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

The normal-form is also called strategic-form, which is denoted by

where denote players’ strategy sets/spaces, denote players’ payoff functions.

Let be a combination of strategies, on for each player. Then is the payoff to player if for each player chooses strategy .

Note that the payoff of a player depends not only on his own action but also on the actions of others ⇒ strategic interaction / interdependence.

For example 1, the normal-form representation is

, D means “Defect” and C means “Confess”.

The payoffs are represented by below bi-matrix

For example 2, the normal-form representation is

The payoffs are represented by below bi-matrix

2. Concepts of strategies

Notations

2.1 Best response

Definition:

In a normal-form game , the best response for player to a combination of other player’s strategies , denoted by , is referred to as the set of maximizers of

Note:

can be an empty set, a singleton, a finite set or an infinite set.

is called the best-response correspondence for player .

2.2 Strictly dominated strategy

Definition:

In a normal-form game , let . Strategy is strictly dominated (严格被占优) by strategy (or strategy strictly dominates strategy ), if for each feasible combination of the other players’ strategies, player ’s payoff from playing is strictly less than its payoff from playing , i.e.

is called a strictly dominated stratgy of player .

Note that a rational player will never choose a strictly dominated strategy.

2.3 Strictly dominant strategy

Definition:

In a normal-form game , is a strictly dominant strategy (严格占优策略) of player , if it strictly dominates any other strategies. Equivalently, if for each feasible combination of the other players’ strategies, player ’s payoff from playing is strictly larger than player ’s payoff from playing any other strategies, i.e.,

Note:

If a strictly dominant strategy exists, then it must be unique.

A rational player will always choose a strictly dominant strategy, if any.

2.4 Example

In Example 1:

Best response:

is a strictly dominated strategy for both players

is a strictly dominant strategy for both players

In Example 2:

Best response: , and

Neither player has any strictly dominated strategy

Neither player has any strictly dominant strategy

3. IESDS and Nash equilibrium

3.1 IESDS

Full name: Iterated Elimination of Strictly Dominated Strategies.

Example

Step 1:

Player 1 does not have a strictly dominated strategy

For player 2, R is a strictly dominated strategy, which is strictly dominated by M. Hence, player 2 will never choose R if he is rational.

If player 1 knows that player 2 is rational, then he can eliminate R from player 2’ s strategy space by playing the following game

Step 2:

Now player 1 has a strictly dominated strategy, which is strategy D

If player 2 also knows that

Player 1 knows that player 2 is rational
Player 1 is rational

then he can also eliminate D

The game is further reduced to

Step 3:

Now player 2 has a strictly dominated strategy, which is strategy L

Again L is eliminated if player 1 knows that

Player 2 knows that player 1 knows that player 2 is rational
Player 2 knows that player 1 is rational
Player 2 is rational

is the final outcome

Two main drawbacks of IESDS:

A key assumption: rationality of all players is common knowledge.

The prediction of IESDS may not be very precise, and sometimes it predicts nothing about the games. For example, IESDS can do nothing with the below game which, however, can be solved by Nash equilibrium

3.2 Nash equilibrium

Definition

In the n-player normal-form game , the strategy profile is a Nash equilibrium if

Equivalently,

is called the equilibrium strategy of player .

Interpretation

Each player’s strategy must be a best response, given other players’ equilibrium strategies

No single player wants to deviate unilaterally ⇒ strategically stable or self-enforcing

Way to find a Nash Equilibrium

In general, find best-response correspondence, and then solve the equations.

For a bi-matrix game, underline the payoff to each player’s best response for any given other player’s strategies. If there is a single entry where all payoffs are underlined, then it is a Nash equilibrium.

Example:

Previous example 1 and example 2

Issues on Nash Equilibrium

A Nash equilibrium needs not to be Pareto optimal, for example, prisoners’ dilemma

More generally, Nash equilibrium does not rule out the possibility that a subset of players can deviate jointly in a way that makes every player in the subset better off

The Nash equilibrium implicitly assumes that players know that each player is to play the equilibrium strategy. Given this knowledge, no player wants to deviate

3.3 NE v.s. IESDS

The relationship between Nash equilibrium and IESDS:

Proposition 1

In an n-player normal-form game , if the strategy profile is a Nash equilibrium, then they survive iterated elimination of strictly dominated strategies.

The proof is straightforward considersing the definition of Nash equilibrium.

Implications of Proposition 1:

Any Nash equilibrium can survive IESDS, and must be an outcome of IESDS, i.e.

Nash equilibrium is a stronger solution concept than IESDS

Nash equilibrium does not require that rationality is common knowledge

Example

IESDS has 4 outcomes:

There are only 2 NEs:

Proposition 2

Consider an n-player normal-form game , which is finite. If iterated elimination of strictly dominated strategies eliminate all but the strategy profile , then this strategy profile is the unique Nash equilibrium of the game.

4. Applications

4.1 Cournot Model of Duopoly

Suppose two firms (1 and 2) produce a homogeneous good, and compete in quantities. Let be the quantity produced by firm . The aggregate quantity of the good is denoted by . The inverse demand of the good is

The cost function of firm is , where . Translate the problem into a normal-form game.

Players: the two firms

Strategies:

Any quantity is a strategy of firm

Payoffs:

The pair of quantities is a Nash equilibrium if for each firm that solves:

or equivalently

where and .

To solve for the Nash equilibrium, we first need to find the best response correspondence of each player.

Case 1: When , player ’s payoff is

which is clearly maximized at . Thus, the best response of firm is .

Case 2: When , player ’s payoff is

The optimal is determined by the first-order-condition . Thus, the best response is .

In sum, the best response correspondence (or function) of player is

The Nash equilibrium is the intersection of two best response correspondences, which imply that

We can obtain by simultaneously solving

The unique Nash equilibrium is

Alternatively, we can solve for the Nash equilibrium graphically, i.e., can be determined by the intersection of the two best response curves.

4.2 Bertrand Model of Duopoly

Suppose two firms produce differentiated products and compete in prices. The demand for firm is

where , which suggests that the two products are substitutes. Firms’ marginal cost is again assumed to be , where .

At this time, the stategy space of firm is and any is a strategy.

The profit of firm is

The pair of prices is a Nash equilibrium if solves

which leads to

The Nash equilibrium is determined by

The unique Nash equilibrium is . Note that the problem only make sense if .

5. Mixed Strategies

Motivation: In some games, each player wants to outguess others, so that there is uncertainty regarding to the strategies chosen by the players. In order to incorporate such uncertainty by allowing players to randomize among their choices, we introduce mixed strategies.

5.1 Definition

In a normal-form game , suppose .

Each strategy is a pure strategy for player

A mixed strategy for player is a probability distribution ,for , where and

Note that there are only pure strategies for player , but infinitely many mixed strategies.

Any pure strategy is a special mixed strategy, i.e. and for all .

5.2 Mixed Strategy Nash Equilibrium: two players

If player 1 thinks that player 2 will play a mixed stategy , then player 1’s expected payoff of playing a pure strategy is

Expected payoff

Player 1’s expected payoff of playing a mixed strategy is

Mixed best response

A mixed strategy is a best response to if

for all over .

Similarly, if player 2 thinks player 1 will play a mixed strategy , then player 2’s expected payoff of playing a mixed strategy is

Mixed Strategy Nash Equilibrium

In a two-player normal-form game , the mixed strategy profile is a Nash equilibrium if each player’s mixed strategy is a best response to the other player’s mixed strategy:

and

Way to find mixed-strategy Nash equilibria

Consider the case with two players, each having two pure strategies. Let be a mixed strategy for player 1 and be a mixed strategy for player 2.

Player 1’s expected payoff of playing , given player 2’s strategy , is

For each or , we need to compute , denoted by such that is a best response to . is the set of solutions to :

Similarly, player 2’s expected payoff is

Given , the best response for player 2 is denoted by , which is the set of solutions to :

A mixed strategy Nash equilibrium is an intersection of the two best-response correspondences and . If is a mixed strategy Nash equilibrium, then

5.3 Examples

Matching Pennies

Two players each has a penny and must choose whether to display it with heads or tails facing up. If the two pennies match (HH or TT), then player 2 wins player 1’s penny. If the pennies do not match, then player 1 wins player 2’s penny.

Let be a mixed strategy for player 1, where is the probability player 1 chooses Heads. Similarly, let be a mixed strategy for player 2, where is the probability player 2 chooses Heads. We are trying to find and .

For player 1:

Player 1 chooses Heads iff

We have

Best response correspondence for player 1:

Similarly, for player 2

Best response correspondence for player 2:

As shown in the below figure, the graphs of best response correspondences and intersect only once at the point where .

Therefore, is the only Nash equilibrium in mixed strategies.

Battle of the Sexes

Let be a mixed strategy in which Husband chooses Opera with probability , and be a mixed strategy in which Wife chooses Opera with probability . Using same method as above, there are three Nash equilibria: .

Proposition: The pure strategies played with a positive probability in a mixed strategy Nash equilibrium survive IESDS.

Example where there are more than two strategies for a player.

Using IESDS, we can first eliminate , and then .

The reduced game is then as shown above right, which is identical to Battle of the Sexes.

5.4 Mixed Strategy Nash Equilibrium: general setting

In general, let be a mixed strategy profile, where , for .

The expected payoff for player is

The mixed strategy is a best response to if

for all probability distribution over .

Definition

In a normal-form game , the mixed strategy profile is a mixed-strategy Nash equilibrium if each player’s mixed strategy is a best response to the other players’ mixed strategies in terms of expected payoff, i.e.

for every over , and for all

Note: the comparation in the definition can also with all pure strategies, which can be proved are equal.

Existence of Nash equilibrium

Theorem (Nash, 1950): In the n-player normal-form game , if is finite and is finite for every , then there exists at least one Nash equilibrium, possibly involving mixed strategies.

The conditions are sufficient but not necessary conditions for the existence of a Nash equilibrium. Recall that in both Cournot and Betrand competition models, Nash equilibrium exists but the strategy space is infinte.

Strictly Dominated Strategy and Best Response

Proposition: A pure strategy is a strictly dominated strategy (dominated by a mixed strategy) if and only if it is never a best response (to mixed strategies).

Note that a pure strategy can be strictly dominated by a mixed strategy, even if it is not strictly dominated by any pure strategy. An example is shown as below

D is not strictly dominated by either U or M. But D is strictly dominated by a mixed strategy , i.e., playing U and M with a half probability. Therefore, D is never a best response.

Besides, a pure strategy can be a best response to a mixed strategy, even if it is not a best response to any pure strategy

D is not a best response to L or R. But D can be a best response to a mixed strategy chosen by player 2, if

i.e. . Therefore, D is not a strictly dominated strategy (because it is not a “never best response”)