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.