Inapproximability of Nash Equilibrium

DOI10.1137/15M1039274zbMath1396.68060WikidataQ129645837 ScholiaQ129645837MaRDI QIDQ4571923

Aviad Rubinstein

Publication date: 4 July 2018

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

zbMATH Keywords

Nash equilibriummarket equilibriumhardness of approximationPPADapproximate competitive equilibrium form equal incomes

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 (14)

On the Complexity of Equilibrium Computation in First-Price Auctions ⋮ Communication complexity of approximate Nash equilibria ⋮ Coordination Games on Weighted Directed Graphs ⋮ A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games ⋮ PPAD-complete approximate pure Nash equilibria in Lipschitz games ⋮ Public goods games in directed networks ⋮ PPAD-complete pure approximate Nash equilibria in Lipschitz games ⋮ Unnamed Item ⋮ Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds ⋮ Computing exact solutions of consensus halving and the Borsuk-Ulam theorem ⋮ The Hairy Ball problem is PPAD-complete ⋮ Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem ⋮ The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich ⋮ Consensus Halving for Sets of Items

Cites Work

• Unnamed Item
• Exponential lower bounds for finding Brouwer fixed points
• On the complexity of the parity argument and other inefficient proofs of existence
• General equilibrium and the theory of directed graphs
• The query complexity of correlated equilibria
• Non-cooperative games
• Can Almost Everybody be Almost Happy?
• On the Complexity of Approximating a Nash Equilibrium
• Computing Approximate Nash Equilibria in Polymatrix Games
• The Computational Complexity of Nash Equilibria in Concisely Represented Games
• Market equilibrium under separable, piecewise-linear, concave utilities
• Approximating Nash Equilibria in Tree Polymatrix Games
• Settling the complexity of computing two-player Nash equilibria
• Market equilibrium via the excess demand function
• Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities
• The Complexity of Computing a Nash Equilibrium
• Query complexity of approximate nash equilibria
• Approximate Nash Equilibria for Multi-player Games
• The complexity of non-monotone markets

This page was built for publication: Inapproximability of Nash Equilibrium