TY - JOUR
T1 - Recent development in computational complexity characterization of Nash equilibrium
AU - Chen, Xi
AU - Deng, Xiaotie
PY - 2007/12
Y1 - 2007/12
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=36048963968&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-36048963968&origin=recordpage
U2 - 10.1016/j.cosrev.2007.09.002
DO - 10.1016/j.cosrev.2007.09.002
M3 - RGC 21 - Publication in refereed journal
SN - 1574-0137
VL - 1
SP - 88
EP - 99
JO - Computer Science Review
JF - Computer Science Review
IS - 2
ER -