Game Theory 002

Game Theory1 Robin Mason March 2, 2006

1 These

notes are based on to a large extent on the notes of Dirk Bergemann and Juuso Valimaki for similar courses at Yale University and the Helsinki School of Economics. I am grateful to them both for the permission to use and edit those notes.

Contents 1 Game Theory: An Introduction 1.1 Game Theory and Parlour Games—a Brief History . . . . . . 1.2 Basic Elements of Noncooperative Games . . . . . . . . . . . .

4 5 6

2 Normal Form Games 2.1 Pure Strategies . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Dominance . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Nash equilibrium . . . . . . . . . . . . . . . . . . . . . . . 2.3.1 Finite Normal Form Game . . . . . . . . . . . . . . 2.3.2 Cournot Oligopoly . . . . . . . . . . . . . . . . . . 2.3.3 Auctions with perfect information . . . . . . . . . . 2.4 Mixed Strategies . . . . . . . . . . . . . . . . . . . . . . . 2.4.1 Basics . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.2 Construction of a mixed strategy Nash equilibrium 2.4.3 Interpretation of mixed strategy equilibria . . . . . 2.5 Mixed Strategies with a Continuum of Pure Strategies . . 2.5.1 All pay auction . . . . . . . . . . . . . . . . . . . . 2.5.2 War of attrition . . . . . . . . . . . . . . . . . . . . 2.5.3 Appendix: Basic probability theory . . . . . . . . . 2.6 Appendix: Dominance Solvability and Rationalizability . . 2.6.1 Rationalizable Strategies . . . . . . . . . . . . . . . 2.7 Appendix: Existence of Mixed Strategy Equilibria . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

7 7 8 12 13 14 15 15 16 20 23 23 23 29 30 33 35 36

3 Extensive Form Games 3.1 Introduction . . . . . . . . . . 3.2 Definitions for Extensive Form 3.2.1 Introduction . . . . . . 3.2.2 Graph and Tree . . . .

. . . .

. . . .

38 38 40 40 40

1

. . . . . Games . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

CONTENTS

3.3 3.4 3.5

2

3.2.3 Game Tree . . . . . . . . . . . . . . . . . . . . . 3.2.4 Notion of Strategy . . . . . . . . . . . . . . . . Subgame Perfect Equilibrium . . . . . . . . . . . . . . 3.3.1 Finite Extensive Form Game: Bank-Run . . . . The Limits of Backward Induction: Additional Material Reading . . . . . . . . . . . . . . . . . . . . . . . . . .

4 Repeated Games 4.1 Finitely Repeated Games . . . . . . . . . . 4.2 Infinitely Repeated Games . . . . . . . . . 4.2.1 The prisoner’s dilemma . . . . . . . 4.3 Collusion among duopolists . . . . . . . . 4.3.1 Static Game . . . . . . . . . . . . . 4.3.2 Best Response . . . . . . . . . . . . 4.3.3 Collusion with trigger strategies . . 4.3.4 Collusion with two phase strategies

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

5 Sequential Bargaining 5.1 Bargaining with Complete Information . . . . . . . 5.1.1 Extending the Basic Model . . . . . . . . . . 5.2 Dynamic Programming . . . . . . . . . . . . . . . . 5.2.1 Additional Material: Capital Accumulation .

. . . . . . . .

. . . .

. . . . . . . .

. . . .

. . . . . .

. . . . . . . .

. . . .

6 Games of Incomplete Information 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 6.1.1 Example . . . . . . . . . . . . . . . . . . . . . . . 6.2 Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2.1 Strategy . . . . . . . . . . . . . . . . . . . . . . . 6.2.2 Belief . . . . . . . . . . . . . . . . . . . . . . . . . 6.2.3 Payoffs . . . . . . . . . . . . . . . . . . . . . . . . 6.3 Bayesian Game . . . . . . . . . . . . . . . . . . . . . . . 6.3.1 Bayesian Nash Equilibrium . . . . . . . . . . . . 6.4 A Game of Incomplete Information: First Price Auction 6.5 Conditional Probability and Conditional Expectation . . 6.5.1 Discrete probabilities - finite events . . . . . . . . 6.5.2 Densities - continuum of events . . . . . . . . . . 6.6 Double Auction . . . . . . . . . . . . . . . . . . . . . . . 6.6.1 Model . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . .

. . . . . . . .

. . . .

. . . . . . . . . . . . . .

. . . . . .

. . . . . . . .

. . . .

. . . . . . . . . . . . . .

. . . . . .

40 43 46 47 48 50

. . . . . . . .

51 51 54 54 55 55 56 57 58

. . . .

60 61 65 65 68

. . . . . . . . . . . . . .

70 70 70 71 71 72 72 72 73 74 75 76 78 80 80

CONTENTS

3

6.6.2 6.6.3

Equilibrium . . . . . . . . . . . . . . . . . . . . . . . . 81 Equilibrium Analysis . . . . . . . . . . . . . . . . . . . 81

7 Adverse selection (with two types) 7.1 Monopolistic Price Discrimination . . . . . . . . . . . . . . . . 7.1.1 First Best . . . . . . . . . . . . . . . . . . . . . . . . . 7.1.2 Second Best: Asymmetric information . . . . . . . . . .

85 85 86 87

8 Theoretical Complements 8.1 Mixed Strategy Bayes Nash Equilibrium 8.2 Sender-Receiver Games . . . . . . . . . . 8.2.1 Model . . . . . . . . . . . . . . . 8.3 Perfect Bayesian Equilibrium . . . . . . 8.3.1 Informal Notion . . . . . . . . . . 8.3.2 Formal Definition . . . . . . . . . 8.4 References . . . . . . . . . . . . . . . . .

89 89 90 90 90 90 91 94

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

Chapter 1 Game Theory: An Introduction Game theory is the study of multi-person decision problems. The focus of game theory is interdependence, situations in which an entire group of people is affected by the choices made by every individual within that group. As such they appear frequently in economics. Models and situations of trading processes (auction, bargaining), labor and financial markets, oligopolistic markets and models of political economy all involve game theoretic reasoning. There are multi-agent decision problems within an organization, many person may compete for a promotion, several divisions compete for investment capital. In international economics countries choose tariffs and trade policies, in macroeconomics, the central bank attempts to control price level. 1. What will each individual guess about the others’ choices? 2. What action will each person take? 3. What is the outcome of these actions? In addition we may ask 1. Does it make a difference if the group interacts more than once? 2. What if each individual is uncertain about the characteristics of the other players? 3. What do observed actions tell about unobservable characteristics of the player?

1

CHAPTER 1. GAME THEORY: AN INTRODUCTION

2

Three basic distinctions can be made at the outset 1. non-cooperative vs. cooperative games 2. strategic (or normal form) games and extensive (form) games 3. games with complete or incomplete information In all game theoretic models, the basic entity is a player. In noncooperative games the individual player and her actions are the primitives of the model, whereas in cooperative games coalition of players and their joint actions are the primitives. In other words, cooperative game theory can be interpreted as a theory that allows for binding contracts between individuals. These notes will consider only non-cooperative game theory.

1.1

Game Theory and Parlour Games—a Brief History

• E. Zermelo (1913) chess, the game has a solution, solution concept: backwards induction. • E. Borel (1913) mixed strategies, conjecture of non-existence. • J. v. Neumann (1928) existence of solutions in zero-sum games. • J. v. Neumann and O. Morgenstern (1944) Theory of Games and Economic Behavior: Axiomatic expected utility theory, Zero-sum games, cooperative game theory. • J. Nash (1950) Nonzero sum games and the concept of Nash equilibrium. • R. Selten (1965,75) dynamic games, subgame perfect equilibrium. • J. Harsanyi (1967/68) games of incomplete information, Bayesian equilibrium.

CHAPTER 1. GAME THEORY: AN INTRODUCTION

1.2

3

Basic Elements of Noncooperative Games

A game is a formal representation of a situation in which a number of individuals interact in a setting with strategic interdependence. The welfare of an agent depends not only on his own action but on the actions of other agents as well. The degree of strategic interdependence may often vary. Example 1 Monopoly, Oligopoly, Perfect Competition To describe a strategic situation we need to describe the players, the rules, the outcomes, and the payoffs or utilities. Example 2 Matching Pennies, Tick-Tack-Toe (Zero Sum Games). Example 3 Meeting in New York with unknown meeting place (Non Zero Sum Game, Coordination Game, Imperfect Information).

Chapter 2 Normal Form Games We start with games that have finitely many strategies for all players and where players choose their strategies simultaneously at the start of the game. In these games, the solution of the game can simply be obtained by searching (in a clever way) among all possible solutions.

2.1

Pure Strategies

We begin with a coordination game played simultaneously between Alice and Bruce. Both Alice and Bruce have a dichotomous choice to be made: either go to an art exhibition or to ballet. This strategic interaction can be represented by a double matrix as follows: The first entry in each cell is the

Alice

Bruce Art Ballet 2, 2 0, 0 0, 0 1, 1

Art Ballet

Figure 2.1: Coordination payoff of the “row player”. The second entry is the payoff of the “column player”. How should this game be played? What should each individual player do? But first we need to give a definition of a game. In order to describe a game, the set of players must be specified: I = {1, 2, ..., I} . 4

(2.1)

CHAPTER 2. NORMAL FORM GAMES

5

In order to describe what might happen in the interaction, we need to specify the set of possible choices, called strategies for each player ∀i, si ∈ Si ,

(2.2)

where each individual player i has a set of pure strategies Si available to him and a particular element in the set of pure strategies is denoted by si ∈ Si . Finally there are payoff functions for each player i: ui : S1 × S2 × · · · × SI → R.

(2.3)

A profile of pure strategies for the players is given by I

s = (s1 , ..., sI ) ∈ × Si i=1

or alternatively by separating the strategy of player i from all other players, denoted by −i: s = (si , s−i ) ∈ (Si , S−i ) . A strategy profile is said to induce an outcome in the game. Hence for any profile we can deduce the payoffs received by the players. This representation of the game is known as normal or strategic form of the game. Definition 4 (Normal Form Representation) The normal form ΓN represent a game as: ΓN = {I, {Si }i , {ui (·)}i } .

2.2

Dominance

The most primitive solution concept to games does not require knowledge of the actions taken by the other players. A dominant strategy is the best choice for a player in a game regardless of what the others are doing. The next solution concepts assumes that rationality of the players is common knowledge. Common knowledge of rationality is essentially a recursive notion, so that every player is rational, every player knows that every player is rational, every player knows that every player knows that every player is rational..., possibly ad infinitum. Finally, the Nash equilibrium concept requires that each player’s choice be optimal given his belief about the other players’ behaviour, and that this belief be correct in equilibrium.

CHAPTER 2. NORMAL FORM GAMES

Cooperate Defect

Cooperate 3, 3 4, 0

6 Defect 0, 4 1, 1

Figure 2.2: Prisoner’s Dilemma Consider next a truly famous game which figures prominently in the debate on the possibility of cooperation in strategic situations, the prisoner’s dilemma game: Besides its somewhat puzzling conclusion this game has another interesting property which comes to light when we analyze the payoff of each individual player, for the row player and for the column player In both

C D

C 3 4

D 0 1

Figure 2.3: Row player’s payoffs in Prisoner’s Dilemma

C D

C 3 0

D 4 1

Figure 2.4: Column player’s payoffs in Prisoner’s Dilemma cases, one strategy is better the other strategy independent of all choices made by the opponent. Definition 5 (Dominant Strategy) A strategy si is a dominant strategy for player i in ΓN if for all s−i ∈ S−i and for all s0i = 6 si , ui (si , s−i ) > ui (s0i , s−i ) . Definition 6 (Weakly Dominant Strategy) A strategy si is a dominant strategy for player i in ΓN if for all s−i ∈ S−i and for all s0i 6= si , ui (si , s−i ) ≥ ui (s0i , s−i ) ,

and ui si , s0−i > ui s0i , s0−i , for some s0−i ∈ S−i .

CHAPTER 2. NORMAL FORM GAMES

7

The most straightforward games to analyze are the ones that have dominant strategies for all players. In those games, there is little need to think about the strategic choices of others as the dominant strategy can never be beaten by another choice of strategy. Definition 7 (Dominant Strategy Equilibrium) If each player i in a game ΓN has a dominant strategy si , then s = (s1 , ..., sN ) is said to be a dominant strategy equilibrium of ΓN . Example 8 Second price auction (with complete information) is an example of a game with a dominant strategy equilibrium. Definition 9 (Purely Strictly Dominated) A strategy si ∈ Si is a purely strictly dominated strategy for player i in ΓN if there exists a pure strategy s0i 6= si , such that ui (s0i , s−i ) > ui (si , s−i ) (2.4) for all s−i ∈ S−i . Definition 10 (Purely Weakly Dominated) A strategy si is a weakly dominated strategy for player i in ΓN if there exists a pure strategy s0i 6= si , such that ui (si , s−i ) ≤ ui (s0i , s−i ) , for all s−i ∈ S−i

and ui si , s0−i < ui s0i , s0−i , for some s0−i ∈ S−i Now consider a game Γ0 obtained from the original game Γ after eliminating all strictly dominated actions. Once again if a player knows that all the other players are rational, then he should not choose a strategy in Γ0 that is never-best response to in Γ0 . Continuing to argue in this way leads to the outcome in Γ should survive an unlimited number of rounds of such elimination: Definition 11 (Iterated Pure Strict Dominance) The process of iterated deletion of purely strictly dominated strategies proceeds as follows: Set Si0 = Si . Define Sin recursively by  n−1 Sin = si ∈ Sin−1 @s0i ∈ Sin−1 , s.th. ui (s0i , s−i ) > ui (si , s−i ) , ∀s−i ∈ S−i ,

CHAPTER 2. NORMAL FORM GAMES Set Si∞

=

∞ \

8

Sin .

n=0

Si∞

The set is then the set of pure strategies that survive iterated deletion of purely strictly dominated strategies. Observe that the definition of iterated strict dominance implies that in each round all strictly dominated strategies have to be eliminated. It is conceivable to define a weaker notion of iterated elimination, where in each step only a subset of the strategies have to be eliminated. Here is an example of iterated strict dominance: α2 2, 3 0, 0

α1 (2) β1

(3)

β2 3, 2 1, 3

(1)

γ2 0, 1 4, 2

Figure 2.5: Iterated strict dominance which yields a unique prediction of the game, and the superscript indicates the order in which dominated strategies are removed. We might be tempted to suggest a similar notion of iteration for weakly dominated strategies, however this runs into additional technical problems as order and speed in the removal of strategies matters for the shape of the residual game as the following example shows: If we eliminate first β1 , then α2 is weakly α1 β1 γ1

α2 β2 3, 2 2, 2 1, 1 0, 0 1, 1 0, 0

Figure 2.6: Iterated weak dominance dominated, similarly if we eliminate γ1 , then β2 is weakly dominated, but if we eliminate both, then neither α2 nor β2 is strictly dominated anymore. A similar example is The discussion of domination demonstrated that less restrictive notion of play may often give good prediction.. However as the following example shows, it clearly is not enough for analyzing all strategic interactions. The next subsection develops a solution concept that singles out (M, M ) as the relevant solution of the above game.

CHAPTER 2. NORMAL FORM GAMES

T M B

9

L R 1, 1 0, 0 1, 1 2, 1 0, 0 2, 1

Figure 2.7: Iterated weak dominance 2 T M B

L M R 3, 0 0, 2 0, 3 2, 0 1, 1 2, 0 0, 3 0, 2 3, 0

Figure 2.8: No dominated strategies

2.3

Nash equilibrium

Let us now go back to the coordination game. How to solve this game. A solution should be such that every player is happy playing his strategy and has no desire to change his strategy in response to the other players’ strategic choices. A start is to do well given what the strategy chosen by the other player. So let us look at the game form the point of one player, and as the game is symmetric it is at the same time, the game of his opponent:

Art Ballet

Art 2 0

Ballet 0 1

Figure 2.9: Individual Payoffs in Battle of Sexes Definition 12 (Best Response) In a game ΓN , strategy si is a best response for player i to his rivals strategies s−i if ui (si , s−i ) ≥ ui (s0i , s−i ) for all s0i ∈ Si . Strategy si is never a best response if there is no s−i for which si is a best response. We can also put it differently by saying that si is a best response if si ∈ arg maxui (s0i , s−i ) ⇔ si ∈ BR (s−i ) ⇔ si ∈ BR (s) . s0i ∈Si

(2.5)

CHAPTER 2. NORMAL FORM GAMES

10

We could now proceed and ask that the best response property holds for every individual engaged in this play. Definition 13 (Pure Strategy Nash Equilibrium) A strategy profile s = (s1 , ..., sn ) constitutes a pure strategy Nash equilibrium of the game ΓN if for every i ∈ I, (2.6) ui (si , s−i ) ≥ ui (s0i , s−i ) , for all s0i ∈ Si . In other words, a strategy profile is a Nash equilibrium if each player’s strategy si is a best response to the strategy profile s−i of all the remaining players. In the language of a best response, it says that s ∈ BR (s) , and hence a pure strategy Nash equilibrium s is a fixed-point under the best response mapping. Let us now consider some more examples to test our ability with these new notions.

2.3.1

