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