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.