A paper titled Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities by 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.
Turing's Invisible Hand 
It is a fascinating issue what should be the interpratation of hardness results regarding Nash equilibrium and now regarding market equilibria. (And also regarding, say models from physics.)It is also interesting were are at preset the main bottleneck in our inability to model (not even saying to predict) markets behavior: Is it 1) the rationality assumption and psychological effects? 2) computational limitations? 3) strategic behavior that compilcates immensly models like marker equilibria? 4) Non adequate quantitative model? 5) inadequate or missing stochastic analysis of current models?
Few comments/mostly questions:
Beautiful as they are, it seems to me that these models are perhaps the farthest from reality among models in AGT. I would love to know the reasons to the contrary.
Do these models have any bearing at all on the study of the real markets (even some micro-markets, forget about global markets and financial meltdown)? How do we know that the real markets are ever in equilibrium (assuming equilibrium is a meaningful concept in reality)? Is the study of centralized algorithms for equilibria supposed to be an exercise before we go on to distributed algorithms, because the real markets seem to be distributed?
What is the evidence that PPAD is a hard class? There was a discussion on this on Lance’s blog, and from what I remember the evidence was the lack of efficient algorithms.
Kamal’s catchphrase is some sort of Church-Turing hypothesis which seems reasonable but is perhaps a bit too confident.
I agree that positive results on finding equilibria (i.e. algorithms), should optimally be followed by “natural” distributed implementations. Negative results (PPAD-completeness) are interesting as-is and provide one technical reason why real markets cannot always be in equilibrium.
I don’t worry too much whether PPAD is hard or not — I simply view these results as showing computational equivalence to another set of problems.
[…] Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities by Xi Chen, Decheng Dai, Ye Du and Shang-Hua Teng. (A link to the paper and some discussion in this blog post.) […]