Sum-of-Squares meets Nash: Optimal Lower Bounds for Finding any Equilibrium.
Pravesh K. KothariRuta MehtaPublished in: CoRR (2018)
Keyphrases
- lower bound
- nash equilibrium
- worst case
- game theory
- finding optimal
- optimal cost
- upper bound
- nash equilibria
- pareto optimal
- dynamic programming
- optimal solution
- equilibrium strategies
- search algorithm
- lower and upper bounds
- branch and bound
- constant factor
- game theoretic
- branch and bound algorithm
- incomplete information
- np hard
- cooperative