Unformatted text preview:

Networks: Lecture 11IntroductionNash EquilibriumExtensive Form GamesApplications6.207/14.15: Networks Lecture 11: Introduction to Game Theory—3 Daron Acemoglu and Asu Ozdaglar MIT October 19, 2009 1Networks: Lecture 11 Introduction Outline Existence of Nash Equilibrium in Infinite Games Extensive Form and Dynamic Games Subgame Perfect Nash Equilibrium Applications Reading: Osborne, Chapters 5-6. 2123Networks: Lecture 11 Nash Equilibrium Existence of Equilibria for Infinite Games A similar theorem to Nash’s existence theorem applies for pure strategy existence in infinite games. Theorem (Debreu, Glicksberg, Fan) Consider an infinite strategic form game �I, (Si )i∈I , (ui )i∈I � such that for each i ∈ I Si is compact and convex; ui (si , s−i ) is continuous in s−i ; ui (si , s−i ) is continuous and concave in si [in fact quasi-concavity suffices]. Then a pure strategy Nash equilibrium exists. 3concave functionnot a concave functionNetworks: Lecture 11 Nash Equilibrium Definitions Suppose S is a convex set. Then a function f : S R is concave if→for any x, y ∈ S and any λ ∈ [0, 1], we have f (λx + (1 − λ)y) ≥ λf (x) + (1 − λ)f (y) . 4� � Networks: Lecture 11 Nash Equilibrium Proof Now define the best response correspondence for player i, Bi : S−i � Si , Bi (s−i ) = si� ∈ Si | ui (si�, s−i ) ≥ ui (si , s−i ) for all si ∈ Si . Thus restriction to pure strategies. Define the set of best response correspondences as B (s) = [Bi (s−i )]i∈I . and B : S � S. 512Networks: Lecture 11 Nash Equilibrium Proof (continued) We will again apply Kakutani’s theorem to the best response correspondence B : S � S by showing that B(s) satisfies the conditions of Kakutani’s theorem. S is compact, convex, and non-empty. By definition � S = Si i∈I since each Si is compact [convex, nonempty] and finite product of compact [convex, nonempty] sets is compact [convex, nonempty]. B(s) is non-empty. By definition, Bi (s−i ) = arg max ui (s, s−i ) s∈Si where Si is non-empty and compact, and ui is continuous in s by assumption. Then by Weirstrass’s theorem B(s) is non-empty. 6Networks: Lecture 11 Nash Equilibrium Proof (continued) 3. B(s) is a convex-valued correspondence. This follows from the fact that ui (si , s−i ) is concave [or quasi-concave] in si . Suppose not, then there exists some i and some s−i ∈ S−i such that Bi (s−i ) ∈ arg maxs∈Si ui (s, s−i ) is not convex. This implies that there exists si�, si�� ∈ Si such that si�, si�� ∈ Bi (s−i ) and λsi� + (1 − λ)si�� ∈/ Bi (s−i ). In other words, λui (si�, s−i ) + (1 − λ)ui (si��, s−i ) > ui (λsi� + (1 − λ) si��, s−i ). But this violates the concavity of ui (si , s−i ) in si [recall that for a concave function f (λx + (1 − λ)y) ≥ λf (x) + (1 − λ)f (y )]. Therefore B(s) is convex-valued. 4. The proof that B(s) has a closed graph is identical to the previous proof. 7Networks: Lecture 11 Nash Equilibrium Existence of Nash Equilibria Can we relax concavity? Example: Consider the game where two players pick a location s1, s2 ∈ R2 on the circle. The payoffs are u1(s1, s2) = −u2(s1, s2) = d(s1, s2), where d(s1, s2) denotes the Euclidean distance between s1, s2 ∈ R2 . No pure Nash equilibrium. However, it can be shown that the strategy profile where both mix uniformly on the circle is a mixed Nash equilibrium. 812Networks: Lecture 11 Nash Equilibrium A More Powerful Theorem Theorem (Glicksberg) Consider an infinite strategic form game �I, (Si )i∈I , (ui )i∈I �such that for each i ∈ I Si is nonempty and compact; ui (si , s−i ) is continuous in si and s−i . Then a mixed strategy Nash equilibrium exists. The proof of this theorem is harder and we will not discuss it. In fact, finding mixed strategies in continuous games is more challenging and is beyond the scope of this course. 9Networks: Lecture 11 Extensive Form Games Extensive Form Games Extensive-form games model multi-agent sequential decision making. For now, we will focus is on multi-stage games with observed actions. Extensive form represented by game trees. Additional component of the model, histories (i.e., sequences of action profiles). Extensive form games will be useful when we analyze dynamic games, in particular, to understand issues of cooperation and trust in groups. 10Networks: Lecture 11 Extensive Form Games Histories Let Hk denote the set of all possible stage-k histories Strategies are maps from all possible histories into actions: sik : Hk → Si Player 1CDEF GHPlayer 2(2,1) (3,0) (0,2) (1,3)Example: Player 1’s strategies: s1 : H0 = ∅ → S1; two possible strategies: C,D Player 2’s strategies: s2 : H1 = {C , D} → S2; four possible strategies. 11Networks: Lecture 11 Extensive Form Games Strategies in Extensive Form Games Consider the following two-stage extensive form version of matching pennies. Player 1HTHT HTPlayer 2(-1,1) (1,-1) (1,-1) (-1,1)How many strategies does player 2 have? 121234Networks: Lecture 11 Extensive Form Games Strategies in Extensive Form Games (continued) Recall: strategy should be a complete contingency plan. Therefore: player 2 has four strategies: heads following heads, heads following tails (HH,HT); heads following heads, tails following tails (HH, TT); tails following heads, tails following tails (TH, TT); tails following heads, heads following tails (TH, HT). 13Networks: Lecture 11 Extensive Form Games Strategies in Extensive Form Games (continued) Therefore, from the extensive form game we can go to the strategic form representation. For example: Player 1/Player 2 (HH, HT ) (HH, TT ) (TH, TT ) (TH, HT ) heads tails (−1, 1) (1, −1) (−1, 1) (−1, 1) (1, −1) (−1, 1) (1, −1) (1, −1) So what will happen in this game? 14Networks: Lecture 11 Extensive Form Games Strategies in Extensive Form Games (continued) Can we go from strategic form representation to an extensive form representation as well? To do this, we need to introduce information sets. If two nodes are in the same information set, then the player making a decision at that point cannot tell them apart. The following two extensive form games are representations of the simultaneous-move matching pennies. These are imperfect information games. Note: For consistency, first number is still player 1’s payoff. Player 1Player 2HTHT


View Full Document

MIT 6 207 - Introduction to Game Theory

Download Introduction to Game Theory
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Introduction to Game Theory and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Introduction to Game Theory 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?