Action-Graph GamesAlbert Xin Jiang∗Kevin Leyton-Brown†Navin A.R. Bhat‡AbstractRepresenting and reasoning with games becomes difficult once they involve large num-bers of actions and players, because utility functions can grow unmanageably. Action-GraphGames (AGGs) are a fully-expressive game representation that can compactly express util-ity functions with structure such as context-specific (or strict) independence, anonymity, andadditivity. We show that AGGs can be used to compactly represent all games that are com-pact when represented as graphical games, symmetric games, anonymous games, congestiongames, and polymatrix games. We further show that AGGs can compactly represent addi-tional, realistic games that require exponential space under all of these existing representa-tions. We give a dynamic programming algorithm for computing a player’s expected utilityunder an arbitrary mixed-strategy profile, which can achieve running times polynomial in thesize of an AGG representation. We show how to use this algorithm to achieve exponentialspeedups 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 dramaticincrease in the size of games accessible to computational analysis.1Keywords: game representations, graphical models, large games, computational tech-niques, Nash equilibria.JEL classification codes: C63—Computational Techniques, C72—Noncooperative Games.1 IntroductionSimultaneous-action games have received considerable study, which is reasonable as these gamesare in a sense the most fundamental. Most of the game theory literature presumes that simultaneous-action games will be represented in normal form. This is problematic because in many domainsof interest the number of players and/or the number of actions per player is large. In the nor-mal form representation, the game’s payoff function is stored as a matrix with one entry foreach player’s payoff under each combination of all players’ actions. As a result, the size of therepresentation grows exponentially with the number of players.Fortunately, most large games of practical interest have highly-structured payoff functions,and thus it is possible to represent them compactly. Intuitively, this helps to explain why peopleare able to reason about these games in the first place: we understand the payoffs in terms ofsimple relationships rather than in terms of enormous lookup tables. One thread of recent workin the literature has explored game representations that are able to succinctly describe games ofinterest. In some sense, nearly every game form besides the normal form itself can be seen as∗Department of Computer Science, University of British Columbia. [email protected]†Department of Computer Science, University of British Columbia. [email protected]‡Department of Physics, University of Toronto. [email protected] gratefully acknowledge Moshe Tennenholtz for his co-authorship of a paper on Local Effect Games [Leyton-Brown & Tennenholtz, 2003], an action-centric graphical model for games that inspired our work on AGGs.1such a compact representation. For example, the extensive form allows games with temporalstructure to be encoded in exponentially less space than the normal form. In what follows,however, we concentrate on game representations that are compact even for simultaneous-movegames of perfect information.Perhaps the most influential class of compact game representations is those that exploit strictindependencies between players’ utility functions. This class includes graphical games [Kearnset al., 2001; Kearns, 2007], multi-agent influence diagrams [Koller & Milch, 2003], and gamenets [LaMura, 2000]; we focus on the first of these. Consider a graph in which nodes correspondto agents and an edge from one node to another represents the proposition that the first agent isable to affect the second agent’s payoff. If every node in the graph has a small in-degree—thatis, if each agent’s payoff depends only on the actions of a small number of others—then thegraphical game representation is compact, by which we mean that it is exponentially smallerthan its induced normal form. Of course, there are any number of ways of representing gamescompactly. For example, games of interest could be assigned short ID numbers. What makesgraphical games important is the fact that computational questions about these games can beanswered by algorithms whose running time depends on the size of the representation rather thanthe size of the induced normal form. (Note that this property does not hold for the naive IDnumber scheme.) To state one fundamental property [Daskalakis et al., 2006a], it is possible tocompute an agent’s expected utility under an arbitrary mixed strategy profile in time polynomialin the size of the graphical game representation. This property implies that a variety of algorithmsfor computing game-theoretic quantities of interest, such as sample Nash [Govindan & Wilson,2003; van der Laan et al., 1987] and correlated equilibrium, can be made exponentially fasterfor graphical games without introducing any change in the algorithms’ behavior or output [Blumet al., 2006; Papadimitriou, 2005]. Furthermore, graphical games are also computationally well-behaved in other ways; efficient algorithms exist for computing other quantities of interest forthese games such as Nash equilibria on restricted graphs [Kearns et al., 2001; Elkind et al.,2006] or subject to a fairness criterion [Elkind et al., 2007], pure Nash equilibrium [Daskalakis& Papadimitriou, 2006], ǫ-Nash equilibrium [Kearns et al., 2001; Vickrey & Koller, 2002], andevolutionary stable strategies [Kearns & Suri, 2006].A drawback of the graphical games representation is that it only helps when there exist agentswho never affect some other agents’ utilities. Unfortunately, many games of interest lack anystructure of this kind. For example, nontrivial symmetric games are cliques when representedas graphical games. Another useful form of structure not generally captured by graphical gamesis dubbed anonymity; it holds when each agent’s utility depends only on the number of agentswho took each action, rather than on these agents’ identities.2Recently, researchers such asPapadimitriou and Roughgarden [2005], Kalai [2005] and Daskalakis and Papadimitriou [2007]have explored the representational, computational and
View Full Document
Unlocking...