Abstract
Action-Graph Games (AGGs) (Bhat & Leyton-Brown 2004) are a fully expressive game representation which can compactly express strict and context-specific independence and anonymity structure in players' utility functions. We present an efficient algorithm for computing expected payoffs under mixed strategy profiles. This algorithm runs in time polynomial in the size of the AGG representation (which is itself polynomial in the number of players when the in-degree of the action graph is bounded). We also present an extension to the AGG representation which allows us to compactly represent a wider variety of structured utility functions.
Introduction
In classical game theory, games are often represented in "normal form"—essentially a massive multi-dimensional lookup table (a matrix) containing every possible outcome for every player. The primary challenge with this representation is its exponential growth: a game with 10 players each having 5 choices requires storing nearly 10 million entries. For 20 players, the memory requirements become physically impossible.
However, most real-world strategic interactions are not unstructured. They typically exhibit anonymity (a player's utility depends on how many others chose an action, not their specific identities) and context-specific independence (local interactions matter more than distant ones). Action-Graph Games (AGGs) were designed to capture this structure. Despite their compactness, computing expected payoffs—a fundamental step for finding Nash equilibria—remained computationally expensive until the development of the polynomial-time algorithm discussed here.
Methods: Exploiting Structure for Efficiency
The researchers introduced two key innovations to make AGGs scalable:
1. Dynamic Programming with Tries
Instead of the naive approach of summing over every possible combination of player actions, the authors developed a Dynamic Programming (DP) algorithm. This algorithm processes one agent at a time, building up the probability distribution of configurations. To manage this efficiently, they utilize a trie (prefix tree) data structure to store and look up these distributions. When the "in-degree" of the action graph—the number of actions that directly affect a specific payoff—is bounded, this algorithm achieves polynomial time complexity relative to the number of players.
2. Action Graph Games with Function Nodes (AGGFNs)
To further enhance compactness, the authors extended the AGG framework by introducing "function nodes." These nodes act as intermediate aggregators that simplify the dependency structure.
As shown in Figure 1, function nodes (represented by white circles) can aggregate information from multiple actions. In a spatial competition model like a "Coffee Shop Game," a player’s utility might depend on the total number of shops in a neighborhood. Rather than a payoff node tracking every individual neighboring block, it observes a single function node that sums these values. This reduces the effective in-degree of the graph, significantly shrinking the representation size.
Experimental Evaluation
The algorithm was evaluated using the Coffee Shop Game, a synthetic benchmark simulating spatial competition on an $r \times c$ grid. The performance was compared against GameTracer, a state-of-the-art tool for normal-form games.
Key Results
The results demonstrate a clear transition from exponential to polynomial scaling.
As illustrated in Figure 2, the normal-form approach (NF) fails to scale beyond five players due to memory and time constraints. In contrast, the AGG algorithm handles 16 players with ease. Furthermore, when the number of players is fixed and the number of actions (grid rows) increases, the AGG algorithm's runtime grows roughly linearly, whereas the normal-form method exhibits higher-order polynomial growth.
Discussion and Future Work
The primary constraint of this approach is the in-degree of the action graph. In "dense" games where every action choice uniquely affects every other player's payoff, the complexity $O(n^I)$ can still become prohibitive.
While this work focuses on the fundamental task of computing expected payoffs, it provides the necessary building blocks for more advanced solvers. Future research aims to fully integrate this algorithm into Nash and correlated equilibrium solvers. Additionally, expanding the AGGFN framework to support more complex, non-linear aggregators beyond "contribution-independent" functions (like sum or max) remains an open challenge.
Summary updated