Recent development in computational complexity characterization of Nash equilibrium

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

2 Scopus Citations
View graph of relations

Author(s)

  • Xi Chen
  • Xiaotie Deng

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)88-99
Journal / PublicationComputer Science Review
Volume1
Issue number2
Publication statusPublished - Dec 2007

Abstract

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.

Citation Format(s)

Recent development in computational complexity characterization of Nash equilibrium. / Chen, Xi; Deng, Xiaotie.

In: Computer Science Review, Vol. 1, No. 2, 12.2007, p. 88-99.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review