This award is funded under the American Recovery and Reinvestment Act of 2009.
A sequential game is a mathematical model of the interaction of multiple self-interested players in dynamic stochastic environments with limited information. The long-term goal of this research project is to design and implement specialized algorithmic tools for the computation of the main solution concept for these games, namely Nash equilibria. The initial phase of the project will concentrate on two-person zero-sum sequential games. The Nash equilibria formulation for this special class of sequential games can be stated as a highly structured saddle-point problem and is amenable to modern smoothing and interior-point techniques for convex optimization. Advanced phases of the project will tackle the more challenging problems of computing equilibria for games with more than two players as well as refinements of Nash equilibria such as sequential, perfect and quasi-perfect equilibria.
The algorithmic advances of this research project have immediate application in the design of automatic game players, which is a topic of major interest in artificial intelligence. At a more fundamental level, the availability of algorithmic technology for equilibria computation will provide new tools for rational decision making in complex dynamic environments such as those encountered in financial markets, multi-user computing networks, political negotiations, and military operations.
