Eco514-Game Theory Lecture 2:(Iterated) Best Response Operators Marciano siniscalchi September 21. 1999 Introduction This lecture continues the analysis of normal-form games. We analyze general, non-zeros ames, emphasizing the informalequation Rational Behavior Assumptions about Beliefs= Solution Concepts Before we tackle the new material. let us review what we have learned about zerosum games in light of this "equation". Rational behavior in the context of normal-form games (zerosum or otherwise) means that players choose strategies which maximize their expected payoff, given their beliefs about their opponents'choices. Today we shall examine a few technical aspects related to the existence and characteristics of the best reply correspondence but the basics should be familiar to you from decision theory The minmax theory makes the following assumption about beliefs: each player expects her opponent to(1)understand that she will best-respond to his strategy, and(2) play so as to minimize her expected payoff. That is, each player reasons as if she were to observe the (possibly random) choice of her opponent and best-respond to it, and as if her opponent anticipating this, chose a strategy in order to make her payoff as low as possible Formally, the problem min max ui(a,a;) a∈△(4)a2∈△(A) defines the belief a; of Player i about Player j Best Replies Let us begin with a formal definition of best replies in the case of finite games
Eco514—Game Theory Lecture 2: (Iterated) Best Response Operators Marciano Siniscalchi September 21, 1999 Introduction This lecture continues the analysis of normal-form games. We analyze general, non-zerosum games, emphasizing the informal “equation”: Rational Behavior + Assumptions about Beliefs = Solution Concepts Before we tackle the new material, let us review what we have learned about zerosum games in light of this “equation”. Rational behavior in the context of normal-form games (zerosum or otherwise) means that players choose strategies which maximize their expected payoff, given their beliefs about their opponents’ choices. Today we shall examine a few technical aspects related to the existence and characteristics of the best reply correspondence, but the basics should be familiar to you from decision theory. The minmax theory makes the following assumption about beliefs: each player expects her opponent to (1) understand that she will best-respond to his strategy, and (2) play so as to minimize her expected payoff. That is, each player reasons as if she were to observe the (possibly random) choice of her opponent and best-respond to it, and as if her opponent, anticipating this, chose a strategy in order to make her payoff as low as possible. Formally, the problem min α i j∈∆(Aj ) max α i i∈∆(Ai) ui(α i i , αi j ) defines the belief α i j of Player i about Player j. Best Replies Let us begin with a formal definition of best replies in the case of finite games. 1
Definition 1 Fix a finite normal-form game G=(N, (Ai, Lien), a player i E I and a probability measure a_i E A(A-i. An action ai E Ai is a best reply to the belief a-i iff ∑a-(a-)u(an,a-)≥∑a-(a-)u1,a-)1∈A In finite games, expected payoffs are always well-defined. Not so for games with infinite action spaces: even assuming a nice measure-theoretic structure, it is not hard to construct (mildly pathological) examples in which payoff functions are not integrable Thus, a better definition for infinite games is the following. Assume that, for every player i E N, the set of actions(Ai, Ai) is a measure space. Endow the product sets A and A-i with the natural product sigma-algebras, denoted A and A_i. Finally, assume that ui is A- measurable. The sigma-algebras on the set of actions will be indicated explicitly for infinite Definition 2 Fix a normal-form game G=(N, (Ai, Ai, uiieN), a player i E N and a belief a-i E A(A-i, A-i). An action a; E Ai is a best reply to the belief a-i iff the Lebesgue integralS ui(ai, a-i)a-i(da )exists, and moreover u(4,a-)a-()2/a(0,a-)a-()∈A whenever the right-hand side integral exists I emphasize that integrals are taken(here and in the following) in the Lebesgue sense Even if expected payoffs are well-defined, the very structure of the game might lead to the non-existence of best replies. An obvious example arises in the Bertrand price competition game. Example. Two firms produce and sell the same good, facing a market of size Q, and zero fixed and marginal cost; finally, the two firms compete by posting unit prices pi, i=1, 2. Assume that consumers have unit demand and buy from the cheapest producer; if P1= P2 buy from each firm with probability 2 Suppose that Firm 1 expects Firm 2 to post a price equal to p2= 2; this corresponds to a degenerate belief, concentrated on 2. Then any price p1 >2 yields 0, any price p1 2 yields Qpl, and P1=P2=2 yields 22=Q. Clearly no price pi satisfies our definition of a best reply The conditions for the existence of best replies are related to those which guarante the existence of an optimum. We need to specify a topology Ti on every action space A 2
Definition 1 Fix a finite normal-form game G = (N,(Ai , ui)i∈N ), a player i ∈ I and a probability measure α−i ∈ ∆(A−i). An action ai ∈ Ai is a best reply to the belief α−i iff X A−i α−i(a−i)ui(ai , a−i) ≥ X A−i α−i(a−i)ui(a 0 i , a−i) ∀a 0 i ∈ Ai . In finite games, expected payoffs are always well-defined. Not so for games with infinite action spaces: even assuming a nice measure-theoretic structure, it is not hard to construct (mildly pathological) examples in which payoff functions are not integrable. Thus, a better definition for infinite games is the following. Assume that, for every player i ∈ N, the set of actions (Ai , Ai) is a measure space. Endow the product sets A and A−i with the natural product sigma-algebras, denoted A and A−i . Finally, assume that ui is Ameasurable. The sigma-algebras on the set of actions will be indicated explicitly for infinite games. Definition 2 Fix a normal-form game G = (N,(Ai , Ai , ui)i∈N ), a player i ∈ N and a belief α−i ∈ ∆(A−i , A−i). An action ai ∈ Ai is a best reply to the belief α−i iff the Lebesgue integral R A−i ui(ai , a−i)α−i(dai ) exists, and moreover Z A−i ui(ai , a−i)α−i(dai ) ≥ Z A−i ui(a 0 i , a−i)α−i(dai ) ∀a 0 i ∈ Ai whenever the right-hand side integral exists. I emphasize that integrals are taken (here and in the following) in the Lebesgue sense. Even if expected payoffs are well-defined, the very structure of the game might lead to the non-existence of best replies. An obvious example arises in the Bertrand price competition game. Example. Two firms produce and sell the same good, facing a market of size Q, and zero fixed and marginal cost; finally, the two firms compete by posting unit prices pi , i = 1, 2. Assume that consumers have unit demand and buy from the cheapest producer; if p1 = p2, consumers buy from each firm with probability 1 2 . Suppose that Firm 1 expects Firm 2 to post a price equal to p2 = 2; this corresponds to a degenerate belief, concentrated on 2. Then any price p1 > 2 yields 0, any price p1 < 2 yields Qp1, and p1 = p2 = 2 yields 2Q 2 = Q. Clearly no price p1 satisfies our definition of a best reply. The conditions for the existence of best replies are related to those which guarantee the existence of an optimum. We need to specify a topology Ti on every action space Ai ; 2
furthermore, we assume that the relevant sigma-algebra in the definition of a best reply is the corresponding Borel sigma-algebra B(Ti)(hence, ui ()is Borel-measurable if it is continuous). Finally, we assume product sets are endowed with the product topology and the induced Borel product sigma-algebra Proposition 0.1 Consider a game G=(N, (Ai, Ii, uiieN) and fix a player i E N. If ui ( is bounded and continuous, and Ai is a compact metrizable space, then for every measure a-i∈△(A-a,B(T) there exists a best reply a;∈A Proof: We need to show that the map p: A,HJA ui(ai, a-i)a-i(da-i) is continuous Since A; is a metric space, sequences characterize continuity. Thus, fix a sequence ai-ai in A;. By assumption, ui(ah, a-i)ui(ai, a-i)for every a_i E A-i, and ui is bounded Thus, by Lebesgue's Dominated Convergence theorem, p(ai-p(ai).B Observe that, in the above proof, it is essential that expectations be defined in the Lebesgue sense: otherwise, stronger conditions are required on the payoff functions and action spaces There are two reasons why we are interested in infinite games. First, for Nash equilibria to exist one must enlarge the players' action spaces to include all mixtures of strategies thus, effectively, one is looking at an infinite game, in which every strategy set is a simplex, hence a compact subset of Euclidean space, and every payoff function is continuous(because the expected payoff from a mixed strategy profile is linear in the probabilities). Thus, the preceding result applies Second. several interesting economic models lend themselves to a formulation involving infinite strategy spaces. Thus, getting some exposure to the issues that arise in such settings can be useful The Best Reply Correspondence Recall that a correspondence is a set-valued function. Since, in general, Player i may have more than one best reply to a belief a-i E A(A-i, A-i), we use correspondences to describe the mapping from beliefs to best replies Definition 3 Fix a game G=(N, (Ai, AieN) and a player i E N. The best-reply corre- spondence for player i, ri: A(A-i, A-i)= Ai, is defined by va-∈△(A-,A-),a1∈ra(a-)台a; is a best reply given a- The preceding proposition then gives conditions under which the best-reply correspon- dence is nonempty
furthermore, we assume that the relevant sigma-algebra in the definition of a best reply is the corresponding Borel sigma-algebra B(Ti) (hence, ui(·) is Borel-measurable if it is continuous). Finally, we assume product sets are endowed with the product topology and the induced Borel product sigma-algebra. Proposition 0.1 Consider a game G = (N,(Ai , Ti , ui)i∈N ) and fix a player i ∈ N. If ui(·) is bounded and continuous, and Ai is a compact metrizable space, then for every measure α−i ∈ ∆(A−i , B(Ti)) there exists a best reply ai ∈ Ai . Proof: We need to show that the map ϕ : Ai 7→ R A−i ui(ai , a−i)α−i(da−i) is continuous. Since Ai is a metric space, sequences characterize continuity. Thus, fix a sequence a k i → ai in Ai . By assumption, ui(a k i , a−i) → ui(ai , a−i) for every a−i ∈ A−i , and ui(·) is bounded. Thus, by Lebesgue’s Dominated Convergence theorem, ϕ(a k i ) → ϕ(ai). Observe that, in the above proof, it is essential that expectations be defined in the Lebesgue sense: otherwise, stronger conditions are required on the payoff functions and action spaces. There are two reasons why we are interested in infinite games. First, for Nash equilibria to exist one must enlarge the players’ action spaces to include all mixtures of strategies; thus, effectively, one is looking at an infinite game, in which every strategy set is a simplex, hence a compact subset of Euclidean space, and every payoff function is continuous (because the expected payoff from a mixed strategy profile is linear in the probabilities). Thus, the preceding result applies. Second, several interesting economic models lend themselves to a formulation involving infinite strategy spaces. Thus, getting some exposure to the issues that arise in such settings can be useful. The Best Reply Correspondence Recall that a correspondence is a set-valued function. Since, in general, Player i may have more than one best reply to a belief α−i ∈ ∆(A−i , A−i), we use correspondences to describe the mapping from beliefs to best replies. Definition 3 Fix a game G = (N,(Ai , Ai)i∈N ) and a player i ∈ N. The best-reply correspondence for player i, ri : ∆(A−i , A−i) ⇒ Ai , is defined by ∀α−i ∈ ∆(A−i , A−i), ai ∈ ri(α−i) ⇔ ai is a best reply given α−i The preceding proposition then gives conditions under which the best-reply correspondence is nonempty. 3
Correlated Rationalizability and Iterated Dominance Having disposed of all required technicalities, let us go back to our "informal equation Rational Behavior Assumptions about Beliefs= Solution Concepts Fix a game G=(N, (Ai, Ti, uiieN) and assume that each(Ai, Ii) is a compact metrizable space(you can also assume that each Ai is finite, as far as the substantive arguments are concerned) and that payoff functions are continuous We begin by asking: what is a plausible outcome of the game, if we are willing to assume that players are(Bayesian) rational? The answer should be clear: we can only expect an action profile(alien to be chosen iff, for every player i E N, ai E rila_i)for some a-∈△(A-2B() That is: if we think that players are "good Bayesians, " we should expect them to formu- late a belief about their opponents choice, and play a best reply given that belief. equiva- lently, we should expect a rational player to choose an action only if it that action is justified by some belief This exhausts all the implications of Bayesian rationality: in particular, we do not pos talate any relationship between the beliefs justifying the actions in any given profile In very simple games, Bayesian rationality is sufficient to isolate a unique solution: for instance, this is true in the Prisoner's Dilemma. However, in Matching Pennies, the Row player(who wants to match) may choose H because she expects the Column player to also choose H, whereas the Column player (who wants to avoid matches) actually chooses T because he(correctly, it turns out)expects the Row player to choose H. Indeed, it is easy to see that any action profile is consistent with Bayesian rationality in Matching Pennies However one might reason as follows If I, the theorist, am able to rule out certain actions because they are never best-replies, perhaps the players will be able to do so, too. But, if so, it seems easonable to assume that their beliefs should assign zero probability to the col- lection of eliminated actions. This entails a further restriction on the collection of actions that they might choose That is, in addition to assuming that players are Bayesian rational, we may be willing to assume that they believe that their own opponents are also Bayesian rational. This is precisely the type of assumption about beliefs referred to in our "informal equation. It is also a very powerful idea
Correlated Rationalizability and Iterated Dominance Having disposed of all required technicalities, let us go back to our “informal equation” Rational Behavior + Assumptions about Beliefs = Solution Concepts. Fix a game G = (N,(Ai , Ti , ui)i∈N ) and assume that each (Ai , Ti) is a compact metrizable space (you can also assume that each Ai is finite, as far as the substantive arguments are concerned) and that payoff functions are continuous. We begin by asking: what is a plausible outcome of the game, if we are willing to assume that players are (Bayesian) rational? The answer should be clear: we can only expect an action profile (ai)i∈N to be chosen iff, for every player i ∈ N, ai ∈ ri(α−i) for some α−i ∈ ∆(A−i , B(Ti)). That is: if we think that players are “good Bayesians,” we should expect them to formulate a belief about their opponents’ choice, and play a best reply given that belief. Equivalently, we should expect a rational player to choose an action only if it that action is justified by some belief. This exhausts all the implications of Bayesian rationality: in particular, we do not postulate any relationship between the beliefs justifying the actions in any given profile. In very simple games, Bayesian rationality is sufficient to isolate a unique solution: for instance, this is true in the Prisoner’s Dilemma. However, in Matching Pennies, the Row player (who wants to match) may choose H because she expects the Column player to also choose H, whereas the Column player (who wants to avoid matches) actually chooses T because he (correctly, it turns out) expects the Row player to choose H. Indeed, it is easy to see that any action profile is consistent with Bayesian rationality in Matching Pennies. However, one might reason as follows: If I, the theorist, am able to rule out certain actions because they are never best-replies, perhaps the players will be able to do so, too. But, if so, it seems reasonable to assume that their beliefs should assign zero probability to the collection of eliminated actions. This entails a further restriction on the collection of actions that they might choose. That is, in addition to assuming that players are Bayesian rational, we may be willing to assume that they believe that their own opponents are also Bayesian rational. This is precisely the type of assumption about beliefs referred to in our “informal equation.” It is also a very powerful idea: 4
Example: Consider a two-firm version of the Cournot quantity competition game, with action spaces A;=0, 1] and payoffs ui( ai, a_i)=(2-ai-a-i)ai: that is, marginal costs are zero, and inverse demand is given by P(a)=2-q Notice that Player i's expected payoff depends linearly on Player -i's expected quantity thus, our analysis can be restricted to degenerate (point)beliefs without loss of generality For any a_i E A-i, Player i's best reply is found by solving Inax so Tila Then notice that no a; E[0, 2)is ever a best reply: after all, even if a-i=l, there would still be residual demand in the market, and consumers would be willing to pay 1 dollar for an dditional marginal unit of the good. That is, Player i is actually facing the residual inverse demand curve P(ai)=1-ai, so setting ai=,(the corresponding monopoly quantity)is optima This is true for i= 1, 2. Thus, assume that Player i understands that a-iE 1]: that is, Player i believes that, since her opponent is rational, he will never produce less than units of the good. But then, producing ai E(, 1] units cannot be a best reply against a belief satisfying this restriction. Since, moreover, we have already concluded that quantities ai E0, 5)must be discarded on the basis of rationality considerations alone, the assumptions Bayesian rationality Belief in the opponent,s Bayesian rationality already imply that only action profiles(a1, a2) with ai E [, i should be expected to Once we are willing to make this assumption about the players beliefs, it becomes natural at least conceive the possibility that the players themselves might contemplate it. This leads to a hierarchy of hypotheses about mutual belief in rationality. That is, we might think that players are Bayesian rational (2) players believe that their opponents are also Bayesian rational (3)players believe that their opponents believe that their own opponents are Bayesian rational: and so on The following definition captures the implications of these assumptions Definition 4 Fix a game G=(N, (Ai, Ti, ui)iEN ) For every player iE N, let A9=Aj.For k≥1 and for every i∈I, let ai∈ A' iff there exists a-∈△(A-,B(T-) such that
Example: Consider a two-firm version of the Cournot quantity competition game, with action spaces Ai = [0, 1] and payoffs ui(ai , a−i) = (2−ai −a−i)ai : that is, marginal costs are zero, and inverse demand is given by P(q) = 2 − q. Notice that Player i’s expected payoff depends linearly on Player −i’s expected quantity; thus, our analysis can be restricted to degenerate (point) beliefs without loss of generality. For any a−i ∈ A−i , Player i’s best reply is found by solving max ai∈[0,1] (2 − ai − a−i)ai , so ri(a−i) = 1 − 1 2 a−i Then notice that no ai ∈ [0, 1 2 ) is ever a best reply: after all, even if a−i = 1, there would still be residual demand in the market, and consumers would be willing to pay 1 dollar for an additional marginal unit of the good. That is, Player i is actually facing the residual inverse demand curve P R(ai) = 1 − ai , so setting ai = 1 2 (the corresponding monopoly quantity) is optimal. This is true for i = 1, 2. Thus, assume that Player i understands that a−i ∈ [ 1 2 , 1]: that is, Player i believes that, since her opponent is rational, he will never produce less than 1 2 units of the good. But then, producing ai ∈ ( 3 4 , 1] units cannot be a best reply against a belief satisfying this restriction. Since, moreover, we have already concluded that quantities ai ∈ [0, 1 2 ) must be discarded on the basis of rationality considerations alone, the assumptions of Bayesian rationality + Belief in the opponent’s Bayesian rationality already imply that only action profiles (a1, a2) with ai ∈ [ 1 2 , 3 4 ] should be expected. Once we are willing to make this assumption about the players’ beliefs, it becomes natural to at least conceive the possibility that the players themselves might contemplate it. This leads to a hierarchy of hypotheses about mutual belief in rationality. That is, we might think that: (1) players are Bayesian rational; (2) players believe that their opponents are also Bayesian rational; (3) players believe that their opponents believe that their own opponents are Bayesian rational; and so on. The following definition captures the implications of these assumptions. Definition 4 Fix a game G = (N,(Ai , Ti , ui)i∈N ). For every player i ∈ N, let A0 i = Ai . For k ≥ 1 and for every i ∈ I, let ai ∈ Ak i iff there exists α−i ∈ ∆(A−i , B(T−i)) such that 5