Eco514|Game Theory Lecture 3: Nash Equilibrium Marciano Siniscalchi September 23, 1999 Introduction Nash equilibrium has undoubtedly proved to be the most in uential idea in game theory. Its development was a major intellectual achievement; what is perhaps more important, it enabled fundamental breakthroughs in economics and the social sciences. Recent foundational research has emphasized the subtleties in the interpretation of Nash equilibrium. This lecture deals with the technical details of equilibrium analysis, but also with these interpretational issues. However, a more precise appraisal of the situation must be postponed until we develop a full-blown model of interactive beliefs. De nitions Fix a game G = (N;(Ai;Ti;ui)i2N), where each (Ai;Ti) is a compact metrizable space (as usual, you can think of nite action spaces unless explicitly noted) and every ui is bounded and continuous. Recall that we denote by ri : (A i;B(A i)))Ai Player i’s best-reply correspondence, which associates with each belief (probability distribution on A i, endowed with the Borel sigma-algebra) the set of best replies to it. The de nition of Nash equilibrium involves best replies to beliefs concentrated on a single action pro le. If the game is nite, these beliefs assign probability one to the speci ed pro le, and probability zero to any other belief; if the game is in nite, these beliefs are Dirichlet measures: that is, for any a i 2A i, we de ne a i 2 (A i;B(T i)) by letting (a i)(E) = 1 i a i2E for any E2B(T i). All you need to know about this is that Z A i ui(ai; )d a i = ui(ai;a i) 1 which is exactly what we want. In any case, to further simplify things, we introduce the following shorthand notation for best replies to beliefs concentrated on a single action pro le: De nition 1 Fix a game G = (N;(Ai;Ti;ui)i2N). For every i2N, Player i’s Nash best- reply correspondence i : A i)Ai is de ned by i(a i) = ri( a i) 8a i2A i That is, i(a i) is the set of Player i’s best replies to beliefs concentrated on a i. Note that this corresponds to OR’s \Bi( )": I wish to reserve the letter Bi for something else. We are ready for the de nition of Nash equilibrium: De nition 2 Fix a game G = (N;(Ai;Ti;ui)i2N). The pro le of actions (ai)i2N is a Nash equilibrium of G i ai2 i(a i) for all i2N. The literal interpretation is clear: in a Nash equilibrium, the action of each player is a best reply to the (belief concentrated on the) actions of her opponents. Existence Note that the above de nition applies to both nite and in nite games. Moreover, as stated, it does not guarantee existence in nite games. For example, Matching Pennies (see Lecture 1) does not have an equilibrium according to the above de nition. At this juncture, the theory treats nite and in nite games di erently. This might seem odd, and to some extent it so appears to this writer, too. However, the theory has developed as follows: for nite action sets, one employs a \trick" which (in some sense) guarantees existence in arbitrary games; for in nite games, theorists have developed conditions on the action spaces and payo functions under which Nash equilibria exist. There is no (known) \trick" which guarantees existence in arbitrary in nite games. I shall focus on existence (with the \trick") in nite games, although this requires a brief detour on in nite games and some ancillary notions. We shall only need to consider very special, well-behaved in nite games, and I will provide details only for those; however, I will indicate how the basic ideas and results extend to more general settings. Upper Hemicontinuity Let us take a step back. Recall that a function f : X!Y, where (X;TX) and (Y;TY ) are topological spaces, is continuous i f 1(V) =fx : f(x)2Vg2TX whenever V 2TY . 2 However, extending this de nition to correspondences is problematic, because the mean- ing of \f 1(V)" is ambiguous. The following de nition presents two alternatives. De nition 3 Let (X;TX) and (Y;TY ) be topological spaces, and consider a correspondence f : X )Y. For any V Y, the upper inverse of f at V is fu(V) = fx : f(x) Vg; the lower inverse of f at V is f‘(V) =fx : f(x)\V 6=;g. Clearly, fu(V) f‘(V), and the two de nitions coincide for singleton-valued correspon- dences, i.e. for functions. Each notion gives rise to a corresponding de nition of continuity: De nition 4 Let (X;TX) and (Y;TY ) be topological spaces, and consider a correspondence f : X)Y. Then f is upper hemicontinuous (uhc) i , for every V 2TY , fu(V)2TX; f is lower hemicontinuous (lhc) i , for every V 2TY , f‘(V) 2TX; f is continuous i it is both uhc and lhc. De nition 4 highlights the connection with the notion of continuity for functions, but is somewhat hard to apply. However, the following characterization is useful:1 Theorem 0.1 Let (X;TX) be metrizable, and (Y;TY ) be compact and metrizable. Then a correspondence f : X)Y is: (1) upper hemicontinuous i , for every pair of convergent sequences fxngn 0 !x in X and fyngn 0 !y in Y such that yn2f(xn), y2f(x); (2) lower hemicontinuous i , for any sequencefxngn 0 !x in X, and for every y2f(x), there exists a subsequencefxnkgk 0 inX and a sequencefynkgk 0 inY such thatynk 2f(xnk) for all k 0, and ynk !y. For in nite games, under our assumptions, the Nash best-reply correspondence is upper hemicontinuous as a consequence of the Maximum Theorem. However, in order to de ne Nash equilibrium for nite games (with the \trick" I mentioned above), a direct proof is easy to provide. Existence of Nash Equilibrium To establish the desired result, we need two ingredients: a \Big Mathematical Hammer," the Kakutani-Fan-Glicksberg Fixed-Point Theorem, and a trick. Let us start with the former.2 1For the more mathematically inclined, the domain of the correspondence in the next theorem need only be rst-countable. 2For the more mathematically inclined, the theorem actually applies to locally convex Hausdor topo- logical vector spaces, such as e.g. the set of real-valued functions on a nonempty set X (endowed with the product topology). 3 Theorem 0.2 Let K be a nonempty, compact and convex subset of Euclidean space, and f : K)K be a correspondence. If f is nonempty- and convex-valued, and upper hemicon- tinuous, then the set of its xed points is nonempty and compact. The trick is contained in the following de nition: De nition 5 Fix a nite game G = (N;(Ai;ui)i2N). The mixed extension of G is the game = (N;( (Ai);Ui)i2N), where, for any collection ( i)i2N 2Qi2N (Ai), Ui( 1;:::; N) = X (ai)i2N2A Y i2N i(ai)ui(a1;:::;aN) For every i2N, denote by i Player i’s Nash best reply correspondence. The idea is to consider the modi ed game in which players have the physical possibility to randomize among their actions, in a stochastically independent fashion. I shall return to the interpretation of this assumption momentarily; formally, note that the set K = Qi2N (Ai), as a product of simplices, is a nonempty, compact, convex subset of Euclidean space, as required by Theorem 0.2. Moreover, de ne a correspondence f : K)K by f( 1;:::; N) =f( 0i)i2N :8i2N; 0i2 i ( i)g It is easy to see that f( ) is nonempty, convex-valued and uhc if i is. So, we need: Proposition 0.3 For any nite game G, the Nash best reply correspondence of its mixed extension is nonempty, convex-valued and upper hemicontinuous. Proof: Nonemptyness follows because the best-reply correspondence of the original nite game is nonempty (and (Ai) contains all degenerate mixed strategies.) Now note that i 2 i ( i) i i assigns positive probability only to actions that are best replies against the belief Qj6=i j (why?). This immediately implies convexity. To prove uhc, note that we can use the characterization in Theorem 0.1. Consider two convergent sequences ( n i)n 1 ! i and ( ni )n 1 ! i such that, for every n 1, ni 2 i ( n i. This means that, for every 0i2 (Ai), Ui( ni; n i) Ui( 0i; n i) Now note that, by de nition, the function Ui( ; ) is jointly continuous in its arguments. Thus, as n!1, Ui( ni; n i) !Ui( i; i and Ui( 0i; n i) !Ui( 0i; i). The result now follows. 4 Observe that i is not lhc in general. Matching Pennies provides an example (you should give the details). We are ready to state our main result today: Theorem 0.4 For any nite game G, its mixed extension has a Nash equilibrium. Interpretation There are two independent issues we need to discuss: the meaning of Nash equilibrium per se, e.g. regardless of the \trick" used to guarantee existence in nite games, and the meaning of randomization. Nash equilibrium For the purposes of this subsection, let us focus on De nition 2, so we need not worry about mixing. There are at least two main approaches to game theory. The eductive approach: we assume that players are rational (e.g. Bayesian rational) and capable of thinking strategically. That is, we assume that players think hard before playing a game, evaluating their options in light of conjectures about their opponents’ behavior. Solution concepts are characterized by assumptions about the speci c line of reasoning followed by the players. The learning approach: we assume that players interact several times, i.e. play the same game over and over. They may be assumed to be rational to di erent extents; the crucial idea is that their beliefs are \empirical", i.e. crucially based on their play experience. Solution concepts then re ect steady states of the ensuing dynamical process. As should be clear by now, the \informal equation" Rationality + Assumptions about Beliefs = Solution Concepts conveys the main message of the eductive approach. Let us rst evaluate Nash equilibrium form this particular viewpoint. Nash equilibrium is characterized by the assumption that players’ beliefs are correct: that is, every player believes that her opponents will choose precisely that action which, according to the solution concept, they will in fact choose. One must be very clear about this. Consider the simple game in Figure 1. 5 L R T 1,1 0,0 B 1,0 -1,2 Figure 1: Correct beliefs This game has a unique Nash equilibrium, (T,L). Suppose that we assume that: (1) Players are rational; (2.1) Player 1 expects Player 2 to choose L; and (2.2) Player 2 expects Player 1 to choose R. Are these assumptions su cient to conclude that Player 1 will choose T and Player 2 will choose L? The answer is no, because a rational Player 1 might equally well choose B if she thinks that Player 2 will choose L. Thus, \correct beliefs" must imply something more than this. We need to consider the following assumption: (2.1’) Player 1 expects Player 2 to play whatever action he actually chooses; (2.2’) Player 2 expects Player 1 to play whatever action she actually chooses. This will be crystal-clear when we develop a model where assumptions about beliefs can be formalized. However, the basic idea should still be easy to grasp: what is needed is a restriction that relates beliefs and actual behavior. The problem with this assumption is that, of course, it does not go much beyond the de nition of Nash equilibrium! Yet, it delivers the required result, for although (B,L) is consistent with assumptions (1), (2.1) and (2.2), it fails (2.2’): for Player 2 to choose L, it must be the case that he expects Player 1 to choose T with high enough probability, but in fact Player 1 chooses B with probability one. Again, these considerations will be clearer once we develop a model of interactive beliefs. By way of comparison, recall that the assumptions we used to justify (correlated) ra- tionalizability (following the eductive approach) were of the following form: (1) Players are rational; (2) Players believe that their opponents are rational; (3) Players believe that their opponents believe that their own opponents are rational; and so on. Note that assumptions (2), (3)... do not involve speci c actions (as our assumptions (2.1) and (2.2) above), and do not in any way refer to what players may actually do in a given \state of the world." Thus, these assumptions are truly decision-theoretical in nature; those required to moti- vate Nash equilibrium are somewhat of a hybrid (indeed, xpoint) nature. One could correctly argue, however, that the above point is only valid for equilibria in which players have multiple best-replies to their equilibrium beliefs; that is, for non-strict equilibria in game-theoretic parlance. One could then observe that in \generic" games (i.e. games with payo s in general position) all pure-action equilibria are strict. 6 This is a valid point. However, note that even generic games need not have pure-action equilibria (generic variants of Matching Pennies prove this point). And, even taking the mixed extension of a nite game seriously, no mixed-action equilibrium can be strict (why?). Hence, for games which admit equilibria only in their mixed representation, one really needs the full force of the non-decision-theoretic \correct beliefs" assumption. The learning approach, by and large, takes the point of view that players know how to best-respond to a belief, but it postulates that beliefs are based on the players’ experience from past strategic interactions. The simplest such model is that of ctitious play. Each player i2N is endowed with a \weighting function" wi : A i!f0;1;2:::g which counts how many times a certain action pro le was observed. Before playing the game, some arbitrary weights are assigned, and upon completing each play of the game, if a i2A i was observed, wi(a i) is increased by 1. Finally, at each stage players best-respond to the belief w i de ned by w i(a i) = wi(a i)P a0 i2A iwi(a i) i.e. they play some action in ri( w i). The attractiveness of this approach lies in the intuitive notion that perhaps learning might be the reason why beliefs are correct. That is, intuitively players might learn how to \coordinate" on some Nash equilibrium. Indeed, several results relate the steady states of this process, or the long-run frequencies, i.e. the long-run w i’s, to Nash equilibrium and other solution concepts. For instance, it can be shown that, in two-player games, if a steady state exists, it must be a strict Nash equilibrium (this is not hard to prove). Also, if the long-run frequencies converge, they represent equilibria of the mixed extension of the game under consideration. The above paragraphs are simply meant to convey the avor of the learning approach: I am certainly not doing any justice to the vast and insightful literature on the subject3. Scant as they are, however, the above remarks do illustrate at least one di culty in applying the ideas from the learning literature to justify Nash equilibrium: convergence to a steady state, or convergence of the long-run frequencies, is not guaranteed at all: it only occurs under appropriate conditions. Indeed, most of these conditions are either very restrictive, or su cient to enable a fully decision-theoretic eductive analysis, without invoking the full strength of the \correct beliefs" assumption. The recent learning literature uses this approach not to justify existing solution concepts, but to provide a foundation for new, interesting ones (e.g. Fudenberg and Levine’s self- con rming equilibrium) which typically involve departures from \correct beliefs." 3Fudenberg and Levine’s book is an excellent reference, if you are interested. 7 Thus, it seems that, if we wish to invoke the notion of Nash equilibrium to draw behavioral predictions, i.e. to say what players will in fact do, we are forced to accept the full force of the \correct beliefs" assumption. As I have observed, this assumption might be unpalatable, and does not add much to our understanding of the formal de nition. Mixed actions I will be more concise with respect to the possibility of randomization. There is no doubt that mixing was introduced merely as a matter of technical convenience. This is not to deny that, in many situations (e.g. the game of Rock, Scissors, Paper, or my own personal favorite, Matching Pennies), randomization is an appealing option. Rather, this is to say that, when we represent Matching Pennies as we conventionally do (each player has two actions, H and T), we are really writing down an incomplete repre- sentation of the actual situation. Perhaps I would not go so far as to say that players can randomize with any probability between H and T, but I would not feel bad about assuming that, for instance, they can ip a coin and choose an action based on the outcome of the coin toss.4 Thus, if we feel that randomization is an important strategic option, then perhaps it might be more appropriate to model it explicitly. An alternative exists, however. We can interpret mixed strategies as beliefs held by the players about each other. Under this interpretation, to say that ( 1; 2) is a Nash equilibrium is to say that 1, viewed as a belief held by Player 2 about Player 1, is a belief which satis es two consistency conditions: (1) Player 2 believes that Player 1 is rational (2) Player 2 believes that Player 1’s beliefs are given by 2 Similar considerations hold for 2, viewed as a belief held by Player 1 about Player 2. Again, the details will only be clear once we have a full-blown model of interactive beliefs (note that (2) is not an assumption we know how to formulate yet); however, observe that (1) and (2) are statements that have to do with beliefs, not with behavior. They are, so to speak, purely decision-theoretic statements|although they have no direct behavioral implication, and adding the assumption that players are indeed rational may lead to the di culties highlighted above with reference to the game in Figure 1. 4In practice, a player may physically generate a sequence of coin tosses prior to playing the game, then memorize it and use it to choose an action each time she has to play. 8 The bottom line is that mixed strategies, and indeed perhaps Nash equilibria in general, are best interpreted as representing \consistent beliefs." Upper and Lower Hemicontinuity of the Nash correspondence I conclude with a technical note. If we x the number of players and the size of each player’s strategy set, then we can identify a nite game with the collection of payo vectors|i.e. with a point u in Euclidean space. Thus, denote by N(u) the set of Nash equilibria of the nite game with corresponding to u. Formally, if M = Qi2IjAij, the space of games is just RI M, so N : RI M )Qi2I (Ai). It is fairly easy to see that N(u) is uhc. However, it is not lhc, as the game in Fig. 2 demonstrates. L R T 1,1 0,0 B 0,0 ;2 Figure 2: LHC fails at = 0. Let u 2 R2 4 denote the payo s in the game with parameter 2 R. It is easy to see that: For < 0, there is a unique NE, (1,1) = (T,L). For > 0, the NE are (1,1), (0,0) and (23; 1+ ). For = 0, the NE are (1,1) and (x;0) for any x 2 [0; 23]|this includes (0,0) and (23; 1+ ) = (23;0) It is easy to see that there is no violation of uhc if we consider payo sequences u n generated by any sequence n!0|this much we expected! However, there is a violation of lhc: any ( 1;0) with 1 2 (0; 23) is in N(u0), but it is impossible to select n2N(u n) so that n!( ;0). 9