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

Simple item page
dc.creatorChen, Xi
dc.creatorDai, Decheng
dc.creatorDu, Ye
dc.creatorTeng, Shang-Hua
dc.date2009-04-03
dc.date.accessioned2026-07-07T13:00:36Z
dc.date.available2026-07-07T13:00:36Z
dc.descriptionWe 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.
dc.identifierhttps://arxiv.org/abs/0904.0644
dc.identifierhttp://arxiv.org/abs/0904.0644
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/225889
dc.subjectComputational Complexity
dc.subjectComputer Science and Game Theory
dc.titleSettling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities
dc.typetext

Files

Collections

arXiv