Complexity of Bimatrix Nash Equilibria

Keywords and Synonyms

Two-player nash; Two-player game; Two-person game; Bimatrix game          

Problem Definition

In the middle of the last century, Nash [8] studied general non-cooperative games and proved that there exists a set of mixed strategies, now commonly referred to as a Nash equilibrium, one for each player, such that no player can benefit if it changes its own strategy unilaterally. Since the development of Nash's theorem, researchers have worked on how to compute Nash equilibria efficiently. Despite much effort in the last half century, no significant progress has been made on characterizing its algorithmic complexity, though both hardness results and algorithms have been developed for various modified versions.

An exciting breakthrough, which shows that computing Nash equilibria is possibly hard, was made by Daskalakis, Goldberg, and Papadimitriou [4], for games among four players or more. The problem was proven to be complete in PPAD(polynomial parity argument, directed...