How hard is it to approximate the best Nash equilibrium?

ABSTRACT

The quest for a PTAS for Nash equilibrium in a two-player game seeks to circumvent the PPAD-completeness of an (exact) Nash equilibrium by finding an approximate equilibrium, and has emerged as a major open question in Algorithmic Game Theory. A closely related problem is that of finding an equilibrium maximizing a certain objective, such as the social welfare. This optimization problem was shown to be NP-hard by Gilboa and Zemel [Games and Economic Behavior 1989]. However, this NP-hardness is unlikely to extend to finding an approximate equilibrium, since the latter admits a quasi-polynomial time algorithm, as proved by Lipton, Markakis and Mehta [Proc. of 4th EC, 2003].

We show that this optimization problem, namely, finding in a two-player game an approximate equilibrium achieving large social welfare is unlikely to have a polynomial time algorithm. One interpretation of our results is that the quest for a PTAS for Nash equilibrium should not extend to a PTAS for finding the best Nash equilibrium, which stands in contrast to certain algorithmic techniques used so far (e.g. sampling and enumeration).

Technically, our result is a reduction from a notoriously difficult problem in modern Combinatorics, of finding a planted (but hidden) clique in a random graph G(n, 1/2). Our reduction starts from an instance with planted clique size k = O(log n). For comparison, the currently known algorithms due to Alon, Krivelevich and Sudakov [Random Struct. & Algorithms, 1998], and Krauthgamer and Feige [Random Struct. & Algorithms, 2000], are effective for a much larger clique size k = Ω(√n).

REFERENCES

