Action-Graph Games

• 成果类型: Article
• 署名作者: Jiang, Albert Xin; Leyton-Brown, Kevin; Bhat, Navin A. R.
• 署名单位: University of British Columbia; University of Toronto
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2010.10.012
• 发表日期: 2011
• 页码: 141-173
• 关键词: Game representations; Graphical Models; Large games; Computational techniques; Nash equilibria

摘要

Representing and reasoning with games becomes difficult once they involve large numbers of actions and players, because the space requirement for 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 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, as well as games that require exponential space under all of these existing representations. We give a polynomial-time algorithm for computing a player's expected utility under an arbitrary mixed-strategy profile, and show how to use this algorithm to achieve exponential speedups of existing methods for computing sample Nash equilibria. We present results of experiments showing that using AGGs leads to a dramatic increase in the size of games accessible to computational analysis. (2) (C) 2010 Elsevier Inc. All rights reserved.