Document Open Access Logo

Tight SoS-Degree Bounds for Approximate Nash Equilibria

Authors Aram Harrow, Anand V. Natarajan, Xiaodi Wu

PDF
Thumbnail PDF

File

LIPIcs.CCC.2016.22.pdf
  • Filesize: 0.57 MB
  • 25 pages

Document Identifiers

Author Details

Aram Harrow
Anand V. Natarajan
Xiaodi Wu

Cite As Get BibTex

Aram Harrow, Anand V. Natarajan, and Xiaodi Wu. Tight SoS-Degree Bounds for Approximate Nash Equilibria. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 22:1-22:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.CCC.2016.22

Abstract

Nash equilibria always exist, but are widely conjectured to require time to find that is exponential in the number of strategies, even for two-player games.  By contrast, a simple quasi-polynomial time algorithm, due to Lipton, Markakis and Mehta (LMM), can find approximate Nash equilibria, in which no player can improve their utility by more than epsilon by changing their strategy. The LMM algorithm can also be used to find an approximate Nash equilibrium with near-maximal total welfare.  Matching hardness results for this optimization problem re found assuming the hardness of the planted-clique problem (by Hazan and Krauthgamer) and assuming the Exponential Time Hypothesis (by Braverman, Ko and Weinstein).

In this paper we consider the application of the sum-squares (SoS) algorithm from convex optimization to the problem of optimizing over Nash equilibria. We show the first unconditional lower bounds on the number of levels of SoS needed to achieve a constant factor approximation to this problem. While it may seem that Nash equilibria do not naturally lend themselves to convex optimization, we also describe a simple LP (linear programming) hierarchy that can find an approximate Nash equilibrium in time comparable to that of the LMM algorithm, although neither algorithm is obviously a generalization of the other. This LP can be viewed as arising from the SoS algorithm at log(n) levels - matching our lower bounds. The lower bounds involve a modification of the Braverman-Ko-Weinstein embedding of CSPs into strategic games and techniques from sum-of-squares proof systems.  The upper bound (i.e. analysis of the LP) uses information-theory techniques that have been recently applied to other linear- and semidefinite-programming hierarchies.

Subject Classification

