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 irrat...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Published: |
Elsevier
2017
|
| 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. |
|---|