×

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
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Azrieli, Y., Shmaya, E.: Lipschitz games. Math. Oper. Res. 38(2), 350–357 (2013) · Zbl 1297.91006 · doi:10.1287/moor.1120.0557
[2] Babichenko, Y.: Best-reply dynamics in large binary-choice anonymous games. Games Econ. Behav. 81(1), 130–144 (2013) · Zbl 1282.91038 · doi:10.1016/j.geb.2013.04.007
[3] Babichenko, Y.: Query complexity of approximate Nash equilibria. In: Proceedings of the 46th Annual ACM Symposium on Theory of Computing. pp. 535–544. STOC 2014. ACM, USA (2014) · Zbl 1315.91003 · doi:10.1145/2591796.2591829
[4] Brandt, F., Fischer, F., Holzer, M.: Symmetries and the complexity of pure Nash equilibrium. J. Comput. Syst. Sci. 75, 163–177 (2009) · Zbl 1154.91352 · doi:10.1016/j.jcss.2008.09.001
[5] Chen, X., Deng, X., Teng, S.: Settling the complexity of computing two-player Nash equilibria. J. ACM 56(3), 1–57 (2009) · Zbl 1325.68095 · doi:10.1145/1516512.1516516
[6] Chen, X., Durfee, D., Orfanou, A.: On the complexity of Nash equilibria in anonymous games. In: Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, ACM, pp. 381–390 (2015) · Zbl 1322.91005 · doi:10.1145/2746539.2746571
[7] Daskalakis, C.: An efficient PTAS for two-strategy anonymous games. In: Papadimitriou, C., Zhang, S. (eds.) WINE 2008. LNCS, vol. 5385, pp. 186–197. Springer, Heidelberg (2008) · Zbl 1304.91013 · doi:10.1007/978-3-540-92185-1_26
[8] Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H.: The complexity of computing a Nash equilibrium. SIAM J. Comput. 39(1), 195–259 (2009) · Zbl 1185.91019 · doi:10.1137/070699652
[9] Daskalakis, C., Papadimitriou, C.H.: Computing equilibria in anonymous games. In: Proceedings of the 48th Symposium on Foundations of Computer Science (FOCS), pp. 83–93 (2007) · doi:10.1109/FOCS.2007.24
[10] Daskalakis, C., Papadimitriou, C.H.: Discretized multinomial distributions and Nash equilibria in anonymous games. In: Proceedings of the 49th Symposium on Foundations of Computer Science (FOCS), pp. 25–34 (2008) · doi:10.1109/FOCS.2008.84
[11] Daskalakis, C., Papadimitriou, C.H.: On oblivious PTAS’s for Nash equilibrium. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, pp. 75–84. ACM, USA (2009) · Zbl 1304.91014 · doi:10.1145/1536414.1536427
[12] Daskalakis, C., Papadimitriou, C.H.: Sparse covers for sums of indicators (2013). CoRR abs/1306.1265 · Zbl 1334.60048
[13] Daskalakis, C., Papadimitriou, C.H.: Approximate Nash equilibria in anonymous games. J. Econ. Theory 156, 207–245 (2015) · Zbl 1330.91015 · doi:10.1016/j.jet.2014.02.002
[14] Etessami, K., Yannakakis, M.: On the complexity of Nash equilibria and other fixed points. SIAM J. Comput. 39(6), 2531–2597 (2010) · Zbl 1204.91003 · doi:10.1137/080720826
[15] Fearnley, J., Gairing, M., Goldberg, P.W., Savani, R.: Learning equilibria of games via payoff queries. In: Proceedings of the 14th ACM Conference on Electronic Commerce, EC 2013, pp. 397–414. ACM, USA (2013) · Zbl 1351.91008 · doi:10.1145/2492002.2482558
[16] Fearnley, J., Savani, R.: Finding approximate Nash equilibria of bimatrix games via payoff queries. In: Proceedings of the Fifteenth ACM Conference on Economics and Computation, EC 2014, pp. 657–674. ACM, USA (2014) · doi:10.1145/2600057.2602847
[17] Goldberg, P.W., Roth, A.: Bounds for the query complexity of approximate equilibria. In: Proceedings of the Fifteenth ACM Conference on Economics and Computation, EC 2014, pp. 639–656. ACM, USA (2014) · doi:10.1145/2600057.2602845
[18] Hart, S., Nisan, N.: The query complexity of correlated equilibria. In: Vöckling, B. (ed.) SAGT 2013. LNCS, vol. 8146, p. 268. Springer, Heidelberg (2013) · Zbl 1400.91006
[19] Kash, I.A., Friedman, E.J., Halpern, J.Y.: Multiagent learning in large anonymous games. In: Eighth International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 765–772 (2009) · Zbl 1216.68304
[20] Lipton, R.J., Markakis, E., Mehta, A.: Playing large games using simple strategies. In: Proceedings of the 4th ACM Conference on Electronic Commerce, EC 2003, pp. 36–41. ACM, USA (2003) · doi:10.1145/779928.779933
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.