Keywords
  • Approximate Nash Equilibrium
  • Sum of Squares
  • LP
  • SDP

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. S. Aaronson, R. Impagliazzo, and D. Moshkovitz. AM with multiple merlins. In Computational Complexity (CCC), 2014 IEEE 29th Conference on, pages 44-55, June 2014. URL: http://dx.doi.org/10.1109/CCC.2014.13.
  2. Noga Alon, Troy Lee, Adi Shraibman, and Santosh Vempala. The approximate rank of a matrix and its algorithmic applications: Approximate rank. In Proceedings of the 45th Annual ACM Symposium on Symposium on Theory of Computing, STOC'13, pages 675-684, 2013. URL: http://dx.doi.org/10.1145/2488608.2488694.
  3. Robert Aumann. Subjectivity and correlation in randomized strategies. Journal of Mathematical Economics, 1(1):67-96, 1974. URL: http://EconPapers.repec.org/RePEc:eee:mateco:v:1:y:1974:i:1:p:67-96.
  4. Yakov Babichenko, Siddharth Barman, and Ron Peretz. Simple approximate equilibria in large games. In Proceedings of the Fifteenth ACM Conference on Economics and Computation, EC'14, pages 753-770, New York, NY, USA, 2014. ACM. URL: http://dx.doi.org/10.1145/2600057.2602873.
  5. Boaz Barak. Sum of squares upper bounds, lower bounds, and open questions. http://www.boazbarak.org/sos/files/all-notes.pdf, 2014.
  6. Siddharth Barman. Approximating Nash equilibria and dense bipartite subgraphs via an approximate version of Caratheodory’s theorem. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC'15, pages 361-369, New York, NY, USA, 2015. ACM. URL: http://dx.doi.org/10.1145/2746539.2746566.
  7. Fernando G. S. L. Brandão and Aram W. Harrow. Quantum de Finetti theorems under local measurements with applications. In Proceedings of the 45th annual ACM Symposium on theory of computing, STOC'13, pages 861-870, 2013. Google Scholar
  8. Fernando G. S. L. Brandão and Aram W. Harrow. Estimating operator norms using covering nets, 2015. Google Scholar
  9. Mark Braverman, Young Kun Ko, and Omri Weinstein. Approximating the best Nash equilibrium in n^o(log n)-time breaks the Exponential Time Hypothesis, 2014. ECCC TR14-092. Google Scholar
  10. Xi Chen, Xiaotie Deng, and Shang-Hua Teng. Settling the complexity of computing two-player Nash equilibria. J. ACM, 56(3):14:1-14:57, May 2009. URL: http://dx.doi.org/10.1145/1516512.1516516.
  11. T. M. Cover and J. A. Thomas. Elements of Information Theory. Series in Telecommunication. John Wiley and Sons, New York, 1991. Google Scholar
  12. Dima Grigoriev. Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity. Theoretical Computer Science, 259:613-622, 2001. Google Scholar
  13. M. Grötschel, L. Lovász, and A. Schrijver. Geometric algorithms and combinatorial optimization. Springer-Verlag, 1993. Google Scholar
  14. Peter D. Grünwald and A. Philip Dawid. Game theory, maximum entropy, minimum discrepancy and robust Bayesian decision theory. Ann. Statist., 32(4):1367-1433, 08 2004. URL: http://dx.doi.org/10.1214/009053604000000553.
  15. Aram W Harrow, Anand Natarajan, and Xiaodi Wu. Limitations of monogamy, Tsirelson-type bounds, and other semidefinite programs in quantum information, 2015. Google Scholar
  16. Elad Hazan and Robert Krauthgamer. How hard is it to approximate the best nash equilibrium? SIAM Journal on Computing, 40(1):79-91, 2011. URL: http://dx.doi.org/10.1137/090766991.
  17. Sam Hopkins, Pravesh Kothari, Aaron Potechin, Prasad Raghavendra, and Tselil Schramm. On the integrality gap of degree-4 sum of squares for planted clique. In SODA'16, 2016. Google Scholar
  18. Jean B. Lasserre. Global optimization with polynomials and the problem of moments. SIAM Journal on Optimization, 11(3):796-817, 2001. Google Scholar
  19. M. Laurent. Sums of squares, moment matrices and optimization over polynomials. Emerging applications of algebraic geometry, 149:157-270, 2009. Google Scholar
  20. James R. Lee, Prasad Raghavendra, and David Steurer. Lower bounds on the size of semidefinite programming relaxations, 2014. Google Scholar
  21. Richard J. Lipton, Evangelos Markakis, and Aranyak Mehta. Playing large games using simple strategies. In EC'03, pages 36-41, 2003. URL: http://dx.doi.org/10.1145/779928.779933.
  22. Francesco M. Malvestuto. Theory of random observables in relational data bases. Information Systems, 8(4):281-289, 1983. Google Scholar
  23. William J. McGill. Multivariate information transmission. Psychometrika, 19(2):97-116, 1954. Google Scholar
  24. John F. Nash. Equilibrium points in n-person games. Proceedings of the National Academy of Sciences, 36(1):48-49, 1950. URL: http://dx.doi.org/10.1073/pnas.36.1.48.
  25. John F. Nash. Non-cooperative games. Annals of mathematics, pages 286-295, 1951. Google Scholar
  26. Y. Nesterov. Squared functional systems and optimization problems. High performance optimization, 13:405-440, 2000. Google Scholar
  27. Ryan O'Donnell, John Wright, Chenggang Wu, and Yuan Zhou. Hardness of robust graph isomorphism, lasserre gaps, and asymmetry of random graphs. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'14, pages 1659-1677. SIAM, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.120.
  28. Christos H. Papadimitriou and Tim Roughgarden. Computing correlated equilibria in multi-player games. J. ACM, 55(3):14:1-14:29, August 2008. URL: http://dx.doi.org/10.1145/1379759.1379762.
  29. Christos H. Papadimitriou and Mihalis Yannakakis. Optimization, approximation, and complexity classes. Journal of Computer and System Sciences, 43:425-440, 1991. Google Scholar
  30. Pablo A. Parrilo. Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. Technical report, MIT, 2000. Ph.D thesis. Google Scholar
  31. Prasad Raghavendra and Ning Tan. Approximating CSPs with global cardinality constraints using SDP hierarchies. In SODA'12, pages 373-387, 2012. Google Scholar
  32. Grant Schoenebeck. Linear level Lasserre lower bounds for certain k-CSPs. In Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS'08, pages 593-602, Washington, DC, USA, 2008. IEEE Computer Society. URL: http://dx.doi.org/10.1109/FOCS.2008.74.
  33. N.Z. Shor. An approach to obtaining global extremums in polynomial mathematical programming problems. Cybernetics and Systems Analysis, 23(5):695-700, 1987. Google Scholar
  34. Madhur Tulsiani. Csp gaps and reductions in the lasserre hierarchy. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 303-312. ACM, 2009. Google Scholar
  35. Satosi Watanabe. Information theoretical analysis of multivariate correlation. IBM Journal of research and development, 4(1):66-82, 1960. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact