Algorithms for Nash Equilibrium and Related Applications
- Xiaotie DENG (Principal Investigator)Department of Computer Science
DescriptionThis project studies algorithmic issues of the Nash Equilibrium problem, its computational method, as well as the related applications. The computational complexity of Nash Equilibrium has long been an open problem, and has been recently completely characterized as PPAD-complete, by Daskalakis, Goldberg and Papadimitriou for the case with four or more players, and finally, by Chen and the principal investigator for the two-player case.Such a result makes it an important issue for the study of approximation algorithms as well as the study of special cases. In addition, Nash equilibrium is the foundation of many important fields involved with many participants such as Economics and Social Sciences. The recent rise of the Internet, with many freewill participants, has also made Nash equilibrium, and related concepts, an important methodology in the study of e-commerce and e-community activities. The operational aspect of such activities demands fast and accurate solutions of those fundamental problems.In this project the investigators will study algorithmic issues of Nash equilibrium and its closely related fundamental problems, and the principles that govern their applications in Internet activities. They will also develop a prototype software system for practical computation of Nash and related fundamental problems.
|Effective start/end date||1/09/07 → 3/03/10|