Playing Anonymous Games using Simple Strategies

Yu Cheng, Ilias Diakonikolas, Alistair Stewart

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We investigate the complexity of computing approximate Nash equilibria in anonymous games. Our main algorithmic result is the following: For any n-player anonymous game with a bounded number of strategies and any constant δ > 0, an Ο(1/n1-δ)-approximate Nash equilibrium can be computed in polynomial time. Complementing this positive result, we show that if there exists any constant δ > 0 such that an Ο(1/n1+δ)- approximate equilibrium can be computed in polynomial time, then there is a fully polynomial-time approximation scheme (FPTAS) for this problem. We also present a faster algorithm that, for any n-player k-strategy anonymous game, runs in time Õ ((n + k)knk} and computes an Õ(n−1/3k11/3)- approximate equilibrium. This algorithm follows from the existence of simple approximate equilibria of anonymous games, where each player plays one strategy with probability 1 — δ, for some small δ, and plays uniformly at random with probability δ. Our approach exploits the connection between Nash equilibria in anonymous games and Poisson multinomial distributions (PMDs). Specifically, we prove a new probabilistic lemma establishing the following: Two PMDs, with large variance in each direction, whose first few moments are approximately matching are close in total variation distance. Our structural result strengthens previous work by providing a smooth tradeoff between the variance bound and the number of matching moments.
Original languageEnglish
Title of host publicationProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms
PublisherSociety for Industrial and Applied Mathematics
Pages616-631
Number of pages16
ISBN (Print)978-1-61197-478-2
DOIs
Publication statusPublished - 19 Jan 2017
EventTwenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms - Hotel Porta Fira, Barcelona, Spain
Duration: 16 Jan 201719 Jan 2017
http://www.siam.org/meetings/da17/

Conference

ConferenceTwenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms
Abbreviated titleSIAM 2017
Country/TerritorySpain
CityBarcelona
Period16/01/1719/01/17
Internet address

Fingerprint

Dive into the research topics of 'Playing Anonymous Games using Simple Strategies'. Together they form a unique fingerprint.

Cite this