Settling the complexity of computing approximate two-player Nash equilibria

DOI10.1109/FOCS.2016.35MaRDI QIDQ6946474zbMATH OpenFDO

Authors Aviad Rubinstein

Publication date 6 August 2025

Full work available at URL https://doi.org/10.1109/FOCS.2016.35

Mathematics Subject Classification ID

Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Cited in

(10)

• Algorithms and complexity for computing Nash equilibria in adversarial team games
• Tree polymatrix games are PPAD-hard
• Automating approximation analysis for Nash equilibria algorithms in two-player games
• A polynomial-time algorithm for 1/3-approximate Nash equilibria in bimatrix games
• On the optimal mixing problem of approximate Nash equilibria in bimatrix games
• Pure-circuit: tight inapproximability for PPAD
• On the optimal mixing problem of approximate Nash equilibria in bimatrix games
• The strongish planted clique hypothesis and its consequences
• A computer-aided approach for approximate Nash equilibria
• Settling the complexity of Nash equilibrium in congestion games

This page was built for publication: Settling the complexity of computing approximate two-player Nash equilibria

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6946474)