Xi Chen, Decheng Dai, Ye Du, and Shang-Hua Teng was recently posted to the arXiv.
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.
This paper is part of a recent line of work of the community that looks at reaching market equilibria as a computational problem. The catchy phrase due to Kamal Jain is: If your laptop can’t find it, neither can the market and the point of view is that such inability of reaching market equilibrium casts some doubt on the whole use of the equilibrium as a predictive model. Chapters 5 and 6 of the algorithmic game theory book survey what is known. The current paper basically shows that even very simple special cases, “all traders use additively separable, piecewise-linear and concave utility functions”, are hard computationally — as hard as general computation of (the computational version of) Brower fixed points.