Following the call for nominations for the prize in February 2008 from the Society President, Peyton Young, Ehud Kalai chaired, at the request of Peyton Young, the prize committee that included Silvio Micali of MIT and Yoav Shoham of Stanford, to determine the Prize winner(s), and reports (July 21, 2008):

Chairing the prize committee was not an easy task. Not because of the people on the committee, they were wonderful to work with, and not because there were no good submissions, but because there were so many outstanding submissions.

The Decision of the committee reads as follows:

We are pleased to announce that the winner of the 2008 prize is “The Complexity of Computing a Nash Equilibrium,” by Constantinos Daskalakis, Paul W. Goldberg and Christos H. Papadimitriou (2006).

This paper made key conceptual and technical contributions in an illustrious line of work on the complexity of computing Nash equilibrium, e.g., Gilboa and Zemel (1989), Conitzer and Sandholm (2003) and Chen and Deng (2006). It also highlights the necessity of constructing practical algorithms that compute equilibria efficiently on important subclasses of games, e.g., Govindan and Wilson (2004), Bárány, Vempala and Vetta (2005) and Porter, Nudelman and Shoham (2008).

We are also pleased to include honorable mentions to “How Bad is Selfish Routing” by Roughgarden and Tardos (2002), an outstanding example of the measurement of the inefficiency of Nash equilibrium, and to “Program Equilibrium” by Tennenholtz (2004), which uses computer-science concepts to substantially enrich standard game-theoretic modeling.

Signed by the members of the committee:

Ehud Kalai   Silvio Micali   Yoav Shoham

References

  • Bárány, I., S. Vempala and A. Vetta, “Nash Equilibria in Random Games,” Foundations of Computer Science, 2005.
  • Chen, X., and X. Deng, “Settling the Complexity of 2-Player Nash-Equilibrium,” Foundations of Computer Science, 2006.
  • Conitzer, V. and T. Sandholm, “Complexity Results about Nash Equilibria”, Proceedings of IJCAI, 2003.
  • Daskalakis, C., P. W. Goldberg and C. H. Papadimitriou, “The Complexity of Computing a Nash Equilibrium,” The Symposium on the Theory of Computing, 2006.
  • Gilboa, I. and E. Zemel, “Nash and Correlated Equilibria: Some Complexity Results,” Games and Economic Behavior, 1989.
  • Govindan S. and R. Wilson, “Computing Nash equilibria by iterated polymatrix approximation,” Journal of Economic Dynamics and Control, 2004.
  • Porter, R. W., E. Nudelman and Y. Shoham, “Simple Search Methods for Finding a Nash Equilibrium,” Games and Economic Behavior, forthcoming 2008.
  • Roughgarden, T. and E. Tardos, “How Bad is Selfish Routing,” Journal of the ACM, 2002.
  • Tennenholtz, M., “Program Equilibrium,” Games and Economic Behavior, 2004.