Abstract:

The Internet owes much of its complexity to the large number of entities that run it and use it. These entities have different and potentially conflicting interests, so their interactions are of a strategic nature. Therefore, to understand these interactions, concepts from Economics and, most importantly, Game Theory are necessary. An important such concept is the notion of Nash equilibrium , which provides us with a rigorous way of predicting the behavior of strategic agents in situations of conflict. But the credibility of the Nash equilibrium as a framework for behavior-prediction depends on whether such equilibria are efficiently computable. After all, why should we expect a group of rational agents to behave in a fashion that requires exponential time to be computed? Motivated by this question, we study the computational complexity of the Nash equilibrium .

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.