Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4951142 | Journal of Computer and System Sciences | 2017 | 41 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Paul W. Goldberg, Stefano Turchetta,