Finite Normal Form Game

Consider the Hawk-Dove game where two animals are fighting over some prey. Each can behave like a dove or like a hawk. How is this game played

Hawk Dove

Hawk 3, 3 4, 1

Dove 1, 4 0, 0

Figure 2.10: Hawk-Dove and what is logic behind it. There are two conflicting interpretations of solutions for strategic and extensive form games: • steady state (“evolutionary”). • deductive (“eductive”). The latter approach treats the game in isolation and attempts to infer the restrictions that rationality imposes on the outcome. The games we are considering next are economic applications. They are distinct from our previous

CHAPTER 2. NORMAL FORM GAMES

11

examples insofar as the strategy space is now a continuum of strategies. The first problem is indeed very continuous and regular optimization instruments apply directly. The second example has continuous but not differentiable, payoff functions and we shall proceed directly without using the regular optimization calculus.

2.3.2

Cournot Oligopoly

Consider the following Cournot model in which the sellers offer quantities and the market price is determined as a function of the market quantities. P (q1 , q2 ) = a − q1 − q2 The profit functions of the firms are: Πi = (a − q1 − q2 )qi and differentiated we obtain: Π0i = a − 2q1 − q2 ⇔

a − q1 a − q2 and q2 (q1 ) = , (2.7) 2 2 where q1 (q2 ) and q2 (q1 ) are the reaction functions or best response functions of the players. The steeper function is q1 (q2 ) and the flatter function is q2 (q1 ). While we can solve (2.7) directly, we realize the symmetry of the problem, which reduces the system of equation to a single equation, and a symmetric equilibrium, so that a−q q= 2 and a q= 3 and hence the profits are q1 (q2 ) =

 a a  a2 Πi q1 = , q2 = = . 3 3 9

(2.8)

CHAPTER 2. NORMAL FORM GAMES

2.3.3

12

Auctions with perfect information

Consider the following setting in which there are n bidders with valuations for a single good 0 < v1 < v2 < .... < vn < ∞. We shall consider two different auction mechanisms: the first and the second price auction. The object is given to the bidder with the highest index among all those who submit the highest bid. In the first price auction, the winner pays his own bid, in the second price auction, the winner pays the second highest bid. The payoff functions in the first price auction are   vi − bi if bi > bj , ∀j 6= i, (2.9) ui (vi , b1 , ..., bn ) = v − bi if bi ≥ bj , and if bi = bj ⇒ i > j.  i 0, otherwise and in the second price auction   vi − bk ui (vi , b1 , ..., bn ) = v − bk  i 0,

they are if bi > bj , ∀j 6= i, if bi ≥ bj , and if bi = bj ⇒ i > j. otherwise

(2.10)

where bk satisfies the following inequality bi ≥ bk ≥ bj , ∀j 6= i, k. We can then show that the equilibrium in the first-price auction has the property that the bidder with the highest value always wins the object. Notice that this may not be true in the second price auction. However we can show that in the second price auction, the bid bi = vi weakly dominates all other strategies. Reading: Chapter 0 in Binmore (1992) is a splendid introduction into the subject. Chapter b of MWG and Chapter 1-1.2 in Gibbons (1992) covers the material of the last two lectures as does Chapter 1-1.2 in FT.

2.4

Mixed Strategies

So far we were only concerned with pure strategies, i.e. situations where each player i picks a single strategy si . However some games don’t have

CHAPTER 2. NORMAL FORM GAMES

13

equilibria in pure strategies. In these cases it is necessary to introduces an element of “surprise” or “bluff” through considering randomized decisions by the players. Consider the game of “matching pennies”:

Heads Tails

Heads 1, −1 −1, 1

Tails −1, 1 1, −1

Figure 2.11: Matching Pennies It is immediate to verify that no pure strategy equilibrium exists. A similar game is “Rock, Paper, Scissors”:

R P S

R P S 0, 0 −1, 1 1, −1 1, −1 0, 0 −1, 1 −1, 1 1, −1 0, 0

Figure 2.12: Rock, Paper, Scissors

2.4.1

Basics

Let us now introduce the notation for mixed strategies. Besides playing a pure strategy si each player is also allowed to randomize over the set of pure strategies. Formally, we have Definition 14 A mixed strategy for player i, σi : Si → [0, 1] assigns to each pure strategy si ∈ Si , a probability σi (si ) ≥ 0 that it will be played, where X σi (si ) = 1 si ∈Si

The mixed strategy can be represented as a simplex over the pure strategies: ( ) n X ∆ (Si ) = (σi (s1 ) , ..., σi (sn )) ∈ Rn : σi (sik ) ≥ 0, ∀j, and σi (sik ) = 1 . k=1

This simplex is also called the mixed extension of Si . For |Si | = 3, it can be easily represented as a two-dimensional triangle sitting in a three dimensional

CHAPTER 2. NORMAL FORM GAMES

14

space. σi (si ) is formally a probability mass function and σi is a probability vector. Such a randomization is called a mixed strategy σi which is a element of set of distributions over the set of pure strategies: σi ∈ ∆ (Si ) . An alternative notation for the set of mixed strategies, which you may find frequently is σi ∈ Σi . In order to respect the idea that the players are choosing their strategies simultaneously and independently of each other, we require that the randomized strategies chosen by the different players satisfy statistical independence.1 In other words, we require that the probability of a pure strategy profile s0 = (s01 , ..., s0N ) is chosen is given by N Y

σi (s0i ) .

i=1

The expected utility of any pure strategy si when some of the remaining players choose a mixed strategy profile σ−i is ! X Y ui (σ1 , ..., σi−1 , si , σi+1 , ..., σI ) = σj (sj ) ui (s1 , ..., si−1 , si , si+1 , ..., sI ) . s−i ∈S−i

j6=i

Similarly, the expected utility of any mixed strategy σi is ! X Y ui (σ1 , ..., σi−1 , σi , σi+1 , ..., σI ) = σj (sj ) ui (s1 , ..., si−1 , si , si+1 , ..., sI ) . s∈S

j

As another example, consider the famous “battle of the sexes” game: This game has clearly two pure strategy equilibria. To see if it has a mixed 1

Much of what follows can be generalized to the case where this independence condition is dropped. The resulting solution concept is then called correlated equilibrium. Since independence is a special case of such correlated random strategies, the analysis below is a special case of correlated equilibrium. The notion of sunspots, familiar from macroeconomic models is an example of correlated strategies. There all players observe a signal prior to the play of the game, and condition their play on the signal even though the signal may be completely unrelated to the underlying payoffs.

CHAPTER 2. NORMAL FORM GAMES

Opera Football

Opera 2, 1 0, 0

15 Football 0, 0 1, 2

Figure 2.13: Battle of Sexes strategy equilibrium as well, calculate the payoff to Sheila if Bruce is choosing according to mixed strategy σB (·): uS (O, σB ) = 2σB (O) + 0σB (F ) , and similarly uS (F, σB ) = 0σB (O) + 1σB (F ) . Again this allows for an illuminating graphical representation by the bestresponse function. Consider the best-response mapping of the two players, where we plot the probability of attending the football game for Sheila on the x- axis and for Bruce on the y- axis. Every point of intersection indicates a Nash equilibrium. An equilibrium mixed strategy by Sheila would be written as   1 2 (2.11) σS = σS (O) = , σS (F ) = 3 3 and if the ordering of the pure strategies is given, then we can write (2.11) simply as   2 1 , . σS = 3 3 Before we give a systematic account of the construction of a mixed strategy equilibrium, let us extend our definitions for pure strategies to those of mixed strategies. Definition 15 (Normal Form Representation) The normal form representation ΓN specifies for each player i a set of strategies Σi , with σi ∈ Σi and a payoff function ui (σ1 , ..., σn ) giving the von Neumann-Morgenstern utility levels associated with the (possible random) outcome arising from strategies (σ1 , ..., σn ) :  ΓN = I, (Σi , ui )i∈I .

CHAPTER 2. NORMAL FORM GAMES

16

 Definition 16 (Best Response) In game ΓN = I, (Σi , ui )i∈I , strategy σi is a best response for player i to his rivals strategies σ−i if ui (σi , σ−i ) ≥ ui (σi0 , σ−i ) for all σi0 ∈ Σi . ∗ Definition 17 (Nash Equilibrium) A mixed strategy profile σ ∗ = (σ1∗ , ..., σN )  constitutes a Nash equilibrium of game ΓN = I, (Σi , ui )i∈I if for every i = 1, ..., I;

∗ ∗ (2.12) ≥ ui σi , σ−i ui σi∗ , σ−i

for all σi ∈ Σi . Lemma 18 Condition (2.12) is equivalent to:

∗ ∗ ui σi∗ , σ−i ≥ ui si , σ−i ,

(2.13)

for all si ∈ Si , since any mixed strategy is composed of pure strategies. Since this is the first proof, we will be somewhat pedantic about it. Proof. Suppose first that (2.12) holds. Then, it is sufficient (why?) to show that for every s0i ∈ Si , there exists σi0 ∈ Σi such that

∗ ∗ ui σi0 , σ−i ≥ ui s0i , σ−i But since the set of pure strategies is a strict subset of the set of mixed strategies, or Si ⊂ Σi , we can simply set σi0 = s0i , and hence it follows that (2.13) has to hold. Next suppose that (2.13) holds and we want to show that this implies that (2.12) holds. It is then sufficient (again, why) to show that for every σi0 ∈ Σi , there exists s0i ∈ Si such that

∗ ∗ ui s0i , σ−i ≥ ui σi , σ−i . But since every mixed strategy σi is composed out of pure strategies, in particular since

X ∗ ∗ ui σi , σ−i = σi (si ) ui si , σ−i , si ∈Si

CHAPTER 2. NORMAL FORM GAMES

17

consider the pure strategy si
among all those with σi (si ) > 0 which achieves ∗ the highest payoff ui si , σ−i . Then it must be the case that

∗ ∗ ui si , σ−i ≥ ui σi , σ−i , and hence the conclusion. The following proposition indicates how to construct mixed strategy equilibria. Let Si+ (σi ) = {si ∈ Si |σi (si ) > 0} , then Si+ (σi ) is the set of all those strategies which receive positive probability under the mixed strategy σi . As Si+ (σi ) contains all points for which σi assigns positive probability, it is mathematically referred to as the support of Si . Proposition 19 (Composition) Let Si+ (σi∗ ) ⊂ Si denote the set of pure strategies that player i plays with positive probability in a mixed strategy profileσ ∗ = (σ1∗ , ..., σI∗ ). Strategy profile σ ∗ is a Nash equilibrium in game ΓN = I, (Σi , ui )i∈I if and only if for all i = 1, ..., I

∗ ∗ (i) ui si , σ−i = ui s0i , σ−i for all si , s0i ∈ Si+ (σi∗ ) ;

∗ ∗ (ii) ui si , σ−i ≥ ui s0i , σ−i for all si ∈ Si+ (σi∗ ) , s0i ∈ S.

2.4.2

Construction of a mixed strategy Nash equilibrium

We return to the example of the battle of sexes.

Sheila

Opera Football

Bruce Opera Football 2, 1 0, 0 0, 0 1, 2

Figure 2.14: Battle of Sexes Then a strategy for Sheila has the following payoff if Bruce is playing a mixed strategy σB (·) uS (σB , O) = 2σB (O) + 0σB (F ) ,

CHAPTER 2. NORMAL FORM GAMES

18

and similarly uS (σB , F ) = 0σB (O) + 1σB (F ) . We want to create a mixed strategy for Sheila and Bruce. If Sheila is supposed to use a mixed strategy, it means that she picks either alternative with a positive probability. As the strategy is supposed to be a best-response to her, it has to be the case that the expected payoffs are identical across the two alternative, for otherwise Sheila would clearly be better off to use only the pure strategy which gives her the strictly higher payoff. In short, it has to be that uS (σB , O) = uS (σB , F ) or explicitly 2σB (O) + 0σB (F ) = 0σB (O) + 1σB (F ) .

(2.14)

Thus when we consider whether Sheila will randomize, we examine conditions on the mixing behaviour of Bruce under which Sheila is indifferent. Let σB (F ) = σB and consequently σB (O) = 1 − σB . The condition (6.13) can then be written as 2 2 (1 − σB ) = σB ⇔ σB = . 3

(2.15)

Thus if Sheila is to be prepared to randomize, it has be that Bruce is randomizing according to (6.14). Now Bruce is willing to randomize with σB = 13 in equilibrium if and only if he is indeed indifferent between the pure strategy alternatives. So, now we have to ask ourselves when is this the case. Well, we have to investigate in turn how the indifference condition of Bruce determines the randomizing behaviour of Sheila. (The construction of the mixed strategy equilibrium highlights the interactive decision problem, which is essentially solved as a fixed point problem.) A similar set of conditions as before gives us uB (σS , O) = uB (σS , F ) or explicitly σS (O) + 0σS (F ) = 0σS (O) + 2σS (F ) .

(2.16)

CHAPTER 2. NORMAL FORM GAMES

19

Thus as we consider whether Bruce is willing to randomize, we examine conditions on the mixing behaviour of Sheila to make Bruce indifferent. Let σS (F ) = σS and consequently σS (O) = 1 − σS . The condition (6.19) can then be written as 1 (1 − σS ) = 2σS ⇔ σS = . 3

(2.17)

Thus we reached the conclusion that the following is a mixed strategy Nash equilibrium   2 1 ∗ σB = σB (O) = , σB (F ) = 3 3   2 1 ∗ σS = σS (O) = , σS (F ) = . 3 3 The payoff to the two players is then 32 in this mixed strategy equilibrium. This examples presents the general logic behind the construction of a mixed strategy Nash equilibrium. The only issue which we still have to discuss is the support of the mixed strategy equilibrium. The following game is a helpful example for this question:

α β γ

α β −1, 1 1, −1 1, −1 −1, 1 x, x x, x

γ x, x x, x x, x

Figure 2.15: Augmented Matching Pennies For x < 0, γ cannot be part of any mixed strategy equilibrium, and for x > 0, the original matching pennies equilibrium cannot be a mixed strategy equilibrium anymore. However for x = 0, there can be many mixed strategy equilibria, and they differ not only in the probabilities, but in the support as well.2 2

Verify that there can’t be an equilibrium in which randomization occurs between α and γ only, or alternatively between β and γ.

CHAPTER 2. NORMAL FORM GAMES

2.4.3

20

Interpretation of mixed strategy equilibria

Finally, consider the competing interpretations of a mixed strategy Nash equilibrium: 1. mixed strategies as objects of choice 2. steady state, probability as a frequency of certain acts 3. mixed strategies as pure strategies in a game where the randomness is introduced through some random private information (Harsanyi’s purification argument) Remark 20 In the battle of sexes, the mixed strategy equilibrium used private randomization by each player. Suppose instead they would have a common (or public) randomization device, say a coin, then they could realize a payoff of ( 32 , 32 ) by e.g. both going to opera if heads and both going to football if tails. Observe that this payoff is far superior to the mixed strategy equilibrium payoff The notion of public randomization is used in the correlated equilibrium. Finally we consider games where each player has a continuum of actions available. The first one is an example of an “all pay auction”.

2.5 2.5.1

Mixed Strategies with a Continuum of Pure Strategies All pay auction

Two investors are involved in a competition with a prize of v. Each investor can spend any amount in the interval [0, v]. The winner is the investor who spends the most. In the event of tie each investor receives v/2. Formulate this situation as a strategic game and find its mixed strategy Nash equilibria. The all pay auction is, despite its initially funny structure, a rather common strategic situation: Raffle, R&D patent races, price wars of attrition, wars, winner take all contests with participation costs.

CHAPTER 2. NORMAL FORM GAMES

21

The payoff function of the very agent is therefore given by  for bj < bi  v − bi 1 ui (v, bi , bj ) = v − bi , for bi = bj  2 −bi for bi < bj The mixed (or pure) strategy by player i can be represented by the distribution function of the bid of i: Fi (bi ) , where we recall that the distribution function (or cumulative distribution function) Fi (bi ) is defining the event Fi (bi ) = Pr (b ≤ bi ) We recall the following notation:
F b− = lim F (a) , a↓b

and
F b+ = lim F (a) . a↑b

Before we can analyze and derive the equilibrium, we have to ask what is the expected payoff from submitting a bid b1 given that player 2 uses an arbitrary distribution function F2 . From the payoff functions, we see that it can be calculated as: E [u1 (v, b1 ) |F2 ] = F2 (b2 < b1 ) (v − b1 ) +   1 v − b1 + (1 − F (b2 ≤ b1 )) (−b1 ) , (F2 (b2 ≤ b1 ) − F2 (b2 < b1 )) 2 which can be written more compactly as


1 − E [u1 (v, b1 ) |F2 ] = F2 b− v − b1 . 1 v + F2 (b1 ) − F2 b1 2

(2.18)

This expected payoff function shows that in this auction the bidder has to find the best trade-off between increasing the probability of winning and the cost associated with increasing the bid.

CHAPTER 2. NORMAL FORM GAMES

22

