Lecture 6: Continuous and Discontinuous Games

6.254: Game Theory with Engineering Applications February 23, 2010 Lecture 6: Continuous and Discontinuous Games Lecturer: Asu Ozdaglar 1 Introduction In this lecture, we will focus on: • Existence of a mixed strategy Nash equilibrium for continuous games (Glicksberg’s theorem). • Finding mixed strategy Nash equilibria in games with infinite strategy sets. • Uniqueness of a pure strategy Nash equilibrium for continuous games. 2 Continuous Games In this section, we consider games in which players may have infinitely many pure strategies. In particular, we want to include the possibility that the pure strategy set of a player may be a bounded interval on the real line, such as [0,1]. We will follow the development of Myerson [3], pp. 140-148. Definition 1 A continuous game is a game �I, (Si ), (ui )� where I is a finite set, the Si are nonempty compact metric spaces, and the ui : S �→ R are continuous functions. A compact metric space is a general mathematical structure for representing infinite sets that can be well approximated by large finite sets. One important fact is that, in a compact metric space, any infinite sequence has a convergent subsequence. Any closed bounded subset of a finite-dimensional Euclidean space is an example of a compact metric space. More specifically, any closed bounded interval of the real line is an example of a compact metric space, where the distance between two points x and y is given by |x − y|. In 6-1 our treatment, we will not need to refer to any examples more complicated than these (see the Appendix for basic definitions of a metric space and convergence notions for probability measures). We next state the analogue of Nash’s Theorem for continuous games. Theorem 1 (Glicksberg) Every continuous game has a mixed strategy Nash equilibrium. With continuous strategy spaces, the space of mixed strategies Σ is infinite-dimensional, therefore we need a more powerful fixed point theorem than the version of Kakutani we have used before. Here we adopt an alternative approach to prove Glicksberg’s Theorem, which can be summarized as follows: • We approximate the original game with a sequence of finite games, which correspond to successively finer discretization of the original game. • We use Nash’s Theorem to produce an equilibrium for each approximation. • We use the weak topology and the continuity assumptions to show that these converge to an equilibrium of the original game. 2.1 Closeness of Two Games and �-Equilibrium Let u = (u1 , . . . , uI ) and ũ = (ũ1 , . . . , ũI ) be two profiles of utility functions defined on S such that for each i ∈ I, the functions ui : S �→ R and ũi : S �→ R are bounded measurable functions. We may define the distance between the utility function profiles u and ũ as max sup |ui (s) − ũi (s)|. i∈I s∈S Consider two strategic form games defined by two profiles of utility functions: G = �I, (Si ), (ui )�, G̃ = �I, (Si ), (ũi )�. If σ is a mixed strategy Nash equilibrium of G, then σ need not be a mixed strategy Nash equilibrium of G̃. Even if u and ũ are very close, the equilibria of G and G̃ may be far apart. 6-2 For example, assume there is only one player, S1 = [0, 1], u1 (s1 ) = �s1 , and ũ1 (s1 ) = −�s1 , where � > 0 is a sufficiently small scalar. The unique equilibrium of G is s∗1 = 1, and the unique equilibrium of G̃ is s∗1 = 0, even if the distance between u and ũ is only 2�. However, if u and ũ are very close, there is a sense in which the equilibria of G are “almost” equilibria of G̃. Definition 2 (�-equilibrium) Given � ≥ 0, a mixed strategy σ ∈ Σ is called an �-equilibrium if for all i ∈ I and si ∈ Si , ui (si , σ−i ) ≤ ui (σi , σ−i ) + �. Obviously, when � = 0, an �-equilibrium is a Nash equilibrium in the usual sense. The following result shows that such �-equilibria have a continuity property across games. Proposition 1 Let G be a continuous game. Assume that σ k → σ, �k → �, and for each k, σ k is an �k -equilibrium of G. Then σ is an �-equilibrium of G. Proof: For all i ∈ I, and all si ∈ Si , we have k ui (si , σ−i ) ≤ ui (σ k ) + �k , Taking the limit as k → ∞ in the preceding relation, and using the continuity of the utility functions together with the convergence of probability distributions under weak topology [see Eq. (11)], we obtain, ui (si , σ−i ) ≤ ui (σ) + �, establishing the result. � We next define formally the closeness of two strategic form games. Definition 3 Let G and G� be two strategic form games with G� = �I, (Si ), (u�i )�. G = �I, (Si ), (ui )�, Assume that the utility functions ui and u�i are measurable and bounded. Then G� is an α−approximation to G if for all i ∈ I and s ∈ S, we have |ui (s) − u�i (s)| ≤ α. 6-3 We next relate the �−equilibria of close games. Proposition 2 If G� is an α-approximation to G and σ is an �-equilibrium of G� , then σ is an (� + 2α)-equilibrium of G. Proof: For all i ∈ I and all si ∈ Si , we have ui (si , σ−i ) − ui (σ) = ui (si , σ−i ) − u�i (si , σ−i ) + u�i (si , σ−i ) − u�i (σ) + u�i (σ) − ui (σ) ≤ � + 2α. � The next proposition shows that we can approximate a continuous game with an essen­ tially finite game to an arbitrary degree of accuracy. Proposition 3 For any continuous game G and any α > 0, there exists an “essentially finite” game which is an α-approximation to G. Proof: Since S is a compact metric space, the utility functions ui are uniformly continuous, i.e., for all α > 0, there exists some � > 0 such that ui (s) − ui (t) ≤ α, for all d(s, t) ≤ �. Since Si is a compact metric space, it can be covered with finitely many open balls Uij , each with radius less than �. Assume without loss of generality that these balls are disjoint and nonempty. Choose an sji ∈ Uij for each i, j. Define the “essentially finite” game G� with the utility functions u�i defined as u�i (s) = ui (sj1 , . . . , sjI ), j ∀s∈U = I � k=1 Then for all s ∈ S and all i ∈ I, we have |u�i (s) − ui (s)| ≤ α, since d(s, sj ) ≤ � for all j, implying the desired result. 6-4 � Ukj . 2.2 Proof of Glicksberg’s Theorem We now return to the proof of Glicksberg’s Theorem. Let {αk } be a scalar sequence with αk ↓ 0. • For each αk , there exists an “essentially finite” αk -approximation Gk of G by Proposi­ tion 3. • Since Gk is “essentially finite” for each k, it follows using Nash’s Theorem that it has a 0-equilibrium, which we denote by σ k . • Then, by Proposition 2, σ k is a 2αk -equilibrium of G. • Since Σ is compact, {σ k } has a convergent subsequence. Without loss of generality, we assume that σ k → σ. • Since 2αk → 0, σ k → σ, by Proposition 1, it follows that σ is a 0-equilibrium of G. 3 Discontinuous Games There are many games in which the utility functions are not continuous (e.g. price competi­ tion models, congestion-competition models). For such games existence of a mixed strategy equilibrium can be established under some assumptions by using an existence result by Das­ gupta and Maskin [1]-[2]. For more on this topic, please refer to Chapters 12.2 and 12.3 of Fudenberg and Tirole. In the following examples, we consider games with discontinuous utility functions and find their mixed strategy equilibria. Example 1 (Bertrand Competition with Capacity Constraints): Consider two firms that charge prices p1 , p2 ∈ [0, 1] per unit of the same good. Assume that there is unit demand and all customers choose the firm with the lower price. If both firms charge the same price, each firm gets half the demand. All demand has to be supplied. The payoff functions of each firm is the profit they make (we assume for simplicity that cost of supplying the good is equal to 0 for both firms). 6-5 (a) Find all pure strategy Nash equilibria. We check all possible candidates to see if there is any profitable unilateral deviation: – p1 = p2 > 0: each of the firms has an incentive to reduce their price to capture the whole demand and increase profits. – p1 < p2 : Firm 1 has an incentive to slightly increase his price. – p1 = p2 = 0: Neither firm can increase profits by changing its price unilaterally. Hence (p1 , p2 ) = (0, 0) is the unique pure strategy Nash equilibrium. (b) Assume now that each firm has a capacity constraint of 2/3 units of demand (since all demand has to be supplied, this implies that when p1 < p2 , firm 2 gets 1/3 units of demand). Show that there does not exist a pure strategy Nash equilibrium. Find a mixed strategy Nash equilibrium. It is easy to see in this case that the pure strategy profile (p1 , p2 ) = (0, 0) is no longer a pure strategy Nash equilibrium: either firm can increase his price and still have 1/3 units of demand due to the capacity constraint on the other firm, thus making positive profits. It can be established using Dasgupta-Maskin result that there exists a mixed strategy Nash equilibrium. Let us next proceed to find a mixed strategy Nash equilibrium. We focus on symmetric Nash equilibria, i.e., both firms use the same mixed strategy. We use the cumulative distribution function F (·) to represent the mixed strategy used by either firm. It can be seen that the expected payoff of player 1, when he chooses p1 and firm 2 uses the mixed strategy F (·), is given by u1 (p1 , F (·)) = F (p1 ) p1 2 + (1 − F (p1 )) p1 . 3 3 Using the fact that each action in the support of a mixed strategy must yield the same payoff to a player at the equilibrium, we obtain for all p in the support of F (·), p 2 −F (p) + p = k, 3 3 6-6 for some k ≥ 0. From this we obtain: F (p) = 2 − 3k . p Note next that the upper support of the mixed strategy must be at p = 1, which implies that F (1) = 1. Combining with the preceding, we obtain ⎧ if 0 ≤ p ≤ 12 , ⎨ 0, 2 − p1 , if 12 ≤ p ≤ 1, F (p) = ⎩ 1, if p ≥ 1. Example 2 (Hotelling Competition): Each of n candidates chooses a position to take on the real line in the interval [0,1]. There is a continuum of citizens, whose favorite positions are uniformly distributed between [0,1]. A candidate attracts votes of citizens whose favorite positions are closer to his position than to the position of any other candidate; if k candidates choose the same position, then each receives the fraction 1/k of the votes that the position attracts. The payoff of each candidate is his vote share. (a) Find all pure strategy Nash equilibria when n = 2. (b) Show that there does not exist a pure strategy Nash equilibrium when n = 3.Find a mixed strategy Nash equilibrium. 4 Uniqueness of a Pure Strategy Equilibrium in Con­ tinuous Games We have shown in the previous lecture the following result on the existence of a pure strategy Nash equilibrium: Given a strategic form game �I, (Si ), (ui )�, assume that the strategy sets Si are nonempty, convex, and compact sets, ui (s) is continuous in s, and ui (si , s−i ) is quasiconcave in si . Then the game �I, (Si ), (ui )� has a pure strategy Nash equilibrium. Then next example shows that even under strict convexity assumptions, there may be infinitely many pure strategy Nash equilibria. Example 3: Consider a game with 2 players, Si = [0, 1] for i = 1, 2, and the payoffs are given by u1 (s1 , s2 ) = s1 s2 − 6-7 s21 , 2 s22 . 2 Note that ui (s1 , s2 ) is strictly concave in si . It can be seen in this example that the best u2 (s1 , s2 ) = s1 s2 − response correspondences (which are unique-valued) are given by B1 (s2 ) = s2 , B2 (s1 ) = s1 . Plotting the best response curves shows that any pure strategy profile (s1 , s2 ) = (x, x) for x ∈ [0, 1] is a pure strategy Nash equilibrium. We will next establish conditions that guarantee that a strategic form game has a unique pure strategy Nash equilibrium. We will follow the development of the classical paper by Rosen [4]. We first provide some notation and standard results from nonlinear optimization. Optimization terminology and background: Given a scalar-valued function f : Rn �→ R, we use the notation �f (x) to denote the gradient vector of f at point x, i.e., � ∂f (x) ∂f (x) �f (x) = ,..., ∂x1 ∂xn �T , (recall our convention that all vectors are column vectors). Given a scalar-valued function � u : Ii=1 Rmi �→ R, we use the notation �i u(x) to denote the gradient vector of u with respect to xi at point x, i.e., � ∂u(x) ∂u(x) �i u(x) = ,..., 1 i ∂xi ∂xm i �T . (1) We next state necessary conditions for the optimality of a feasible solution of a non­ linear optimization problem. These conditions are referred to as the Karush-Kuhn-Tucker conditions in the optimization theory literature. Theorem 2 (Karush-Kuhn-Tucker conditions) Let x∗ be an optimal solution of the optimization problem maximize f (x) subject to gj (x) ≥ 0, 6-8 j = 1, . . . , r, where the cost function f : Rn �→ R and the constraint functions gj : Rn �→ R are continuously differentiable. Denote the set of active constraints at x∗ as A(x∗ ) = {j = 1, . . . , r | gj (x∗ ) = 0}. Assume that the active constraint gradients, �gj (x∗ ), j ∈ A(x∗ ), are linearly independent vectors. Then, there exists a nonnegative vector λ∗ ∈ Rr (Lagrange multiplier vector) such that �f (x∗ ) + r � λ∗j �gj (x∗ ) = 0, j=1 λ∗j gj (x∗ ) = 0, ∀ j = 1, . . . , r. (2) You can view the preceding theorem as a generalization of the Lagrange multiplier the­ orem you might have seen in Calculus for equality constrained optimization problems to inequality constrained optimization problems. The condition that the active constraint gra­ dients, �gj (x∗ ), j ∈ A(x∗ ), are linearly independent vectors is a regularity condition that eliminates “degenerate” cases where there may not exist Lagrange multipliers. These type of conditions are referred to as constraint qualifications. You don’t need to worry about these conditions for this class. The condition in Eq. (2) implies that if λ∗j > 0, then gj (x∗ ) = 0, and if gj (x∗ ) > 0, then λ∗j = 0. It is therefore referred to as the complementary slackness condition and captures loosely the intuitive idea that a multiplier is used only when the constraint is active and the problem is locally unconstrained with respect to the inactive constraints. For convex optimization problems (i.e., minimizing a convex function over a convex con­ straint set, or maximizing a concave function over a convex constraint set), we can provide necessary and sufficient conditions for the optimality of a feasible solution: Theorem 3 Consider the optimization problem maximize f (x) subject to gj (x) ≥ 0, j = 1, . . . , r, where the cost function f : Rn �→ R and the constraint functions gj : Rn �→ R are concave functions. Assume also that there exists some x̄ such that gj (x̄) > 0 for all j = 1, . . . , r. Then 6-9 a vector x∗ ∈ Rn is an optimal solution of the preceding problem if and only if gj (x∗ ) ≥ 0 for all j = 1, . . . , r, and there exists a nonnegative vector λ∗ ∈ Rr (Lagrange multiplier vector) such that ∗ �f (x ) + r � λ∗j �gj (x∗ ) = 0, j=1 λ∗j gj (x∗ ) ∀ j = 1, . . . , r. = 0, Note that the condition that there exists some x̄ such that gj (x̄) > 0 for all j = 1, . . . , r is a constraint qualification (referred to as the Slater’s constraint qualification) that is suitable for convex optimization problems. We now return to the analysis of the uniqueness of a pure strategy equilibrium in strategic form games. In order to discuss the uniqueness of an equilibrium, we provide a more explicit description of the strategy sets of the players. In particular, we assume that for player i ∈ I, the strategy set Si is given by Si = {xi ∈ Rmi | hi (xi ) ≥ 0}, (3) where hi : Rmi �→ R is a concave function. Since hi is concave, it follows that the set Si is � a convex set (check as an exercise!). Therefore the set of strategy profiles S = Ii=1 Si ⊂ �I mi i=1 R , being a Cartesian product of convex sets, is a convex set. The following analysis can be extended to the case where Si is represented by finitely many concave inequality constraints, but we do not do so here for clarity of exposition. � Given these strategy sets, a vector x∗ ∈ Ii=1 Rmi is a pure strategy Nash equilibrium if and only if for all i ∈ I, x∗i is an optimal solution of the optimization problem maximizeyi ∈Rmi ui (yi , x∗−i ) subject to hi (yi ) ≥ 0. (4) In the following, we use the notation �u(x) to denote �u(x) = [�1 u1 (x), . . . , �I uI (x)]T , 6-10 (5) [see Eq. (1)]. We next introduce the key condition for uniqueness of a pure strategy Nash equilibrium. Definition 4 We say that the payoff functions (u1 , . . . , uI ) are diagonally strictly concave for x ∈ S, if for every x∗ , x̄ ∈ S, we have (x̄ − x∗ )T �u(x∗ ) + (x∗ − x̄)T �u(x̄) > 0. Theorem 4 Consider a strategic form game �I, (Si ), (ui )�. For all i ∈ I, assume that the strategy sets Si are given by Eq. (3), where hi is a concave function, and there exists some x̃i ∈ Rmi such that hi (x̃i ) > 0. Assume also that the payoff functions (u1 , . . . , uI ) are diagonally strictly concave for x ∈ S. Then the game has a unique pure strategy Nash equilibrium. Proof: Assume that there are two distinct pure strategy Nash equilibria. Since for each i ∈ I, both x∗i and x̄i must be an optimal solution for an optimization problem of the form (4), Theorem 3 implies the existence of nonnegative vectors λ∗ = [λ∗1 , . . . , λ∗I ]T and λ̄ = [λ̄1 , . . . , λ̄I ]T such that for all i ∈ I, we have �i ui (x∗ ) + λ∗i �hi (x∗i ) = 0, (6) λ∗i hi (x∗i ) = 0, (7) �i ui (x̄) + λ̄i �hi (x̄i ) = 0, (8) λ̄i hi (x̄i ) = 0. (9) and Multiplying Eqs. (6) and (8) by (x̄i − x∗i )T and (x∗i − x̄i )T respectively, and adding over all i ∈ I, we obtain 0 = (x̄ − x∗ )T �u(x∗ ) + (x∗ − x̄)T �u(x̄) � � + λ∗i �hi (x∗i )T (x̄i − x∗i ) + λ̄i �hi (x̄i )T (xi∗ − x̄i ) i∈I > � i∈I λ∗i �hi (x∗i )T (x̄i i∈I − x∗i ) + � i∈I 6-11 λ̄i �hi (x̄i )T (x∗i − x̄i ), (10) where to get the strict inequality, we used the assumption that the payoff functions are diagonally strictly concave for x ∈ S. Since the hi are concave functions, we have hi (x∗i ) + �hi (x∗i )T (x̄i − x∗i ) ≥ hi (x̄i ). Using the preceding together with λ∗i > 0, we obtain for all i, λ∗i �hi (x∗i )T (x̄i − x∗i ) ≥ λ∗i (hi (x̄i ) − hi (x∗i )) = λ∗i hi (x̄i ) ≥ 0, where to get the equality we used Eq. (7), and to get the last inequality, we used the facts λ∗i > 0 and hi (x̄i ) ≥ 0. Similarly, we have λ̄i �hi (x̄i )T (x∗i − x̄i ) ≥ 0. Combining the preceding two relations with the relation in (10) yields a contradiction, thus concluding the proof. � Let U (x) denote the Jacobian of �u(x) [see Eq. (5)]. In particular, if the xi are all 1-dimensional, then U (x) is given by ⎛ ∂2u 1 (x) ∂x21 ∂ 2 u2 (x) ⎜ U (x) = ⎜ ⎝ ∂x 2 ∂x1 ∂ 2 u1 (x) ∂x1 ∂x2 ... .. . ⎞ ··· ⎟ ⎟. ⎠ The next proposition provides a sufficient condition for the payoff functions to be diago­ nally strictly concave. Proposition 4 For all i ∈ I, assume that the strategy sets Si are given by Eq. (3), where hi is a concave function. Assume that the symmetric matrix (U (x) + U T (x)) is negative definite for all x ∈ S, i.e., for all x ∈ S, we have y T (U (x) + U T (x))y < 0, ∀y= � 0. Then, the payoff functions (u1 , . . . , uI ) are diagonally strictly concave for x ∈ S. 6-12 Proof: Let x∗ , x̄ ∈ S. Consider the vector x(λ) = λx∗ + (1 − λ)x̄, for some λ ∈ [0, 1]. Since S is a convex set, x(λ) ∈ S. Because U (x) is the Jacobian of �u(x), we have d dx(λ) �u(x(λ)) = U (x(λ)) dλ d(λ) = U (x(λ))(x∗ − x̄), or � 1 U (x(λ))(x∗ − x̄)dλ = �u(x∗ ) − �u(x̄). 0 Multiplying the preceding by (x̄ − x∗ )T yields (x̄ − x∗ )T �u(x∗ ) + (x∗ − x̄)T �u(x̄) � 1 1 ∗ = − (x − x̄)T [U (x(λ)) + U T (x(λ))](x∗ − x̄)dλ 2 0 > 0, where to get the strict inequality we used the assumption that the symmetric matrix (U (x)+ U T (x)) is negative definite for all x ∈ S. � Recent work has shown that the uniqueness of a pure strategy Nash equilibrium can be established under conditions that are weaker than those given above. This analysis is beyond our scope; for more information on this, see the recent papers [6], [7],[8]. 5 Appendix For more on metric spaces, refer to any textbook on real analysis, for example Rudin [5]. For completeness, we summarize the basic definitions here. A metric space is a set M together with a function d : M × M �→ R, that defines the “distance” d(x, y) between any two points x, y in the set. The distance function satisfies the following properties for every x, y, z ∈ M : • d(x, y) = d(y, x) ≥ 0, 6-13 • d(x, y) = 0 if and only if x = y, • d(x, y) + d(y, z) ≥ d(x, z). In a metric space M , a point y ∈ M is the limit of a sequence of points {xk }∞ k=1 ⊂ M if and only if the distance d(xk , y) → 0 as k → ∞. An open ball of radius � around a point x, denoted by B(x, �), is the set of all points in the metric space that have a distance less than � from x, i.e., B(x, �) = {y | d(x, y) < �}. A set S is an open subset of a metric space M if and only if for every x ∈ S, there exists some � > 0 such that B(x, �) ⊂ S. A metric space is compact if and only if every collection of open sets that “covers” M (i.e., their union includes all of M ), has a finite subcollection that also covers M . When there are infinitely many actions in the set Si , a mixed strategy for player i can no longer be described by just listing the probability of each individual action (i.e., by a finite dimensional probability vector). For example, suppose that Si is the interval [0, 1]. If player i selected his action from a uniform probability distribution over the interval [0,1], then each individual action in [0,1] would have zero probability; but the same would be true if he selected his action from a uniform probability distribution over the interval [0.5,1]. To describe a probability distribution over Si , we must list the probabilities of subsets of Si . Unfortunately, for technical reasons, it may be mathematically impossible to consistently assign probabilities to all subsets of an infinite set, so some weak restriction is needed on the class of subsets whose probabilities can be meaningfully defined. These are called the measurable sets. Here, we let the measurable subsets of S and of each set Si be the smallest class of subsets that includes all open subsets, all closed subsets, and all finite or countably infinite unions and intersections of sets in the class. These are the Borel subsets (and they include essentially all subsets that could be defined without the use of very sophisticated mathematics). Let Bi denote the set of such measurable or Borel subsets of Si . Let Σi denote the set of probability distributions over Si , i.e., σi ∈ Σi if and only if σi is a function that assigns a nonnegative number σi (Q) to each Q that is a Borel subset of Si , 6-14 σ(Si ) = 1, and for any countable collection (Qk )∞ k=1 of pairwise-disjoint Borel subsets of Si , �∞ � ∞ � k σi Q = σi (Qk ). k=1 k=1 We define convergence for mixed strategies by assigning the weak topology to Σi . Two implications of this topology are important for our purposes: • The set of probability distributions Σi is a compact metric space, i.e., every sequence {σik } ⊂ Σi has a convergent subsequence. • A sequence {σik } ⊂ Σi of mixed strategies converges to σi ∈ Σi if and only if for all continuous functions f : Si �→ R, we have � � k lim f (si )dσi (si ) = f (si )dσi (si ). k→∞ Si (11) Si The preceding condition asserts that if s̃ki is a random strategy drawn from Si according to the σik distribution, and s̃i is a random strategy drawn from Si according to the σi distribution, then the expected value of f (s̃ki ) must converge to the expected value of f (s̃i ) as k → ∞. A function g : S �→ R is called (Borel) measurable if for every scalar t, the set {x ∈ S | g(x) ≥ t} is a Borel subset of S. A function g : S �→ R is bounded if there exists some scalar K such that |g(x)| ≤ K for all x ∈ C. To be able to define expected utilities, we must require that player’s utility functions are measurable and bounded in this sense. Note that this assumption is weaker than the continuity of the utility functions. With � this assumption, the utility functions ui are extended from S = Ij=1 Sj to the space of � probability distributions Σ = Ij=1 Σj as follows: � ui (σ) = ui (s)dσ(s), C where σ ∈ Σ. References [1] Dasgupta, P. and Maskin E., “The existence of equilibrium in discontinuous economic games. 1: Theory,” Review of Economic Studies, vol. 53, pp. 1-26, 1986. 6-15 [2] Dasgupta, P. and Maskin E., “The existence of equilibrium in discontinuous economic games. 2: Applications,” Review of Economic Studies, vol. 53, pp. 27-42, 1986. [3] Myerson R., Game Theory: Analysis of Conflict, Harvard University Press, Cambridge, MA, 1991. [4] Rosen J. B., “Existence and uniqueness of equilibrium points for concave N -person games,” Econometrica, vol. 33, no. 3, 1965. [5] Rudin W., Principles of Mathematical Analysis, McGraw-Hill, 1976. [6] Simsek, A., Ozdaglar, A., and Acemoglu, D., “A generalized Poincare-Hopf Theorem for compact nonsmooth regions,” Mathematics of Operations Research, vol. 32, no. 1, pp. 193-214, 2007. [7] Simsek, A., Ozdaglar, A., and Acemoglu, D., “Local indices for degenerate variational inequalities, to appear in Mathematics of Operations Research, 2008. [8] Simsek, A., Ozdaglar, A., and Acemoglu, D., “Uniqueness of generalized equilibrium for box constrained problems and applications,” Proc. of Allerton Conference, September 2005. 6-16