TY - GEN
T1 - Sum-of-Squares meets nash
T2 - 50th Annual ACM Symposium on Theory of Computing, STOC 2018
AU - Kothari, Pravesh K.
AU - Mehta, Ruta
N1 - Publisher Copyright:
© 2018 Association for Computing Machinery.
PY - 2018/6/20
Y1 - 2018/6/20
N2 - Computing Nash equilibrium (NE) in two-player game is a central question in algorithmic game theory. The main motivation of this work is to understand the power of sum-of-squares method in computing equilibria, both exact and approximate. Previous works in this context have focused on hardness of approximating “best” equilibria with respect to some natural quality measure on equilibria such as social welfare. Such results, however, do not directly relate to the complexity of the problem of finding any equilibrium. In this work, we propose a framework of roundings for the sum-of-squares algorithm (and convex relaxations in general) applicable to finding approximate/exact equilbria in two player bimatrix games. Specifically, we define the notion of oblivious roundings with verification oracle (OV). These are algorithms that can access a solution to the degree d SoS relaxation to construct a list of candidate (partial) solutions and invoke a verification oracle to check if a candidate in the list gives an (exact or approximate) equilibrium. This framework captures most known approximation algorithms in combinatorial optimization including the celebrated semidefinite programming based algorithms for Max-Cut, Constraint-Satisfaction Problems, and the recent works on SoS relaxations for Unique Games/Small-Set Expansion, Best Separable State, and many problems in unsupervised machine learning. Our main results are strong unconditional lower bounds in this framework. Specifically, we show that for = Θ(1/pol (n)), there’s no algorithm that uses a o(n)-degree SoS relaxation to construct a 2o(n)-size list of candidates and obtain an -approximate NE. For some constant, we show a similar result for degree o(log (n)) SoS relaxation and list size no(log (n)). Our results can be seen as an unconditional confirmation, in our restricted algorithmic framework, of the recent Exponential Time Hypothesis for PPAD. Our proof strategy involves constructing a family of games that all share a common sum-of-squares solution but every (approximate) equilibrium of any game is far from every equilibrium of any other game in the family (in either player s strategy). Along the way, we strengthen the classical unconditional lower bound against enumerative algorithms for finding approximate equilibria due to Daskalakis-Papadimitriou and the classical hardness of computing equilibria due to Gilbow-Zemel.
AB - Computing Nash equilibrium (NE) in two-player game is a central question in algorithmic game theory. The main motivation of this work is to understand the power of sum-of-squares method in computing equilibria, both exact and approximate. Previous works in this context have focused on hardness of approximating “best” equilibria with respect to some natural quality measure on equilibria such as social welfare. Such results, however, do not directly relate to the complexity of the problem of finding any equilibrium. In this work, we propose a framework of roundings for the sum-of-squares algorithm (and convex relaxations in general) applicable to finding approximate/exact equilbria in two player bimatrix games. Specifically, we define the notion of oblivious roundings with verification oracle (OV). These are algorithms that can access a solution to the degree d SoS relaxation to construct a list of candidate (partial) solutions and invoke a verification oracle to check if a candidate in the list gives an (exact or approximate) equilibrium. This framework captures most known approximation algorithms in combinatorial optimization including the celebrated semidefinite programming based algorithms for Max-Cut, Constraint-Satisfaction Problems, and the recent works on SoS relaxations for Unique Games/Small-Set Expansion, Best Separable State, and many problems in unsupervised machine learning. Our main results are strong unconditional lower bounds in this framework. Specifically, we show that for = Θ(1/pol (n)), there’s no algorithm that uses a o(n)-degree SoS relaxation to construct a 2o(n)-size list of candidates and obtain an -approximate NE. For some constant, we show a similar result for degree o(log (n)) SoS relaxation and list size no(log (n)). Our results can be seen as an unconditional confirmation, in our restricted algorithmic framework, of the recent Exponential Time Hypothesis for PPAD. Our proof strategy involves constructing a family of games that all share a common sum-of-squares solution but every (approximate) equilibrium of any game is far from every equilibrium of any other game in the family (in either player s strategy). Along the way, we strengthen the classical unconditional lower bound against enumerative algorithms for finding approximate equilibria due to Daskalakis-Papadimitriou and the classical hardness of computing equilibria due to Gilbow-Zemel.
KW - Approximate equilibria
KW - Equilibria
KW - Lower bounds
KW - Oblivious rounding
KW - PPAD
KW - Sum-of-squares
UR - http://www.scopus.com/inward/record.url?scp=85049909858&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85049909858&partnerID=8YFLogxK
U2 - 10.1145/3188745.3188892
DO - 10.1145/3188745.3188892
M3 - Conference contribution
AN - SCOPUS:85049909858
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 114
EP - 122
BT - STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
A2 - Henzinger, Monika
A2 - Kempe, David
A2 - Diakonikolas, Ilias
PB - Association for Computing Machinery
Y2 - 25 June 2018 through 29 June 2018
ER -