Game theory provides the basis for rational behavior in situations involving multiple agents. It provides the means for modeling the objectives of agents and the information available to them, and specifies notions of optimal strategic behavior. However, the practical use of game theory has hitherto been limited by the lack of efficient algorithms for computing optimal strategies, and of software tools for game analysis. In this project, several approaches are explored to develop effective game-theoretic solution algorithms. The approaches are unified in their use of structured representations. Similarities between game states are exploited by abstraction-based approximation methods; regularities in the creation and revelation of information are exploited by information-based decomposition methods; and the decomposition of a complex situation using a set of weakly interacting variables is exploited by factored representations.
In addition to the new algorithms, software tools are developed for the representation, solution and analysis of games. An innovative course on computational game theory is also developed. The impact of these methods, tools and educational materials will be to transform game theory from a theoretic tool for analyzing prototypical situations to a practical tool for designing strategic agents for real-world problems.
