NfgTransformer: Equivariant Representation Learning for Normal-form Games
Authors: Siqi Liu
Luke Marris
Georgios Piliouras
Ian Gemp
Nicolas Heess
Venue: ICLR 2024 poster (2024)
Keywords: Game Theory
Deep Learning
Representation Learning
Nash Equilibrium
Primary area: general machine learning (i.e., none of the above)
TL;DR: We present a general-purpose, equivariant representation learning architecture for normal-form games.

Abstract: Normal-form games (NFGs) are the fundamental model of *strategic interaction*. We study their representation using neural networks. We describe the inherent equivariance of NFGs --- any permutation of strategies describes an equivalent game --- as well as the challenges this poses for representation learning. We then propose the NfgTransformer architecture that leverages this equivariance, leading to state-of-the-art performance in a range of game-theoretic tasks including equilibrium-solving, deviation gain estimation and ranking, with a common approach to NFG representation. We show that the resulting model is interpretable and versatile, paving the way towards deep learning systems capable of game-theoretic reasoning when interacting with humans and with each other.

Published as a conference paper at ICLR 2024
NEGTRANSFORMER, EQUIVARIANT REPRESENTATION LEARNING FOR NORMAL-FORM GAMES
Siqi Liu Luke Marris Georgios Piliouras', Ian Gemp', Nicolas Heess?
Gooole DeepMind, University College London {liusiqi, marris, gpil, imgemp, heess @google com
ABSTRACT
Normal-form games (NFGs) are the fundamental model of strategic interaction. We study their representation using neural networks. We describe the inherent equivariance of NFGs any permutation of strategies describes an equivalent game - as well as the challenges this poses for representation learning. We then propose the Nfg ofgTTransformed architecture that leverages this equivariance, lead- ing to state-of-the-art performance in a range of game-theoretic tasks including equilibrium-solvingg deviation gain estimation and ranking, with common ap- proach to NFG representation. We show that the resulting model is interpretable and versatile, paving the way towards deep learning systems capable of game- theoretic reasoning when interacting with humans and with each other.
INTRODUCTION
Representing data in learned embedding space, representation learning, is one of the time- less ideas of deep learning. Foundational representation learning architectures (LeCun et al. [995] Hochreiter & Schmidhuber] 1997| Vaswani al., 2017) have provided performance and general- ity, bringing together researchers who used to work on expert systems targeting narrow domains. Consider Convolutional Neural Networks (CNNs): by exploiting the translation invariance inherent to images, CNNs replaced feature descriptors underpinning tasks as diverse as image classification, segmentation and in-painting, leading to paradigm shifts across the field.
One area of research that has resisted this trend is game theory. Here, we see two striking similar- ities to classical computer vision research. First, active research topics such as equilibrium solving (Vlatakis- Gaaiiiis--aaaggouuiss et al. (220). ranking (Balduzzi et al. 2018), social choice theory (Anshele- vich et al. (202T) and population learning (Lanctot et al., 2017) all focus on specialised solutions, despite sharing the common language of normal-form games (NFGs). Second, task-specific so- lutions suffer from fundamental limitations. The popular Elo ranking algorithm (Elo) 2008), for instance, assigns scalar rating to each player derived from an NFG between players. Although Elo ratings are designed to be predictive match outcomes, they are poor predictors beyond transitive games the Elo score is simply too restrictive representation to reflect cyclic game dynamics. Im- provements to Elo followed (Bertrand et al.) 2023), but all relied on engincered feature descriptors, instead of learning. In equilibrium-solvve two-player zero-sum games (Daskalakis et al. (209)) yet approximate solvers are non-differentiable,, take -on-deterministic amount of time to converge, struggle to parallelise, and can fail. These fun- damental limitations have indirect consequences too. An entire line of works in tabular multiagent reinforcement learning (RL) (Littman et al., 2001; Hu Wellman 2003, Greenwald et al., 2003) relied on equilibrium solving as part of their learning rules an NFG is constructed from agents' Q-tables in each state, whose equilibrium informs subsequent policy updates. Unfortunately, re- viving these ideas in the context of deep RL has been challenging, if not impossible, as it requires equilibrium solving as a subroutine in between every gradient update.
computing exact Nash equilibria is intractable beyond
Indeed, we not the first to recognise these limitations. Several recent works incorporated repre- sentation learning implicitly, in narrow domains Maarris et al. 2022, Duan et al. 2023 Vadori & Savani 2023). We address these limitations explicifly and in generality. Our goal is to develop prin- cipled, general- purpose representation of NEGs that can be used in a wide range of game-theoretic
'The model is open-sourced at htttps::/gtttbb.cooo
e- deepmi nd httpgngtaaattaaaaooonnneeo

---

Published as a conference paper at ICLR 2024
applications. We ask 1) which property, if any, could we leverage for efficient representation learning of NFGs without loss of generality and 2) can we expect performance in a range of game-theoretic tasks using common approach to representing NFGs. We answer both questions affirmatively and propose NfgTrranfformr,, a general-purpont representation learning architecture with state-of-the-ar performance in tasks diverse as equilibrium solving, deviation gain estimation and ranking.
In its most basic form, strategic interactions between players are formulated as NFGs where players simultaneously select actions and receive payoff's subject to the joint action. Strategic interactions are therefore presented as payoff tensors, with values to each player tabulated under every joint ac- tion. This tabular view of strategic interactions presents its own challenges to representation learn- ing. Unlike modalities such as images and text whose spatial structure can be exploited for efficient representation learning (LeCun et al.] 1995, Hochreiter & Schmidhuber 1997), the position of an action in the payoff tensor is unimportant: permuting the payoff matrix of any NFG yields an equíva- lent game an equivalency known as strongly isomorphic games (MeKinsey 195T Gabarró et al.) 2011) This inherent equivariance to NFGs has inspired prior works to compose order-invariant pooling functions in the neural network architecture for efficiency, albeit at the expense of the gen- erality of the representation (Feng et al., 2021 Marris et al. 2022
We aim to leverage this inherent equivariance of NFGs while preserving full generality of the learned representation. This implies several desiderata that we discuss in turn. First, the representation needs to be versatile, allowing for inquiries at the level of individual actions, joint-actions, per-player or for the entire game. Second, it needs to be equívariant: for any per-action inquiry, the outputs for two actions should be exchanged if their positions are exchanged in the payoff' tensor. Third, the embedding function should not assume that outcomes of all joint-actions are observed the representation should accommodate incomplete NFGs in a principled way. Fourth, the function should apply to games of different sizes. This implies that the number of network parameters should be independent from the size of the games (Hartford et al. 2016p. Finally, it would be desirable if the network architecture interpretable, allowing for inspection at different stages of the network.
In the rest of this paper, we show how our proposed encoder architecture, Nfg WigTransformer, satisfies all these desiderata simultaneously. The key idea behind our approach to consider the embedding function class that represents NFG action embeddings, reversing the generative process from actions to payoffs. Action embeddings can be suitably composed to answer questions at different granularities and allows for equivariance in straightforward way permutations of actions or players in the payoff tensor shall be reflected as a permutation in the action embeddings. We ar- gue that Nfg Transformer is competitive candidate for general-purpose equivariant representation learning for NFGs, bridging the gap between deep learning and game-theoretic reasoning.
BACKGROUND
Normal-form Games NFGs are the fundamental game formalism where each player p simulta-
neously plays one of its T actions Op E {ap................. T = Ap and receives a payoff Gp : A + R as a function of the joint action = (a),..., aN) E A of all N players. Let a = (ap, a-p) with a-p (..., ap+1- 1: ...) A- the actions of all players except p. Let a(a) = (ap, a-p) denote the probability of players playing the joint action a and a probability distribution over the space of joint actions A. A pure strategy is an action distribution that is deterministic when a mixed- strategy can be stochastic. The value to player under is given as Eaza Ea (Gp(ap a-p)]- We refer to the payoff tensor tabulated according to the action and player ordering above as G.
Nash Equilibrium (NE) Under a mixed joint strategy that factorises into an outer product of marginals a = 2 Tn player p's unilateral deviation incentive is defined as
(a) = max E of A, amaa
[Gp(0 a.p) -Gp(a)].
(1)
A factorisable mixed joint strategy We refer to this quantity as the NE GAP as it intuitively measures the distance from to an NE of
op is e-NE if and only if 6(0) max, (a) <
the game. A mixed-strategy NE is guaranteed to exist for a finite game Nashh 1951] but exactly computing a normal-form NE beyond two-player zero-sum is PPAD-complete (Chen et al. 2009 Daskalakis et al. 2009). If a is deterministic with (a) = 1, then 5(a) or equivalently d(a) defines the maximum deviation gain of the joint pure-strategy a. a is pure-strategy NE when 6(a) 0.
2

