Recent development in computational complexity characterization of Nash equilibrium

The computation of Nash equilibria has been a problem that spanned half a century that has attracted Economists, Operations Researchers, and most recently, Computer Scientists. The study of its complexity, in particular that of the two-player game, has come to a conclusion recently. It is, however, impossible without the subsuming ideas from important progresses made in the various fronts of its investigation. In this article, we present a review of the most relevant ideas, methods, and results in a way that would lead interested readers to get a full picture of the subject. We will also discuss some new issues opened up by the characterization of complexity for the two-player Nash equilibrium problem. © 2007 Elsevier Ltd. All rights reserved.