• 1: Noga Alon , Alexandr Andoni , Tali Kaufman , Kevin Matulef , Ronitt Rubinfeld , Ning Xie, Testing k-wise and almost k-wise independence, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250863]
• 2: Noga Alon , Michael Krivelevich , Benny Sudakov, Finding a large hidden clique in a random graph, Random Structures & Algorithms, v.13 n.3-4, p.457-466, Oct., 1998
• 3: {BBM07} H. Bosse, J. Byrka, and E. Markakis. New algorithms for approximate nash equilibria in bimatrix games. In WINE 2007, volume 4858 of Lecture Notes in Computer Science, pages 17--29. Springer, 2007.
• 4: Xi Chen , Xiaotie Deng , Shang-Hua Teng, Computing Nash Equilibria: Approximation and Smoothed Complexity, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.603-612, October 21-24, 2006 [doi>10.1109/FOCS.2006.20]
• 5: {CS03} V. Conitzer and T. Sandholm. Complexity results about nash equilibria. In 18th International Joint Conference on Artificial Intelligence, pages 765--771, 2003.
• 6: Constantinos Daskalakis , Paul W. Goldberg , Christos H. Papadimitriou, The complexity of computing a Nash equilibrium, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132527]
• 7: {DMP06} C. Daskalakis, A. Mehta, and C. H. Papadimitriou. A note on approximate nash equilibria. In WINE 2006, volume 4286 of Lecture Notes in Computer Science, pages 297--306. Springer, 2006.
• 8: Constantinos Daskalakis , Aranyak Mehta , Christos Papadimitriou, Progress in approximate nash equilibria, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA [doi>10.1145/1250910.1250962]
• 9: {DP08} C. Daskalakis and C. H. Papadimitriou. Discretized multinomial distributions, covers, and nash equilibria in anonymous games. To appear in FOCS, 2008.
• 10: Edith Elkind , Leslie Ann Golberg , Paul W. Goldberg, Computing good nash equilibria in graphical games, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA [doi>10.1145/1250910.1250935]
• 11: Uriel Feige, Relations between average case complexity and approximation complexity, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509985]
• 12: Uriel Feige , Robert Krauthgamer, Finding and certifying a large hidden clique in a semirandom graph, Random Structures & Algorithms, v.16 n.2, p.195-208, March 2000 [doi>10.1002/(SICI)1098-2418(200003)16:2<195::AID-RSA5>3.0.CO;2-A]
• 13: Uriel Feige , Robert Krauthgamer, The Probable Value of the Lovász-Schrijver Relaxations for Maximum Independent Set, SIAM Journal on Computing, v.32 n.2, p.345-370, 2003 [doi>10.1137/S009753970240118X]
• 14: Tomas Feder , Hamid Nazerzadeh , Amin Saberi, Approximating nash equilibria using small-support strategies, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA [doi>10.1145/1250910.1250961]
• 15: {GZ89} I. Gilboa and E. Zemel. Nash and correlated equilibria: Some complexity considerations. Games and Economic Behavior, 1:80--93, 1989.
• 16: {HH05} E. Halperin and E. Hazan. HAPLOFREQ - estimating haplotype frequencies efficiently. In 9th RECOMB, volume 3500 of Lecture Notes in Computer Science, pages 553--568. Springer, 2005.
• 17: {Hoe63} W. Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13--30, 1963.
• 18: {Jer92} M. Jerrum. Large cliques elude the Metropolis process. Random Structures Algorithms, 3(4):347--359, 1992.
• 19: Ari Juels , Marcus Peinado, Hiding Cliques for Cryptographic Security, Designs, Codes and Cryptography, v.20 n.3, p.269-280, July 2000 [doi>10.1023/A:1008374125234]
• 20: Michael J. Kearns , Michael L. Littman , Satinder P. Singh, Graphical Models for Game Theory, Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, p.253-260, August 02-05, 2001
• 21: {KPS06} S. C. Kontogiannis, P. N. Panagopoulou, and P. G. Spirakis. Polynomial algorithms for approximating nash equilibria of bimatrix games. In WINE 2006, volume 4286 of Lecture Notes in Computer Science, pages 286--296. Springer, 2006.
• 22: Luděk Kučera, Expected complexity of graph partitioning problems, Discrete Applied Mathematics, v.57 n.2-3, p.193-212, Feb. 24, 1995 [doi>10.1016/0166-218X(94)00103-K]
• 23: {KV02} M. Krivelevich and V. H. Vu. Approximating the independence number and the chromatic number in expected polynomial time. J. Comb. Optim., 6(2):143--155, 2002.
• 24: Richard J. Lipton , Evangelos Markakis , Aranyak Mehta, Playing large games using simple strategies, Proceedings of the 4th ACM conference on Electronic commerce, p.36-41, June 09-12, 2003, San Diego, CA, USA [doi>10.1145/779928.779933]
• 25: F. McSherry, Spectral Partitioning of Random Graphs, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.529, October 14-17, 2001
• 26: {Pap07} C. H. Papadimitriou. The complexity of finding nash equilibria. In N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani, editors, Algorithmic Game Theory, chapter 2, pages 29--51. Cambridge University Press, 2007.
• 27: Christos H. Papadimitriou, The Search for Equilibrium Concepts, Proceedings of the 1st International Symposium on Algorithmic Game Theory, April 30-May 02, 2008, Paderborn, Germany [doi>10.1007/978-3-540-79309-0_1]
• 28: Christos H. Papadimitriou , Mihalis Yannakakis, On limited nondeterminism and the complexity of the V-C dimension, Journal of Computer and System Sciences, v.53 n.2, p.161-170, Oct. 1996 [doi>10.1006/jcss.1996.0058]
• 29: {Rou08} T. Roughgarden. An algorithmic game theory primer. To appear in TCS, invited survey, 2008.
• 30: Paul G. Spirakis, Approximate Equilibria for Strategic Two Person Games, Proceedings of the 1st International Symposium on Algorithmic Game Theory, April 30-May 02, 2008, Paderborn, Germany [doi>10.1007/978-3-540-79309-0_3]
• 31: {TS07} H. Tsaknakis and P. G. Spirakis. An optimization approach for approximate nash equilibria. In WINE 2007, volume 4858 of Lecture Notes in Computer Science, pages 42--56. Springer, 2007.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.1 Applications and Expert Systems
          Subjects: Games