Representation and Learning in Computational Game Theory

Game theory has emerged as the key tool for understanding and designing complex multiagent environments such as the Internet, systems of autonomous agents, and electronic communities or economies. To support these relatively recent uses of game theory — as well as for more ambitious modeling in some of the traditional application areas — there is a growing need for a computational theory that is largely absent from classical game theory research. Such a computational theory needs to provide a rich and flexible collection of models and representations for complex game-theoretic problems; powerful and efficient algorithms for manipulating and learning these models; and a deep understanding of the algorithmic and resource issues arising in all aspects of game theory. The overarching goal of the proposed work is to “scale up ” the applicability of game theory, in much the same way that Bayesian networks and associated advances made complex, high-dimensional probabilistic modeling possible in a wide set of applications in computer science and beyond. Two of the most important topics that have materialized to date — and the primary emphases of the current proposal — are the representation and efficient manipulation of large and complex games, and new approaches to learning in game-theoretic settings. On the topic of representation, the proposal includes the development of methods to model structured interaction in large-population games; the intersection of social network theory and game theory; new representations in repeated games; and representational issues for