Must-Read: : Computer Science Meets Economics: “Constantinos Daskalakis,[‘s]… dissertation… proves that computing the Nash equilibrium for a three-person game…
…is computationally intractable…. Consequently, Daskalakis argues, it’s unlikely that the real-world markets modeled by game theorists have converged on Nash equilibria either…. When computer scientists run up against an intractable problem, their first recourse is to investigate the tractability of approximate solutions to it. After his doctoral thesis, Daskalakis focused on importing notions of approximation from computer science into economics. First, he published several papers examining the computation of approximate Nash equilibria. Some of those results were disheartening: For general games, even relatively coarse approximations are still intractably hard to find…