Computing Nash equilibria is intractable

We show that computing a Nash equilibrium is an intractable problem. Since by Nash’s theorem a Nash equilibrium always exists, the problem belongs to the family of total search problems in NP, and previous work establishes that it is unlikely that such problems are NP-complete. We show instead that the problem is as hard as solving any Brouwer fixed point computation problem, in a precise complexity theoretic sense. The corresponding complexity class is called PPAD, for Polynomial Parity Argument in Directed graphs, and our precise result is that computing a Nash equilibrium is a PPAD-complete problem.

In view of this hardness result, we are motivated to study the complexity of computing approximate Nash equilibria, with arbitrarily close approximation. In this regard, we consider a very natural and important class of games, called anonymous games. These are games in which every player is oblivious to the identities of the other players; examples arise in auction settings, congestion games, and social interactions. We give a polynomial time approximation scheme for anonymous games with a bounded number of strategies.

That is from the abstract of Constantinos Daskalakis's thesis [pdf], underlining emphasis mine. I had a tweet about this earlier this week, but I wanted to say a bit more about it. Since we can view the market as an algorithm to solve a computational problem (I like this blog post and there is also this paper), the market is probably not a Nash equilibrium. What is also interesting is that the Nash equilibrium problem is as hard as solving the Arrow-Debreu equilibrium problem (an application of the Brouwer fixed point theorem) ... although that shouldn't be surprising since the proof of existence of Nash equilibria can also proceed via Brouwer's theorem.

Daskalakis proceeds to look at algorithms to find approximate Nash equilibria, but this result makes me think that economic equilibria may not be even approximate Nash or Arrow-Debreu equilibria. The process of tâtonnement (an algorithm for finding approximate equilibria) would proceed until you reached either a satiation point (one all parties can live with) or simply the most likely point (the average of all possible system configurations) ... i.e. the maximum entropy point (see also this).

Also, one of the ways to "break" intractability is with randomness -- that is the idea behind Monte Carlo algorithms  -- see this old Scientific American article [pdf]. Remember when Scientific American was good?

Economists will probably just ignore this like they ignore the SMD theorem [Kirman, pdf], though.