Playing anonymous games using simple strategies

DOI10.1137/1.9781611974782.40MaRDI QIDQ4575777zbMATH OpenOpenAlexFDO

Authors Yu Cheng, Ilias Diakonikolas, Alistair Stewart

Publication date 16 July 2018

Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1608.07336

zbMATH Keywords

anonymous gamesapproximate Nash equilibriacomputational complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) (n)-person games, (n>2) (91A06) Noncooperative games (91A10)

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 $delta>0$, an $O(1/n^{1-delta})$-approximate Nash equilibrium can be computed in polynomial time. Complementing this positive result, we show that if there exists any constant $delta>0$ such that an $O(1/n^{1+delta})$-approximate equilibrium can be computed in polynomial time, then there is a fully polynomial-time approximation scheme for this problem. We also present a faster algorithm that, for any $n$-player $k$-strategy anonymous game, runs in time $ildeO((n+k)k{n}^k)$ and computes an $ildeO(n^{-1/3}{k}^{11/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-delta$, for some small $delta$, and plays uniformly at random with probability $delta$. 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.

Recommendations

• Approximate Nash equilibria in anonymous games
• An Efficient PTAS for Two-Strategy Anonymous Games
• Query complexity of approximate equilibria in anonymous games
• Query complexity of approximate equilibria in anonymous games
• On the complexity of Nash equilibria in anonymous games

Cited in

(13)

• The Poisson Multinomial Distribution and Its Applications in Voting Theory, Ecological Inference, and Machine Learning
• The Lipschitz constant of perturbed anonymous games
• Approximate Nash equilibria in anonymous games
• Query complexity of approximate equilibria in anonymous games
• On the complexity of Nash equilibria in anonymous games
• Query complexity of approximate equilibria in anonymous games
• Computing Equilibria in Large Games We Play
• scientific article; zbMATH DE number 6866347 (Why is no real title available?)
• Sparse covers for sums of indicators
• scientific article; zbMATH DE number 7307484 (Why is no real title available?)
• The Fourier transform of Poisson multinomial distributions and its algorithmic applications
• A size-free CLT for Poisson multinomials and its applications
• An Efficient PTAS for Two-Strategy Anonymous Games

This page was built for publication: Playing anonymous games using simple strategies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575777)