A new paper, Reducibility Among Fractional Stability Problems, by Shiva Kintali, Laura J. Poplawski, Rajmohan Rajaraman, Ravi Sundaram, and Shang-Hua Teng was just uploaded to the arXiv. The paper proves PPAD-completeness for half a dozen problems, from various domains of application, all related to stability. The simple interpretation of PPAD-completeness is that these problems are shown to be computationally equivalent to computational variants of Brower’s fixed point theorem or to finding a Nash-equilibrium.
While I can not say that I am specifically interested in any of these problems, I do think that this type of methodological characterization of the complexity of problems related to stability and equilibrium is important. It maps the space of such problems, separating variants that have some special structure from those whose are general enough to hide within them the general problem. Maybe it is time for someone to maintain a compendium of PPAD-complete problems? (In the spirit of the compendium of NP-optimization problems.) My favorite entry would be Nash equilibrium for 2-player win-lose games.
Turing's Invisible Hand 
I started a compendium of PPAD-complete problems. It is still under construction. Hopefully I will have it ready with more details soon.
Great!
One nice example not in the compendium is 2D-Sperner proved PPAD-complete by Chen and Deng
Thanks. Added 2D-Sperner to the compendium.
[…] Reducibility Among Fractional Stability Problems by Shiva Kintali, Laura Poplawski, Rajmohan Rajaraman, Ravi Sundaram and Shang-Hua Teng. (A link to the paper and some discussion in this blog post.) […]