  It is a common belief that computing a market equilibrium in Fisher's
spending model is easier than computing a market equilibrium in Arrow-Debreu's
exchange model. This belief is built on the fact that we have more algorithmic
success in Fisher equilibria than Arrow-Debreu equilibria. For example, a
Fisher equilibrium in a Leontief market can be found in polynomial time, while
it is PPAD-hard to compute an approximate Arrow-Debreu equilibrium in a
Leontief market.
  In this paper, we show that even when all the utilities are additively
separable, piecewise-linear, and concave functions, finding an approximate
equilibrium in Fisher's model is complete in PPAD. Our result solves a
long-term open question on the complexity of market equilibria. To the best of
our knowledge, this is the first PPAD-completeness result for Fisher's model.