We suppose for the moment that the distribution function F2 (·) is continuous(ly differentiable) everywhere. Then (2.18) can be rewritten as E [u1 (v, b1 ) |F2 ] = F2 (b1 ) v − b1 . As agent i chooses his bids optimally in equilibrium, his bid must maximize his payoff. In other words, his optimal bidding strategy is characterized by the first order conditions which represent the marginal benefit equals marginal cost condition f2 (b1 ) v − 1 = 0, (2.19) which states that the increase in probability of winning which occurs at the rate of f (b1 ) multiplied by the gain of v must equal the marginal cost of increasing the bid which is 1. As we attempt to construct a mixed strategy equilibrium, we know that for all bids with f1 (b1 ) > 0, the first order condition has to be satisfied. Rewriting (2.19) we get 1 f2 (b1 ) = . v

(2.20)

As we look for a symmetric equilibrium, in which agent i and j behave identically, we can omit the subscript in (6.4) and get a uniform (constant) density 1 f ∗ (b) = v with associated distribution function: b F ∗ (b) = . v

(2.21)

As F (b = 0) = 0 and F (b = v) = 1, it follows that F ∗ (b) in fact constitutes a mixed equilibrium strategy. We went rather fast through the derivation of the equilibrium. Let us now complete the analysis. Observe first that every pure strategy can be represented as a distribution function. We start by explaining why there can’t be a pure strategy equilibrium in the all-pay auction, or in other words why there can be no atoms with probability 1. Lemma 21 (Non-existence of pure strategy equilibrium) @ a pure strategy equilibrium in the all pay auction.

CHAPTER 2. NORMAL FORM GAMES

23

Proof. We argue by contradiction. Suppose therefore that there is a pure strategy equilibrium. Then either (i) bi > bj or (ii) bi = bj . Suppose first that bi > b j then bi would lower his bid and still win the auction. Suppose then that bi = bj . The payoff of bidder i would then be 1 v − bi , 2 but by increasing the bid to bi + ε for small ε, he would get the object for sure, or v − bi − ε. As ε → 0, and when taking the difference, we see that i would have a jump in his net utility of 12 v as   1 1 1 v − bi = v − ε → v, v − bi − ε − 2 2 2 which concludes the proof. As we have now shown that there is no pure strategy equilibrium, we can concentrate on the derivation of a mixed strategy equilibrium. In the derivation above, we omitted some possibilities: (i) it could be that the distribution function of agent i is not continuous and hence has some mass points or atoms, (ii) we have not explicitly derived the support of the distribution. We will in turn solve both problems. A similar argument which excludes a pure strategy (and hence atoms with mass one) also excludes the possibility of atoms in mixed strategy equilibrium. Lemma 22 (Non-existence of mass points in the interior) @ a mixed strategy equilibrium with a mass point b in the interior of the support of either player’s mixed strategy ( i.e. Fi (b) − Fi (b− ) > 0 for some i) in the all pay auction.

CHAPTER 2. NORMAL FORM GAMES

24

Proof. Suppose to the contrary that the strategy of player j contains an atom so that for some b,
Fj (b) − Fj b− > 0, If Fj (·) has an atom at b, then for any ε > 0, it must be that Fi (b) − Fi (b − ε) > 0, otherwise j could lower the bids at the atom without changing the probability of winning. But consider the winnings of i at b0 < b. They are at best
vFj b− − b− 00

but by increasing the bid to b > b, i would receive  0 vFj b − b0 . 0

00

But letting b ↑ b and b ↓ b, we can calculate the expected payoff difference between     0   00 

0 00 lim00 vFj b − b − vFj b − b = v Fj (b) − Fj b− > 0, b0 ↑b, b ↓b

(2.22) and hence would offer a profitable deviation for player i.  Notice the argument applies to any b < v, but not for b ≥ v, and hence there could be atoms at the upper bound of the support of the distribution.3 It then remains to find the mixed strategy equilibrium which has an interval as its support. Suppose Fi (bi ) is the distribution functions which defines the mixed strategy by player i. For her to mix over any interval   bi ∈ bi , bi (2.23) 3

Recall the support of a (density) function is the closure of the set {x : f (x) 6= 0} ,

and thus the support is supp f = {x : f (x) 6= 0}

CHAPTER 2. NORMAL FORM GAMES

25

she has to be indifferent: vFj (b) − b = c,

(2.24)

where c is the expected payoff from any mixed strategy equilibrium. Argue that c = 0, then we solve the equation to b Fj (b) = , v

(2.25)

which tells us how player j would have to randomize to make player i indifferent. The argument is actually already made by the derivation of the first order conditions and the observation that there can’t be any atom in the interior of [0, v]. By symmetry, (2.25) then defines the equilibrium pricing strategy by each player. Suppose we were to increase the number of bidders, then (6.10) changes under the assumption of symmetry to v (F (b))n−1 − b = c,

(2.26)

where c is the expected payoff from any mixed strategy equilibrium. Argue again that c = 0, then we solve the equation to 1   n−1 b F (b, n) = v

(2.27)

and the expected payment of each individual bidder is Z v Z v bdF (b) = bf (b) db 0

0

and since F 0 (b) = f (b) = we obtain Z 0

v

b v

b v

(n − 1) b

1
n−1

(n − 1)

1
n−1

db =

v . n

(2.28)

CHAPTER 2. NORMAL FORM GAMES

2.5.2

26

War of attrition

Suppose two players are competing for a prize of value v. They have to pay c per unit of time to stay in the competition. If either of the two player drops out of the competition, then the other player gets the object immediately. This is a simple example of a timing game, where the strategy is defined by the time τi at which the player drops
out. There are pure strategy Nash c equilibria, which have τi = 0, τj ≥ v , however the only symmetric equilibrium is a mixed strategy equilibrium, where each player must be indifferent between continuing and dropping out of the game at any point in time, or fi (t) fi (t) c v=c⇔ = , 1 − Fi (t) 1 − Fi (t) v where the indifference condition may be interpreted as a first order differential equation c dFi (t) = . (1 − Fi (t)) v It is very easy to solve this equation once it is observed that the left hand side in the equation is d − ln (1 − Fi (t)) . dt Hence integrating both sides and taking exponentials on both sides yields c

c

1 − Fi (t) = e− v t , or Fi (t) = 1 − e− v t . Alternatively, we may appeal to our knowledge of statistics, recognize fi (t) 1 − Fi (t) as the hazard rate4 , and notice that only the exponential distribution function 4

To understand why this is called the hazard rate, think of t as the time a machine fails. Then as time t passes, and moving from t to t + dt, one finds that the conditional probability that the machine fails in this interval, conditional on not having failed before is f (t) dt . 1 − F (t) Als recall that the conditional probability is P (A |B ) =

P (A ∩ B) P (B)

CHAPTER 2. NORMAL FORM GAMES

27

has a constant hazard ratio λ F (t) = 1 − e−λt and f (t) = λe−λt . The symmetric equilibrium is then given by: c

F (t) = 1 − e− v t and the expected time of dropping out of the game, conditional on the other player staying in the game forever is Z ∞ Z ∞ v tdF (t) = tf (t) dt = . c 0 0

2.5.3

Appendix: Basic probability theory

The general framework of probability theory involves an experiment that has various possible outcomes. Each distinct outcome is represented by a point in a set, the sample space. Probabilities are assigned to certain outcomes according to certain axioms. More precisely X is called a random variable, indicating that the value of X is determined by the outcome of the experiment. The values X can take are denoted by x. We can then refer to events such as {X = x} or {X ≤ x} and the sample space is X . We distinguish two cases of probability distributions: discrete and continuous. Discrete Case In the discrete case, the numbers of possible outcomes is either finite or countable and so we can list them. Consider the following experiment in which the numbers x ∈ {1, 2, 3, 4} are drawn with probabilities p (x) as indicated. Any point x with p (x) > 0 is called a mass point or an atom. The function p (·) is a probability mass function p : X → [0, 1] , such that X x∈X

p (x) = 1.

CHAPTER 2. NORMAL FORM GAMES

28

This is an example of discrete probabilities. The cumulative distribution function is then given by X F (z) = p (z) . x≤z

Notice that F (x) is a piecewise constant function, which is monotonically increasing and at the points x ∈ {1, 2, 4} discontinuous. The function F (x) is zero before 1 and 1 at and after 4. Continuous Case Suppose next that we wish to choose any number between x ∈ [0, 4]. The assignment of probabilities occurs via the density function f (x) ≥ 0, so that Z 4 f (x) dx = 1. 0

The likelihood that we pick a number x ≤ x0 is then given by 0

0

Z

x0

F (x ) = F (x ≤ x ) =

f (x) dx 0

The likelihood that a number x ∈ [x0 , x00 ] is chosen in the experiment is given by Z x00 00 0 F (x ) − F (x ) = f (x) dx x0

In other words, any interval of numbers [x, x0 ] has some positive probability of being chosen. An example of such a distribution function is then given by:   0,
3 for x < 0 (2.29) F (x) = 1 − 1 − 41 x , for 0 ≤ x ≤ 4  1, for x > 4. We may then ask what is the probability that a number is drawn out of the interval (x, x0 ), and it is given by F (x0 ) − F (x) .

CHAPTER 2. NORMAL FORM GAMES

29

The density function then identifies the rate at which probability is added to the interval by taking the limit as ∆ = x0 − x converges to zero: F (x + ∆) − F (x) F (x0 ) − F (x) = . 0 ∆→0 x −x ∆

f (x) = lim

Notice that the density is only the rate at which probability is added to the interval, but is not the probability of a particular x, call it xˆ occurring since the probability of xˆ occurring is of course 0 under a continuous distribution function, since Z x ˆ

f (x) dx = 0. x ˆ

Thus we have to distinguish between events which have probability zero, but are possible and impossible events. The density function associated with the distribution function F (x) is given by   0,
2 for x < 0 1 3 f (x) = 1 − 4 x , for 0 ≤ x ≤ 4  4 0 for x > 4. Mixed Case Finally, we can of course have distribution functions with continuous and discrete parts. We saw an example of this in the case of a mixed strategy with an atom. Notice that the discrete probability mass introduces a discontinuity in the distribution function so that
F p− = lim F (p0 ) 6= F (p) . 0 p ↑p

The point x = 2 is often called an atom as it carries strictly positive probability to the distribution function. Expectations The density function f (x) is of course Z x F (x) = f (z) dz −∞

CHAPTER 2. NORMAL FORM GAMES

30

as we had in the discrete case the analogous expression in the sum X F (x) = p (z) . z≤x

Finally we can take the expectation of the lottery as Z ∞ zf (z) dz E [x] = −∞

or for discrete random variables E [x] =

X

zp (z)

z

Reading: Recall: A brief review of basic probability concepts, including sample space and event, independent events, conditional probabilities and Bayes’ formula, discrete and continuous random variables, probability mass function, density and distribution function, all introduced in Ross (1993), Chapter 1–2.4 is highly recommended. Osborne and Rubinstein (1994), chapter 3 contains a very nice discussion of the interpretation and conceptual aspects of the equilibrium notion, especially in its mixed version.

2.6

Appendix: Dominance Solvability and Rationalizability

In this section, we elaborate on the notion of iterated deletion of dominated strategies. We define dominance in a way that allows for the use of mixed strategies as well and we also connect this concept to the notion of rationalizable strategies where the question is phrased in terms of finding a set of mutually compatible strategies in the sense that all such strategies are best responses to some element in the other players’ allowed set of strategies. Nash equilibrium is a special case of this concept where it is also required that the sets of allowed strategies are singletons for all players. Definition 23 (Strictly Dominated) A strategy si ∈ S i is a strictly dom inated strategy for player i in game ΓN = I, (Σi , ui )i∈I if there exists a mixed strategy σi0 6= si , such that ui (σi0 , s−i ) > ui (si , s−i )

(2.30)

CHAPTER 2. NORMAL FORM GAMES

31

for all s−i ∈ S−i . Remark 24 This notion of dominance is based on domination by pure or mixed strategies. Clearly, more strategies can be dominated if we allow mixed strategies to be in the set of dominating strategies. Definition 25 (Never-Best response) A strategy si is never-best response if it is not a best response to any belief by player i. In other words, for all σ−i ∈ Σ−i , there is a s0i such that

0 0 ui s0i , σ−i > ui si , σ−i . Lemma 26 In a two player game, a strategy si of a player is never-best response if and only if it is strictly dominated. The notion of strict dominance has hence a decision-theoretic basis that is independent of the notion of mixed strategy.5 Now consider a game Γ0 obtained from the original game Γ after eliminating all strictly dominated actions. Once again if a player knows that all the other players are rational, then he should not choose a strategy in Γ0 that is never-best response to in Γ0 . Continuing to argue in this way leads to the outcome in Γ should survive an unlimited number of rounds of such elimination: Definition 27 (Iterated Strict Dominance) The process of iterated deletion of strictly dominated strategies proceeds as follows: Set Si0 = Si , and Σi = Σ0i . Define Sin recursively by  n−1 Sin = si ∈ Sin−1 @σi ∈ Σn−1 , s.th. u (σ , s ) > u (s , s ) , ∀s ∈ S , i i −i i i −i −i i −i and similarly Σni = {σi ∈ Σi |σi (si ) > 0 only if si ∈ Sin } . Set Si∞

=

∞ \

Si ,

i=1 5

The above Lemma extends to more than two players if all probability distributions on S−i and not only the ones satisfying independence are allowed.

CHAPTER 2. NORMAL FORM GAMES

32

