Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities
Lists
Only you see this
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},
}