Inapproximability of Nash Equilibrium

DOI10.1145/2746539.2746578zbMath1321.68320arXiv1405.3322OpenAlexW1991713925MaRDI QIDQ2941532

Aviad Rubinstein

Publication date: 21 August 2015

Published in: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1405.3322

zbMATH Keywords

Nash equilibriummarket equilibriumPPADCEEI

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Noncooperative games (91A10) Special types of economic equilibria (91B52) Approximation algorithms (68W25)

Related Items

kNN Classification with an Outlier Informative Distance Measure ⋮ Morphisms of open games ⋮ Approximating Nash Equilibria in Tree Polymatrix Games ⋮ Unnamed Item ⋮ Ex post Nash equilibrium in linear Bayesian games for decision making in multi-environments ⋮ Computing approximate Nash equilibria in polymatrix games ⋮ Zero-sum polymatrix games with link uncertainty: a Dempster-Shafer theory solution ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria ⋮ Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria

Uses Software

• Graphs

Cites Work

• Unnamed Item
• Ramsey partitions and proximity data structures
• On sparse spanners of weighted graphs
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• On Approximate Distance Labels and Routing Schemes with Affine Stretch
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Approximate distance oracles
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Near-Linear Time Construction of Sparse Neighborhood Covers
• Shortest-path queries in static networks
• Approximate distance oracles with constant query time
• Automata, Languages and Programming