Eco514--Game Theory Lecture 3: Nash equilibrium Marciano siniscalchi September 23. 1999 Introduction Nash equilibrium has undoubtedly proved to be the most influential 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 quilibrium. 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 Definitions Fix a game G=(N,(Ai, Ii, uiieN), where each(Ai, Ii) is a compact metrizable space(as usual, you can think of finite action spaces unless explicitly noted) and every u; is bounded and continuous Recall that we denote by ri: A(A-i, B(A-1))=A: Player i's best-reply correspondence, which associates with each belief (probability distribution on A-i, endowed with the borel gma-algebra) the set of The definition of Nash equilibrium involves best replies to beliefs concentrated on a single action profile. If the game is finite, these beliefs assign probability one to the specified profile, and probability zero to any other belief; if the game is infinite, these beliefs are Dirichlet measures: that is, for any a_i E A-i, we define Sa-i E A(A-i, B(T-i) by letting d(a-i(e)=l iff a-i E E for any E E B(T-i. All you need to know about this is that nilai
Eco514—Game Theory Lecture 3: Nash Equilibrium Marciano Siniscalchi September 23, 1999 Introduction Nash equilibrium has undoubtedly proved to be the most influential 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. Definitions Fix a game G = (N,(Ai , Ti , ui)i∈N ), where each (Ai , Ti) is a compact metrizable space (as usual, you can think of finite 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 definition of Nash equilibrium involves best replies to beliefs concentrated on a single action profile. If the game is finite, these beliefs assign probability one to the specified profile, and probability zero to any other belief; if the game is infinite, these beliefs are Dirichlet measures: that is, for any a−i ∈ A−i , we define δa−i ∈ ∆(A−i , B(T−i)) by letting δ(a−i)(E) = 1 iff a−i ∈ E for any E ∈ B(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 profile Definition 1 Fix a game G=(N, (Ai, Ti, uiieN). For every i E N, Player i's Nash best reply correspondence Pi: A-i= Ai is defined by p(a-)=r(a-)a-a∈A-a That is, Pi(a-i) is the set of Player i's best replies to beliefs concentrated on a_i. Note that this corresponds to OR'sBi (" I wish to reserve the letter B; for something else We are ready for the definition of Nash equilibrium: Definition 2 Fix a game G=(N, (Ai, Ti, lilieN). The profile of actions(ai)ieN is a Nash equilibrium of g iff a;∈p(a-1) for all i∈N The literal interpretation is clear: in a Nash equilibrium, the action of each player is best reply to the(belief concentrated on the) actions of her opponents Existence Note that the above definition applies to both finite and infinite games. Moreover, as stated, it does not guarantee existence in finite games. For example, Matching Pennies(see Lecture 1)does not have an equilibrium according to the above definition At this juncture the theory treats finite and infinite games differently. This might seem odd, and to some extent it so appears to this writer, too. However, the theory has developed as follows: for finite action sets, one employs a"trick"which(in some sense) guarantees existence in arbitrary games: for infinite games, theorists have developed conditions on the action spaces and payoff functions under which Nash equilibria exist. There is no(known) trick "which guarantees existence in arbitrary infinite games I shall focus on existence(with the "trick?")in finite games, although this requires a brief detour on infinite games and some ancillary notions. We shall only need to consider very special, well-behaved infinite 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, Iy) are topological spaces, is continuous iff f-(V)=c: f()EV E Tx whenever V Ty 2
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 profile: Definition 1 Fix a game G = (N,(Ai , Ti , ui)i∈N ). For every i ∈ N, Player i’s Nash bestreply correspondence ρi : A−i ⇒ Ai is defined by ρi(a−i) = ri(δa−i ) ∀a−i ∈ A−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 definition of Nash equilibrium: Definition 2 Fix a game G = (N,(Ai , Ti , ui)i∈N ). The profile of actions (ai)i∈N is a Nash equilibrium of G iff ai ∈ ρi(a−i) for all i ∈ N. 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 definition applies to both finite and infinite games. Moreover, as stated, it does not guarantee existence in finite games. For example, Matching Pennies (see Lecture 1) does not have an equilibrium according to the above definition. At this juncture, the theory treats finite and infinite games differently. This might seem odd, and to some extent it so appears to this writer, too. However, the theory has developed as follows: for finite action sets, one employs a “trick” which (in some sense) guarantees existence in arbitrary games; for infinite games, theorists have developed conditions on the action spaces and payoff functions under which Nash equilibria exist. There is no (known) “trick” which guarantees existence in arbitrary infinite games. I shall focus on existence (with the “trick”) in finite games, although this requires a brief detour on infinite games and some ancillary notions. We shall only need to consider very special, well-behaved infinite 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 iff f −1 (V ) = {x : f(x) ∈ V } ∈ TX whenever V ∈ TY . 2
However, extending this definition to correspondences is problematic, because the mean- ing of "f-(V) "is ambiguous. The following definition presents two alternatives Definition 3 Let(X, Ix) and(Y, Ty)be topological spaces, and consider a correspondence f: X=Y. For any V C Y, the upper inverse of f at V is f(v)=far: f(a)CV; the lower inverse of f at V is f(V)={x:f(x)∩V≠0} Clearly, fu(v)cf(v), and the two definitions coincide for singleton-valued dences. i.e. for functions Each notion gives rise to a corresponding definition of continuity Definition 4 Let(X, Tx) and(Y, Iy) be topological spaces, and consider a correspondence f: X>Y. Then f is upper hemicontinuous(uhc)iff, for every V E Ty, fu(V)EIx; f is lower hemicontinuous(lhc)iff, for every V E Ty, f(V)ETx; f is continuous iff it is both uhc and lhc Definition 4 highlights the connection with the notion of continuity for functions, but is somewhat hard to apply. However, the following characterization is useful Theorem 0.1 Let(X, Ix) be metrizable, and(Y, Ty) be compact and metrizable. Then a correspondence f: X=Yis (1)upper hemicontinuous iff, for every pair of convergent sequences aln>0 x in X and{y"}n≥0→ y in Y such that y∈f(x),y∈f(x); (2) lower hemicontinuous iff, for any sequence aIn>0-a in X, and for every E f(a there exists a subsequence ank k>o in X and a sequence y"k ]k>o in Y such that ynk E f(a"k for all k≥0, and ynk→y For infinite games, under our assumptions, the Nash best-reply correspondence is upper hemicontinuous as a consequence of the Maximum Theorem. However, in order to define Nash equilibrium for finite 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 B]For the more mathematically inclined, the domain of the correspondence in the next theorem need only first-countable 2For the more mathematically inclined, the theorem actually applies to locally convex hausdorff topo- logical vector spaces, such as e.g. the set of real-valued functions on a nonempty set X(endowed with the 3
However, extending this definition to correspondences is problematic, because the meaning of “f −1 (V )” is ambiguous. The following definition presents two alternatives. Definition 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 f u (V ) = {x : f(x) ⊂ V }; the lower inverse of f at V is f ` (V ) = {x : f(x) ∩ V 6= ∅}. Clearly, f u (V ) ⊂ f ` (V ), and the two definitions coincide for singleton-valued correspondences, i.e. for functions. Each notion gives rise to a corresponding definition of continuity: Definition 4 Let (X, TX) and (Y, TY ) be topological spaces, and consider a correspondence f : X ⇒ Y . Then f is upper hemicontinuous (uhc) iff, for every V ∈ TY , f u (V ) ∈ TX; f is lower hemicontinuous (lhc) iff, for every V ∈ TY , f ` (V ) ∈ TX; f is continuous iff it is both uhc and lhc. Definition 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 iff, for every pair of convergent sequences {x n}n≥0 → x in X and {y n}n≥0 → y in Y such that y n ∈ f(x n ), y ∈ f(x); (2) lower hemicontinuous iff, for any sequence {x n}n≥0 → x in X, and for every y ∈ f(x), there exists a subsequence {x nk }k≥0 in X and a sequence {y nk }k≥0 in Y such that y nk ∈ f(x nk ) for all k ≥ 0, and y nk → y. For infinite games, under our assumptions, the Nash best-reply correspondence is upper hemicontinuous as a consequence of the Maximum Theorem. However, in order to define Nash equilibrium for finite 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 first-countable. 2For the more mathematically inclined, the theorem actually applies to locally convex Hausdorff topological 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 fixed points is nonempty and compact The trick is contained in the following definition: Definition 5 Fix a finite game G=(N, (Ai, ui)ieN). The mixed extension of G is the game r=(N,(△(A),Ul)ieN), where, for any collection(a)ieN∈IleN△(A), U(a1…,aN)=∑Ia(a)(a1,,ay) (a)ieN∈AieN For every i N, denote by pi Player is Nash best reply correspondence The idea is to consider the modified game in which players have the physical possibility te 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= IleN A(Ai) as a product of simplices, is a nonempty, compact, convex subset of Euclidean space, as required by Theorem 0. 2. Moreover, define a correspondence f: K= K by f(a1,,aN)={a)ieN:W∈N,a2∈(a-1)} It is easy to see that f( is nonempty, convex-valued and uhc if P is. So, we need Proposition 0. 3 For any finite game G, the Nash best reply correspondence of its mixed extension T is nonempty, convex-valued and upper hemicontinuous Proof: Nonemptyness follows because the best-reply correspondence of the original finite game is nonempty(and A(Ai) contains all degenerate mixed strategies. Now note that ai E P(a-i iff ai assigns positive probability only to actions that are best replies against the belief liti a,(why? ) This immediately implies convexity To prove uhe, note that we can use the characterization in Theorem 0. 1. Consider two convergent sequences(ai)n>1 -a-i and(ai)>1 -a; such that, for every n a∈n(an1, This means that, for every a∈△(A) U(a,a2)≥U(a2,a2) Now note that, by definition, the function U; ( ) is jointly continuous in its arguments Thus,asn→∞,Ul(a2,a2)→Ul(a,a- and vi(a,a2)→Ul(a,a-). The result now follows.■
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 hemicontinuous, then the set of its fixed points is nonempty and compact. The trick is contained in the following definition: Definition 5 Fix a finite game G = (N,(Ai , ui)i∈N ). The mixed extension of G is the game Γ = (N,(∆(Ai), Ui)i∈N ), where, for any collection (αi)i∈N ∈ Q i∈N ∆(Ai), Ui(α1, . . . , αN ) = X (ai)i∈N ∈A Y i∈N αi(ai)ui(a1, . . . , aN ) For every i ∈ N, denote by ρ Γ i Player i’s Nash best reply correspondence. The idea is to consider the modified 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 = Q i∈N ∆(Ai), as a product of simplices, is a nonempty, compact, convex subset of Euclidean space, as required by Theorem 0.2. Moreover, define a correspondence f : K ⇒ K by f(α1, . . . , αN ) = {(α 0 i )i∈N : ∀i ∈ N, α0 i ∈ ρ Γ i (α−i)} It is easy to see that f(·) is nonempty, convex-valued and uhc if ρ Γ i is. So, we need: Proposition 0.3 For any finite 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 finite game is nonempty (and ∆(Ai) contains all degenerate mixed strategies.) Now note that αi ∈ ρ Γ i (α−i) iff αi assigns positive probability only to actions that are best replies against the belief Q j6=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 (α n i )n≥1 → αi such that, for every n ≥ 1, α n i ∈ ρ Γ i (α n −i . This means that, for every α 0 i ∈ ∆(Ai), Ui(α n i , αn −i ) ≥ Ui(α 0 i , αn −i ) Now note that, by definition, the function Ui(·, ·) is jointly continuous in its arguments. Thus, as n → ∞, Ui(α n i , αn −i ) → Ui(αi , α−i and Ui(α 0 i , αn −i ) → Ui(α 0 i , α−i). The result now follows. 4
Observe that pi 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 finite 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 finite games, and th he meanl of randomization Nash equilibrium For the purposes of this subsection, let us focus on Definition 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 ents behavior. Solution concepts are characterized by assumptions about the 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 different extents the crucial idea is that their beliefs are"empirical", i.e. crucially based on their play experience. Solution concepts then reflect 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 first evaluate Nash equilibrium form this particular viewpoint ash 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
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 finite 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 finite games, and the meaning of randomization. Nash equilibrium For the purposes of this subsection, let us focus on Definition 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 specific 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 different extents; the crucial idea is that their beliefs are “empirical”, i.e. crucially based on their play experience. Solution concepts then reflect 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 first 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
R 1,10.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 sufficient 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 hat 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 I to play whatever action she actually chooses This will be crystal-clear when we develop a model where assumptions about beliefs 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 definition 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 specific 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- ate Nash equilibrium are somewhat of a hybrid (indeed, fixpoint )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 payoffs in general position) all pure-action equilibria are strict
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 sufficient 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 definition 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) rationalizability (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 specific 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 motivate Nash equilibrium are somewhat of a hybrid (indeed, fixpoint) 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 payoffs 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 finite 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 st-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 fictitious play. Each player i E N is endowed with a weighting function"w'i: A-i-10, 1, 2... which counts how many times a certain action profile was observed. Before playing the game, some arbitrary weights are assigned, and upon completing each play of the game, if a-i E A-i was observed, wi(a-i) is increased by 1. Finally, at each stage players best-respond to the belief a i defined by -i)= i.e. they play some action in riai 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 ais, 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 flavor of the learning approach: I am certainly not doing any justice to the vast and insightful literature on the subject Scant as they are, however, the above remarks do illustrate at least one difficulty 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 sufficient 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- confirming equilibrium) which typically involve departures from "correct beliefs 3Fudenberg and Levine's book is an excellent reference, if you are interested
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 finite 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 fictitious play. Each player i ∈ N is endowed with a “weighting function” wi : A−i → {0, 1, 2 . . .} which counts how many times a certain action profile was observed. Before playing the game, some arbitrary weights are assigned, and upon completing each play of the game, if a−i ∈ A−i was observed, wi(a−i) is increased by 1. Finally, at each stage players best-respond to the belief α w −i defined by α w −i (a−i) = wi(a−i) P a 0 −i∈A−i wi(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 flavor 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 difficulty 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 sufficient 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 selfconfirming 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 definition 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 convenie 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 Hip a coin and choose an action based on the outcome of the coin toss Thus, if we feel that randomization is an important strategic option, then perhaps it ight 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(a1, a2) is a Nash equilibrium is to say that a1 ewed as a belief held by Player 2 about Player 1, is a belief which satisfies two consistency conditions Player 2 believes that Player 1 is rational (2)Player 2 believes that Player 1s beliefs are given by 2 Similar considerations hold for a2, 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 difficulties highlighted above with reference to the game in Figure In 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
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 definition. 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 representation 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 flip 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 satisfies 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 difficulties highlighted above with reference to the game in Figure 1. 4 In 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 fix the number of players and the size of each players strategy set, then we can identify a finite game with the collection of payoff vectorse with a point u in Euclidean space. Thus, denote by N(u) the set of Nash equilibria of the finite game with corresponding to u. Formally, if M=lier Ail, the space of games is just R1M,soN:RM→Iler△A1) 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 ,10,0 Figure 2 LHC fails at A=0 Let ux E R2- denote the payoffs in the game with parameter A E R. It is easy to see that For A0, the NE are(1, 1),(0,0)and (2, 1) For A=0, the NE are(1, 1)and(, 0) for any T E [0, 2]-this includes(0,0)and (3,1)=(3,0) It is easy to see that there is no violation of uhc if we consider payoff sequences uAn generated by any sequence A-0-this much we expected However, there is a violation of lhc: any(a1,0) with an E(0, 2)is in N(uo), but it is mpossible to select a∈N(uxn) so that a→(a,0)
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 fix the number of players and the size of each player’s strategy set, then we can identify a finite game with the collection of payoff vectors—i.e. with a point u in Euclidean space. Thus, denote by N(u) the set of Nash equilibria of the finite game with corresponding to u. Formally, if M = Q i∈I |Ai |, the space of games is just RI·M, so N : RI·M ⇒ Q i∈I ∆(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λ ∈ R2·4 denote the payoffs in the game with parameter λ ∈ R. It is easy to see that: • For λ 0, the NE are (1,1), (0,0) and ( 2 3 , λ 1+λ ). • For λ = 0, the NE are (1,1) and (x, 0) for any x ∈ [0, 2 3 ]—this includes (0,0) and ( 2 3 , λ 1+λ ) = ( 2 3 , 0) It is easy to see that there is no violation of uhc if we consider payoff 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 ∈ (0, 2 3 ) is in N(u0), but it is impossible to select α n ∈ N(uλn ) so that α n → (α, 0). 9
