How Hard Is It to Approximate the Best Nash Equilibrium?

DOI10.1137/090766991zbMath1229.91092OpenAlexW2069488552WikidataQ57567488 ScholiaQ57567488MaRDI QIDQ2999855

Elad Hazan, Robert Krauthgamer

Publication date: 17 May 2011

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: http://epubs.siam.org/sicomp/resource/1/smjcat/v40/i1/p79_s1

zbMATH Keywords

Nash equilibriumcliquerandom graphtwo-player gameapproximate equilibriumpolynomial-time approximation schemealgorithmic game theory

Mathematics Subject Classification ID

2-person games (91A05) Combinatorics in computer science (68R05) Applications of game theory (91A80) Computational methods for problems pertaining to game theory, economics, and finance (91-08)

Related Items (20)

A Direct Reduction from k-Player to 2-Player Approximate Nash Equilibrium ⋮ Computing equilibria: a computational complexity perspective ⋮ If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser ⋮ Approximating Nash Equilibria and Dense Subgraphs via an Approximate Version of Carathéodory's Theorem ⋮ Optimal detection of sparse principal components in high dimension ⋮ On the Number of Iterations for Dantzig--Wolfe Optimization and Packing-Covering Approximation Algorithms ⋮ The Ehrenfeucht-Fraïssé Method and the Planted Clique Conjecture ⋮ Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation ⋮ Inapproximability Results for Approximate Nash Equilibria ⋮ Statistical and computational limits for sparse matrix detection ⋮ On perfect Nash equilibria of polymatrix games ⋮ A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem ⋮ On the hardness of designing public signals ⋮ Inapproximability results for constrained approximate Nash equilibria ⋮ Abstracting Nash equilibria of supermodular games ⋮ Approximating the existential theory of the reals ⋮ Approximating the existential theory of the reals ⋮ Inapproximability of NP-Complete Variants of Nash Equilibrium ⋮ Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning ⋮ Computational barriers in minimax submatrix detection

This page was built for publication: How Hard Is It to Approximate the Best Nash Equilibrium?