Inapproximability of Nash equilibrium
From MaRDI portal
Abstract: We prove that finding an -approximate Nash equilibrium is PPAD-complete for constant and a particularly simple class of games: polymatrix, degree 3 graphical games, in which each player has only two actions. As corollaries, we also prove similar inapproximability results for Bayesian Nash equilibrium in a two-player incomplete information game with a constant number of actions, for relative -Well Supported Nash Equilibrium in a two-player game, for market equilibrium in a non-monotone market, for the generalized circuit problem defined by Chen, Deng, and Teng [CDT'09], and for approximate competitive equilibrium from equal incomes with indivisible goods.
Recommendations
Cites work
- Approximate distance oracles
- Approximate distance oracles with constant query time
- Automata, Languages and Programming
- Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
- Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
- Fast C-K-R partitions of sparse graphs
- Near-Linear Time Construction of Sparse Neighborhood Covers
- On approximate distance labels and routing schemes with affine stretch
- On sparse spanners of weighted graphs
- Ramsey partitions and proximity data structures
- Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
- Shortest-path queries in static networks
Cited in
(30)- Undecidability of the existence of pure Nash equilibria
- Ex post Nash equilibrium in linear Bayesian games for decision making in multi-environments
- Inapproximability results for constrained approximate Nash equilibria
- Zero-sum polymatrix games with link uncertainty: a Dempster-Shafer theory solution
- Morphisms of open games
- Inefficiency of the Nash equilibrium for selfish machine covering on two hierarchical uniform machines
- Can almost everybody be almost happy?
- On the complexity of approximating a Nash equilibrium
- Inapproximability results for approximate Nash equilibria
- Inapproximability of NP-Complete Variants of Nash Equilibrium
- A direct reduction from k-player to 2-player approximate Nash equilibrium
- Approximating Nash equilibria in tree polymatrix games
- Nash Equilibria: Where We Stand
- Inefficiency of Nash Equilibria
- Inapproximability of Nash equilibrium
- scientific article; zbMATH DE number 6866322 (Why is no real title available?)
- scientific article; zbMATH DE number 6866347 (Why is no real title available?)
- Hardness results for consensus-halving
- Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria
- kNN Classification with an Outlier Informative Distance Measure
- Computing approximate Nash equilibria in polymatrix games
- Finding a Nash equilibrium is no easier than breaking Fiat-Shamir
- Tight SoS-degree bounds for approximate Nash equilibria
- Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria
- PPAD-complete pure approximate Nash equilibria in Lipschitz games
- Separable Network Games with Compact Strategy Sets
- Complexity of equilibria in first-price auctions under general tie-breaking rules
- Tight inapproximability of Nash equilibria in public goods games
- Computing constrained approximate equilibria in polymatrix games
- Smooth Nash equilibria: algorithms and complexity
This page was built for publication: Inapproximability of Nash equilibrium
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2941532)
