Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities

Xi Chen, Decheng Dai, Ye Du, Shang-Hua Teng

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.
BibTeX
@inproceedings{chen2009settling,
  author = {Xi Chen and Decheng Dai and Ye Du and Shang-Hua Teng},
  title = {{Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities}},
  booktitle = {FOCS},
  year = {2009},
  doi = {10.1109/focs.2009.29},
}
Figure