Cette page appartient aux archives web de l'EPFL et n'est plus tenue à jour.
This page belongs to EPFL's web archive and is no longer updated.

Action graph games

Please comment on the following paper by April 4th before class. It is available from the course webpage.

A. Xiang, K. Leyton-Brown and N. Bhat, 2011, Action-graph games, Games and Economic Behavior, Vol 71, pp. 141-173

Posted by Katherine Skirving Larson on Tuesday 27 March 2012 at 14:08
This paper examines specific representation of games called action-graph games. AGG unifies characteristic of both graphical games and congestion games; it is fully-expressive and tends to be compact for many interesting structured games. The later property enables us to speed up the process of finding Nash equilibria for specific types of games.

The paper first describes basic action graph games, which is sometimes able to exploit anonymity and context-specific independence structure in games. Unfortunately, anonymity and context-specific independence structures are not always captured by the basic AAG. This drawback is circumvented by introducing function nodes. Special case of AGG with function node is when only simple agregator nodes are used. Authors show that representation size of the AGG-FN with simple agregate nodes is bounded by polynomial in the number of players, actions and function nodes. Moreover, when only utility functions of additive structure are taken into account, one can achieve even more compact representation (thus obtaining AGG -FN with additive structure). One important property of AGG-FNA is that it can encode congestion game with no loss of compactness.

The importance of having compact AGG is best seen when it comes to calculating an agent's expected payoff. The paper shows that there exist efficient algorithms for computing expected payoff if the AGG (AGG-FN, AGG-FNA) representation is compact enough. Since many algorithms for finding Nash equilibrium contain expected payoff as an inner loop-problem, efficient calculation can significantly speed up the process. It is not surprising that the complexity of finding Nash equilibrium for AGG is in PPAD, just as it is for normal form representation. Therefor there should be some benefits of working with AGG representation. Authors experimentally show that this indeed happens: for particular classes of structured games (graphical games, symmetric games, anonymous games, congestion games), one can achieve exponential speedup of existing methods for computing Nash equilibria by exploiting the possibility that expected utility for AGG representation is easier to calculate.
Posted by Goran Radanovic on Sunday 1 April 2012 at 23:57
This paper presents Action-graph Games (AGG), an alternative way of representing games which is claimed to be expressive enough and compact. In this paper, the authors give a lot of example to show how it works; a very nice approach to attract readers' interest.
Action-graph Games, is outlined from the basics (Basic Action Graph Games) up to the recent advancement, Action Graph Games - Function Nodes with Additive Structures (AGG-FNAs). AGG-FNAs enable us to define utility functions as decision trees, logic programs, circuits, or even another algorithms. This is what missing in conventional utility representation.
Not only present the representation, but in this paper the authors also present algorithms and complexity analysis in computing an agent's expected utility and finding an e-Nash equilibrium of an AGG (since finding Nash equilibrium for a game with more than 2 players could involve irrational numbers).
In section 6, to anticipate readers' doubt the authors present the experimental results, comparing the performance of AGG with the normal form representation (in terms of representation size, time to compute expected utility and equilibria).
All in all, this representation has been proven to be yet another useful way to represent games together with its expressiveness and compactness. In addition, it would be interesting to see how to use AGG on a repeated game.
Posted by Tri Kurniawan Wijaya on Tuesday 3 April 2012 at 12:07