and 0  ∞ 0 , s ) > u (σ , s ) , ∀s ∈ S ∈ Σ s.th. u (σ = σ ∈ Σ @σ Σ∞ −i i i −i −i i i i i −i i i i The set Si∞ is then the set of pure strategies that survive iterated deletion of strictly dominated strategies. The set Σ∞ i is the set of player’s i mixed strategies that survive iterated strict dominance.

2.6.1

Rationalizable Strategies

The notion of rationalizability begins by asking what are all the strategies that a rational player could play? Clearly, a rational player will play a best response to his beliefs about the play of other players and hence she will not use a strategy that is never a best response. Hence such strategies may be pruned from the original game. If rationality of all players is common knowledge, then all players know that their opponents will never use strategies that are never best responses. Hence a player should use only strategies that are best responses to some belief of other players’ play where the others are not using never best response strategies. Iteration of this reasoning leads to a definition of rationalizable strategies. Denote the convex hull of A by co (A) . In other words, co (A) is the smallest convex set containing A. Definition 28 (Rationalizable Strategies) Set Σ0i = Σi and for each i define recursively 

∃σ−i ∈ ×j6=i co Σn−1 , s.th. ui (σi , σ−i ) ≥ ui (σi0 , σ−i ) , ∀σi0 ∈ Σn−1 . Σni = σi ∈ Σn−1 i j i (2.31) The rationalizable strategies for player i are Ri =

∞ \

Σni .

(2.32)

n=0





I, (Σi , ui )i∈I , the strategies in ∆ (Si ) that survive the iterated removal of strategies that are never a best response are known as player i0 s rationalizable strategies. The reason for having the convex hull operator in the recursive definition is the following. Each point in the convex hull can be obtained as a randomization over undominated strategies for j 6= i. This randomization

CHAPTER 2. NORMAL FORM GAMES

33

corresponds to i0 s subjective uncertainty over j 0 s choice. It could fully well be that this random element is dominated as a mixed strategy for player j.
n−1 n−1 6= Σj in some cases. Hence co Σj Rationalizability and iterated strict dominance coincide in two player games. The reason for the coincidence is the equivalence of never-best response and strictly dominated in two player games which does not hold in three player games as the following example suggests. In the game below, we have pictured the payoff to player 3, and player 3 chooses either matrix A, B, C or D.

α1 β1

α2 9 0

β2 0 0 A

α1 β1

α2 0 9

β2 9 0 B

α1 β1

α2 0 0

β2 0 9

α1 β1

α2 6 0

C

β2 0 6 D

Figure 2.16: Rationalizable vs. undominated strategies where we can show that action D is not a best response to any mixed strategy of players 1 and 2, but that D is not dominated. If each player i can have a correlated belief about the others’ choices, the equivalence of ‘correlated rationalizability’ and iterated deletion of strictly dominated strategies can be established.

2.7

Appendix: Existence of Mixed Strategy Equilibria

Up to this point, we have not shown that mixed strategy equilibria exist for general games. We have simply assumed their existence and characterized them for some games. It is important to know that for most games, mixed strategy Nash equilibria do exist. The first existence result was proved by Nash in his famous paper Nash (1950). Theorem 29 (Existence in Finite Games) Finite games, i.e. games with a finite number of players and a finite number of strategies for each player, have a mixed strategy Nash equilibrium.

CHAPTER 2. NORMAL FORM GAMES

34

The proof of this result is a standard application of Kakutani’s fixed point theorem, and it is given in almost all graduate level textbooks, for instance the appendix to Chapter 8 in MWG give the proof. Many strategic situations are more easily modeled as games with a continuum of strategies for each player (e.g. the Cournot quantity competition mode above). For these games, slightly different existence theorems are needed. The simplest case that was also proved by Nash is the following (and also covered in the same appendix of MWG).  Theorem 30 (Continuous-Quasiconcave case) Let ΓN = I, (Si , ui )i∈I be a normal form game where I = {1, ..., N } for some N < ∞ and Si = [ai , bi ] ⊂ R for all i. Then if ui : S → R is continuous for all i and quasiconcave in si for all i, ΓN has a pure strategy Nash equilibrium. Observe that this theorem actually guarantees the existence of a pure strategy equilibrium. This results from the assumption of continuity and quasiconcavity. If either of these requirements is dropped, pure strategy equilibria do not necessarily exist. Unfortunately, the payoffs in many games of interest are discontinuous (e.g. the all pay auction and the war of attrition examples above show this). For these games, powerful existence results have been proved, but the mathematical techniques are a bit too advanced for this course. State of the art results are available in the recent article Reny (1999). The basic conclusion of that paper is that it will be very hard to find economically relevant games where existence of mixed strategy equilibria would be doubtful. An artificial game where no equilibria (in either pure or mixed strategies) exists is obtained by considering a modification of the Cournot quantity game. Recall that in that game, the payoffs to the two players are given by Πi (qi , qj ) = (a − q1 − q2 ) qi .
a a , If the payoffs are modified to coincide with these at all (q , q ) except 1 2 3 3
and πi a3 , a3 = 0 for both firms, then one can show that the game has no Nash equilibria. The argument to show this is that all of the strategies except for qi = a3 are deleted in finitely many rounds of iterated deletion of strictly dominated strategies. Hence none of those strategies can be in the support
of any mixed strategy Nash equilibrium. But it is also clear that a3 , a3 is not a Nash equilibrium of the game. Reading: Chapter 8 in MWG, chapter 2 in FT and to a lesser extent Chapter 1 in Gibbons (1992) cover the material of this chapter.

Chapter 3 Extensive Form Games 3.1

Introduction

This lecture covers dynamic games with complete information. As dynamic games, we understand games which extend over many periods, either finitely many or infinitely many. The new concept introduced here is the notion of subgame perfect Nash equilibrium (SPE), which is closely related to the principle of backward induction. The key idea is the principle of sequential rationality: equilibrium strategies should specify optimal behaviour from any point in the game onward. The notion of subgame perfect Nash equilibrium is a strengthening of the Nash equilibrium to rule out incredible strategies. We start with finite games, in particular games with a finite horizon. We then consider two of the most celebrated applications of dynamic games with complete information: the infinite horizon bargaining game of Rubinstein and the theory of repeated games. Example 31 Predation. There is an entrant firm and an incumbent firm. Sharing the market (1, 1) is less profitable than monopoly (0, 2), but it is better than a price war (−3, −1). Depict the game in the normal form and the extensive form. Characterize the equilibria of the game. Distinction between subgame perfect and Nash equilibrium. Credible vs. incredible threat. Future play (plan) affects current action. Example 32 Cournot Model.

Stackelberg Equilibrium.

35

Consider

CHAPTER 3. EXTENSIVE FORM GAMES

36

again the quantity setting duopoly with aggregate demand P (q1 , q2 ) = a − q1 − q2 and the individual profit function: Πi (qi , qj ) = (a − q1 − q2 )qi The best response function in the quantity setting game are, as we observed before, a − qi qj = R (qi ) = 2 Suppose player i moves first, and after observing the quantity choice of player i , player j chooses his quantity optimal. Thus i takes into account the reaction (function) of player j, and hence a qi a − qi )qi = ( − )qi 2 2 2 and the associated first-order conditions are a Π0i (qi , R (qi )) = − qi = 0. 2 The Stackelberg equilibrium is then  a a  a2 a , = q i = , Πi 2 2 4 8   a a a a2 q j = , Πj , = 4 2 4 16 The sequential solution method employed here is called “backward induction” and the associated Nash equilibrium is called the “subgame perfect” Nash equilibrium. Comparing with the Cournot outcome we find a a qiS + qjS ≥ qiC + qiC = + 3 3 but a2 = , ΠSj < ΠC ΠSi > ΠC i j . 9 This example illustrates the value of commitment, which is in this game simply achieved by moving earlier than the opponent. Notice that the Cournot equilibrium is still a Nash equilibrium. But is it reasonable? One has to think about the issue of “non credibility” and “empty threats”. Πi (qi , R (qi )) = (a − qi −

CHAPTER 3. EXTENSIVE FORM GAMES

3.2 3.2.1

37

Definitions for Extensive Form Games Introduction

The extensive form of the game captures (i) the physical order of play, (ii) the choices each player can take, (iii) rules determining who is to move and when, (iv) what players know when they move, (v) what the outcome is as a function of the players’ actions and the players’ payoff from each possible outcome, (vi) the initial condition that begin the game (move by nature).

3.2.2

Graph and Tree

We introduce all the elements of the conceptual apparatus, called the game tree. The language of a tree is borrowed from graph theory, a branch of discrete mathematics and combinatorics. A graph G is given by (V, E), where V = {v1 , ..., vn } is a finite set of nodes or vertices and E = {vi vj , vk vl , ..., vr vs } is a set of pairs of vertices (or 2-subsets of V), called branches or edges which indicates which nodes are connected to each other. In game theory, we are mostly interested in graphs that are directed. Edges in a directed graph are ordered pairs of nodes (v1 , vj ) and we say that the edge starts at vi and ends at vj . A walk in a graph G is a sequence of vertices, v1 , v2 , ...., vn such that vi and vi+1 are adjacent, i.e., form a 2-subset. If all its vertices are distinct, a walk is called a path. A walk v1 , v2 , ...., vn such that v1 = vn is called a cycle. A graph T is a tree if it has two properties (T 1) T is connected, (T 2) there are no cycles in T, where connected means that there is a path from every vertex to every other vertex in the graph. A forest is a graph satisfying (T 2) but not necessarily (T 1).

3.2.3

Game Tree

The game form is a graph T endowed with a physical order represented by ≺, formally (T, ≺) The order ≺ represents precedence on nodes. We write

CHAPTER 3. EXTENSIVE FORM GAMES

38

y ≺ x if y precedes x in the game form, i.e. if every path reaching x goes through y. The relation ≺ totally orders the predecessors of each member of V . Thus ≺ is asymmetric and transitive. The following notation based on the game form (T, ≺) is helpful: name

notation

definition

terminal nodes (outcomes) decision nodes initial nodes predecessors of t immediate predecessor of t

Z X W p (t) p1 (t)

{t ∈ T : s (t) = ∅} {T \Z} {t ∈ T : p (t) = ∅} {x ∈ T : x ≺ t} {x ∈ T : x ≺ t and y ≺ t ⇒ y ≺ x}

n-th predecessor number of predecessors immediate successor terminal successor

pn (t) l (t) s (x) z (x)

p1 (pn−1 (t)) with pn−1 (t) ∈ / W, p0 (t) = t pl(t) (t) ∈ W {y ∈ T : x ≺ y and t ∈ y ⇒ y ≺ t} {z ∈ Z : x ≺ z} for x ∈ X.

In order to define formally the extensive form game, we need the following ingredients. (i) The set of nodes V consists of initial nodes W , decision nodes X, and terminal nodes Y . T = {W, X, Y } . (ii) A mapping p : T \W → T, which is called the predecessor mapping (it is a point to set mapping). The immediate predecessor nodes are p1 (x) and the immediate successor nodes of x are s (x) .where p1 (s (x)) = x. (iii) An assignment function α : T \W → A, where we require that α is a one-to-one function onto the set s (x) of x. The term α (s (x)) represents the sets of all actions which can be taken at x.

CHAPTER 3. EXTENSIVE FORM GAMES

39

(iv) A function ι:X→I assigning each decision node to the player who moves at that node. Definition 33 A partition H of a set X is a collection of subsets of X, with H = {h1 , ..., hk } , s.th. hk ∩ h0k = ∅, and [

hk = X.

k

Definition 34 A partition H of X is called a collection of information sets if ∀x0 , x00 x00 ∈ h (x0 ) ⇒ ι (x0 ) = ι (x00 ) and α (s (x0 )) = α (s (x00 )) .

(3.1)

Information sets as histories. By the consistency requirement imposed in (6.3) we define the set of actions which can be taken at an information set h as A (h), where A (h) , α (s (h)) ⇔ A (h) , α (s (x0 )) = α (s (x00 )) , for all x00 ∈ h (x0 ) . The partition H can be further partitioned into Hi such that Hi = ι−1 (i), where Hi is the set of all decision nodes at which i is called to make a move. A prominent way of identifying an information set is through the history leading to it. Hence h ∈ H is often called a particular history of the game.1 (vi) A collection of payoff functions u = {u1 (·) , ..., uI (·)} , assigning utilities to each terminal node that can be reached ui : Z → R. For notational convenience, we assume that α is onto and that for each a ∈ A, A−1 (a) is a singleton on H, but not on X of course. That is, each action can be taken only in a single information set. 1

CHAPTER 3. EXTENSIVE FORM GAMES

40

Observe that since each terminal node can only be reached through a single path, defining payoffs on terminal nodes is equivalent to defining payoffs on paths of actions. (vii) An initial assessment ρ as a probability measure over the set of initial nodes ρ : W → [0, 1] , assigning probabilities to actions where nature moves. Definition 35 (Extensive Form Game) The collection {T, ≺; A, α; I, ι; H; ui ; ρ} is an extensive form game. Definition 36 (Perfect Information) A game is one of perfect information if each information set contains a single decision node. Otherwise, it is a game of imperfect information. Definition 37 (Almost Perfect Information) A game is of “almost” perfect information if the player’s choose simultaneously in evert period t, knowing all the actions chosen by everybody at dates 0 to t − 1.

3.2.4

Notion of Strategy

A strategy is a complete contingent plan how the player will act in every possible distinguishable circumstance in which she might be called upon to move. Consider first the following game of perfect information: Definition 38 (Pure Strategy) A strategy for player i is a function si : Hi → A,

(3.2)

where A = ∪h A (h) , such that si (h) ∈ A (h) for all h ∈ Hi . Definition 39 (Mixed Strategy) Given player i0 s (finite) pure strategy set Si , a mixed strategy for player i, σi : Si → [0, 1] assigns to each pure strategy si ∈ Si a probability σi (si ) ≥ 0 that it will be played where X σi (si ) = 1. si ∈Si

CHAPTER 3. EXTENSIVE FORM GAMES

41

Definition 40 (Outcome) The outcome induced by a mixed strategy profile σ in an extensive form game is the distribution induced by the initial assessment ρ and the mixed strategies on the terminal nodes. In general the number of pure strategies available to each player is given by |Si | =

Y

|A (hi )|

hi ∈Hi

where |S| represents in general the cardinality of a set S, i.e. the number of members in the set. If the number of actions available at each information set hi is constant and given by |A (hi )|, then |Si | simplifies to |Si | = |A (hi )||Hi | . In extensive form games, it is often customary to use a slightly different notion for a mixed strategy. In the definition above, the number of components needed to specify a mixed strategy is |Si | − 1. This is often a very large number. A simpler way to define a random strategy is the following. Rather than considering a grand randomization at the beginning of the game for each player, we could consider a sequence of independent randomizations, one at each information set for each of the players. This leads to the notion of a behaviour strategy. Definition 41 (Behaviour Strategy) A behaviour strategy of player i is a mapping bi : Hi → ∆ (A) such that for all hi ∈ Hi , b (hi ) ∈ ∆ (A (hi )) . Observe that in order to specify a behaviour strategy for player i, only X |A (hi ) − 1| hi ∈Hi

components must be specified. It is immediately obvious that each behaviour strategy generates a mixed strategy in the sense of the above definition. Much less obvious is that most often it is enough to consider behaviour strategies in the sense that each outcome induced by a mixed strategy profile is also induced by some behaviour strategy profile. This is true as long as the game is one of perfect recall.

CHAPTER 3. EXTENSIVE FORM GAMES

42

Definition 42 (Perfect Recall) An extensive form game {T, ≺; A, α; I, ι; H; ui ; ρ} has perfect recall if i) ∀i, ∀hi ∈ Hi , x, x0 ∈ hi ⇒+ (x ≺ x0 ). ii) If x00 ∈ h (x0 ) and x ∈ p (x0 ) , then ∃b x ∈ h (x) such that x b ∈ p (x00 ) and all the actions on the path from x to x0 coincide with the actions from x b to x00 . The first requirement says intuitively that no player forgets his moves, and the second says that no player forgets past knowledge. Theorem 43 (Kuhn’s Theorem) If the extensive form game {T, ≺; A, α; I, ι; H; ui ; ρ} has perfect recall and an outcome µ ∈ ∆ (Z) is induced by ρ and σ = (σ1 , ..., σN ) , then there is a behaviour strategy profile b = (b1 , ..., bN ) such that µ is induced by ρ and b. In other words, in games of perfect recall, there is no loss of generality in restricting attention to behaviour strategies. The following example is due to Rubinstein and Piccione (see the special issue of Games and Economic Behavior, July 1997, on games of imperfect recall). Example 44 (Absent Minded Driver) This is a single person game with two decision nodes for the player. The player must decide whether to keep on driving D on the highway or whether to exit E. If the driver chooses D twice, he ends in a bad neighborhood and gets payoff of −1. If he exits at the first node, he gets 0. M If he chooses D followed by E, then his payoff is 2. The twist in the story is that the driver is absent minded. He cannot remember if he has already decided or not in the past. This absent mindedness is represented by a game tree where both of the nodes are in the same information set even though the two nodes are connected by an action by the single player. Hence the game is not one of perfect recall as defined above. It is a useful exercise to draw the game tree for this problem and consider the various notions of strategies. The first step in the analysis of any games is to decide what the possible strategies are. As usual, a strategy should be an assignment of a (possibly mixed) action to each information set. With this definition for a strategy, it is easy to show that the optimal strategy in this game cannot be a pure strategy. Observe also that if the driver were able to commit to a mixed strategy, then she would choose to exit with probability p = 32 resulting in a payoff of 29 .

CHAPTER 3. EXTENSIVE FORM GAMES

43

If the driver were to adopt the strategy of exiting with probability 23 , then she would assign probabilities 3/4 and 1/4 respectively to the first and the second node in her information set. In order to calculate correctly the payoffs to the driver, behaviour at other nodes must be kept constant when calculating the current payoff to exiting or driving on. Thus choosing D and then following the proposed strategy yields a payoff of 1 1 3 2 1 (2 − ) − = . 4 3 3 4 2 Choosing E yields similarly a payoff of 12 . The key to understanding the workings of the game lies in the interpretation of a deviation from the proposed equilibrium strategy. Most game theorists believe that in games of this type, a deviation should be modeled as a single deviation away from the proposed strategy. In particular, this would imply that a deviation can take place at a single node in the information set without necessarily happening at the other. Piccione and Rubinstein offer a different interpretation of the game, see the discussions in the issue of GEB as cited above.

3.3

Subgame Perfect Equilibrium

Before we can define the notion of a subgame perfect equilibrium we need to know what a subgame is. The key feature of a subgame is that, contemplated in isolation it forms its own game. Definition 45 (Subform) A subform of an extensive form is a collection of nodes Tˆ ⊆ T , together with {≺; A, α; I, ι; H} all defined on the restriction to Tˆ, satisfying closure under succession and preservation of information sets: if x ∈ Tˆ, then s (x) ⊆ Tˆ, h (x) ⊆ Tˆ, A proper subform is a subform Tˆ consisting solely of some node x and its successors. Definition 46 (Subgame) Given a proper subform, the associated proper subgame starts at x, with the payoffs restricted to Tˆ ∩ Z, and the initial assessment ρˆ (x) = 1.

CHAPTER 3. EXTENSIVE FORM GAMES

44

Definition 47 (Subgame Perfect Nash Equilibrium) A profile of strategies σ = (σ1 , ..., σn ) in an extensive form game ΓE is a SPE if it induces a Nash equilibrium in every subgame of ΓE . Clearly, every SPE is an NE, but the converse doesn’t hold. Consider first the extensive form games with perfect information. Chess is a finite extensive form game as is centipede game introduced above. What is the unique subgame perfect equilibrium in this game? It is a description of the equilibrium strategy for each player: s∗1 = (s, s0 , s00 ) , s∗2 = (s, s0 ) , on and off the equilibrium path. The equilibrium path is the set of connected edges which lead from an initial node to a final node. The equilibrium path is thus {s} and the equilibrium outcome is the payoff realization (1, 1). Thus a description of the equilibrium strategy asks for the behaviour of every player on and off the equilibrium path. Theorem 48 (Zermelo, Kuhn) Every finite game of perfect information ΓE has a pure strategy subgame perfect Nash equilibrium.

3.3.1

Finite Extensive Form Game: Bank-Run

Consider the following bank-run model with R > D > r > D/2. The interpretation is as follows. The bank acts as an intermediary between lender and borrower. Each lender deposit initially D. The bank also attempts to transform maturity structures. The deposits are short-term, but the loan is long-term. Suppose the deposits are applied towards an investment project which has a return of 2r if the project is liquidated after one period and 2R if liquidated after two periods. The return is 2D if the project is continued for more than two terms. If either of the depositor asks for a return of its deposit, then the project is liquidated, and the withdrawing depositor either gets D or his share in liquidation proceeds, whichever is larger. Denote the first stage actions by w for withdrawing and n for not withdrawing. Let the second period actions for the two players be W and N respectively. Thus the stage payoffs are given by the two matrices There are two pure strategy

CHAPTER 3. EXTENSIVE FORM GAMES w r, r 2r − D, D

