Abstract
We investigate the problem of equilibrium computation for “large” n-player games where each player has two pure strategies. Large games have a Lipschitz-type property that no single player’s utility is greatly affected by any other individual player’s actions. In this paper, we assume that a player can change another player’s payoff by at most \(\frac{1}{n}\) by changing her strategy. We study algorithms having query access to the game’s payoff function, aiming to find \(\varepsilon \)-Nash equilibria. We seek algorithms that obtain \(\varepsilon \) as small as possible, in time polynomial in n.
Our main result is a randomised algorithm that achieves \(\varepsilon \) approaching \(\frac{1}{8}\) in a completely uncoupled setting, where each player observes her own payoff to a query, and adjusts her behaviour independently of other players’ payoffs/actions. \(O(\log n)\) rounds/queries are required. We also show how to obtain a slight improvement over \(\frac{1}{8}\), by introducing a small amount of communication between the players.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
If the player i never plays an action j in any query, set \(\widehat{u}_{i,j} = 0\).
- 2.
In particular, if we use \(\mathcal {Q}_{\beta ,\delta }\) for our query access, we will get \((\varepsilon + O(\beta ))\)-approximate equilibrium, with \(\varepsilon = 0.272, 0.25\) with probability at least \(1-\delta \).
References
Azrieli, Y., Shmaya, E.: Lipschitz games. Math. Oper. Res. 38(2), 350–357 (2013)
Babichenko, Y.: Best-reply dynamics in large binary-choice anonymous games. Games Econ. Behav. 81, 130–144 (2013)
Babichenko, Y.: Query complexity of approximate Nash equilibria. In: Proceedings of 46th STOC, pp. 535–544 (2014)
Babichenko, Y., Barman, S.: Query complexity of correlated equilibrium. ACM. Trans. Econ. Comput. 4(3), 1–35 (2015)
Chen, X., Cheng, Y., Tang, B.: Well-supported versus approximate Nash equilibria: Query complexity of large games (2015). ArXiv rept. 1511.00785
Fearnley, J., Savani, R.: Finding approximate Nash equilibria of bimatrix games via payoff queries. In: Proceedings of 15th ACM EC, pp. 657–674 (2014)
Fearnley, J., Gairing, M., Goldberg, P.W., Savani, R.: Learning equilibria of games via payoff queries. J. Mach. Learn. Res. 16, 1305–1344 (2015)
Foster, D.P., Young, H.P.: Regret testing: learning to play Nash equilibrium without knowing you have an opponent. Theor. Econ. 1(3), 341–367 (2006)
Germano, F., Lugosi, G.: Global Nash convergence of Foster and Young’s regret testing (2005). http://www.econ.upf.edu/lugosi/nash.pdf
Goldberg, P.W., Roth, A.: Bounds for the query complexity of approximate equilibria. In: Proceedings of the 15th ACM-EC Conference, pp. 639–656 (2014)
Goldberg, P.W., Turchetta, S.: Query complexity of approximate equilibria in anonymous games. In: Markakis, E., et al. (eds.) WINE 2015. LNCS, vol. 9470, pp. 357–369. Springer, Heidelberg (2015). doi:10.1007/978-3-662-48995-6_26
Hart, S., Mansour, Y.: How long to equilibrium? the communication complexity of uncoupled equilibrium procedures. Games Econ. Behav. 69(1), 107–126 (2010)
Hart, S., Mas-Colell, A.: A simple adaptive procedure leading to correlated equilibrium. Econometrica 68(5), 1127–1150 (2000)
Hart, S., Mas-Colell, A.: Uncoupled dynamics do not lead to Nash equilibrium. Am. Econ. Rev. 93(5), 1830–1836 (2003)
Hart, S., Nisan, N.: The query complexity of correlated equilibria (2013). ArXiv tech rept. 1305.4874
Kalai, E.: Large robust games. Econometrica 72(6), 1631–1665 (2004)
Kearns, M., Pai, M.M., Roth, A., Ullman, J.: Mechanism design in large games: Incentives and privacy. Am. Econ. Rev. 104(5), 431–435 (2014). doi:10.1257/aer.104.5.431
Young, H.P.: Learning by trial and error (2009). http://www.econ2.jhu.edu/people/young/Learning5June08.pdf
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Goldberg, P.W., Marmolejo Cossío, F.J., Wu, Z.S. (2016). Logarithmic Query Complexity for Approximate Nash Computation in Large Games. In: Gairing, M., Savani, R. (eds) Algorithmic Game Theory. SAGT 2016. Lecture Notes in Computer Science(), vol 9928. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-53354-3_1
Download citation
DOI: https://doi.org/10.1007/978-3-662-53354-3_1
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-53353-6
Online ISBN: 978-3-662-53354-3
eBook Packages: Computer ScienceComputer Science (R0)