CAIAC

Game theory is a mathematical theory of games, which are systems with multiple, self-interested agents. In the last decade, there has been much research at the interface of computer science and game theory. One important class of problems at this interface is the computation of solution concepts of a finite game, which predict the likely outcomes of the game under certain assumptions of rationality of the agents. In order to take advantage of the highly-structured utility functions in games of practical interest, it is important to design compact representations of games as well as efficient algorithms for computing solution concepts using such representations.

In this thesis I present several novel contributions in this direction. These include the design and analysis of novel compact representations: Action-Graph Games (AGGs) for representing static games (in which agents make decisions simultaneously), Temporal Action-Graph Games for representing dynamic games (in which agents make decisions in sequence) and Bayesian Action-Graph Games for representing Bayesian games (in which agents are uncertain about the underlying game). These representations generalize and unify existing compact representations proposed in the literature. Furthermore I show that we can leverage these compact representations to exponentially speed up existing algorithms for the computation of solution concepts inculding Nash equilibrium.

I also present several novel algorithms for efficient computation of solution concepts given compactly-represented games. We propose a polynomial-time algorithm for computing pure-strategy Nash equilibria in symmetric AGGs with bounded treewidth. Correlated equilibrium is another important solution concept. In a landmark paper, Papadimitriou and Roughgarden described a polynomial-time algorithm ("Ellipsoid Against Hope") for computing sample correlated equilibria of compactly-represented games. However it was recently shown that this algorithm can fail to find an exact solution. I present a variant of the Ellipsoid Against Hope algorithm that guarantees the polynomial-time identification of exact correlated equilibrium. We also analyze the problem of computing an optimal correlated equilibrium according to some linear objective. We prove a sufficient condition for the tractability of the optimal correlated equilibrium problem, and using it we are able to identify new classes of games for which the optimal correlated equilibrium problem is tractable.