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.
April 10, 2009 at 11:27 pm |
I started a compendium of PPAD-complete problems. It is still under construction. Hopefully I will have it ready with more details soon.
April 11, 2009 at 1:20 pm |
Great!
April 11, 2009 at 8:51 am |
One nice example not in the compendium is 2D-Sperner proved PPAD-complete by Chen and Deng
April 12, 2009 at 8:03 pm |
Thanks. Added 2D-Sperner to the compendium.
July 2, 2009 at 6:32 pm |
[...] 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.) [...]