The computation of approximate competitive equilibrium is PPAD-hard
From MaRDI portal
Publication:975493
DOI10.1016/j.ipl.2008.07.011zbMath1189.91090OpenAlexW2026871840MaRDI QIDQ975493
Publication date: 9 June 2010
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2008.07.011
Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) General equilibrium theory (91B50)
Cites Work
- Unnamed Item
- Exchange market equilibria with Leontief's utility: freedom of pricing leads to rationality
- Non-computability of competitive equilibrium
- On the complexity of the parity argument and other inefficient proofs of existence
- Excess demand functions, equilibrium prices, and existence of equilibrium
- Nash and Walras equilibrium via Brouwer
- A path to the Arrow-Debreu competitive market equilibrium
- The complexity of computing a Nash equilibrium
- On the complexity of equilibria
- Leontief economies encode nonzero sum two-player games
- Equilibrium points in n -person games
- Existence of an Equilibrium for a Competitive Economy