Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities
arXiv:0904.0644
Abstract
We prove that the problem of computing an Arrow-Debreu market equilibrium is PPAD-complete even when all traders use additively separable, piecewise-linear and concave utility functions. In fact, our proof shows that this market-equilibrium problem does not have a fully polynomial-time approximation scheme unless every problem in PPAD is solvable in polynomial time.
Cited by in corpus (5)
- A Complexity View of Markets with Social Influence
- The Complexity of Non-Monotone Markets
- Spending is not Easier than Trading: On the Computational Equivalence of Fisher and Arrow-Debreu Equilibria
- Non-Separable, Quasiconcave Utilities are Easy -- in a Perfect Price Discrimination Market Model
- Constant Rank Bimatrix Games are PPAD-hard