Comment of the Day: C. Trombley: Computer Science Meets Economics: “Highly misleading headline… It has only been shown that Nash is PPAD-Complete — not NP, which is something that needs to be mentioned. It’s still mathematically possible that Nash is in P! Daskalakis’s paper is interesting enough that an honest summary is deserved. Further, though NP is considered the gold standard of hard, map programs have to solve them everyday. Therefore, the economic philosophy consequences are vague at best. For those who want to think economists are fools: If computational complexity is bad, then tractability is good, right? Look at another class of economic models — convex programming. That’s in P — Kantorovich had an algorithm for it in polynomial time. But read Shalizi’s Kantorovich essay. The practical problems are there. So it can’t be computational complexity that is objectionable…. The write-up is superficial and inaccurate. Nash is now known PPAD-complete, so the relation to P (tractability) is technically unknown. Unless P=NP, it is known — trivial even — that it cannot be NP-complete. This result important but not surprising, as Papadimitriou realized PPAD was interesting exactly because Nash was in it. The biggest hint as to tractability comes from another Papadimitriou paper: any constructive form of Brouwer that depends only on function evaluations must be exponential in the worst case. Since Nash and Brouwer are equivalent, you see the same result. Weakenings of Nash such as correlated equilbria are tractable. What does that mean? I don’t know. What the consequences of tractability are is something deeply unclear. We don’t stop using maps because using them is an NP-Complete problem, after all. Algorithmic mechanism design is facsinating, deep and deserves better reporting than this.

Originally published on bradford-delong.com