---

Published as a conference paper at ICLR 2024
Permutation Equivariance Consider strong isomorphism & G G' NFGS (Gabarró al. 2011 with & ((Tp, w)) Tp dj oj player action permutation and player permutation. Elements of the transformed game G' ((G) are therefore given
Guip) (Tw(I)(Ou()): .... Tu(N)((u(N))) Gp(an, aN).
An encoder f: f (A ...... AN), with A, -aa , the action embeddings for player p. is said to be equivariant if
ag))
f(o(G)) = (AI...., A with Al(r) (Fp(a))) ................................ Tp(a,)
Here slightly abuse the notation of Tp to operate over action embeddings. Intuitively, permutation equivariance implies that @ and f commute, or [(((G)) = ((J())- We adopt the convention that the player permutation applied after player action permutations Tp. Vpp
Multi- Head Attention We describe self- and cross-attention QKV mechanisms that have become ubiquitous thanks to their generality and potential scaling (Vaswani et al. 2017 Dosovitskiy al. 2021 Jaegle et al. 202T). Both operations extend the basic QKV attention mechanism as follows:
QKKT Vdn
Attention(Q. K, V) softmax
with Q E Re K R and E xd, the ng queries and nig key-value pairs. Concep- tually, the attention mechanism outputs a weighted sum of nı values for each of ny query vectors, whose weights are determined by pairwise dot product between the key and query vectors. The output is of shape Xd, The inputs QKV are outputs from fully-connected networks themselves, with Q function of zq E Xdee and K, V projected from the same input The E R Rdu.d The attention operation is: 1) order-invariant with respect Tkoi and 2) equivariant with respect to 2q. These are the key properties we leverage in the design of the Nfg NfgTransformer to achieve its permutation equivariance property. We refer to an attention layer as self-attention when Tg is the same Tku, and cross-attention if not. In practice, each attention layer may have H attention heads performing the attention operation of Equation S in parallel. This enables the attention layer aggregate multiple streams of information in one forward pass.
EQUIVARIANT GAME REPRESENTATION
While we have informally motivated the need for equivariant embedding functions, we formally state two practical implications of equivariant embedding function that follow from a general theorem on the conditions under which two actions must have identical embeddings given embedding function. For conciseness, we defer all formal statements and proofs to Appendix A Proposition 3.1 (Repeated Actions), If Ga a-p) = G(ad, app, Va-p and f is deterministic and equivariant with f(G (..., (...,,pp.... app.... .......)..... then it follows that aj = a/.-
equivariant
Proposition 3.2 (Player Symmetry). If player and q are symmetric, f is deterministic and equiv- ariant with f(G) ,..., Ap.... Ag....), then Ap and Aq are identical up to permutation.
Proposition 3.1 guarantees by construction that repeated actions are treated identically in any down- stream applications. Proposition 3.2 guarantees that player symmetry are reflected in the action embedding space which we show empirically in Section 5.3 for the Níg Transsorrrmrr
4 NrGTRANSFORMER
We now describe the NigTransformer, an encoder network that factorises a payoff tensor into ac- tion embeddings via a sequence of K Nfg Transformrrr blocks (Figure I (Top)), each composed of sequence of self- and cross-attention operations (Figure | (Bottom)). We then show concrete exam- ples of decoders and loss functions in Figure 2 for several camee-heoretic tasks at different decoding granularities, showing the generality of our approach. Finally, we discuss how the NfgTransfone naturally incorporates incomplete payoff tensors leveraging the flexibility of attention operations.
3

---

Published as a conference paper at ICLR 2024
Nfg TrgTrrssformrr
Inttia action embeddiings
Final ambeddings
[0] Wi e [N]]
Nfg TigT
x K
{a WE (T.
Action-to-jointe to--ooon-oanniioonnn
Action-to-play
Action-to-action
QKV
KV
OKV
Self Attention
(nt. )up) Va-p) For each of N actore
Cross Attention
Self Attention
(comcut(ay: (p(
re-arranging
A
For each of joint- joint-actionss actions
each of
(p (ap. a vp}
For each of NkT actions
For each of 1N loint-actonss
NigTransformerBlock
An overview the NigTransformer. The payoff tensor G is encoded as action embeddings {a Vt E Vp E [N] (Top). Action embeddings zero-initialised and iteratively updated through a sequence of NfgTransformer blocks (Bottom). An arrow labeled with "(Q)KV" orig- inates from of input (query-)key-vall) and terminates denotes an unordered set of elements of a specific type and cardinality.
Figure 1:
of outputs. Each dashed box
4.1 INITIALISATION & ITERATIVE REFINEMENT
Permutation equivariance implies that action embeddings must be agnostic to how players and ac- tions are ordered in the payoff tensor. This suggests that action embeddings across players and actions must be initialised identically. We zero-initialise all action embeddings A = {aa = 0 Vt Pp E [N] with a,, R.,. Upon initialisation, action embeddings iteratively refined via a sequence of blocks given current action embeddings and the payoff tensor G. Each block returns updated action embeddings via self- and cross-attention operations that describe in turn.
action-to-joont--cctin self-attention represents play of each action Op under a joint-action (ap, a-p) given payoff values to all players. Recall the definition of self-attention operation, Th Ske = (concat(ap: Gp(a))] yielding one vector output per action for every joint-action. We refer to the output p (ap, amp)) play of a under the joint action and payoff's G;
action-to-play cross-attention then encodes information from all plays of each action af. with key-values Tke = (a a-p) Va-p) and x { singleton query. This operation yields singleton output, {a ). function of all its plays and its input action embedding vector;
action-to-action self-attention then represents each action given all action embeddings. Here, Tg = Zke = {at Vp [N], Vt E [T]}- We ablate this operation (by varying A) in Section 5.1 showing its benefits in propagating information across action embeddings.
Within each block, equivariance is preserved given key-value order-invariance, and query equiv- ariance properties of the attention operation. Each output embedding a' function of its own embedding at input, its unordered set of plays, and the unordered set of all action embeddings.
4.2 TASK-SPECIFIC DECODING
The resulting action embeddings can be used for a variety of downstream tasks at different decoding granularities. We describe and empirically demonstrate three use-cases in specifics (Figure 2
4

---

Published as a conference paper at ICLR 2024
maxp (p(0ppp)
L2(8(a), max, 6p(a))
In(G,(a),
Task-specific loss functions
O softmax(ut) pmp............
b(a) MLP ap) For each T joint-actions
Cx(a))
each of joint-actions
For each of N players
Max deviation-gain estimation
Self Attention
QKV
(a) Vt [ [N]
ML)(
For each of T joint-actions
For each of NxT actions
NigTranstormer
a,y
Nash equilibrium solving
Payoff reconstruction
Figure 2: Example task-specific decoders and losses from general-purpore action embeddings.
Nash equilibrium-solving requires decoding at the level of each action, estimating a marginal action distribution for each player op softmax pp..... w)²) ( where w MLP(a,,) is the logit for action a, Here, we follow Duan et al. 2023) in minimising the loss function max (p) end- to-end via gradient descent with = 8p6p and (ō) maXa,EA, Earo (Gplo a-p) - Gy(a)].
Max deviation-gain estimation decodes a scalar estimate for each joint-action a (a1,-.., a,), Va A. Here, represent each joint action imum deviation gain 8(a) by minimising T2(ō((),, max,
Ep ap and estimate its max- 5p (a)) = (δ(a) max, (a)) with (a) = maxo;eA,,1 (G,, (ap a-p) - Ga(a) the deviation gain to player under the joint action a.
Payoff reconstruction decodes a scalar for each payoff value G,(a), Vp E [N]. Ya e A. Here self-attention operation for decoding, similar the action-to-joint-action self-attention operation the encoder but without appending to action embeddings their payoff values, which are to be reconstructed. To compute reconstruction loss, we minimise L2 Lz((G(a), Gp(a)). with Gp(a) function of the action embedding ap and the unordered of co-player action embeddings a-p.
4.3 REPRESENTING INCOMPLETE GAMES
We have assumed thus far that outcomes for every joint-action the game are observed. This is not always the case in practice the costs of evaluating every joint-action can be prohibitive. Instead, one may infer outcomes for all joint-actions, given an incomplete NEG (El 2008). With a slight modification, the Nfg Trgarassfrre accommodates such use-cases in a principled way. To do so, extend the vanilla attention implementation (Equation 3 to allow for additional binary mask vectors m, 10 and m&r E {0, 1) for the query and key-value inputs, indicating their validity. Equation defines this masked attention operation, with 1 (1)
and (0) oo.
(QKT QOKT 10 (m, & mau) Vdl
MaskedAAttemtionn( Q, K, V, myg, m = softmax
(4)
To represent incomplete NFGs, we use the Equation in lieu of Equation 3 in all self- and cross- attention operations and set masking vectors accordingly. For instance, if a joint-action is unob- served, then one would set myy to reflect the validity of each play for the action-te to-ool operation. The NigTransformer architecture is highly effective for representing actions incomplete games and predict payoff's for unobserved joint-actions,
show empirically in Section 5.2
5

---

Published as a conference paper at ICLR 2024
5 RESULTS
The goal of our empirical studies is three-fold. First, compare the NigTransformer to baseline architectures to demonstrate improved performance in diverse downstream tasks on synthetic and standard games. Second, we vary the model hypper-prrmeetes and observe how they affect perfor- mance. We show in particular that some tasks require larger action embedding sizes while others benefit from more rounds of iterative refinement. Lastly, we study how the model learned solve certain tasks by interpreting the sequence of learned attention masks in a controlled setting. Our results reveal that the solution found by the model reflects elements of intuitive solutions to NE- solving in games. For completeness, we discuss additional empirical results in Appendix D For instance, we show all nontrivial equilibriun-invariant 2x2 games are embedded following structure of the known embedding space proposed in Marris et al. (203)).
5.1 SYNTHETIC GAMES
Table I: We compare Nfg NigTransformer to baseline architectures in synthetic games. Each configura-
tion is averaged across 5 independent runs. For Nfg' Trgnsffoorrrrr variants (Ours), we annotate each variant with corresponding typer-parameters (K, A and as shown in Figure D. We provide train- ing curves with confidence intervals and parameter counts of each configuration in Appendix B.1
NE (NE Gap)
Max- Deviation Gain (MSE)
Model
N=2
N=2
N=3
N=3
N=2
N=2
N=3
N=3
T=16
T=64
T=8
T=16
T=16
T=64
T=8
T=16
Ours (D= 32, 02,
0.2239
0.1685
0.1344
0.0796
0.0949
0.5008
0.5206
0.6649
Ours (D= 32, A=1,
0.0466
0.1096
0.0892
0.0553
0.0248
0.3755
0.3679
0.6173
Ours (D= 32, A=)
0.0344
0.0554
0.0484
0.0334
0.0067
0.2989
0,3582
0.5825
Ours (D= 64,K=8,A=0
0.0332
0.0661
0.0636
0.0384
0.0056
0.1549
0.2848
0.5583
Ours (D= 64,K=8,A11
0.0308
0.0545
0.0478
0.0325
0.0007
0.0784
0.1830
0.4961
Ours (D= K=8
0.0243
0.0542
0.0437
0.0314
0.0005
0.0759
0.1942
0.4725
Ours (D=118, K-2,A-1)
0,2090
0.1665
0.1274
0.0769
0.0159
0.1922
0.3154
0.5357
Ours (O> (D=122, K-4,A-1)
0.0429
0.0981
0.0804
0.0530
0.0013
0. 0.1361
0.0955
0.4153
Ours (I>- (DD-128, K-,,
0.0308
0.0502
0.0412
0.0297
0.0001
0.0161
0,0487
0.3641
EquivariantMLP
0.2770
0.2132
0.1431
0.0929
0.1789
0.8153
0.5433
0.7914
MLP NES
0.3905
0.3248
0.1741
0.1381
0.3854
0.83554
0.5623
0.7906
0.0829
0.1635
0.1478
0.1140
0.0488
0.4860
0.4047
0.6480
We first evaluate variations of the NfgTransformer architecture on synthetic games of varying sizes on NE equilibrium-solving and deviation gain estimation. To generate synthetic games with broad coverage, we follow Marris et al. (022) which samples games from the ceulibbruum-invariinn subspace, covering all strategic interactions that can affect the equilibrium solution of NFG. Each game's payoff tensor G has zero-mean over other player strategies and Frobenius norm
|| VTNN We compare our results to baseline MLP networks with numbers of parameters at least that of our largest transformer variant (at 4.95M parameters), an equivariant MLP network that re-arragess actions in descending order of their average payoffs, as well as an NES (Marris et al.) See Appendix B.T for details on game sam- pling, network architectures and parameter counts of each model. We note that the parameter count of the Nfg NigTraasformrr independent of the game size, a desideratum of Hartford et al. (2016).
2022) network that designed for equilibrium-solvine
5.1.1 SOLVING FOR NE EQUILIBRIUM
For equilibrium solving, we optimise variants of the NfgTransformer minimise the NE GAP 5(0) = max, x (ō) (Figure 2 (Left)). Table [ (Left) shows our results. EquivariantMLPP outper- forms MLP (Duan et al. 2023). , demonstrating the importance of leveraging equivariance inherent to NFGs but remains ineffective at solving this task. NES MMrris et al. 2022). equivariant by construction, significantly outperforms both MLP variants in 2- 2-player settings but trails behind in 3- player games. The Nfg NigTransformer is also equivariant by construction but learns to capture relevant information without handcrafted payoff feature vectors. All Nfg Transformer variants, most at fewer parameter count than baselines, significantly outperform across game sizes with near-zero NE GAP.

---

Published as a conference paper at ICLR 2024
Z
P- 10.00%
P-36.67%
P- 63.30%
P 80.00%
p- 10.00%
P-3667%
P- P-63.205
P- 90.00%
Mean Squared Erer (MSB)
0.00
Mean Squerdd Eror (MSS))
0.04-
0.02
<0
Our
Gur.
Curs
nB.
Ous-
9c
cue.
B6
Cun
Figure 3: Payoff prediction error averaged over all players across unobserved joint-actions.
Results
are averaged over 32 randomly sampled empirical DISC games in each game configuration.
Among the NigTransformer variants, our results show clear trend: increasing the number of trans- former blocks (with K E [2.....& ,8) improves performance, especially as the game becomes large. This makes intuitive sense, as it adds to the number of times the action embeddings can be usefully refined - action embeddings at the end of one iteration become more relevant queries for the next. In contrast, the benefit of increased action embedding size is muted (with D E [32,... 128)). We hypothesise that for equilibrium-solvvee often be ignored through iterative refinement (e.g. dominated actions), they do not contribute to the final equilibrium solution. Lastly, we evaluate an Nfg NigTrrasffrmmr variant that does not perform any action-to-action self-attention (A 0). In this case, action embeddings for the same player do not interact within the same block and its performance is markedly worse. Of particular interests is and A 2 where A 2 demonstrates bene- fits in the most complex games of size 16 x 16 x 16 but not in smaller games. This suggests that action-to- to-acion self- aelf-attention facilitates learning, especially in tasks that require iterative reasoning.
information related to a subset of the available actions can
the comparison between the variants with A
5.1.2 ESTIMATING MAXIMUM DEVIATION GAINS
A related task is to determine what the maximum incentive for any player to deviate from a joint pure-strategy (or equivalently, joint-action). This quantity is informative on the stability of joint behaviour - in particular, if joint pure-strategy has maximum deviation gain 8(a) of zero, then by definition we have found a pure-strategy NE. We optimise NigTrrasforrmrr network to regress towards the maximum deviation action decoder architecture (Figure 2 (Middle)). We report the regression loss in mean squared error of different architecture variants in Table I (Right). We observe that NES consistently outperforms MLP baselines, but underperforms the Níg Transformer variants as the size of the game increases.
d(a) for every joint pure-strategy a, using a per joint-
Similar to our observations in Section 5.1.I the number of transformer blocks played role in transformer variants' final performance. However, it is no longer the main factor. Instead, the action eetion-embedding size D becomes critical. Variants with higher embedding size D = 128 can be competitive, even for shallow models (e.g. K = 4 16 16 x 16 games). This can be explained by the lack of structure in the underlying game, as payoff tensors cover the full squilibrium-invarian subspace of NFGs: payoffs one joint-action does not provide any information on the outcomes of another. To perform well, the model must learn to memorise outcomes of different roint-actions reduced action embedding size can become a bottleneck.
5.2 PAYOFF PREDICTION IN EMPIRICAL DISC GAMES
What if the game class follows a structured generative process? This is often the case in practice and useful representation learning method should capture any such latent structure. We turn to Disc games (Balduzzi et al. 2019) to evaluate the efficacy of Tranffoforre in this case, compared to several payoff prediction methods from the ranking literature.
Definition 5.1 (Disc Game), Let ur U, E t [Z'], the win-probability to action i when playing against j is defined as P.j a (u, Dj uz v,) - P;; with (Ir 1+e-z the sigmoid function.
Definition 5.1 deseribes class of symmetric two-player zero-sum games where the outcomes defined by Jatent vectors u₁ v, E ? E [T], generalising the original definition of DIsC game (Balduzzi et al. 2019) allow for latent vectors with Z 1. Payoff values under joint-action

---

Published as a conference paper at ICLR 2024
Action to plays
Payoff
block
blook
block
block
block
block
block
block
Approx.
NE
Action embeddings (PCA)
01000
block
block
14ppe
XX
X
X0
payoff
action
player
1
O2 O8 04 O6
Oe 07 0
V
(NE Gap - 4.6e-06)
Figure 4: Visualisation of attention masks and action-embeddings at inference time on a held-out instance of Bertrand Oligopoly game whose payoff tensor is shown the Left and the inferred NE strategy profile shown on the right (with NE GAP at near zero). The equilibrium pure-strategies for the two players are shown in red. The sequence of action-to- tt--lay attention masks and the PCA- reduced action-embes seiion-mmeddiings at the end of each transformer block are shown in the middle.
therefore become informative for predicting the outcomes of others. The amount of information that be inferred about one joint-action from knowing another is controlled by the latent vector dimension Z. The problem setting as follows. Each algorithm is given access to an empirical game where outcomes for each joint-action is observed with probability The goal is to accurately predict the outcome to each player under unobserved joint-actions.
A rich body of literature have been dedicated to solving this task owing to its relevance in real-world competitions. In Go and Chess, players are classically assigned Elo ratings which are designed be predictive of the win-probabilityy between any two ranked players. Several improvements to Elo have been proposed since, recognising the many limitations Elo. We compare our results methods such as Elo (Elo 2008), mElo (Balduzzi et al. 2018) and xElo (Bertrand et al., (023) across different settings of the DISC game. Figure 5 shows our results in MSE averaged across unobserved joint-actions. NigTransformer outperforms all baselines significantly across all settings. recovered the latent variable game (i.e. Z = 1) near perfectly as
In particular, NfgTraasformn soon as 10% of the joint-actions are observed, with an error rate an order of magnitude lower than the second best method. This result is particularly remarkable as baseline methods are designed with DISC games mind, when Nrgnrfnsformer is not. At Z = 8, NfgTransformer continues to outperform, with its prediction accuracy degrading gracefully Our results suggest that Níg Transformer is highly effectively at recognising and exploiting the latent structure in games if it exists. We provide details game sampling. masking, network architecture and baseline implementation in Appendix [.2] For Nfg Vig.rrasforrmer outcomes of the unobserved joint-actions masked out following the procedure described in Section 4.3 At training time, the model minimises reconstruction loss for all joint-actions.
fewer joint actions observed.
5.3 INTERPRETING NEGTRANSFORMER
Nfg Transformer explicitly reasons about action reriidne through structured attention mechanism, allowing for inspection at each stage of the iterative refinement process. We exploit this property and investigate how the model implements game-theoretic algorithms such as equilibrium-solf
in a suite of 22 GAMUT games representing diverse strategic interactions (Nudelman et al. 2204 Porter et al. 2008 that are classically studied in the economics and game theory literature. We optimised an Nfg Transformer network in Section 5.1 but focused on 10 10 games and removed the action-to- action self-attention (i.e. = 0) for more concise visualisation. Instead of attending to multiple pieces of information in parallel, each attention layer is implemented by single attention head
8

---

Published as a conference paper at ICLR 2024
(H 1). We show in Appendix C that this simplified architecture is sufficient in approximating NE in games of this size to reasonable accuracy. We visualise the network on held-out games.
Figure 4 iillustrates instance of iterative NE solving in game of Bertrand Oligopoly in action. The Nig Nigrrassformrr successfully identified a pure-strategy NE (Right) with near zero NE GAP (Top-Right). Inspecting the payoff tensor (Left), verify that player 0 playing action 2 and player countering with action 1 is indeed a pure-strategy NE. Is this solution reflected the underlying attention mechanism? Indeed, the action-to-plays attention masks (Top) appear to have converged to a recurring pattern where each action attends to the equilbrrimm-straeegy of its co-player. This remarkable for two reasons, First, NE by definition implies indifference across action choices when co-players implement the equilibrium strategy. the focal player should be indifferent to its action choice. Here, this indifference played out. Second, an equilibrium solution should be stable which appears to be the case over the last few iterations of setion-to-playy attentions. Zooming in on the attention masks at earlier iterations, we see that following sero-initialisation of all action embeddings, the attention mask for each action is equally spread across all its plays. The attention masks at the next block, by contrast, appear structured. Indeed, each action attends to the play that involves the best-response from the co-player. It is worth noting that this pattern of attending to one's best-response in NE-solving emerged through learning, without prior knowledge.
The action embeddings themselves also reveal interesting properties of the game, such sym- metry (Proposition 3.2). While it might not be immediately obvious that the payoff matrices in Figure 3 can be made symmetric by permuting actions, the action embeddings (Bottom) show that action-embeddings across the two players overlap exactly, thanks to the inherent equivariance of the NfgTransformmr.. The ordering of players and actions unimportant the representation of an action is entirely driven by its outcomes under the joint-actions. Here, action embeddings revealed the inherent symmetry of Bertrand Oligopoly (Bertrand 1883).
For completeness, we offer similar analysis of the NigTransformer applied to other game classes in Appendix C including games without symmetry. with -trrttgyy NE as well as instances where Nfg FigTTransforer failed. Additionally, we show examples of applying NfgTransformer to out- of-distribution games such as Colonel Blotto (Roberson, 2006) that presents several strategy cycles.
RELATED WORKS
Recent works leveraged deep learning techniques to accelerate scientific discoveries in mathematics
(Fawzi et al., 2022), physics (Prau et al. (020) and biology (Jumper et al.] (02T). Our work is similarly motivated, but brings deep learning techniques game theory and economic studies. We
follow a line of works in bringing scalable solutions to game theory MMrris et al. 2022] Duan
ct al. 2023 Vadori& & Savani (023). or integrating components for strategic reasoning as part of
machine learning system (Hu & Wellman 2003 Greenwald et al. [003)] Feng et al. 2021 Liu et al.,
20226 a). In game theory, Hartford al. (0166) is the closest to our work and the first to apply deep
representation learning techniques to cognitive modelling of human strategic reasoning using NFGs. The authors systematically outlined number of desiderata for representation learning of two-player NFGs, including player and action equivariance well as the independence between the number of parameters of the learned model and the size of the game. The Nig Tigrrsssfrrerr satisfies these desiderata but applies nt-layer general-sum games. |Wiedenbeck & Brinkman (2023) studies efficient data structures for payoff representation; our approach can be readily integrated into deep learning systems without any assumption on the games.
CONCLUSION
We proposed Nfg Transformer as ceneral-purposse equivariant architecture that represents NFGs as action embeddings. We demonstrate its versatility and effectiveness in a number of benchmark tasks from different sub-fields of game theory literature, including equilibrium solving, deviation gain estimation and ranking. We report empirical results that significantly improve upon state-of-the art baseline methods, using unified representation learning approach. We show that the resulting model is also interpretable and theoretic reasoning into deep learning systems as they are deployed in the real-world.
Our work paves the way for integrating game-

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
We are grateful to Bernardino Komera-Paredee for the productive discussion on the different consid- erations in designing an equivariant neural architecture, to Wojciech M. Czarnecki for his expertise in ranking and evaluation in games and to Skanda Koppula for his advice on optimisation techniques for the transformer architecture.
REFERENCES
Elliot Anshelevich, Aris Filos-Ratsikas, Nisarg Shah, and Alexandros A. Voudouris. Distortion in social choice problems: The first 15 years and beyond. In International Joint Conference on Artificial Intelligence, 2021. URL https::/app semattiesscolla..ooo//ooooooou
232075911
David Balduzzi, Karl Tuyls, Julien Perolat, and Thore Graepel. Re-evaluating evaluation. Advances in Neural Information Processing Systems, 31, 2018.
David Balduzzi, Marta Garnelo, Yoram Bachrach, Wojciech Czarnecki, Julien Perolat, Max Jader- berg, and Thore Graepel. Open-ended learning in symmetrie zero-sum games. In International Conference on Machine Learning, pp. 434-443, PMLR, 2019.
Joseph Bertrand. Théorie mathématique de la richesse sociale. Journal des savants, 67(1883): 499-508, 1883.
Quentin Bertrand, Wojciech Marian Czarnecki, and Gauthier Gidel. On the limitations of the Elo, real-world games are transitive, not additive. In International Conference on Artificial Intelligence and Statistics, pp. 2921. PMLR, 2023.
Xi Chen, Xiaotie Deng, and Shang-Hua Teng. Settling the complexity of computing two-player Nash equilibria. Journal of the ACM (JACM), 56(3):1-57, 2009.
Constantinos Daskalakis, Paul W Goldberg, and Christos Papadimitriou. The complexity of computing a Nash equilibrium. Communications of the ACM, 52(2):89 2009.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszko- reit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recogni- tion at scale. In International Conference on Learning Representations, 2021. URL https: //openzeview. www.eeeeeooomdd-io/er/e
Zhijian Duan, Wenhan Huang, Dinghuai Zhang, Yali Du, Jun Wang, Yaodong Yang, and Xiaotie Deng. Nash equilibrium approximator learnable? In Proceedings of the 2023 International Conference Autonomous Agents and Mulliagent Systems, pp. 233-241, 2023.
A.E. Elo. The Rating of Chessplayers: Past and Present. Ishi Press International, 2008. ISBN 9780923891275, URL
www.ke...oooo....ooooo. co www.c....kuooe wot..o/....bbbo..cc.ceee........
Alhussein Fawzi, Matej Balog, Aja Huang. Thomas Hubert, Bernardino Romera-Paredes, Moham- madamin Barekatain, Alexander Novikov, Francisco J R Ruiz, Julian Schrittwieser, Grzegorz Swirszez, et Discovering faster matrix multiplication algorithms with reinforcement learning- Nature, 47057930) 2022.
Xidong Feng, Oliver Slumbers, Ziyu Wan, Bo Liu, Stephen McAleer, Ying Wen, Jun Wang, and Yaodong Yang. Neural auto-curricula two-player zero-sum games. Advances in Neural Infor- mation Processing Systems, 34:3504-3517, 2021.
Joaquim Gabarró, Alina García, and Maria Serna. The complexity of game isomorphism. Theoreti- cal Computer Science, (12(4))666756665 2011.
Amy Greenwald, Keith Hall, Roberto Serrano, et al. Correlated Q-learning. In /CMI, volume 3, pp- 242-249, 2003.
Jason Hartford, James R Wright, and Kevin Leyton-Brow Brown. Deep learning for predicting human strategic behavior. Advances in neural information processing systems, 29, 2016.
10

---

Published as a conference paper at ICLR 2024
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8): 1735-1780, 1997.
Junling Hu and Michael P Wellman. Nash q-leamiin for general-sun stochastic games. Journal of machine learning research, 4(Nov):1039-1066) 2003.
Andrew Jaegle, Felix Gimeno, Andy Brock, Oriol Vinyals, Andrew Zisserman, and Joao Carreira. Perceiver: General perception with iterative attention. In Interaational conference on machine learning, pp. 4651 1-664 PMLR, 2021.
John Jumper, Richard Evans, Alexander Pritzel, Tim Green, Michael Figurnov, Olaf Ronneberger, Kathryn Tunyasuvunakool, Russ Bates, Augustin Zidek, Anna Potapenko, et al. Highly accurate protein structure prediction with alphafold. Nature, 596(7873):583-33
2021.
Mare Lanctot, Vinicius Zambaldi, Audrumas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien Pérolat, David Silver, and Thore Graepel. A unified game-theoretic approach multiagent rein- forcement learning. Advances in neural information processing systems, 30, 2017.
Yann LeCun, Yoshua Bengio, al. Convolutional networks for images, speech, and time series. The handbook of brain theory and neural networks, (16) 1995.
Michael L. Littman et al. Friend-or-foe q-learning in general-sum games. In ICML, volume 1, pp- 322-328, 2001.
Siqi Liu, Mare Lanctot, Luke Marris, and Nicolas Heess. Simplex neural population learning: Any- mixture bayes-optimality in symmetric zero-sum games. In International Conference on Machine Learning, pp. 13793-13806. PMLR, 2022a.
Siqi Liu, Luke Marris, Daniel Hennes, Josh Merel, Nicolas Heess, and Thore Graepel. NeuPL: Neural population learning. In International Conference on Learning Representations, 2022b.
URL httpp:://pperrevaaieet wet.rreeiiweeeeeeeeeeeeee htw.:ew.eee/oooreeeeeeeeeeee www.eeewwwee/e...iiiiii.e.e.. Boee:/E3rrmm1
Luke Marris, Ian Gemp, Thomas Anthony, Andrea Tacchetti, Siqi Liu, and Karl Tuyls. Turbocharg- ing solution concepts: Solving NEs, CEs and CCEs with neural equilibrium solvers. Advances in Neural Information Processing Systems, 35:5586-566 2022.
Luke Marris, Ian Gemp, and Georgios Piliouras. Equilibrium invariant embedding, metric space, and fundamental set of 2 normal-form games. arXiv preprint arXiv:2304..m 09978, 2023.
J. C. C. McKinsey. 11. ISOMORPHISM OF GAMES, AND STRATEGIC EQUIVALENCE, pp. 117- 130. Princeton University Press, Princeton, 1951 ISBN 9781 4008881777 doi: doi:10.1515/ 9781400881127-012 URL httpss:/doii. org / 10. 1555 /11115/77711481117777777
John Nash. Non-cooperative games. Annals of Mathematics, 54(2):286-255, 1951. ISSN 0003486X. BtLp:t/:///ww
cetttoo.org/sttllle.. 1969222 969529
Eugene Nudelman, Jennifer Wortman, Yoav Shoham, and Kevin Leyton-Brown Run gamut: A comprehensive approach to evaluating game-theoretic algorithms. In AAMAS, volume 4, pp- 880-887, 2004.
David Pfau, James S. Spencer, Alexander G. D. G. Matthews, and W. M. C. Foulkes. Ab initio solution of the many-electron Schrödinger equation with deep neural networks. Phys. Rev. Res., 2:033429, Sep 2020. doi: R0.100//hyyReeweeearc.......
brg/doi/10. http://6..11.yyyysseeeeeeeeeeee.
Ryan Porter, Eugene Nudelman, and Yoav Shoham. Simple search methods for finding Nash equilibrium. Games and Economic Behavior, (622):642-62,, 2008
Brian Roberson. The colonel blotto game. Economic Theory, 29(1):1-24, 2006.
Nelson Vadori and Rahul Savani. Ordinal potential-bart player rating. arXiv preprint arXiv:2306.053366 2023.
11

---

Published as a conference paper at ICLR 2024
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural informa- fion processing systems, 30, 2017.
Emmanouil-Vasieee Vlatakis- GaaaaiiiGGaaakooniii. Lampros Flokas, Thanasis Lianeas, Panayotis Mer- tikopoulos, and Georgios Piliouras. No-regret learning and mixed nash equilibria: They do not mix. Advances in Neural Information Processing Systems, 33:1380-1399 2020.
Bryce Wiedenbeck and Erik Brinkman. Data structures for deviation payoffs. In Adaptive
Agents and Multi-Agent Systems, 2023. URL https: /api. semanticscco.o..oooomm org/
Corpus1D:255220115
12


Reviews:
[{"review_id": "P8yiz0ekdl", "reviewer": "Reviewer_6Yok", "summary": "The paper proposes an action-payoff encoder architecture for normal-form games (NFGs), which can be used to predict the payoffs, and maximal deviation of a player. The main contribution of this work is NfgTransformer, which is an action-payoff encoder that leverages the permutation-invariance of transformer architectures. The proposed architecture reportedly outperforms baselines in various game-theoretic toy examples.", "questions": "From my understanding, the \"equivariance\" property of NfgTransformer architecture is a direct consequence of transformer architecture itself -- which is OK, but hard to be considered as a significant technical contribution; it would be appreciated if the authors could clarify this point.", "limitations": "", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 1, "strengths": "# Strengths\n- The empirical results of the proposed architecture outperforms the baselines in several toy benchmarks.", "weaknesses": "# Weakness\n- [Presentation]\n    - It is hard to parse the main goal of this work at the first glance; the main contribution of this work is a game encoder architecture that exhibits a baked-in equivariance (which is a direct consequence of transformer architecture)\n    - I think it would have been much better if the authors emphasized why we need such a game encoder, and why it is important; for example, the authors state “For practical applications such as ranking in Go and Chess, it is infeasible to evaluate all pairs of players yet we may wish to make predictions about the game based on incomplete information from a subset of the matchups.” In Sec. 1 — more concrete examples would help the readers to understand the motivation of this work. \n    - In Sec. 1, the authors vaguely describe the main contribution of this work as: \n        - “… we consider the problem of bringing game-theoretic reasoning to deep learning systems and, conversely, using deep learning techniques to solve challenges in game theory.” \n        - “… NFGs are canonical descriptions of strategic interaction between players that allows one to ask a variety of questions.”\n        - But none of the descriptions clearly states that the actual contribution lies in an encoder architecture that encodes action & payoffs.\n    - Hard to understand the illustration of the proposed architecture in Fig. 1 and Fig.2\n        - The illustration and caption are not self-contained; readers need to resort to Sec. 4 to actually grasp the implementation \n        - What is the difference between light colors and bold colors in Fig.1 ?\n        - It is hard to parse the meaning of the annotations attached to the tokens in Fig. 1; for example, in “Payoffs” of Fig. 1, different lengths are identically annotated as “T” \n    - Some of internal links are broken\n        - Pointers to Fig. 5\n        - Pointers to Proposition 3.2\n        - Pointer to Sec. 5.1.\n        - Pointers to Sec 4.4\n        - Some links to the references\n- [Technical Novelty]\n    - If I understood correctly, it seems like the equivariance of NfgTransformer is a direct consequence of transformer architecture, and therefore, hard to consider it as a novel technical contribution.\n- [Experiment]\n    - The games presented in the experiments are rather toy-ish — given that the main contribution of this work lies in an empirical architecture, I think the efficiency of the proposed architecture should be validated on a real-world games, e.g., Go and Chess, which the authors listed as possible practical applications in Sec. 1.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SBHxhvZBD2", "reviewer": "Reviewer_pter", "summary": "The submission proposes a transformer architecture for learning normal-form games. They evaluate this architecture on a variety of game-related tasks, including solving for Nash equilibria and predicting deviation payoffs.", "questions": "What's a regular isomorphism as opposed to strong isomorphism in the context of games?\n\n---\n\nOverall, I think the submission needs to be re-written to make it more clear what problem it is trying to solve and how it is training its architecture.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 1, "strengths": "Regarding originality, I don't know of any paper that has done what the submission seems to be doing.", "weaknesses": "### First sentence\n\nI'm going to start off by discussing the first sentence of the introduction:\n\n> A number of celebrated results in artificial intelligence (AI) have appealed to game-theoretic principles during training, evaluation and ranking (Silver et al., 2016; Lanctot et al., 2017; Vinyals et al., 2019; Omidshafiei et al., 2019; Liu et al., 2022b; Perolat et al., 2022).\n\nThe way this sentence is written leaves the reader with the impression that the citations are examples of celebrated results that have appealed to game-theoretic principles. Let's go through them and examine whether this claim is true. I agree that Silver et al. (2016) is a celebrated result. However, it is not clear to me that it uses any game-theoretic principles during training (it uses supervised learning + self-play) or evaluation/ranking (it uses elo rankings). Lanctot et al. (2017) is not a result at all -- it is a paper that advocates for combining double oracle and deep RL. Vinyals et al. (2019), Omidshafiei et al. (2019), Liu et al. (2022b), Perolat et al. (2022) all use some level of game-theoretic justification, but none live up to the very high standard implied by the term \"celebrated\". One also cannot help but notice that all six of the cited papers are DeepMind papers. While it is certainly the case that DeepMind has made important contributions to RL in games (and perhaps more so than any other group), citing only DeepMind papers here is completely unjustifiable. Arguably, the two most significant sets of successes that directly appeal to game-theoretic principles are those concerning poker (DeepStack/Libratus/Pluribus/ReBeL) and No-Press Diplomacy (Diplodocus). That the submission choses to cite DeepMind papers as opposed to more-relevant non-DeepMind papers to support their claim gives the impression that it is attempting to push a narrative rather than give an honest perspective (or, alternatively, that the submission is simply uninformed). One might argue here that I am being too pedantic about a somewhat boilerplate sentence in the introduction that is not closely related to the submission's contributions. But I think it is important that the submission not mislead the reader.\n\n---\n\n### Motivation of paper\n\nAfter reading the introduction, I am not quite sure I fully grasp the problem that the submission is trying to solve. The submission abstractly states \"We consider the problem of bringing game-theoretic reasoning to deep learning systems and, conversely, using deep learning techniques to solve challenges in game theory\" but does not immediately clarify why would would want bring game-theoretic reasoning to deep learning systems or what challenges the submission is going to solve in game theory. It further states \"In its most basic form, strategic interactions between players are formulated as NFGs where players simultaneously select actions and receive payoffs subject to the joint action. Strategic interactions are therefore presented as payoff tensors, where values to each player are tabulated under every joint action. This tabular view of strategic interactions presents its own challenges to representation learning.\" Under the presumption that doing representation learning on a normal form game is important, I agree there are some representation learning-related challenges, but the submission hasn't really explained why we would want to be doing this in the first place. The submission then lists some game-theory related questions \"Examples of such enquiries permeate different communities within game theory: given sets of actions, what would be\nan equilibrium strategy (Greenwald et al., 2003; Marris et al., 2022; Duan et al., 2023a;b)? How does the efficiency of the system degrade due to individual selfishness (Koutsoupias & Papadimitriou,1999)? How might we cluster actions considering transitivity and strategy cycles (Czarnecki et al., 2020)? Given outcomes for some joint actions, can one predict payoffs for the others (Balduzzi et al., 2018; Bertrand et al., 2023; Vadori & Savani, 2023)? To what extent can we reduce the dimensionality of a class of NFGs (Marris et al., 2023)?\" This gives the reader the impression that these are some of the questions the submission is interested in. But the big question of *Why we need to learn a representation of the game to do this* remains unaddressed -- it is unclear to the why problems such as \"what would be an equilibrium strategy\" ought not to be addressed from a normal-form representation. The submission proceeds to list desiderata for a unified representation for solving these tasks.\n\n---\n\n### Description of methodology\n\nThe submission refers the reader to Figure 1 to understand the architecture that they're proposing, but I find the figure not very easy to grok. What does it mean when two arrows point at the same block?\n\nThe submission describes the architecture in Section 4, but I could not figure out what the architecture was being trained to do. I also still do not understand what the downstream use case of this architecture is.\n\n---\n\n### Experiments\n\nIn Section 5.1.1, the submission says this \"For equilibrium solving, we optimise variants of the NfgTransformer to minimise the NE GAP\n() = maxp p() directly.\" How is the submission performing this optimization? How are we recovering a NE strategy from the action embeddings? These questions are central to the paper, but seem to be unanswered in the text. Furthermore, why should we want to solve NFGs with this architecture instead of using a classical method? Without discussing this question, the reader is left wondering why they should care about these experiments.\n\nIn Section 5.1.2, the submission says this \"We optimise a NfgTransformer network to regress towards the maximum deviation-gain () for every joint pure-strategy (deterministic) , using a per joint-action decoder architecture (Figure 2).\" Again, it is totally not obvious how the submission is doing this based on the text in the paper. Furthermore, the submission again has no discussion about why we should want to use an architecture instead of a classical method for this task (which in this case just amounts to matrix multiplications).\n\nSection 5.2 studies a kind of payoff table completion task. Here it seems reasonable that one might actually want to use an architecture of the kind the submission describes. However, the submission still neglects to disclose how the the architecture was trained.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dwf9FRjsPq", "reviewer": "Reviewer_s4as", "summary": "This paper considers the permutation equivariance in normal-form games (NFGs) in terms of player action and players. The authors claim that there is inherent equivariance in NFGs – “any permutation of strategies describes an equivalent game.” Then they design an NfgTransformer to leverage this equivariance. They conduct comprehensive experiments show their method significantly outperformes strong baselines in a range of game-theoretic applications.", "questions": "Please address the above.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "This paper proposes to discover the \"inherent symmetry\" in game theoretical problems using equivariant neural networks. This idea is impressive, timely, and promising.\n\nThe authors design an NfgTransformer to meet their aim. I find using transformer reasonable.\n\nThey also conducted experiments covering a wide range of cases.", "weaknesses": "My concerns are as follows:\n\n- I am worried about the claim that permutation equivariance is \"inherent\" in normal-form games either in terms of action or player. This is not obvious to me. Please prove this. Also, such permutation equivariance is a quite strong assumption, and leads to a significantly restrictive application domain.\n\n- It is not clear to what extent the proposed NfgTransformer is different from a vanilla one which has naturally been permutation equivariant. The authors did not clearly present the architecture of NfgTransformer - I could not validate the novelty in terms of model design.\n\n- The authors did not give any theoretical guarantee - whether the proposed method secure the desired permutation equivariance, whether the method can reach the desired Nash equilibrium, how fast would the algorithm converge, whether the generalisability of the proposed method (as a learning algorithm) is satisfiable, whether the proposed method has any theoretical advances, etc. Before answering this question, I was quite hesitant about the proposed algorithm.\n\n- I appreciate the empirical results. However, game theory has a very wide range of applications - I do not think experiments in a few applications could justify an algorithm which is claimed to have advances in general cases.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YgiSxoMBkR", "reviewer": "Reviewer_6Avg", "summary": "In this paper, the authors aim to learn the representations of each action of every player in normal-form games. They propose a transformer-based architecture called NfgTransformer, which takes the payoffs and zero-initialized action representations as input and outputs the action embeddings. These output embeddings can be used for many downstream tasks.\n\nIn experiments, authors verify the effectiveness of NfgTransformer in Nash equilibrium solving under full-observed payoffs, and in payoff prediction when some payoffs are unobserved. Furthermore, they also conduct case studies of attention weights in small bimatrix games to demonstrate the interpretability of NfgTransformer.", "questions": "1. At the end of Section 4.4, you mentioned, \"During training, invalid joint-actions are simply masked out from the set of values...\" How are these invalid joint-actions masked out? Is this achieved by reducing the corresponding pre-softmax scores significantly?\n2. In Section 5.2, how are the instances of DISC games generated? How do you train your model?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1. The paper introduces a novel task: learning game representations. The acquired embeddings have the potential to enhance numerous downstream applications, making them particularly valuable in empirical game theory.\n2. The attention-based architecture offers a degree of interpretability, and I found the case studies presented in Figure 5 to be particularly insightful.\n3. NfgTransformer exhibits scalability as its parameters remain independent of the number of actions", "weaknesses": "The presentation can be further improved:\n\n(a) The description of the three attention mechanisms in Section 4.2 is too brief. I believe it would be beneficial to introduce more mathematical expressions.\n\n(b) Also, in Section 4.2, I find the name of the first attention mechanism to be misleading. I would suggest using \"joint-action-to-player self-attention\" rather than the original \"player-to-coplayer self-attention.\"\n\n(c) I'm having difficulty discerning the results presented in Figure 3. Perhaps using a table would be clearer than the loss curves.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)