1 Search Results for "Natarajan, Anand V."

Document

DOI: 10.4230/LIPIcs.CCC.2016.22

Tight SoS-Degree Bounds for Approximate Nash Equilibria

Authors: Aram Harrow, Anand V. Natarajan, and Xiaodi Wu

Published in: LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{harrow_et_al:LIPIcs.CCC.2016.22,
  author =	{Harrow, Aram and Natarajan, Anand V. and Wu, Xiaodi},
  title =	{{Tight SoS-Degree Bounds for Approximate Nash Equilibria}},
  booktitle =	{31st Conference on Computational Complexity (CCC 2016)},
  pages =	{22:1--22:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-008-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{50},
  editor =	{Raz, Ran},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.22},
  URN =		{urn:nbn:de:0030-drops-58565},
  doi =		{10.4230/LIPIcs.CCC.2016.22},
  annote =	{Keywords: Approximate Nash Equilibrium, Sum of Squares, LP, SDP}
}

Refine by Author
1 Harrow, Aram
1 Natarajan, Anand V.
1 Wu, Xiaodi

Refine by Classification

Refine by Keyword
1 Approximate Nash Equilibrium
1 LP
1 SDP
1 Sum of Squares

Refine by Type
1 document

Refine by Publication Year
1 2016

1 Search Results for "Natarajan, Anand V."

Tight SoS-Degree Bounds for Approximate Nash Equilibria

Abstract

Cite as

Thanks for your feedback!

Could not send message