Home → Magazine Archive → February 2009 (Vol. 52, No. 2) → The Complexity of Computing a Nash Equilibrium → Abstract

The Complexity of Computing a Nash Equilibrium

By Constantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou

Communications of the ACM, Vol. 52 No. 2, Pages 89-97

[article image]

Traditionally, computational problems fall into two classes: those that have a polynomial-time algorithm and those that are NP-hard. However, the concept of NP-hardness cannot be applied to the rare problems where "every instance has a solution."

The full text of this article is premium content


No entries found