w n

45

n D, 2r − D second period

Figure 3.1: First period W N

W R, R D, 2R − D

N 2R − D, D D, D

Figure 3.2: Second period subgame perfect equilibria of this game s∗1 = {w, W } , s∗2 {w, W } and s∗1 = {n, W } , s∗2 {n, W } Consider the following two-period example with imperfect information. The first period game is a prisoner’s dilemma game and the second game is coordination game: and then Specify all subgame perfect equilibria in this

α β

α β 2, 2 −1, 3 3, −1 0, 0

Figure 3.3: First period game. Does the class of subgame perfect equilibria coincide with the class of Nash equilibria? For x ≥ 2, cooperation is sustainable in a subgame perfect equilibria by switching from the pure to the mixed strategy equilibrium in the second stage game.

3.4

The Limits of Backward Induction: Additional Material

Consider the following example of game, referred to as “Centipede Game”. There are two players each start with 1 dollar. They alternate saying “stop”

CHAPTER 3. EXTENSIVE FORM GAMES

γ δ

γ x, x 0, 0

46

δ 0, 0 x, x

Figure 3.4: Second period or “continue”, starting with player 1. If they say continue, 1 dollar is taken from them and 2 dollar is given to the other player. As soon as either player says stop the game is terminated and each player receives her current pile of money. Alternatively, the game ends if both players pile reach 100 dollars: (1) −→ ↓ (1, 1)

(2) −→ ↓ (0, 3)

(1) −→ ↓ (2, 2)

(2) −→ ↓ (1, 4)

(1) ....

(2) −→ ↓ (98, 101)

(1) −→ ↓ (100, 100)

The first entry in the payoff vector refers to player 1, the second to player 2. Instead of looking at the ‘true’ centipede game, let us look at a smaller version of the game: (1) c (2) c (1) c0 (2) c0 (1) c00 (2, 4) s s s0 s0 s00 (1, 1) (0, 3) (2, 2) (1, 4) (3, 3) What is a strategy for player 1 in this small centipede game? A strategy is a complete description of actions at every information set (or history). Player 1 has two histories at which he could conceivable make a choice H1 = {∅, cc} and likewise H2 = {c, ccc0 }. Thus a possible strategy for player 1 is

s1

h1 = ∅ h1 = cc ↓ ↓ = { c , c0

h1 = ccc0 c0 ↓ s00 }.

Another possible strategy is however:

s1

h1 = ∅ h1 = cc ↓ ↓ = { s , c0

h1 = ccc0 c0 ↓ s00 }.

The notion of a strategy in the extensive form game is stretched beyond what we would call a plan. We saw in the centipede game that it requires

(100, 100)

CHAPTER 3. EXTENSIVE FORM GAMES

47

a player to specify his action after histories that are impossible if he carries out his plan. A different interpretation of the extensive form game may help our understanding. We may think of each player having as many agents (or multiple selves) as information sets. The strategy of each player is to give instructions to each agents (which he may not be able to perfectly control) as to what he should do if he is called to make a decision. All agents of the same player have the same payoff function. A plan is then a complete set of instructions to every agent who acts on behalf of the player. Notice that we did not discuss notions similar to rationalizability in the context of extensive form games. The reason for this is that making sense of what common knowledge of rationality means in extensive form games is much more problematic than in normal form games. A simple example will illustrate. Robert Aumann has maintained that common knowledge of rationality in games of perfect information implies backwards induction. Hence e.g., the centipede game should have a unique solution where all players stop the game at all nodes. Suppose that this is the case. Then after observing a move where the first player continues the game, the second player ought to conclude that the first player might not be rational. But then it might well be in the second player’s best interest to continue in the game. But if this is the case, then it is not irrational for the first player to continue at the first node. It should also be pointed out that knowledge and belief with probability 1 are more or less the same in normal form games, but in extensive form games these two notions yield very different conclusions. Appropriate models of knowledge for extensive form games form a very difficult part of interactive logic (or epistemic logic) and Chapter 14 in FT is a slightly outdated introduction into this area.

3.5

Reading

The notion of extensive form game is first (extensively) developed in Kuhn (1953) and nicely developed in Kreps (1990) and Kreps and Wilson (1982). The relation between mixed and behaviour strategies is further discussed in FT, Ch.3.4.3.

Chapter 4 Repeated Games 4.1

Finitely Repeated Games

We first briefly consider games which are repeated finitely many times. Then we move on the theory of infinitely repeated games. We first introduce some notation. Consider the prisoner’s dilemma game: and repeat the stage game

C D

C D 4, 4 0, 5 5, 0 1, 1

Figure 4.1: Prisoner’s Dilemma
T times. A pure strategy si = s1i , ..., sTi for a player i in the repeated game is then a mapping from the history of the game H t into the strategies in the stage game Si : sti : H t−1 → Si . A complete specification of a repeated game strategy has to suggest a strategy choice after every possible history of the game, (and not only the histories which will emerge in equilibrium). A complete specification can be thought of as a complete set of instructions written before playing the game, so that no matter what happens in the game, once it started a prescription of play is found the set of instructions. The history of the game is formed by the past observed strategy choices of the players:
t−1 . H t−1 = s11 , ..., s1I ; ...; st−1 1 , ..., sI 48

CHAPTER 4. REPEATED GAMES

49

 Definition 49 Given a stage game Γ = I, (Si )i∈I , (ui )i∈I , we denote by Γ (T ) the finitely repeated game in which Γ is played T times. The outcomes of all preceding plays are observed before the next play begins. The payoffs for Γ (T ) are simply the sums of the payoffs from the T stage games. Definition 50 In a repeated game Γ (T ) a player’s strategy specifies the action the player will take in each stage, for each possible history of play through the previous stage:  si = s0i , ...., sTi where: sti : H t−1 → Si . Theorem 51 If the stage game Γ has a unique Nash equilibrium then, for any finite T , the repeated game Γ (T ) has a unique subgame-perfect outcome: the Nash equilibrium of Γ is played in every stage. Corollary 52 Every combination of stage game Nash equilibria forms a subgame perfect equilibrium. Consider now the following game with multiple equilibria in the stage game Can coordination among the players arise in a stage game?

C D E

C D E 4, 4 0, 5 −3, −3 5, 0 1, 1 −3, −3 −3, −3 −3, −3 -2,-2

Figure 4.2: Modified Prisoner’s Dilemma

Example 53 To understand the complexity of repeated games, even if they are repeated only very few times, let us consider the prisoner’s dilemma played three times. What are all possible histories of a game? How many strategy choice have to be made in order for the repeated game strategy to be a complete specification?

CHAPTER 4. REPEATED GAMES

50

The history H −1 is naturally the empty set: H −1 = {∅} . The history H 0 is the set of all possible outcomes after the game has been played once. Each outcome is uniquely defined by the (pure) strategy choices leading to this outcome, thus H 0 = {CC, CD, DC, DD} . The cardinality of possible outcomes in period 0 is of course 0 H = |S1 | × |S2 | = 4. We then observe that the number of possible histories grows rather rapidly. In period 1, it is already 1 H = |S1 | × |S2 | × |S1 | × |S2 | = 16, and in general it is t H = (|S1 | × |S2 |)t+1 . However the complexity of strategies grows even faster. A complete strategy for period t specifies a particular action for every possible history leading to period t. Thus the number of contingent choices to be made by each player in period t is given by t t+1 Si = |Si ||H t−1 | = |Si ||S1 |×|S2 | . Notice that a strategy even in this two period game is not merely an instruction to act in a specific manner in the first and second period, but needs to specify the action after each contingency. In order to sustain cooperation, two conditions need to be satisfies: (i) there are rewards from cooperation, and (ii) there are credible strategies to punish deviators. This theme of “carrots and sticks” is pervasive in the entire theory of repeated games. As the punishment occurs in the future, agents must value the future enough so that lower payoffs in the future would indeed harm the agent’s welfare sufficiently. If the discount factor represents the agent’s attitude towards the future, then higher discount factors make cooperation easier to achieve as lower payoffs in the future figure more prominently in the agent’s calculation.

CHAPTER 4. REPEATED GAMES

4.2

51

Infinitely Repeated Games

Next we consider games which are repeated infinitely often. Definition 54 Given a stage game Γ, let Γ (δ) denote the infinitely repeated game in which Γ is repeated forever and where each of the players discounts future at discount factor δ < 1. The payoff in an infinitely repeated game with stage payoffs πt and discount factor δ < 1 is given by ∞ X

δ t πt .

t=0

Definition 55 Given the discount factor δ, the average payoff of the infinitely repeated sequence of payoffs π0 , π1 , π2 , ... is given by (1 − δ)

∞ X

δ t πt .

t=0

Notice that in infinitely repeated games every subgame is identical to the game itself.

4.2.1

The prisoner’s dilemma

Let us consider again the stage game in figure 4.1 which represented the prisoner’s dilemma and consider the following strategy suggested to the players. I cooperate in the first period unconditionally and then I continue to cooperate if my opponent cooperated in the last period. In case he defected in the last period, I will also defect today in all future periods of the play. When can we sustain cooperation? This strategy is often called the grim-trigger strategy, which can be formally described by  C if Ht−1 = {CC, ...., CC} or H−1 = ∅ i st = D if otherwise We now want to show that this set of strategies form a subgame perfect equilibrium. To prevent a deviation the following has to hold: 5+

4 β ≤ , 1−β 1−β

CHAPTER 4. REPEATED GAMES

52

or 5 (1 − β) + β ≤ 4, so that

1 β≥ . 4 Thus if the players are sufficiently patient, cooperation can be sustained in this repeated game. The equilibrium we suggested implies cooperation forever along the equilibrium path. However, this is clearly not the only equilibrium. There are many more, and many of them of very different characteristics. In the limit as δ → 1, one can show, and this is the content of the celebrated “folk” theorem of the repeated games, that the entire convex hull of all individually rational payoffs of the stage game can be achieved as a subgame perfect equilibrium. Notice, that this may involve very asymmetric payoffs for the players.

4.3

Collusion among duopolists

The special feature of the prisoner’s dilemma game is that the minimum payoff a player can guarantee himself in any stage, independent of the actions chosen by all other players, is equal to the payoff in the stage game Nash equilibrium. This minimum payoff is called the reservation payoff. It constitutes the limit to the damage an opponent can inflict on the player. The individual rational payoff vi is the lowest payoff that the other players can force upon player i: vi = min max ui (si , s−i ) . s−i ∈S−i si ∈Si

4.3.1

Static Game

Consider the following Cournot oligopoly model with prices determined by quantities as p (q1 , q2 ) = a − q1 − q2 . The Cournot stage game equilibrium is found by solving the first order conditions of the profit functions, where we normalize the marginal cost of production to zero, πi (q1 , q2 ) = qi (a − q1 − q2 ) .

CHAPTER 4. REPEATED GAMES

53

We saw earlier that the Cournot outcome is a qiC = , 3 and the associated profits are:
a2 πi q1C , q2C = . 9 In contrast, the strategy of the monopolist would be to maximize π (q) = q (a − q) , which would result in the first order conditions a − 2q = 0 and hence qM =

a 2

and the profits are
a2 π qM = πM = . 4

4.3.2

Best Response

Suppose the two firms agree to each supply q to the market, then the profits are given by: πi (q, q) = q (a − 2q) = aq − 2q 2 . By the best response function, the optimal response to any particular q is q ∗ (q) =

a−q 2

(4.1)

and the resulting profits are π1 (q ∗ (q) , q) = where:

(a − q)2 . 4


1 (a − q)2 − aq − 2q 2 = (3q − a)2 ≥ 0 4 4 a and with equality at q = 3 , which is the Cournot output.

(4.2)

CHAPTER 4. REPEATED GAMES

4.3.3

54

Collusion with trigger strategies

