Query complexity of approximate Nash equilibria. (English) Zbl 1315.91003
Proceedings of the 46th annual ACM symposium on theory of computing, STOC ’14, New York, NY, USA, May 31 – June 3, 2014. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2710-7). 535-544 (2014).
MSC:
| 91A06 | \(n\)-person games, \(n>2\) |
| 68Q25 | Analysis of algorithms and problem complexity |
| 68W25 | Approximation algorithms |
Keywords:
adaptive dynamics; approximate Nash equilibrium; complexity; fixed point; game theory; query complexity; rate of convergenceSoftware:
SuLQReferences:
| [1] | Babichenko, Y. (2013) “Query Complexity of Approximate Nash Equilibria,” arXiv:1306.6686. |
| [2] | Babichenko, Y. and Barman, S. (2013) “Query Complexity of Correlated Equilibrium,” arXiv:1306.2437. |
| [3] | Babichenko, Y. and Peretz, R. (2013) “Approximate Nash Equilibria Via Sampling,” arXiv:1307.4934. |
| [4] | Blume, L. (1993) “The Statistical Mechanics of Strategic Interaction,” Games and Economic Behavior 5, 387-424. · Zbl 0797.90123 |
| [5] | Chen, X. and Deng, X., (2006) “Settling the Complexity of Two-Player Nash Equilibrium,” in 47th Annual IEEE Symposium on Foundations of Computer Science, pp. 261-272. 10.1109/FOCS.2006.69 |
| [6] | Conitzer, V. and Sandholm, T. (2004) “Communication Complexity as a Lower Bound for Learning in Games,” The Twenty-First International Conference on Machine Learning, 185-192. 10.1145/1015330.1015351 |
| [7] | Daskalakis, C., Goldberg, P. W., and Papadimitriou, C. H., (2009) “The Complexity of Computing a Nash Equilibrium,” SIAM Journal of Computing 39, 195âĂŞ-259. 10.1137/070699652 · Zbl 1185.91019 |
| [8] | Daskalakis, C., Mehta, A., and Papadimitriou, C. H. (2009) “A Note on Approximate Nash Equilibria,” Theoretical Computer Science 410, 1581-1588. 10.1016/j.tcs.2008.12.031 · Zbl 1167.91390 |
| [9] | Daskalakis, C. and Papadimitriou, C. H. (2008) “Discretized Multinomial Distributions and Nash equilibria in Anonymous Games,” Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, pp. 25-34. 10.1109/FOCS.2008.84 |
| [10] | Diaconis, P., Graham, R. L., and Morrison J. A. (1990) “Asymptotic Analysis of a Random Walk on a Hypercube with Many Dimensions,” Random Structures and Algorithms, 1, 51âĂŞ-72. · Zbl 0723.60085 |
| [11] | Fearnley, J., Gairing, M., Goldberg, P. W., and Savani, R. (2013) “Learning Equilibria of Games Via Payoff Queries,” arXiv:1302.3116. |
| [12] | Foster, D. and Vohra, R. (1998) “Asymptotic Calibration,” Biometrika, 85, 379âĂŞ-390. · Zbl 0947.62059 |
| [13] | Goldberg, P., and Roth, A. (2013) “Bounds for the Query Complexity of Approximate Equilibria,” Electronic Colloquium on Computational Complexity, TR13-136. |
| [14] | Hart, S. and Mansour, Y. (2010) “How Long to Equilibrium? The Communication Complexity of Uncoupled Equilibrium Procedures,” Games and Economic Behavior 69, 107-126. · Zbl 1229.91029 |
| [15] | Hart, S. and Mas-Colell, A. (2000) “A Simple Adaptive Procedure Leading to Correlated Equilibrium,” Econometrica, 68, 1127âĂŞ-1150. · Zbl 1020.91003 |
| [16] | Hart, S. and Mas-Colell, A. (2003) “Uncoupled Dynamics do Not Lead to Nash Equilibrium,” American Economic Review 93, 1830-1836. |
| [17] | Hart, S. and Mas-Colell, A. (2005) “Adaptive Heuristics,” Econometrica 73, 1401-1430. · Zbl 1152.91370 |
| [18] | Hart, S. and Mas-Colell, A. (2006) “Stochastic Uncoupled Dynamics and Nash Equilibrium,” Games and Economic Behavior 57, 286-303. · Zbl 1156.91319 |
| [19] | Hart, S. and Nisan, N. (2013) “The Query Complexity of Correlated Equilibria,” arXiv:1305.4874. |
| [20] | Hirsch, M. D., Papadimitriou, C. H., and Vavasis, S. A. (1989) “Exponential Lower Bounds for Finding Brower Fixed Points,” Journal of Complexity 5, 379-416. 10.1016/0885-064X(89)90017-4 · Zbl 0696.65045 |
| [21] | Hoeffding, W. (1963) “Probability Inequalities for Sums of Bounded Random Variables,” Journal of the American Statistical Association 58, 13-30. · Zbl 0127.10602 |
| [22] | Jiang, A. X. and Leyton-Brown, K. (2013) “Polynomial-time Computation of Exact Correlated Equilibrium in Compact Games,” Games and Economic Behavior, forthcoming. |
| [23] | Kushilevitz, E. and Nisan, N., 1997. Communication Complexity. Cambridge Univ. Press. · Zbl 0869.68048 |
| [24] | Lipton, R. J., Markakis, E., and Mehta, A. (2003) “Playing Large Games Using Simple Strategies,” in Proceedings of the 4th ACM Conference on Electronic Commerce, pp. 36-41. 10.1145/779928.779933 |
| [25] | Littlestone, N. and Warmuth, M. K. (1989) “The Weighted Majority Algorithm,” in 30th Annual Symposium on Foundations of Computer Science, pp. 256-261. 10.1109/SFCS.1989.63487 |
| [26] | Papadimitriou, C. H. and Roughgarden, T. (2008) “Computing Correlated Equilibria in Multi-Player Games,” Journal of the ACM 55, Article No. 14. 10.1145/1379759.1379762 · Zbl 1314.91012 |
| [27] | Robinson, J. (1951) “An Iterative Method of Solving a Game,”, Annals of Mathematics 54, 296-301. · Zbl 0045.08203 |
| [28] | Sandholm, W. H. (2010) Population Games and Evolutionary Dynamics, MIT Press. · Zbl 1208.91003 |
| [29] | Shmaya, E. (January 5, 2012) “Brouwer Implies Nash Implies Brouwer,” The Leisure of the Theory Class, http://theoryclass.wordpress.com/2012/01/05/brouwer-implies-nash-implies-brouwer/. |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
