Harrow, Aram ;
Natarajan, Anand V. ;
Wu, Xiaodi
Tight SoSDegree Bounds for Approximate Nash Equilibria
Abstract
Nash equilibria always exist, but are widely conjectured to require time to find that is exponential in the number of strategies, even for twoplayer games. By contrast, a simple quasipolynomial 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 nearmaximal total welfare. Matching hardness results for this optimization problem re found assuming the hardness of the plantedclique 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 sumsquares (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 BravermanKoWeinstein embedding of CSPs into strategic games and techniques from sumofsquares proof systems. The upper bound (i.e. analysis of the LP) uses informationtheory techniques that have been recently applied to other linear and semidefiniteprogramming hierarchies.
BibTeX  Entry
@InProceedings{harrow_et_al:LIPIcs:2016:5856,
author = {Aram Harrow and Anand V. Natarajan and Xiaodi Wu},
title = {{Tight SoSDegree Bounds for Approximate Nash Equilibria}},
booktitle = {31st Conference on Computational Complexity (CCC 2016)},
pages = {22:122:25},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770088},
ISSN = {18688969},
year = {2016},
volume = {50},
editor = {Ran Raz},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5856},
URN = {urn:nbn:de:0030drops58565},
doi = {10.4230/LIPIcs.CCC.2016.22},
annote = {Keywords: Approximate Nash Equilibrium, Sum of Squares, LP, SDP}
}
2016
Keywords: 

Approximate Nash Equilibrium, Sum of Squares, LP, SDP 
Seminar: 

31st Conference on Computational Complexity (CCC 2016)

Issue date: 

2016 
Date of publication: 

2016 