The discrepancy between monopoly and duopoly profit suggests that the duopolists may collude in the market to achieve higher prices. How could they do it? Consider the following strategy. n M M   M M o ( M q q q q q if h = , , ...., , or h = ∅ t t 2 2 2 2 2 qti = C q otherwise and consider whether the symmetric strategy can form a subgame perfect equilibrium. We have to consider the alternatives available to the players. Consider a history in which  M M   M M  q q q q ht = , , ...., , , 2 2 2 2 then the resulting payoff would be δ 1 1 M π ≥ πd + πC . 1−δ2 1−δ

(4.3)

Thus to evaluate whether the player follows the equilibrium strategy, we have to evaluate π d . SPE This suggests the following trigger strategy equilibrium: 1 1 M δ π ≥ πd + πC , 1−δ2 1−δ

(4.4)

9 which can be sustained for δ ≥ 17 . The question then arises whether we can do better; or more precisely whether there are punishment strategies which would act even more harshly on deviators. We still have to verify that following a deviation i.e., all histories different from collusive histories,

δ 1 πC ≥ πd + πC ; 1−δ 1−δ but since qi = q C , (4.4) is trivially satisfied.

(4.5)

CHAPTER 4. REPEATED GAMES

4.3.4

55

Collusion with two phase strategies

We next consider a repeated game where the equilibrium strategy consists of two different phases: a maximal reward and a maximal punishment phase, a “carrot and stick” strategy. The strategy may formally be described as follows:  M M o n M M   M q q q q  , ...., if h = , , q2 t  2 2 2 2

i M j q i qt = , q = q, q if q t−1 t−1 2   q if otherwise Let x denote the level of output in the punishment phase (to be determined as part of the equilibrium). We may then write the equilibrium conditions as: Continuation z }| { Punishment z }| {
δ2 1 M 1 1 M π ≥ π d + δ ax − 2x2 + π (4.6) 1−δ2 1−δ2 and

}|
{ ax − 2x2 +

Deviation

Continuation z }| { z }| { Punishment }| { 2 }| { z
δ 1 M (a − x) δ2 1 M π ≥ +δ ax − 2x2 + π 1−δ2 4 1−δ2 Continuation

Punishment

z

z

(4.7)

Equation (4.6) may be rewritten as,
(1 − δ) (1 + δ) 1 M π ≥ π d + δ ax − 2x2 1−δ 2 and finally as:  δ


1 M π − ax − 2x2 2



1 ≥ πd − πM . 2

(4.8)

The inequality (4.8) suggests that the relative gains from deviating in contrast to collusion today must be smaller than the relative losses tomorrow induced by a deviation today and again in contrast to continued collusion. Similarly for the punishment to be credible, starting from (4.7), we get

(a − x)2 1 + δ ax − 2x2 . ax − 2x2 + δ π M ≥ 2 4

(4.9)

and which permits an intuitive interpretation in terms of today’s and tomorrow’s payoff, or alternatively as the one shot deviation strategy. By inserting

CHAPTER 4. REPEATED GAMES

56

the value of π M we obtain two equalities:  2    1a 9 2 1 a2 2 δ 2 4 − (ax − 2x ) = 64 a − 2 4   2 2 − (ax − 2x2 ) δ 21 a4 − (ax − 2x2 ) = (a−x) 4 which we can solve and obtain the following results as the harshest level of 5 9 punishment x = 12 a and the lowest level of discount factor δ = 32 for which cooperation is achievable. Reading: Gibbons (1992), Ch. 2.3 is a nice introduction in the theory of repeated games. A far more advanced reading is FT, Ch.5. The characterization of extremal equilibria is first given in Abreu (1986).

Chapter 5 Sequential Bargaining The leading example in all of bargaining theory is the following trading problem in the presence of bilateral monopoly power. A single seller and a single buyer meet to agree on the terms of trade for a single unit of output. The seller incurs a cost of c to produce the good while the buyer has a value of v for the good. If the two parties have payoff functions that are quasilinear in money and the good, then there are positive gains from trade if and only if v > c. The two parties have also an opportunity to refuse any trade which yields them an outside option value of 0. Both parties prefer (weakly) trading at price p to not trading at all if p satisfies v ≥ p ≥ c. Which (if any) of such prices will be agreed upon when the two parties negotiate? The conventional wisdom up to late 1970s was that the determination of the price depends largely on psychological and sociological factors determining the bargaining power of the two parties and as a result economics had little to say on the issue. When the concept of subgame perfect equilibrium was established as the standard solution concept in games of perfect information, the bargaining issue was taken up again. Preliminary work was done on bargaining in simple two period models, but the real breakthrough was the infinite horizon bargaining model with alternating offers proposed by Ariel Rubinstein in 1982. There he showed that the infinite horizon game has a unique subgame perfect equilibrium and that the division of surplus between the bargainers can be explained in terms of the time discount rates of the bargainers. It should be pointed out that other approaches to bargaining were also adopted. An entirely different methodology starts by describing a set of possible outcomes X that can be obtained in the bargaining process between 57

CHAPTER 5. SEQUENTIAL BARGAINING

58

the two players and an alternative d that represent the outcome in the case of no agreement. Each of the bargainers has preference relation i defined on X ∪ {d}. Let the set of possible preference relations of i be denoted by Ri . A solution to the bargaining problem is a function that associates an outcome to each profile of preferences. In other words, the solution is a function f such that f : R1 × R2 → X ∪ d. The method of analysis in this approach is often taken to be axiomatic. The analyst decides in the abstract a set of criteria that a good solution concept should satisfy. An example of a criterion could be Pareto efficiency of the solutions, i.e. if x i x0 and x j x0 , then x0 ∈ / f (i , j ) . Once the criteria have been established, the analyst determines the set of functions f that satisfy these criteria. Preferably this set is small (ideally a singleton) so that some clear properties of the solutions can be established. This approach precedes the noncooperative approach to be followed in this handout. The first contribution to this cooperative or axiomatic approach to bargaining was made by John Nash in “The Bargaining Problem” in Econometrica 1950. Various other solutions were proposed for two player and many player bargaining models. A good survey of these developments can be found in chapters 8-10 in Roger Myerson’s book “Game Theory: Analysis of Conflict”. Rubinstein’s solution of the noncooperative bargaining game picks the same solution as Nash’s original cooperative solution for that game. A recurring theme in the noncooperative bargaining literature has been the identification of fully strategic models that yield the classical cooperative bargaining solutions as their equilibrium outcomes.

5.1

Bargaining with Complete Information

In this section, we focus our attention on the case where two players bargain over the division of 1 unit of surplus. We start by considering the following simple extensive form to the bargaining procedure. There are just two stages in the game. Player 1 proposes a sharing rule for the surplus we assume that all real numbers between 0 and 1 represent feasible shares. Denote the shares going to 1 and 2 by x and 1 − x respectively. Player 2 then sees the proposal and decides whether to accept it or not. If the proposal is accepted, the outcome in the game is a vector (x, 1 − x) for the two players, if the offer is rejected, the outcome is (0, 0) . It is easy to see that the only subgame

CHAPTER 5. SEQUENTIAL BARGAINING

59

perfect equilibrium in this simple game results in a proposal x = 1 which is accepted in equilibrium by player 2. In this case, we say that player 1 has all the bargaining power because she is in the position of making a take-itor-leave-it offer to player 2 and as a result, player 1 gets the entire surplus in the game. Consider next the version of the game that extends over 2 periods. The first period is identical to the one described in the paragraph above except that if player 2 refuses the first period offer, the game moves into the second period. The second period is identical to the first, but now player 2 makes the offer and 1 decides whether to accept or not. At the end of the second stage, the payoffs are realized (obviously if player 2 accepts the first offer, then the payoffs are realized in period 1). If the players are completely patient, i.e. their discount factor is 1, then it is clear that the subgame perfect equilibria in the game have all the same outcomes. Since player 2 can refuse the first period offer which put her in the position of player 1 in the paragraph above, it must be that the equilibrium shares in the game are (0, 1) . Hence we could say that player 2 has all the bargaining power since she is the one in a position to make the last take it or leave it offer. The situation changes somewhat if the players are less than perfectly patient. Assume now that player i has a discount factor δi between the periods in the game. If player 2 refuses the first offer and gets all of the surplus in the second period, her payoff from this strategy is δ2 . Hence she will accept any first period offer x > δ2 and refuse any offer x < δ2 . At x = δ2 , she is indifferent between accepting and rejecting the offer, but it is again easily established that in the unique subgame perfect equilibrium of the game, she will accept the offer x = δ2 and the outcome of the game is (1 − δ2 , δ2 ) . Notice that the introduction of time discounting lessens the advantage from being in the position to make the take it or leave it offer since the value of that eventual surplus is diminished. If there were 3 periods in the game, the unique equilibrium in the subgame that starts following a rejection of the first offer would be the solution of the 2 period game (by uniqueness of the subgame perfect equilibrium in the 2 period game with discounting). Hence player 2 could secure a payoff of 1 − δ1 from the second period onwards. As a result, player 1 must offer to keep exactly 1 − δ2 (1 − δ1 ) to himself in the first period and the outcome is thus (1 − δ2 (1 − δ1 ) , δ2 (1 − δ1 )) . At this point, we are ready to guess the form of the equilibrium in a game with T periods. Proposition 56 Let xT denote the unique subgame perfect equilibrium share

CHAPTER 5. SEQUENTIAL BARGAINING

60

of player 1 in the bargaining game of length T. Then we have
xT +2 = 1 − δ2 1 − δ1 xT . Furthermore, the offer of xT is accepted immediately. Proof. Consider the game with T + 2 periods. In period T + 1, player
2 must offer a share of δ1 xT to player 1. This results in surplus 1 − δ1 xT
to player 2. Hence player 1 must offer a share δ2 1 − δ1 xT to player 2 in period T +2 proving the first claim. To see that in equilibrium, the first period offer must be accepted, assume to the contrary and denote the equilibrium continuation payoff vector by (v1 , v2 ) after the refusal by player 2. Because of time discounting and feasibility v1 + v2 < 1. But then it is possible for 1 to offer x0 such that x0 > v1 and (1 − x0 ) > v2 contradicting the optimality of the original offer. The proposition gives the equilibrium shares as a solution to a difference equation. The most interesting question about the shares is what happens as the horizon becomes arbitrarily long, i.e. as T → ∞. Let x∗ = limT →∞ xT . Then it is easy to see that x∗ =

1 − δ2 . 1 − δ1 δ2

Observe that in the case of identical discount factors, this share is monotonically decreasing in δ and that (by using L’Hopitals rule) limδ→1 x∗ (δ) = 12 . Hence the unique outcome in finite but long bargaining games with equally patient players is the equal division of surplus. Notice that finite games of this type always put special emphasis on the effects of last stages. By the process of backwards induction, these effects have implications on the earlier stages in the game as well. If the bargaining can effectively take as much time as necessary, it is questionable if it is appropriate to use a model which features endgame effects. The simplest way around these effects is to assume that the bargaining process may take infinitely many periods. A simple argument based on the continuity of the payoff functions establishes that making the offers from the finite game in all periods of the infinite game continues to be an equilibrium in the infinite game. The more difficult claim to establish is the one showing that there are no other subgame perfect equilibria in the game. In order to establish this, we start by defining the strategies a bit more carefully.

CHAPTER 5. SEQUENTIAL BARGAINING

61

The analysis here is taken from Fudenberg and Tirole, Chapter 4. The infinite horizon alternating offer bargaining game is a game with perfect information, i.e. at all stages, a single player moves and all of the previous moves are observed by all players. In odd periods, player 1 makes the offer and player 2 either accepts (thereby ending the game) or rejects and the game moves to the next period. In even periods, the roles are reverse. Denote by ht the vector of all past offers and acceptance decisions. A strategy for player i is then a sequence of functions: st1 : ht → [0, 1] for t odd, st1 : ht × [0, 1] → {A, R} for t even. The strategies of player 2 are similarly defined. We say that an action ati is conditionally dominated at history ht if in the beginning of the subgame indexed by ht , every strategy that assigns positive probability to ati is strictly dominated. Iterated deletion of conditionally dominated strategies removes in each round all conditionally dominated strategies in all subgames given that the opponent’s strategies have survived previous deletions. Observe that this process never deletes subgame perfect equilibrium strategies. We will show that the alternating offer bargaining game has a unique strategy profile that survives iterated deletion of conditionally dominated strategies. In what follows, we take each offer to be an offer for player 1’s share in the game. Observe first that it is conditionally dominated for one to refuse any offer from 2 that gives 1 a share exceeding δ1 and similarly 2 must accept any share for 1 that is below 1 − δ2 . At the second round, 2 will never offer more than δ1 and 2 will reject all offers above 1 − δ2 (1 − δ1 ) . Also 1 never offers below 1 − δ2 and never accepts offers below δ1 (1 − δ2 ) . Suppose then that after k iterations of the deletion process, 1 accepts all offers above xk and 2 accepts all offers below y k where y k < xk . Then after one more round of deletions, 2 never offers more than xk and rejects all offers
k above 1 − δ2 1 − x . Player 1 never offers below y k and rejects all offers below δ1 y k . At the next round, player 1 must accept all offers above xk+1 ≡ δ1 (1 − δ2 )+ δ1 δ2 xk . To see this, consider the implications of refusing an offer by player 2. This has three possible implications. First, it may be that agreement is never reached. The second possibility is that 2 accepts some

future offer from 1. k This has a current value of at most δ1 1 − δ2 1 − x . The third possibility

CHAPTER 5. SEQUENTIAL BARGAINING

62

is that player 1 accepts one of player 2’s future offers. The payoff from this is at most δ12 xk . The payoff from the second possibility is the largest of the three. Hence 1 must accept all offers above xk+1 . A similar argument shows that player 2 must accept all offers below k+1 y ≡ 1 − δ2 + δ1 δ2 y k . The sequences xk and y k are monotonic sequences with limits x∞ =

1 − δ2 δ1 (1 − δ2 ) ∞ , y = . 1 − δ1 δ2 1 − δ1 δ2

1−δ2 and Hence player 2 rejects any offer where 1’s share is above y ∞ = 1−δ 1 δ2 accepts all shares below y ∞ . Hencethe unique outcome is again for 1 to 1−δ2 1−δ2 , 1 − 1−δ and for 2 to accept immediately. propose the share 1−δ 1 δ2 1 δ2

5.1.1

Extending the Basic Model

It is a relatively easy exercise to show that if the surplus is divisible only in finitely many pieces, then any sharing of the surplus can be realized in a subgame perfect equilibrium as δ → 1. Again, the interpretation of this result relies on the view one takes on modeling. If it is thought that the fact that monetary sums can be divided only into pounds and pennies is important in the mind of the bargainers, then this result is probably troublesome. If on the other hand it is thought that this is not that important for the bargainers, then it is probably best to use a model where the indivisibility is not present. A more troublesome observation is that the result is somewhat sensitive to the extensive form of the bargaining game. If the protocol of offers and rejections is modified, then other outcomes can be supported in equilibrium as well. Finally, the extensions to 3 or more player bargaining have been unsuccessful. The uniqueness seems to be beyond the reach of the theory. Probably the most successful models in this class have been the ones where a random proposer suggests a sharing of the surplus in each period and the acceptance is decided by majority vote. Models along these lines have been developed by Baron and Ferejohn in the literature on political economy.

5.2

Dynamic Programming

How can the notion of backwards induction be extended to an infinite time horizon? Consider first a schematic decision problem in a decision tree and

CHAPTER 5. SEQUENTIAL BARGAINING

63

observe what the process of backward reduction does to reduce the complexity of the decision problem. It represents and reduces subtrees through values, where the values represent the maximal value one can attain in any subtree. When does this reduction lead to the optimal decision through the entire tree? If and only if we replace each subtree with the optimal value. Theorem 57 Every finite decision tree (with finitely many periods and finitely may choices) has an optimal solution which can be obtained by backwards induction. We can extend this theorem certainly to an interactive decision problem, provided that it maintains the structure of single person decision tree, namely perfect information. Theorem 58 (Zermelo, Kuhn) Every finite game of perfect information ΓE has a pure strategy subgame perfect Nash equilibrium. The theorem applies to many parlour games, in particular to chess. Thus in principle we can apply backward induction to solve for a subgame perfect Nash equilibrium in chess. How does a computer program approach the problem of evaluating a move? By approximating the value of a move through a forward looking procedure which assesses the value of the position in three or four moves from then on. We may apply the same idea of approximation to every problem with an infinite horizon. In fact, we can obtain in many situations an exact approximation. We now return to the bargaining problem as defined above. Two players, 1 and 2 bargain over a prize of value 1.. The first player starts by making an offer to the second player who can either accept or reject the offer. If he rejects the offer, then in the next period he has the right to make an offer which can again be accepted or rejected. The process of making offers then starts again. The agents are impatient and have common discount factor of δ = 1/ (1 + r) < 1. Consider first the game with an infinite horizon. The surprising result and the even more surprising simplicity of the argument is given first. We can adopt the definition of stationarity also for equilibrium strategies.

CHAPTER 5. SEQUENTIAL BARGAINING

64

Definition 59 (Stationary strategies) A set of strategies:  t I,∞ si i=1,t=0 is stationary if sti = si , ∀i, ∀t. Theorem 60 The unique subgame perfect equilibrium to the alternate move bargaining game is given by for the offering party i to suggest v=

δ 1+δ

in every period and for the receiving party i to always accept if v ≥ δ/ (1 + δ) and reject if v < δ/1 − δ. Notice that you have to specify the strategy for every period in the infinite time horizon model. The proof proceeds in two parts. First we show that a stationary equilibrium exists, and then we show that it is the unique subgame perfect equilibrium, stationary or not. To do the later part of the argument, first upper and lower bounds are obtained for each player’s equilibrium payoff. Then it is shown that the upper and lower bounds are equal, which shows that an equilibrium exists and that it is unique. Proof. We start with the stationary equilibrium and use directly the payoffs and then later on derive the strategies which support these payoff. Suppose then that there is a stationary equilibrium. Then the following has to be true for the person who accepts today: v = δ (1 − v) , which leaves us with

δ . 1+δ Next we show that this is indeed the unique subgame perfect equilibrium. Let us start in the first period. Let v¯ be the largest payoff that player 1 gets in any SPE. By the symmetry, or stationarity of the bargaining game, this is also the largest sum seller 2 can expect in the subgame which begins after she refused the offer of player 1. By backwards induction the payoff of player 1 cannot be less than v=

v = 1 − δ¯ v,

CHAPTER 5. SEQUENTIAL BARGAINING

65

or 1 = v + δ¯ v.

(5.1)

Next we claim that v¯ cannot be larger than 1 − δv if the offer is accepted in the first period. But what about making an offer that is rejected in the first period? As the second player gets at least v in the next period, this cannot give the player more than δ (1 − v) as he has to wait until the next period. Hence v¯ ≤ 1 − δv. Note that this implies that v¯ ≤ 1 − δv = v + δ¯ v − δv,

(5.2)

where the last equality has been obtained through (5.1). But rewriting (5.2) we obtain v¯ (1 − δ) ≤ v (1 − δ) , which be the definition of the upper and lower bounds imply that v¯ = v. Let us denote this payoff by v ∗ . Since v ∗ = 1 − δv ∗ , we find that player 1 must earn 1 v∗ = , 1+δ and player 2 must earn δ . δv ∗ = 1+δ The derivation of the equilibrium strategies follows directly from here.

5.2.1

Additional Material: Capital Accumulation

Consider the following investment problem. The return of a capital kt in period t is αkt . The capital stock depreciates in every period by λ, so that kt+1 = (1 − λ) kt + it and can be replenished by an investment level it . The cost of investment is given by 1 c (it ) = i2t . 2

CHAPTER 5. SEQUENTIAL BARGAINING

66

The value of the investment problem can therefore be written as (∞  ) X 1 V (k0 ) , max δ t αkt − i2t {it }∞ 2 t=0 t=0 and likewise for all future periods (∞  ) X 1 V (kτ ) , max δ (t−τ ) αkt − i2t {it }∞ 2 t=τ t=0 Thus if we knew the values in the future say V (k1 ), we could certainly find the optimal policy for period 0, as we could formulate the following problem   1 2 (5.3) V (k0 ) , max αk0 − i0 + δV ((1 − λ) k0 + i0 ) i0 2 Supposing that V is differentiable, we would get as a first order condition δV 0 ((1 − λ) k0 + i0 ) − i0 = 0. Consider now a stationary solution. Definition 61 (Stationary) A policy (or strategy) is stationary if for all t = 0, 1, ..., ∞: kt = k In other words, the strategy is time invariant and clearly we have that it = i = λk for all t. Suppose there exists a k ∗ such that   ∞ X 1 t ∗ 2 ∗ ∗ δ αk − (λk ) V (k ) = 2 t=0 or

αk ∗ − 21 (λk ∗ )2 V (k ) = 1−δ However, it still remains to verify what the optimal solution is. But we can do this now by analyzing the first order condition of the Bellman equation α − λk ∗ δ − λk ∗ = 0 1−δ Thus we get αδ k∗ = . λ ∗

Chapter 6 Games of Incomplete Information 6.1

Introduction

This is a very modest introduction into the theory of games with incomplete information or Bayesian games. We start by defining incomplete information, then suggest how to model incomplete information (as a move by nature) to transform it into a game of imperfect information. We then introduce the associated equilibrium concept of Bayesian Nash equilibrium.

6.1.1

Example

Harsanyi’s insight is illustrated by the following example. Suppose payoffs of a two player two action game are either:

α β

α β 1,1 0,0 0,1 1,0

α β

α β 1,0 0,1 0,0 1,1

or

i.e. either player II has dominant strategy to play H or a dominant strategy to play T . Suppose that II knows his own payoffs but player I thinks there 67

CHAPTER 6. GAMES OF INCOMPLETE INFORMATION

68

is probability p that payoffs are given by the first matrix, probability 1 − p that they are given by the second matrix. Say that player II is of type 1 if payoffs are given by the first matrix, type 2 if payoffs are given by the second matrix. Clearly equilibrium must have: II plays H if type 1, T if type 2; I plays H if p > 12 , T if p < 21 . But how to analyze this problem in general? All payoff uncertainty can be captured by a single move of “nature” at the beginning of the game.

6.2

Basics

A (finite) static incomplete information game consists of • Players 1, ..., I • Actions sets A1 , ..., AI • Sets of types T1 , ..., TI • A probability distribution over types p ∈ ∆ (T ), where T = T1 × ... × TI • Payoff functions g1 , ..., gI , each gi : A × T → R Interpretation. Nature chooses a profile of players types, t ≡ (t1 , ..., tI ) ∈ T according to probability distribution p (.). Each player i observes his own type ti and chooses an action ai . We also refer to ti as the private information of agent i. Now player i receives payoffs gi (a, t). By introducing fictional moves by nature, first suggested by Harsanyi (1967) we transform a game of incomplete information into a game of imperfect information. In the transformed game one player’s incomplete information about the other player’s type becomes imperfect information about nature’s moves.

6.2.1

Strategy

A pure strategy is a mapping si : Ti → Ai . Write Si for the set of such strategies, and let S = S1 × .. × SI . A mixed strategy can also depend on his private information: σi : Ti → ∆(Si ).

CHAPTER 6. GAMES OF INCOMPLETE INFORMATION

6.2.2

69

Belief

A player’s “type” ti is any private information relevant to the player’s decision making. The private information may refer to his payoff function, his belief about other agent’s payoff function, the likelihood of some relevant event, etc. We assume that for the players types {ti }Ii=1 there is some objective distribution function p (t1 , ..., tI ) where ti ∈ Ti , which is called the prior distribution or prior belief. The conditional probability
0
p t , t i −i p t0−i |ti = P t−i ∈T−i p (t−i , ti ) by Bayes rule denotes the conditional probability over the other player’s types give one’s own type ti . This expression assumes that Ti are finite. Similar expressions hold for infinite Ti . If the player’s types are independent then p (t−i |ti ) = pi (t−i ) , ∀ti ∈ Ti .

6.2.3

Payoffs

The description of the Bayesian game is completed by the payoff function gi (a1 , ..., aI ; t1 , ..., tI ) . If player i knew the strategy of the other players as a function of his type then he could calculate the expected payoff from his decision given the conditional probability p (t−i |ti ).

6.3

Bayesian Game

Definition 62 A Bayesian game in normal form is given by n o ΓN = I, (Ai )Ii=1 , (Ti )Ii=1 , p (·) , (gi (·; ·))Ii=1 . The timing of a static Bayesian game is then as follows: 1. (a) nature draws a type vector t = (t1 , ..., tn ) , ti ∈ Ti ,

CHAPTER 6. GAMES OF INCOMPLETE INFORMATION

70

(b) nature reveals ti to player i but not to any other player, (c) players choose simultaneously actions si ∈ Si , (d) payoffs gi (a1 , ..., aI ; t1 , ..., tI ) are received. Again, by imperfect information we mean that at some move in the game the player with the move does not know the complete history of the game thus far. Notice that with this specification, the only proper subgame of a game of incomplete information is the whole game. Any Nash equilibrium is then subgame perfect and the subgame perfection has no discriminating power.

6.3.1

Bayesian Nash Equilibrium

Player i’s payoff function of the incomplete information game, ui : S → R, is X ui (s) , p (t) gi (s (t) , t) t∈T

where s = (s1 , ..., sI ) and s (t) = (s1 (t1 ) , ..., sI (tI )). Recall: (Old) Definition: Strategy profile s∗ is a pure strategy Nash equilibrium if

ui s∗i , s∗−i ≥ ui si , s∗−i for all si ∈ Si and i = 1, .., I This can be re-written in the context of incomplete information as: P

p (t) gi



P s∗i (ti ) , s∗−i (t−i ) , t ≥ p (t) gi

t∈T



si (ti ) , s∗−i (t−i ) , t

t∈T

for all si ∈ Si and i = 1, .., I Writing p (ti ) =

P t0−i

as: P t−i ∈T−i

p (t−i |ti ) gi

p

ti , t0−i




and p (t−i |ti ) ≡



s∗i (ti ) , s∗−i (t−i ) , t ≥

p(ti ,t−i ) , p(ti )

P

(6.1) this can be re-written

p (t−i |ti ) gi

t−i ∈T−i



ai , s∗−i (t−i ) , t

for all ti ∈ Ti , ai ∈ Ai and i = 1, ..., I (6.2)

CHAPTER 6. GAMES OF INCOMPLETE INFORMATION

71

Definition 63 A pure strategy Bayesian Nash equilibrium of Γ = {A1 , ..., AI ; T1 , ..., TI ; u1 , ..., uI ; p} is a strategy profile s∗ = (s∗1 , ..., s∗I ) such that, for all i, for all ti ∈ T , condition (6.8) is satisfied. Notice the differences in the definition between the Bayesian Nash equilibrium and the Nash equilibrium. In the former the payoff function may depend on the type. Moreover the payoff is calculated as an expected payoff given his own information, with the conditional distribution over all other agent’s type.

6.4

A Game of Incomplete Information: First Price Auction

Suppose there are two bidders for an object sold by an auctioneer and the valuation of the object is private information. Each buyer i = 1, 2 has a valuation vi ∼ U ([0, 1]) and submits a bid bi for the object. The valuations are assumed to be statistically independent. If bidder i submits the higher of the bids, buyer i receives vi − bi and the seller receives bi .  v i − bi , if bi ≥ b−i ,   1 (vi − bi ) , if bi = b−i , ui (vi ) = 2   0, if bi < b−i . A Bayesian Nash equilibrium is then a strategy pair {b1 (v1 ) , b2 (v2 )}. The optimal strategy is found for each player by solving the following problem max (vi − bi ) Pr (bi > bj (vj )) + bi

1 (vi − bi ) Pr (bi = bj (vj )) . 2

We simplify the analysis by looking at linear equilibria: b i = ai + c i v i . Hence we can write the objective function in (6.3) as max (vi − bi ) Pr (bi ≥ aj + cj vj ) bi

(6.3)

CHAPTER 6. GAMES OF INCOMPLETE INFORMATION Notice that



b i − aj Pr (bi ≥ aj + cj vj ) = Pr vj ≤ cj

72

 ,

(6.4)

and by the uniformity this results in max (vi − bi ) bi

b i − aj . cj

The first-order conditions for this problem result in bi (vi ) = (vi + aj ) /2.

(6.5)

Similarly and by symmetry we have bj (vj ) = (vj + ai ) /2.

(6.6)

But in equilibrium we must have (vi + aj ) /2 = ai + ci vi ,

∀vi ,

and (vj + ai ) /2 = aj + cj vj , ∀vj , and hence

1 ci = cj = , 2

and consequently ai = aj = 0. Hence the equilibrium strategy is to systematically underbid 1 bi (vi ) = vi . 2

6.5

Conditional Probability and Conditional Expectation

Before we analyze the next game, the double auction, recall some basic concepts in probability theory, namely conditional probability and conditional expectation.

CHAPTER 6. GAMES OF INCOMPLETE INFORMATION

6.5.1

73

Discrete probabilities - finite events

We start with a finite number of events, and then consider a continuum of events Consider the following example. Suppose a buyer is faced with a lottery of prices 0 < p1 < ... < pi < ... < pn < ∞ where each price pi has an unconditional probability 0 < αi < 1, and Pn i=1 αi = 1, by which the price pi is chosen. Suppose the buyer is willing to accept all prices, then the expected price to be paid by the buyer is n X E [p] = αi pi , (6.7) i=1

which is the unconditional expectation of the price to be paid. Suppose next, that the buyer adopts a rule to accepts all price higher or equal to pk and reject all other prices. (Recall this is just an example.) Then the unconditional expectation of the price to be paid is E [p] =

n X

αi pi ,

(6.8)

i=k

The expectation in (6.8) is still unconditional since no new information entered in the formation of the expectation. Suppose we represent the acceptance rule of the buyer by the index k below the expectations operator E [·], as in Ek [·]. The expected payment is then Ek [p] =

k−1 X

αi 0 +

n X

i=1

αi pi ,

i=k

since all price strictly lower than pk are rejected. Clearly E1 [p] > Ek [p] as E1 [p] − Ek [p] =

n X i=1

αi pi −

n X i=k

αi pi =

k−1 X

αi pi > 0.

(6.9)

i=1

since the buyer is willing to pay pi in more circumstances in (6.7) and (6.8).

CHAPTER 6. GAMES OF INCOMPLETE INFORMATION

74

Consider now the average price which is paid under the two different policies conditional on accepting a price and paying it, in other words, we ask for the conditional expectation: Ek [p |p ≥ pk ] We consider now exclusively the events, i.e. realization of prices p, where p ≥ pk for some k. The conditional probability of a price pi being quoted conditional on pi ≥ pk is then given by Pr (pi |pi ≥ pk ) =

Pr (pi ) , Pr (pi ≥ pk )

(6.10)

since Pr ({pi } ∩ {pi ≥ pk }) = Pr (pi ) if indeed pi satisfies pi ≥ pk , which is the nothing else than Bayes rule.1 Notice that we can write more explicitly as: αi , (6.12) Pr (pi |pi ≥ pk ) = Pn j=k αj and that

n X

(pi |pi ≥ pk ) = 1.

i=k

The conditional expectation of the prices, conditioned on accepting then price, is then nothing else but taken the expectation with respect to the conditional probabilities rather than with the unconditional probabilities, so that n X α Pn i pi , Ek [p |p ≥ pk ] = j=k αj i=k where Ek [p |p ≥ pk ] is now the expected price paid conditional on accepting the price. You may now verify that the expected price or average price paid, conditional on paying is increasing in k, as we might have expected it. Next we generalize the notion of conditional expectation to continuum of prices where the prices are distributed according to a distribution function. 1

Recall that Bayes rule says for any two events, A and B, that Pr (A |B ) =

Pr (A ∩ B) Pr (B)

(6.11)

CHAPTER 6. GAMES OF INCOMPLETE INFORMATION

6.5.2

75

Densities - continuum of events

You will see that the generalization is entirely obvious, but it may help to familiarize yourself with the continuous case. Suppose a buyer is faced with a lottery of prices   p ∈ p, p¯ where the distribution of prices is given by a (continuous) distribution function F (p) and an associated density function f (p). Again suppose the buyer is willing to accept all prices, then the expected price to be paid by the buyer is Z p¯ Z p¯ E [p] = pf (p) dp = pdF (p) (6.13) p

p

which is the unconditional expectation of the price to be paid. Notice that the summation is now replaced with the integral operation. Suppose next, that the buyer adopts a rule to accept all prices higher or equal to pˆ and reject all other prices. (Recall this is just an example.) Then the unconditional expectation of the price to be paid is Z p¯ Epˆ [p] = pdF (p) (6.14) pˆ

Again, the expectation in (6.14) is still unconditional since no new information entered in the formation of the expectation and we represent the acceptance rule of the buyer by the index pˆ below the expectations operator E [·], as in Epˆ [·]. The expected payment is then Z

pˆ

Z 0dF (p) +

Epˆ [p] =

p¯

pdF (p) pˆ

p

since all price strictly lower than pˆ are rejected. Clearly E [p] > Epˆ [p] , for all pˆ > p. as Z E [p] − Epˆ [p] =

pˆ

pdF (p) > 0.

(6.15)

p

since the buyer is willing to pay p in more circumstances in (6.13) and (6.14).

CHAPTER 6. GAMES OF INCOMPLETE INFORMATION

76

Consider now the average price which is paid under the two different policies conditional on accepting a price and paying it, in other words, we ask for the conditional expectation: Epˆ [p |p ≥ pˆ] We consider now exclusively the events, i.e. realization of prices p, where p ≥ pˆ for some pˆ. Notice that we have now a continuum of events, each of which has probability zero, but all of which have associated densities. We then switch to densities. The conditional densities of a price p being quoted conditional on p ≥ pˆ is then given by f (p |p ≥ pˆ) =

f (p) . 1 − F (ˆ p)

(6.16)

Compare this expression to (6.10) and (6.12) above and notice that this follows from {p} ∩ {p ≥ pˆ} = {ˆ p} as long as p ≥ pˆ, and otherwise the intersection is of course the empty set Notice that, as before the conditional densities integrate up to 1 since Z p¯ Z p¯ Z p¯ f (p) 1 f (p |p ≥ pˆ) dp = dp = f (p) dp = 1, (6.17) p) 1 − F (ˆ p) pˆ pˆ pˆ 1 − F (ˆ where the last equality of course follows from2 : Z p¯ f (p) dp = 1 − F (ˆ p) . pˆ

Finally, the conditional expectation of the prices, conditioned on accepting then price, is then nothing else but taken the expectation with respect to the conditional probabilities rather than with the unconditional probabilities, so that Z pˆ Z pˆ Z pˆ f (p) 1 Epˆ [p |p ≥ pˆ] = pf (p |p ≥ pˆ) dp = p pf (p) dp. dp = 1 − F (ˆ p) 1 − F (ˆ p) pˆ pˆ pˆ 2

Recall the similarity between the second to last term in (6.17) to the term appearing when computing the expected value of the bid ps (vs ).

CHAPTER 6. GAMES OF INCOMPLETE INFORMATION

77

Again you may verify that the expected price or average price paid, conditional on paying is increasing in pˆ, as we might have expected it. In particular, lim Epˆ [p |p ≥ pˆ] = p¯

pˆ→¯ p

(6.18)

where in contrast, we have of course lim Epˆ [p] = 0.

pˆ→¯ p

(6.19)

You may wish to verify (6.18) and (6.19) to realize the difference between expected value (price) and conditional expected value (price) in the second example.

6.6 6.6.1

Double Auction Model

We present here another important trading situation where both sides of the market have private information. The trading game is also called a double auction. We assume that the seller’s valuation is vs ∼ F (vs ) = U ([0, 1]) ,

(6.20)

which we may think of the cost of producing one unit of the good. Buyer’s valuation vb ∼ F (vb ) = U ([0, 1]) . (6.21) The valuations vs and vb are independent. If sale occurs at p, buyer receives vb − p and seller receives p − vs . Trade occurs at p = 12 (ps + pb ) , if ps ≤ pb . There is no trade if ps > pb . If there is no trade both, buyer and seller receive zero payoff. Given vb , pb and ps , the buyer’s payoff is:  vb − 21 (ps + pb ) if pb ≥ ps ub (vb , pb , ps ) = 0 if pb < ps and similar for the seller  us (vs , pb , ps ) =

1 2

(ps + pb ) − vs if pb ≥ ps 0 if pb < ps

CHAPTER 6. GAMES OF INCOMPLETE INFORMATION

6.6.2

78

Equilibrium

A strategy for each agent is then a mapping pi : Vi → R.

(6.22)

Denote an equilibrium strategy by p∗i (vi ) We can then define a Bayes-Nash equilibrium as follows. Definition 64 A Bayes-Nash equilibrium is given by {p∗b (vb ) , p∗s (vs )} such that Ep∗s [ub (vb , p∗b (vb ) , p∗s )] ≥ Ep∗s [ub (vb , p0b , p∗s )] , ∀vb , p0b ,

(6.23)

Ep∗b [us (vs , p∗s (vs ) , p∗b )] ≥ Ep∗b [us (vs , p0s , p∗b )] , ∀vs , p0s .

(6.24)

and

Remark 65 The Bayes part in the definition of the Bayes-Nash equilibrium through (6.23) and (6.24) is that the buyer has to find an optimal bid for every value vb while he is uncertainty about the ask (p∗s ) of the seller. From the buyer’s point of view, he is uncertain about p∗s as the ask, p∗s = p∗s (vs ) will depend on the value the seller assigns to the object, but as this is the private information of the seller, the buyer has to make his bid only knowing that the seller will adopt the equilibrium strategy: p∗s : Vs → [0, 1], but not knowing the realization of vs and hence not knowing the realization of p∗s = p∗s (vs ).

6.6.3

Equilibrium Analysis

To find the best strategy for the buyer, and likewise for the seller, we have to able to evaluate the net utility of the buyer for every possible bid he could make, given a particular value vb he assigns to the object,   Z 1 ∗ ∗ Ep∗s [ub (vb , pb , ps )] = vb − (pb + ps ) dG∗ (p∗s ) + (6.25) 2 ∗ ∗ {ps |ps ≤pb }

CHAPTER 6. GAMES OF INCOMPLETE INFORMATION Z + {p∗s |p∗s >pb }

79

0dG∗ (p∗s )

where G∗ (x) = Pr (p∗s ≤ x) is the distribution of the equilibrium asks of the seller. Notice now that the equilibrium ask, p∗s , of the seller will depend on the realization of the seller’s value vs .Thus we can equivalently, the expectation in (6.25) with respect to vs , or   Z 1 ∗ ∗ vb − (pb + ps (vs )) dF (vs ) (6.26) Evs [ub (vb , pb , ps (vs ))] = 2 {vs |p∗s (vs )≤pb } The advantage of the later operation is that we have direct information about the distribution of values, whereas we have only indirect information about the distribution of the equilibrium asks. Using (6.20), we get   Z 1 ∗ ∗ Evs [ub (vb , pb , ps (vs ))] = vb − (pb + ps (vs )) dvs . (6.27) 2 {vs |p∗s (vs )≤pb } However, as we don’t know the exact relationship between vs and p∗s , we can’t take the expectation yet. Similar to the auction example, we therefore make the following guess, which we shall verify eventually about the relationship of vs and p∗s : p∗s (vs ) = as + cs vs . (6.28) Inserting (6.28) into (6.27) leads us to   Z 1 vb − (pb + as + cs vs ) dvs . 2 {vs |p∗s (vs )≤pb }

(6.29)

The final question then is what is the set of vs over which we have to integrate, or {vs |p∗s (vs ) ≤ pb } = {vs |as + cs vs ≤ pb }   p − a b s = vs vs ≤ cs and hence (6.29) is Z 0

pb −as cs

  1 vb − (pb + as + cs vs ) dvs 2

CHAPTER 6. GAMES OF INCOMPLETE INFORMATION

80

Integrating yields   pbc−as  s 1 2 1 p b v s + as v s + c s v s vb vs − 2 2 0 or Evs [ub (vb , pb , p∗s

p b − as (vs ))] = cs



1 vb − 2



1 p b − as p b + as + c s 2 cs

 (6.30)

The expected utility for the buyer is now expressed as a function of vb , pb and the constants in the strategy of the seller, but independent of p∗s or vs . Simplifying, we get expected net utility conditional on trade

probability of trade

ub (vb , pb , as , cs ) =

z }| { p b − as cs

z ×

1 vb − 2

 }| { 3 1 p b + as 2 2

,

(6.31)

which essentially represents the trade-off for the buyer. A higher bid pb increases the probability of trade but decreases the revenue conditional on trade. The first order conditions are   3pb + as 3 ∂ub (vb , pb , as , cs ) = vb − − (pb − as ) = 0 ∂pb 4 4 or

2vb as + . (6.32) 3 3 We can perform a similar steps of arguments for the seller to obtain  Z 1  1 (ps + ab + cb vb ) − vs dvb ps −ab 2 c p∗b (vb ) =

b

and we get the sellers payoff as a function of vs , ps , ab , cb :    1 1 1 2 us (vs , ps , ab , cb ) = p s v b + ab v b + c b v b − v s v b ps −ab 2 2 cb

and when evaluated it give us probability of trade

us (vs , ps , ab , cb ) =

z }| { c b − p s + ab × cb

expected net utility conditional on trade

z }| { 1 (3ps + cb + ab − 4vs ) 4

CHAPTER 6. GAMES OF INCOMPLETE INFORMATION

81

where the trade-off is now such that a higher ask leads to lower probability of trade, but a higher net utility conditional on trade. Taking the first order conditions, leads us to ∂us (vs , ps , ab , cb ) =0 ∂ps or equivalently 1 1 2 p∗s (vs ) = cb + ab + vs (6.33) 3 3 3 ¿From the solution of the two pricing policies, we can now solve for ab and as as well as 1 1 c b + ab = as 3 3 as = ab 3 and hence

1 1 as = , a b = 4 12 and thus the complete resolution is p∗b (vb ) =

1 2 + vb 12 3

and

1 2 + vs 4 3 Next we can evaluate the efficiency of the equilibrium. Since trade occurs if p∗s (vs ) =

2 1 2 1 + vb ≥ + vs 12 3 4 3 1 ⇔ vb − vs ≥ 4

p∗b (vb ) ≥ p∗s (vs ) ⇔

trade occurs if the gains from trade exceed 41 . The following strategies also form an equilibrium for any x ∈ [0, 1] .   x if vb ≥ x x if vs ≤ x pb = ps = . 0 otherwise 1 otherwise Readings. Chapter 3 in Gibbons (1992), FT Chapter 6, MWG, Chapter 8.E.

Chapter 7 Adverse selection (with two types) Often also called self-selection, or “screening”. In insurance economics, if a insurance company offers a tariff tailored to the average population, the tariff will only be accepted by those with higher than average risk.

7.1

Monopolistic Price Discrimination

A simple model of wine merchant and wine buyer, who could either have a coarse or a sophisticated taste, which is unobservable to the merchant. What qualities should the merchant offer and at what price? The model is given by the utility function of the buyer, which is v (θi , qi , ti ) = u (θi , qi ) − ti = θi qi − ti , i ∈ {l, h}

(7.1)

where θi represent the marginal willingness to pay for quality qi and ti is the transfer (price) buyer i has to pay for the quality qi . The taste parameters θi satisfies 0 < θl < θh < ∞. (7.2) The cost of producing quality q ≥ 0 is given by c (q) ≥ 0, c0 (q) > 0, c00 (q) > 0.

(7.3)

The ex-ante (prior) probability that the buyer has a high willingness to pay is given by p = Pr (θi = θh ) 82

CHAPTER 7. ADVERSE SELECTION (WITH TWO TYPES)

83

We also observe that the difference in utility for the high and low valuation buyer for any given quality q u (θh , q) − u (θl , q) is increasing in q. (This is know as the Spence-Mirrlees sorting condition.). If the taste parameter θi were a continuous variable, the sorting condition could be written in terms of the second cross derivative: ∂ 2 u (θ, q) > 0, ∂θ∂q which states that taste θ and quality q are complements. The profit for the seller from a bundle (q, t) is given by π (t, q) = t − c (q)

7.1.1

First Best

Consider first the nature of the socially optimal solution. As different types have different preferences, they should consume different qualities. The social surplus for each type can be maximized separately by solving max {θi qi − c (qi )} qi

and the first order conditions yield: qi = qi∗ ⇐⇒ c0 (qi∗ ) = θi ⇒ ql∗ < qh∗ . The efficient solution is the equilibrium outcome if either the monopolist can perfectly discriminate between the types (first degree price discrimination) or if there is perfect competition. The two outcomes differ only in terms of the distribution of the social surplus. With a perfectly discriminating monopolist, the monopolist sets ti = θi qi (7.4) and then solves for each type separately: max π (ti , qi ) ⇐⇒ max {θi qi − c (qi )} ,

{ti ,qi }

{ti ,qi }

using (7.4). Likewise with perfect competition, the sellers will break even, get zero profit and set prices at ti = c (qi∗ ) in which case the buyer will get all the surplus.

CHAPTER 7. ADVERSE SELECTION (WITH TWO TYPES)

7.1.2

84

Second Best: Asymmetric information

Consider next the situation under asymmetric information. It is verified immediately that perfect discrimination is now impossible as θh ql∗ − t∗l = (θh − θl ) ql∗ > 0 = θh∗ qh∗ − th

(7.5)

but sorting is possible. The problem for the monopolist is now max

{tl ,ql ,th ,qh }

(1 − π) tl − c (ql ) + π (th − (c (qh )))

(7.6)

subject to the individual rationality constraint for every type θi qi − ti = 0

(IRi )

(7.7)

and the incentive compatibility constraint θi qi − ti = θi qj − tj (ICi )

(7.8)

The question is then how to separate. We will show that the binding constraint are IRl and ICh , whereas the remaining constraints are not binding. We then solve for tl and th , which in turn allows us to solve for qh , and leaves us with an unconstrained problem for ql .Thus we want to show (i) IRl binding, (ii) ICh binding, (iii) qˆh ≥ qˆl (iv) qˆh = qh∗

(7.9)

Consider (i). We argue by contradiction. As θh qh − th = θh ql − tl = θl ql − tl ICh

(7.10)

θh >θl

suppose that θl ql − tl > 0, then we could increase tl , th by a equal amount, satisfy all the constraints and increase the profits of the seller. Contradiction. Consider (ii) Suppose not, then as θh qh − th > θh ql − tl = θl ql − tl = 0 θh >θl

(7.11)

(IRl )

and thus th could be increased, again increasing the profit of the seller. (iii) Adding up the incentive constraints gives us (ICl ) + (ICl ) θh (qh − ql ) = θl (qh − ql )

(7.12)

CHAPTER 7. ADVERSE SELECTION (WITH TWO TYPES)

85

and since: θh > θl ⇒ qˆh − qˆl = 0.

(7.13)

Next we show that ICl can be neglected as th − tl = θh (qh − ql ) = θl (qh − ql ) .

(7.14)

This allows to say that the equilibrium transfers are going to be tl = θl ql

(7.15)

and th − tL = θh (qh − qL ) ⇒ th = θh (qh − qL ) + θl ql . Using the transfer, it is immediate that qˆh = qh∗ and we can solve for the last remaining variable, qˆl . max {(1 − p) (θl ql− (c (ql )) + p (θh (qh∗ − qL ) + θl ql − c (qh∗ )))} ql

qh∗

but as is just as constant, the optimal solution is independent of constant terms and we can simplify the expression to: max {(1 − p) (θl ql − c (ql )) − p (θh − θl ) ql } ql

Dividing by (1 − p) we get  max θl ql − c (ql ) − ql

p (θh − θl ) ql 1−p



for which the first order conditions are p (θh − θl ) ql = 0 θl − c0 (ql ) − 1−p This immediately implies that the solution qˆl : ⇐⇒ c0 (ˆ ql ) < θl ⇐⇒ qˆl < ql∗ and the quality supply to the low valuation buyer is inefficiently low (with the possibility of complete exclusion). Consider next the information rent for the high valuation buyer, it is I (ql ) = (θh − θl ) ql and therefore the rent is increasing in ql which is the motivation for the seller to depress the quality supply to the low end of the market. The material is also covered in Salanie (1997), Chapter 2.

Chapter 8 Theoretical Complements 8.1

Mixed Strategy Bayes Nash Equilibrium

Definition 66 A Bayesian Nash equilibrium of Γ = {S1 , ..., SI ; T1 , ..., TI ; u1 , ..., uI ; p} is a strategy profile σ ∗ = (σ1∗ , ..., σI∗ ) such that, for all i, for all ti ∈ T and all si ∈ supp σi∗ (ti ): mixed strategy Nash Bayes

z

}|

