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

DOI10.1145/3188745.3188892zbMath1428.68163OpenAlexW2809314237MaRDI QIDQ5230377

Pravesh K. Kothari, Ruta Mehta

Publication date: 22 August 2019

Published in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3188745.3188892

zbMATH Keywords

lower boundsequilibriasum-of-squaresoblivious rounding

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Noncooperative games (91A10) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (4)

A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games ⋮ A Polynomial-Time Algorithm for 1/3-Approximate Nash Equilibria in Bimatrix Games ⋮ Unnamed Item ⋮ Unnamed Item

This page was built for publication: Sum-of-squares meets Nash: lower bounds for finding any equilibrium