CS 684 Algorithmic Game Theory Scribe: Muthu VenkitasubramaniamInstructor: Eva Tardos October 26, 2004The construction itself is an art, its application to the world an evil parasite.- L E J BrouwerRandomized Nash EquilibriumIn this lecture, we discuss the proof of existence of Nash equilibrium in a randomized game. We considergames where the number of players and the strategy sets are finite. We remark here that the finiteness ofthe strategy set and player set is crucial to the main theorem. We have discussed several games in the pastlectures where the players set and the strategy set are finite and infinite, some of which are listed below.• Job-scheduling game - The number of jobs (i.e. players) is finite, and the number of machines (strategyset) each job could be assigned is finite too.• Facility-location game - The number of players is finite, and the number of locations where eachplayer could open a facility is finite.• Job splitting game - The jobs were considered a large number of infinitesimally small jobs, in effectassuming infinite jobs, with finite strategy. There is also a related game with finite jobs with infinitestrategies where users control a finite amount of flow, and may split flow.• Johari Tsitsiklis game - The player set is finite, while the number of strategies is infinite.Main theoremThere are n players, and each player i has a finite strategy set Sifrom which it plays. We consider a valuationfunction vifor player i. vi(s1, s2, . . . , sn) is the benefit function for player i when the players strategies ares1, s2, . . . , sn(, i.e. player j plays strategy sj).In the games discussed so far, we have considered only pure Nash equilibrium. In a pure Nash, eachplayer plays exactly one strategy from the strategy set. In this lecture, we consider randomized Nash whereeach player can play several strategies with some probability. Games in general, need not have a pure Nashequilibrium, while randomized Nash equilibrium always exists.A randomized strategy is a probability distribution piover the strategy set Sifor each player i. pi(s) isthe probability with which player i plays strategy s ∈ Si. Since this is a probability distribution,pi(s) ≥ 0 andXs∈Sipi(s) = 1.Each player tries to maximize its benefit in expectation. Given a probability distribution pjfor eachplayer j, the benefit for player i is E(vi(s1, s2, . . . , sn)). This can be thought of as the benefit player i will geton the average, when the game is played several times with the same randomized strategy.E(vi(s1, s2, . . . , sn)) =Xsi∈Si,∀ip1(s1)p2(s2)· · · pn(sn)vi(s1, s2, . . . , sn)To make our notation cleaner we will use vi(p1, p2, . . . , pn) to denote the above expectation. Note thatpihere is a probability distribution for player i.We now state the main theorem for the lecture,Theorem 1 (J. F. Nash) For any game with finite players and finite strategy sets, there exists a randomizedNash equilibrium.We take a slight detour into real analysis, to develop machinery to solve the main theorem.Brouwer’s Fixed Point theoremTheorem 2 (L. E. J. Brouwer) Every continuous mapping f from a closed, bounded and convex set C ⊂nto itself has a fixed point, i.e. there exists x ∈ C such that f(x) = x.Refer to Appendix A for the definitions. We do not prove this theorem here, and refer to [2] for the proof.We given some intuition as to why this is true. Consider continuous functions f : [0, 1] → [0, 1]. [0, 1]is a closed, bounded and convex, and f is continuous. Since these functions satisfy the conditions of thetheorem, there exists an x ∈ [0, 1] such that f(x) = x. As seen in the Figure 1, f(0) must lie somewhere onthe line segment AB and f(1) must lie somewhere on the line segment CD. Since the function is continuous,the path traced by f is a curve from f(0) to f(1). This should meet line segment AD at some point (x0inFigure 1). This point is a fixed point for function f.Figure 1: Fixed point in 1-dimensionFigure 2: Fixed point in 1-dimensionWe illustrate with another example as to why convexity is required. Consider the annulus shown inFigure 2. This is a closed and bounded set in 2, but not convex. We define a function f on this, that rotatesthe annulus by some angle. This function is continuous, but does not have a fixed point.Having set the machinery, we now proceed on to the main theorem.Proof of Theorem 1: The basic idea is that we invoke the Brouwer’s fixed point theorem. The set Cunder consideration is {(p1, p2, . . . , pn)} where piis the probability distribution over the strategy set Si.Therefore, C ⊂ |S1|+|S2|+...+|Sn|. C is closed, bounded and convex, since we have the constraints pi(s) ≥0 andPs∈Sipi(s) = 1.Given (p1, p2, . . . , pn), define qito be the best response for player i, that is, we define qito be theprobability distribution q maximizingmaxqvi(p1, p2, . . . , pi−1, q, pi+1, . . . , pn)).We now define the mapping f : C → C as follows,f(p1, p2, . . . , pn) = (q1, q2, . . . , qn)Clearly, a fixed point for the function f is a Nash equilibrium. If f satisfies the conditions for Brouwer’sTheorem, we are done. But we are not quite there, with respect to satisfying the conditions of Brouwer’sTheorem for the following reasons:• The best response qimay not be unique for player i. We have seen this in several of our games, suchas job scheduling, atomic routing, etc. Hence, f is not well defined.• Suppose, we chose one of the possible best responses (say the lexicographically first one) as qithenf will not be continuous around the points that had multiple best responses.To resolve these issues, there are two approaches,1. Kakutani’s Fixed Point Theorem: This approach deals with more general notions of functions wherethe function maps the points in the set C to closed and convex subsets of C (in our case the set of bestresponses), and the theorem states that for such functions there is a point x such that x ∈ f(x). This isexactly what we need.2. So we don’t have to deal with extending the fixed point theorem, the proof of Kakutani’s fixed pointtheorem, defined in approach 1, for this case we define a point function f which satisfies the conditionsof Brouwer’s fixed point theorem and hence prove the theorem.Approach 2We define qias the probability distribution that maximizesmaxqhvi(p1, p2, . . . , pi−1, q, pi+1, . . . , pn)− ||pi− q||2iWe need to show that,1. f is a function: We claim that there exists an unique q that maximizes