Slide 1Slide 2Multiplayer Zero-Sum, wha?Polymatrix GamesPolymatrix GamesSlide 6anonymous gamesPTASsketch of algorithm for 2 strategiessketch for 2 strategies (cont.)sketch for 2 strategies (cont.)The TV BoundCompleting the algorithmSlide 14proof of approximation resultproof of approximation resultproof of approximation resultAnonymous Games SummarySlide 19Slide 20proof of structural resultAnonymous Games SummaryIs there an even faster PTAS?Anonymous Games Summary6.896: Topics in Algorithmic Game TheoryLecture 13Constantinos Daskalakismultiplayer zero-sum gamesMultiplayer Zero-Sum, wha?Take an arbitrary two-player game, between Alice and Bob.Add a third player, Eve, who does not affect Alice or Bob’s payoffs, but receives payoffThe game is zero-sum, but solving it is PPAD-complete.intractability even for 3 player, if three-way interactions are allowed.What if only pairwise interactions are allowed?Polymatrix Games- players are nodes of a graph G- player’s payoff is the sum of payoffs from all adjacent edges……- edges are 2-player gamesN.B. finding a Nash equilibrium is PPAD-complete for general games on the edges [D, Gold, Pap ’06]What if the total sum of players’ payoffs is always 0?Polymatrix GamesTheorem [Daskalakis-Papadimitriou ’09, Cai-Daskalakis’10] - a Nash equilibrium can be found efficiently with linear-programming;- if every node uses a no-regret learning algorithm, the players’ behavior converges to a Nash equilibrium.- the Nash equilibria comprise a convex set;strong indication that Nash eq. makes sense in this setting.i.e. payoffs approach equilibrium payoffs, and empirical strategies approach Nash equilibriumIf the global game is zero-sum:N.B. but [+ Tardos ’09] the value of the nodes need not be unique.essentially the broadest class of zero-sum games we could hope to solveAnonymous Gamesanonymous gamesEvery player is (potentially) different, but only cares about how many players (of each type) play each of the available strategies.e.g. symmetry in auctions, congestion games, social phenomena, etc.‘‘The women of Cairo: Equilibria in Large Anonymous Games.’’ Blonski, Games and Economic Behavior, 1999.“Partially-Specified Large Games.” Ehud Kalai, WINE, 2005.‘‘Congestion Games with Player- Specific Payoff Functions.’’ Milchtaich, Games and Economic Behavior, 1996.- all players share the same set of strategies: S = {1,…, s}- payoff functions: up = up (σ ; n1, n2,…,ns )number of the other players choosing each strategy in Schoice of pDescription Size: O(min {s ns, n sn })PTASThere is a PTAS for anonymous games with a constant #strategies.Theorem [Daskalakis, Papadimitriou ’07, ’08]:Remarks:- exact computation is not known to be PPAD-complete for multi-player anonymous games with a constant number of strategies;- on the flip side, if n is small and s is large (few players, many strategies) then trivially PPAD-complete, since general 2-player games can be reduced to this.sketch of algorithm for 2 strategies0101p2p1• discretize [0,1]n into multiples of δ, and restrict search to the discrete space• pick best point in discrete space• since 2 strategies per player, Nash equilibrium lies in [0,1]nsketch for 2 strategies (cont.)Basic Question:what grid size  is required for  - approximation?if function of  only  PTASif function also of n  nothing0101p2p1First trouble:size of search space 1 nbut will deal with this laterTheorem [Daskalakis, Papadimitriou ’07]: Given - n ind. Bernoulli’s Xi with expectations pi , i =1,…, n there exists another set of Bernoulli’s Yi with expectations qi such that- a constant  independent of n qi’s are integer multiples of in fact:N.B. argument from last lecture givessketch for 2 strategies (cont.)The TV BoundHow much does player p’s payoff from pure `strategy σ change if we replace X = (X1, X2, …, Xn) with Y = (Y1, Y2, …, Yn) ?Given previous theorem, can guarantee that there exists a discretized point making the above difference at most by selecting .Completing the algorithmdynamic programming+discretization +TV boundcomplete this step (2 points)assume that the players only use mixed strategies in probabilities that are multiples of . enough to guarantee a discretized- Nash equilibriumResulting running time for 2 strategies.Theorem [Daskalakis, Papadimitriou ’07]: Given - n ind. Bernoulli’s Xi with expectations pi , i =1,…, n The first probabilistic approximation theoremthere exists another set of Bernoulli’s Yi with expectations qi such that- a constant  independent of n qi’s are integer multiples of in fact:argument from last time givesproof of approximation resultLaw of Rare Events + CLT- rounding pi’s to the closest multiple of  gives total variation n- probabilistic rounding up or down quickly runs into problems- what works:Poisson ApproximationsBerry-Esséen(Stein’s Method)proof of approximation resultIntuition: If pi’s were small iiX∑would be close to a Poisson with meaniip∑iiX∑ define the qi’s so thati ii iq p≈∑ ∑iiY∑iiPoisson p⎛ ⎞⎜ ⎟⎝ ⎠∑iiPoisson q⎛ ⎞⎜ ⎟⎝ ⎠∑Poisson approximation is only good for small values of pi’s. (LRE)proof of approximation resultFor intermediate values of pi’s, Normals are better. (CLT)iiX∑iiY∑Berry-EsséenBerry-EsséenAnonymous Games Summary2-strategies per player:[DP ’07]constant #strategies per player:bad function of s[DP ’08]is there a faster PTAS?Theorem [Daskalakis ’08]: There is an oblivious PTAS with running time - or, at most mix, and they choose mixed strategies which are integer multiples of Theorem [D’08]: In every anonymous game there exists an ε-approximate Nash equilibrium in which the underlying structural result…- either all players who mix play the same mixed strategyLemma:- The sum of m ≥ k3 indicators Xi with expectations in [1/k,1-1/k] is O(1/k)-close in total variation distance to a Binomial distribution with the same mean and variancethe corresponding symmetry… … i.e. close to a sum of indicators with the same expectation[tightness of parameters by Berry-Esséen]proof of structural resultround some of the Xi’s falling here to 0 and some of them to ε so that the total mean is preserved to within ε- if more than 1/ε3 Xi’s are left here, appeal to previous