Action-Graph Games

Representing and reasoning with games becomes difficult once they involve large numbers of actions and players, because utility functions can grow unmanageably. Action-Graph Games (AGGs) are a fully-expressive game representation that can compactly express utility functions with structure such as context-specific (or strict) independence, anonymity, and additivity. We show that AGGs can be used to compactly represent all games that are compact when represented as graphical games, symmetric games, anonymous games, congestion games, and polymatrix games. We further show that AGGs can compactly represent additional, realistic games that require exponential space under all of these existing representations. We give a dynamic programming algorithm for computing a player's expected utility under an arbitrary mixed-strategy profile, which can achieve running times polynomial in the size of an AGG representation. We show how to use this algorithm to achieve exponential speedups of existing methods for computing sample Nash and correlated equilibria. Finally, we present the results of extensive experiments, showing that using AGGs leads to a dramatic increase in the size of games accessible to computational analysis.