Sum-of-squares meets nash: lower bounds for finding any equilibrium.

Pravesh K. Kothari Ruta Mehta

Published in: STOC (2018)

Keyphrases

lower bound
nash equilibrium
nash equilibria
game theory
upper bound
equilibrium strategies
worst case
np hard
branch and bound
optimal solution
lower and upper bounds
branch and bound algorithm
game theoretic
social welfare
utility function
online algorithms
quadratic assignment problem
optimal cost