The Complexity of Finding Nash Equilibria

Abstract

Computing a N ash equilibrium, given a game in normal form, is a fundamental problem for Algorithmic Game Theory. The problem is essentially combinatorial, and in the case of two players it can be solved by a pivoting technique called the Lemke–Howson algorithm, which however is exponential in the worst case. We outline the recent proof that finding a N ash equilibrium is complete for the complexity class PPAD, even in the case of two players; this is evidence that the problem is intractable. We also introduce several variants of succinctly representable games, a genre important in terms of both applications and computational considerations, and discuss algorithms for correlated equilibria, a more relaxed equilibrium concept. Introduction N ash's theorem – stating that every finite game has a mixed N ash equilibrium (Nash, 1951) – is a very reassuring fact: Any game can, in principle, reach a quiescent state, one in which no player has an incentive to change his or her behavior. One question arises immediately: Can this state be reached in practice? Is there an efficient algorithm for finding the equilibrium that is guaranteed to exist? This is the question explored in this chapter. But why should we be interested in the issue of computational complexity in connection to N ash equilibria? After all, a N ash equilibrium is above all a conceptual tool, a prediction about rational strategic behavior by agents in situations of conflict – a context that is completely devoid of computation.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 98 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.