Query complexity of approximate equilibria in anonymous games

We study the computation of Nash equilibria of anonymous games, via algorithms that use adaptive queries to a game's payoff function. We show that exact equilibria cannot be found via query-efficient algorithms, and exhibit a two-strategy, 3-player anonymous game whose exact equilibria require...

Full description

Saved in:
Bibliographic Details
Published in:Journal of computer and system sciences 2017-12, Vol.90, p.80-98
Main Authors: Goldberg, Paul W., Turchetta, Stefano
Format: Article
Language:English
Subjects:
Algorithms
Computational complexity
Game theory
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We study the computation of Nash equilibria of anonymous games, via algorithms that use adaptive queries to a game's payoff function. We show that exact equilibria cannot be found via query-efficient algorithms, and exhibit a two-strategy, 3-player anonymous game whose exact equilibria require irrational numbers. We obtain positive results for known sub-classes of anonymous games. Our main result is a new randomized query-efficient algorithm for approximate equilibria of two-strategy anonymous games that improves on the running time of previous algorithms. It is the first to obtain an inverse polynomial approximation in poly-time, and yields an efficient polynomial-time approximation scheme. •We study equilibrium computation of multi-player anonymous games.•We extend and develop the general theory of query-efficiency of multi-player games.•We obtain improved computational efficiency, as well as query efficiency.•Our main result leads to a new polynomial-time approximation scheme.•We exhibit an anonymous game whose exact equilibria require irrational numbers.
ISSN:0022-0000
1090-2724
DOI:10.1016/j.jcss.2017.07.002