z X }| { X pi (t−i |ti )  t−i ∈T−i

{

∗ ui ((s0i , s−i ) ; (ti , t−i )) σ−i (s−i |t−i )

s−i ∈S−i

≥ mixed strategy Nash Bayes

z

}|

{ z X }| X pi (t−i |ti )  t−i ∈T−i

{

∗ ui ((s0i , s−i ) ; (ti , t−i )) σ−i (s−i |t−i ), ∀s0i

s−i ∈S−i


∗ ∗ ∗ where σ−i (s−i |t−i ) ≡ σ1∗ (s1 |t1 ) , ..., σi−1 (si−1 |ti−1 ) , σi+1 (si+1 |ti+1 ) , ..., σn∗ (sn |tn ) . Since the strategy choices are independent across players, we can write that: Y ∗ σ−i (s−i |t−i ) = σj∗ (sj |tj ) . j6=i

86

CHAPTER 8. THEORETICAL COMPLEMENTS

8.2 8.2.1

87

Sender-Receiver Games Model

A signaling games is a dynamic game of incomplete information involving two players: a sender (S) and receiver (R). The sender is the informed party, the receiver the uniformed party. (Describe the game in its extensive form). The timing is as follows: 1. nature draws a type tiP ∈ T = {t1 , ..., tI } according to a probability distribution p (ti ) ≥ 0, i p (ti ) = 1, 2. sender observes ti and chooses a message mj ∈ M = {m1 , ..., mJ }, 3. receiver observes mj (but not ti ) and chooses an action ak ∈ A = {a1 , ..., aK }, 4. payoffs are given by uS (ti , mj , ak ) and uR (ti , mj , ak ).

8.3 8.3.1

Perfect Bayesian Equilibrium Informal Notion

The notion of a perfect Bayesian equilibrium is then given by: Condition 67 At each information set, the player with the move must have a belief about which node in the information set has been reached by the play of the game. For a non singleton information set, a belief is a probability distribution over the nodes in the information set; for a singleton information set, the player’s belief puts probability one on the single decision node. Condition 68 Given their beliefs, the players’ strategies must be sequentially rational. That is, at each information set the action taken by the player with the move (and the player’s subsequent strategy) must be optimal given the player’s belief at that information set and the other players’ subsequent strategies (where a “subsequent strategy” is a complete plan of action covering every contingency that might arise after the given information set has been reached).

CHAPTER 8. THEORETICAL COMPLEMENTS

88

Definition 69 For a given equilibrium in a given extensive-form game, an information set is on the equilibrium path if it will be reached with positive probability if the game is played according to the equilibrium strategies, and is off the equilibrium path if it is certain not to be reached if the game is played according to the equilibrium strategies (where “equilibrium” can mean Nash, subgame-perfect, Bayesian, or perfect Bayesian equilibrium). Condition 70 At information sets on the equilibrium path, beliefs are determined by Bayes’ rule and the players’ equilibrium strategies. Condition 71 At information sets off the equilibrium path beliefs are determined by Bayes’ rule and the players’ equilibrium strategies where possible. Definition 72 A perfect Bayesian equilibrium consists of strategies and beliefs satisfying Requirements 1 through 4.

8.3.2

Formal Definition

Condition 73 After observing any message mj from M , the Receiver must have a belief about which types could have sent mj . Denote this belief by the probability distribution µ (ti |mj ), where µ (ti |mj ) ≥ 0 for each ti in T and X µ (ti |mj ) = 1 (8.1) ti ∈T

Condition 74 1. For each mj in M, the Receiver’s action a∗ (mj ) must maximize the Receiver’s expected utility, given the belief µ (ti |mj ) about which types could have sent mj . That is, a∗ (mj ) solves X max µ (ti |mj )UR (ti , mj , ak ) . (8.2) ak ∈A

ti ∈T

2. For each ti in T, Sender’s message m∗ (ti ) must maximize the Sender’s utility, given the Receiver’s strategy a∗ (mj ) . That is, m∗ (ti ) solves: max Us (ti , mj , a∗ (mj ))

mj ∈M

(8.3)

CHAPTER 8. THEORETICAL COMPLEMENTS

89

Condition 75 For each mj in M , if exists ti in T such that m∗ (ti ) = mj , then the Receiver’s belief at the information set corresponding to mj must follow from Bayes’ rule and the Sender’s strategy: p (ti ) . µ (ti |mj ) = P p (ti )

(8.4)

ti ∈T

We can summarize these results to get the definition of a Perfect Bayesian Equilibrium: Definition 76 A pure-strategy perfect Bayesian equilibrium in a signaling game is a pair of strategies m∗ (ti ) and a∗ (mj ) and a belief µ (ti |mj ) satisfying signaling requirements (73)-(75). Alternatively, we can state it more succinctly as saying that: Definition 77 (PBE) A pure strategy Perfect Bayesian Equilibrium is a set of strategies {m∗ (ti ) , a∗ (mj )} and posterior beliefs p∗ (ti |mj ) such that: P 1. ∀ti , ∃p∗ (ti |mj ) , s.th. p∗ (ti |mj ) ≥ 0, and ti ∈T p∗ (ti |mj ) = 1; P 2. ∀mj , a∗ (mj ) ∈ arg max ti ∈T uR (ti , mj , ak ) p∗ (ti |mj ) ; 3. ∀ti , m∗ (ti ) ∈ arg max uS (ti , mj , a∗ (mj )) 4. ∀mj if ∃ti ∈ T s.th. at m∗ (ti ) = mj , then: p (ti ) p (ti |mj ) = P . 0 {t0i |m∗ (t0i )=mj } p (ti ) We can now introduce additional examples to refine the equilibrium set. Example 78 Job Market Signalling Example 79 Cho-Kreps (Beer-Quiche) - Entry Deterrence. Remark the payoffs in Gibbons (1992) have a problem, they don’t allow for a separating equilibrium, modify)

CHAPTER 8. THEORETICAL COMPLEMENTS

90

Definition 80 (Equilibrium Domination) Given a P BE, the message mj is equilibrium-dominated for type ti , if US∗ (ti ) > max US (ti , mj , ak ) . ak ∈A

Definition 81 (Intuitive Criterion) If the information set following mj is off the equilibrium path and mj equilibrium dominated for type ti , then µ (ti |mj ) = 0. This is possible provided that mj is not equilibrium dominated for all types in T . Readings: MWG Chapter 9.C, FT Chapter 8.

CHAPTER 8. THEORETICAL COMPLEMENTS

8.4

91

References

D. Abreu. Extremal equilibria of oligopolistic supergames. Journal of Economic Theory, 39:191–225, 1986. K. Binmore. Fun and Games. D.C. Heath, Lexington, 1992. D. Fudenberg and J. Tirole. Game Theory. MIT Press, Cambridge, 1991. R. Gibbons. Game Theory for Applied Economists. Princeton University Press, Princeton, 1992. D. M. Kreps. A Course in Microeconomic Theory. Princeton University Press, Princeton, 1990. D.M. Kreps and R. Wilson. Sequential equilibria. Econometrica, 50:863– 894, 1982. H. Kuhn. Extensive games and the problem of information. In H. Kuhn and A. Tucker, editors, Contributions to the Theory of Games, pp. 193–216. Princeton University Press, Princeton, 1953. A. Mas-Collel, M.D. Whinston, and J.R. Green. Microeconomic Theory. Oxford University Press, Oxford, 1995. J. Nash. Equilibrium points in n-person games. Proceedings of the National Academy of Sciences, 36:48–49, 1950. M.J. Osborne and A. Rubinstein. A Course in Game Theory. MIT Press, Cambridge, 1994. P. Reny. On the existence of pure and mixed strategy Nash equilibria in discontinuous games. Econometrica, 67:1029–1056, 1999. S.M. Ross. Probability Models. Academic Press, San Diego, 1993. A. Rubinstein. Perfect equilibrium in a bargaining model. Econometrica, 50:97–109, 1982. B. Salanie. The Economics of Contracts. MIT Press, Cambridge, 1997.