- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper suggests an empirical approach to structure the space of two-player normal-form games based on their solver dynamics. The authors construct a low-dimensional representation, an "atlas" with 12 dimensions, of the game space. The atlas is meant to preserve the distance structures of trajectories which were generated across 7 solvers and multiple configurations per solver. The goal of this representation is to capture structures of games and their behavior that extend beyond traditional analytical properties such as monotonicity, potentialness, zero-sum, etc. On top of that, a direct mapping between game payoff matrices and the low-dimensional representations is learned, which means that the behavior space can be directly linked to a game's definition.
The obtained representations are tested extensively based on information that can recovered from them. For example, the authors analyze if trajectory features by unseen solvers can be deduced from the atlas and if trajectory properties (exploitability, movement, recurrence, reversal) can be predicted based on neighboring games in the structure.
Critical strengths
-
Novelty: The overall idea of the paper is very intriguing: Instead of analyzing narrow classes of games (such as potential games), the authors suggest to learn representations that encode a more general behavior across all games empirically. I agree that many solvers share common behavioral patterns (this paper even quantifies that, see Fig. 2), and that the currently provided explanations are not sufficient for understanding the overall structure of all games. This paper is, to my knowledge, the first that applies this kind of representation learning with game theory, which is a novel step. Despite the concerns stated below, this alone is sufficient reason for me to (weakly) recommend this paper for acceptance, specifically in the context of ICLR.
-
I also appreciate the amount of empirical evidence provided. (I didn't go through all of the results in the appendix.)
-
Presentation: The overall exposition of the paper is clear, and its core ideas are presented intuitively. In particular, the three compression steps () are easy to understand on a high level.
Critical weaknesses
-
Motivation: Despite the interesting prospect of having an cartographical representation of all games, this paper leaves some motivational issues and contains some inconclusive results:
- It is unclear to me which direct benefits can be drawn from the atlas. Whereas potentialness, zero-sum, and monotonicity provide a direct convergence guarantee for certain algorithms that can be directly drawn from the game itself, the learned representation provide no such things. While the authors provide an analyis of behavior along a path of games, this does not provide a complete picture of the set of all games and why they do or do not converge. (I admit that this is a very difficult task.)
- The current analysis seems limited to small, square two-player games. These, by no means, represents the space of all games and possible dynamics. It would be interesting to see how the structure of games varies outside of this narrow field.
- The NMAE values reported in Fig. 3 do not seem convincing to me: If 1 is considered to be the baseline value, 0.8 does not appear to be particularly good.
-
Presentation: Given the complex implementation of the atlas training and evaluation steps, some parts of the paper remain elusive unless a reader spends substantial amount of time with the paper and its appendix.
- How was the corpus of games sampled? (This is partially addressed in the appendix.)
- Where exactly is the TEST set used?
- Recurrence and reversal are only explained in the appendix but are essential for understanding the paper. I would at least explain them in words in the main text.
- The size of the analyzed games is not stated in the main text.
- Figures 1 and 3 need further explanation. Many of the metrics/comparison methods used are either not explained or explained later/in the appendix.
The written text is sometimes quite condensed and difficult to follow. In particular, the paper is written for a very knowledgable reader: Many sentences contain words that are either subject-specific or require further context, which is often only provided in the appendix. Most readers will either have a background in game theory (such as myself) or in heavy-duty machine learning - combining both topics is an important step, which nonetheless requires taking care of both groups.
Questions for authors
Clarifications:
- Some of the solvers are quite similar. Are the LOSO results in Fig. 3 really that great?
- What are the comparison methods used in Figure 3?
- Can you provide any additional insights on the structure of game behavior based on your atlas?
- Why did you always withheld the recurrence and reversal traits? Couldn't they be used to reach a more informative atlas, while still being able to perform a leave--categories-out analysis?
Future work:
- Have you considered exploring other games with more players, non-square structure (), and more actions?
- Does your set of prototype games include any games with complex, potentially chaotic structure? The Kohlberg-Mertens game analyzed in a paper by Milionis et al. (https://doi.org/10.1073/pnas.2305349120) could be worth a look.
4 comments
Response to jtzv: Evaluation Protocol and Figure Clarifications
Corpus and held-out evaluation.
The principal experimental corpus contains 35,804 two-player normal-form games, with the main representation and transfer experiments using 3×3 games. We construct the corpus from canonical game families and interpolations between them to cover diverse structural settings. Separate cross-size experiments evaluate transfer to 4×4 and 5×5 games. TRAIN, DEV and TEST are separated by generative root so that variants of the same game do not cross splits. The main behavioural reference sets contain 2,048 TRAIN and 512 DEV games. The new evaluation uses 5,371 held-out TEST games, with the models and evaluation settings frozen beforehand. We will make the game size and split roles clearer in the main text.
Figures 1 and 3.
Figure 1 shows variation in GDA recurrence within structural categories. Recurrence measures whether a solver returns near earlier strategy states and is excluded from atlas construction. The learned atlas predicts it with MAE 0.049, compared with 0.100 for structural baselines (oracle: 0.029). Figure 3 compares Direct GNN, response graph, Candogan PH/PHN, NfgTransformer and our learned atlas across 20, 102 and 205 labelled reference games. Its rows distinguish full-library from LOSO evaluation; its columns distinguish source-derived from withheld behavioural quantities. Figure 3 uses Ridge readouts, whereas the aggregate TEST LOSO NMAE 0.694 reported in the main response uses 10-neighbour kNN. We will state this explicitly in the caption and text.
Why withhold recurrence and reversal?
The behavioural distance uses exploitability and step-to-step movement distributions at each iteration. It does not directly track whether individual runs revisit an earlier state (recurrence) or reverse their update direction (reversal). Excluding these quantities tests whether the geometry predicts behaviour beyond its construction signals. These quantities could be incorporated into a different atlas, but they would no longer provide the same test of predicting behaviour excluded from representation construction.
Interpreting NMAE.
NMAE measures prediction error relative to a constant-median predictor fitted on the same labelled reference games. An NMAE of 0.8 therefore represents a 20% reduction in prediction error, rather than an accuracy of 80%. Our main TEST result achieves NMAE 0.694, corresponding to approximately 31% lower error than the constant reference. We also report performance for individual solvers and behavioural targets, since these vary in predictability. The new neighbourhood and failure-localisation experiments provide complementary tests of whether the representation captures useful behavioural relationships.
What the atlas reveals beyond game structure.
Our additional within-potentialness analysis addresses the reviewer's question about what behavioural cartography contributes beyond analytical classifications. Even when neighbouring games are restricted to the same TRAIN-defined potentialness quartile, behaviour-supervised representations identify games with substantially more similar finite-time solver behaviour than the evaluated structural features. This demonstrates why analytical structure and empirical solver behaviour provide complementary information: games with comparable potentialness can still differ substantially in how a learning algorithm behaves over a fixed horizon.
Thank you for the clarifications and additional experiments. The cross-size transfer results are good, and the distinction between analytical guarantees and finite-time behavioural prediction is helpful. Please incorporate these clarifications into the main text. Two questions remain: How much does LOSO performance depend on similarity between the held-out and remaining solvers? And can you provide one concrete insight into game dynamics revealed by the atlas beyond improved prediction? The within-potentialness analysis is useful, but sharing a quartile does not imply equivalent analytical structure. Overall, I maintain my weak acceptance recommendation.
Thank you for revisiting our responses and for your constructive assessment. We will incorporate the cross-size results, the relationship to analytical guarantees, and the evaluation clarifications into the main text.
Dependence on solver similarity. Our paired-exclusion experiments directly test whether LOSO transfer relies on retaining a closely related solver. Excluding GDA and averaging/anchoring together yields TEST NMAE 0.536; excluding extragradient and optimistic gradient together yields 0.599. Thus, substantial predictive information remains even when these related mechanisms are jointly excluded from atlas construction.
Transfer is nevertheless heterogeneous: jointly excluding EMD and damped proximal gives NMAE 0.948. These findings show that nominal algorithmic-family similarity does not fully determine transfer, although they do not establish uniform generalisation across arbitrary solver families. We will make this distinction explicit in the manuscript.
A concrete insight into learning dynamics. Figure 5 provides an illustrative example beyond prediction accuracy. We continuously interpolate between zero-sum and common-interest payoffs while holding the endpoint games fixed. Along this path, measured GDA recurrence decreases sharply between adjacent mixtures at and , before gradually increasing towards the common-interest endpoint.
Thus, a smooth change in game payoffs can produce a rapid, non-monotonic change in the solver's finite-time dynamics. The behavioural atlas organises this variation and identifies the region of changing recurrent behaviour. This illustrates how empirical cartography can reveal dynamical regimes and transitions that are not directly specified by the structural interpolation itself.
We also agree that membership in the same potentialness quartile does not imply analytical equivalence. Our within-quartile experiment is intended as a controlled comparison against one structural descriptor, rather than an assertion that the games share identical convergence guarantees. We will clarify this distinction and highlight the controlled-interpolation example in the main text.
We appreciate your continued engagement with the paper.
Response to jtzv: Scope and Analytical Guarantees
We thank the reviewer for recognising the novelty of behavioural cartography and for asking how it relates to analytical results and extends to other game sizes.
What our approach adds to analytical game theory.
Properties such as potentialness and monotonicity can tell us when an algorithm has a convergence guarantee. Our aim is different: we study how algorithms actually behave when run for a fixed number of steps. Games with the same structural properties can still lead to different outcomes for a solver. Our atlas organises games by these observed differences.
The atlas also does more than visualise behaviour. It predicts recurrence (whether a solver returns near earlier strategy states) and reversal (whether its updates change direction). Neither property was used to construct the atlas. For example, the learned atlas predicts GDA recurrence with an MAE of 0.049, compared with 0.100 using structural game-category labels (Figure 1). Our controlled game-mixture experiments also show that the atlas tracks changes in behaviour as game structure varies.
Transfer to larger games.
We have also tested whether the representation works beyond the 3×3 games on which it was trained. We kept the learned payoff recogniser fixed and used only labelled 3×3 games as reference examples. In particular, there were no behavioural labels from the larger games and no retraining for those sizes. The resulting prediction errors are:
The values average over 35 solver–behaviour targets; the reported variation for the neural representations is across three seeds. Our atlas has the lowest average NMAE of these methods at both sizes, without using any labels from the larger games.
These results support two conclusions. First, the atlas captures useful differences in solver behaviour that structural game labels alone do not explain. Second, the learned representation remains informative when applied to the larger games we evaluated.
Our claims concern two-player normal-form games under the specified solver protocol. Games with unequal action sets, substantially larger games, and multiplayer settings are natural directions for extending this work.