DocumentCode
1964378
Title
Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities
Author
Chen, Xi ; Dai, Decheng ; Du, Ye ; Teng, Shang-Hua
Author_Institution
Princeton Univ., Princeton, NJ, USA
fYear
2009
fDate
25-27 Oct. 2009
Firstpage
273
Lastpage
282
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.
Keywords
computational complexity; marketing; Arrow-Debreu equilibria; PPAD-complete; additively separable utilities; market-equilibrium problem; polynomial time; Computational complexity; Computer science; Nash equilibrium; Piecewise linear approximation; Piecewise linear techniques; Polynomials; Pricing; Programmable control; USA Councils; Arrow-Debreu markets; Computational complexity; PPAD-completeness;
fLanguage
English
Publisher
ieee
Conference_Titel
Foundations of Computer Science, 2009. FOCS '09. 50th Annual IEEE Symposium on
Conference_Location
Atlanta, GA
ISSN
0272-5428
Print_ISBN
978-1-4244-5116-6
Type
conf
DOI
10.1109/FOCS.2009.29
Filename
5438624
Link To Document