# zbMATH — the first resource for mathematics

Query complexity of approximate equilibria in anonymous games. (English) Zbl 1404.91009
Markakis, Evangelos (ed.) et al., Web and internet economics. 11th international conference, WINE 2015, Amsterdam, The Netherlands, December 9–12, 2015. Proceedings. Berlin: Springer (ISBN 978-3-662-48994-9/pbk; 978-3-662-48995-6/ebook). Lecture Notes in Computer Science 9470, 357-369 (2015).
Summary: We study the computation of equilibria of two-strategy anonymous games, via algorithms that may proceed via a sequence of adaptive queries to the game’s payoff function, assumed to be unknown initially. The general topic we consider is query complexity, that is, how many queries are necessary or sufficient to compute an exact or approximate Nash equilibrium.
We show that exact equilibria cannot be found via query-efficient algorithms. We also give an example of a 2-strategy, 3-player anonymous game that does not have any exact Nash equilibrium in rational numbers. Our main result is a new randomized query-efficient algorithm that finds a $$O(n^{-1/4})$$-approximate Nash equilibrium querying $$\tilde{O}(n^{3/2})$$ payoffs and runs in time $$\tilde{O}(n^{3/2})$$. This improves on the running time of pre-existing algorithms for approximate equilibria of anonymous games, and is the first one to obtain an inverse polynomial approximation in poly-time. We also show how this can be used to get an efficient PTAS. Furthermore, we prove that $$\varOmega (n \log {n})$$ payoffs must be queried in order to find any $$\epsilon$$-well-supported Nash equilibrium, even by randomized algorithms.
For the entire collection see [Zbl 1326.68026].

##### MSC:
 91A06 $$n$$-person games, $$n>2$$ 91A10 Noncooperative games 91-04 Software, source code, etc. for problems pertaining to game theory, economics, and finance
Full Text: