Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities
- Xi Chen ,
- Decheng Dai ,
- Ye Du ,
- Shang-Hua Teng
MSR-TR-2009-49 |
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.