Turbocharging Solution Concepts: Solving NEs, CEs and CCEs with Neural Equilibrium Solvers
Authors: Luke Marris
Ian Gemp
Thomas Anthony
Andrea Tacchetti
Siqi Liu
Karl Tuyls
Venue: NeurIPS 2022 Accept (2022)
Keywords: Game Theory
Nash Equilibrium
Correlated Equilibrium
Coarse Correlated Equilibrium

Abstract: Solution concepts such as Nash Equilibria, Correlated Equilibria, and Coarse Correlated Equilibria are useful components for many multiagent machine learning algorithms. Unfortunately, solving a normal-form game could take prohibitive or non-deterministic time to converge, and could fail. We introduce the Neural Equilibrium Solver which utilizes a special equivariant neural network architecture to approximately solve the space of all games of fixed shape, buying speed and determinism. We define a flexible equilibrium selection framework, that is capable of uniquely selecting an equilibrium that minimizes relative entropy, or maximizes welfare. The network is trained without needing to generate any supervised training data. We show remarkable zero-shot generalization to larger games. We argue that such a network is a powerful component for many possible multiagent algorithms.

Turbocharging Solution Concepts: Solving NEs, CEs and CCEs with Neural Equilibrium Solvers
Luke Marris
DeepMind (marris@deepmind. com), UCL
Ian Gemp DeepMind
Thomas Anthony
Andrea Tacchetti
Siqi Liu DeepMind, UCL
Karl Tuyls DeepMind
DeepMind
DeepMind
Abstract
Solution concepts such as Nash Equilibria, Correlated Equilibria, and Coarse Correlated Equilibria useful components for many multiagent machine learning algorithms. Unfortunately, solving a normal-form game could take prohibitive non-deterministic time to converge, and could fail. We introduce the Neural Equilibrium Solver which utilizes a special equivariant neural network architecture approximately solve the space of all games of fixed shape, buying speed and determinism. We define a flexible equilibrium selection framework, that is capable of uniquely selecting an equilibrium that minimizes relative entropy, or maximizes welfare. The network is trained without needing to generate any supervised training data. We show remarkable zero-shot generalization to larger games. We argue that such network is powerful component for many possible multiagent algorithms.
1 Introduction
Normal-fone formal-form solution concepts such as Nash Equilibrium (NE)
28 46 Correlated Equilibrium
(CE) 3. and Coarse Correlated Equilibrium (CCE) 45 are useful components and subroutines for many multiagent machine learning algorithms. For example, value- based reinforcement learning algorithms for solving Markov games, such Nash Q-learning (27 and Correlated Q-Learning
19 maintain state action values for every player in the game. These action values are equivalent to per-state normal-form games, and policies equilibrium solutions of these games. Critically, this policy will need to be recomputed each time the action-value is updated during training, and for large or continuous state-space Markov games, every time the agents need take action. Another class of multiagent algorithms are those in the space of Empirical Game Theoretic Analysis (EGTA) 60 [1 including PSRO 351 44 JPSRO (10), and NeuPL
3D 3X These algorithms are capable games, and require finding equilibria of empirically estimated
of training policies in extensive-foo normal-form games subroutine (the "meta-solver" step). In particular, these algorithms have been critical in driving agents to superhuman performance in Go 54
Chess 55 and StarCraft (59]
Unfortunately, solving for equilibrium can be computationally complex. NEs known to be PPAD g. (C)CEs are defined by linear constraints, and if linear objective is used to select an equilibrium, can be solved by linear programs (LPs) in polynomial time. However, in general, the solutions to LPs are non-unique (e.g. zero-sum games), and therefore are unsuitable equilibrium selection methods for many algorithms, and unsuitable for training neural networks which benefit from unambiguous targets. Objectives such as Maximum Gimi 4 (a quadratic program (QP)), and Maximum Entropy 48 nonlinear program), are unique but are more complex solve.
As result, solving for equilibria often requires deploying iterative solvers, which theoretically can scale to large normal-form games but may (i) take unpredictable amount of time converge, (ii)
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

take a prohibitive amount of time to do so, and (iii) may fail unpredictably on ill cll-cindtt problems. Furthermore, classical methods [6 36 S (i) do not scale, and (ii) are non-differentiable. This limits the applicability of equilibrium solution concepts in multiagent machine learning algorithms.
Therefore, there exists important niche for approximately solving equilibria in medium sized normal-form games, quickly, in batches, reliably, and in a deterministic amount of time. With appropriate care, this goal can be accomplished with Neural Network which amortizes up-front training cost to map normal-form payoff's to equilibrium solution concepts quickly at test time. We propose the Neural Equilibirum Solver (NES). This network is trained to optimize a composite objective function that weights accuracy of the returned equilibrium against auxiliary objectives that a user may desire such as maximum entropy, maximum welfare, or minimum distance some target distribution. We introduce several innovations into the design and training of NES so that is efficient and accurate. Unlike most supervised deep learning models, NES avoids the need to explicitly construct a labeled dataset of (game, equilibrium) pairs. Instead we derive loss function that can be minimized in an unsupervised fashion from only game inputs. We also exploit the duality of the equilibrium problem. Instead of solving for equilibria in the primal space, we train NES to solve for them in the dual space, which has a much smaller representation. We utilize a training distribution that efficiently represents the space of all normal-form games of desired shape and use an invariant preprocessing step to map games at test time to this space. In terms of the network architecture, we design series of layers that are equivariant to symmetries in games such as permutations of players and strategies, which reduces the number of training steps and improves generalization performance. The network architecture is independent of the number of strategies in the game and we show interesting zero-shot generalization to larger games. This network can either be pretrained before being deployed, trained online alongside another machine learning algorithm, or a mixture of both.
2 Preliminaries
Game Theory Game theory is the study of the interactive behaviour of rational payoff maximizing agents in the presence of other agents. The environment that the agents operate in is called a game. We focus a particular type of single-shot, simultancous move game called a normal-form game. A normal-
game consists of N players, a set of strategies available to each player, Op E Ap- and a payoff for each player under particular joint action, Gp(a), where
(a1 (aI...., aN)
(ap. a-p) E A= Ap.p. The subscript notation -p is used to mean "all players apart from player p". Games sometimes referred to by their shape, for example: [A1 x x [Ax]. The distribution of play is described by a joint (a). The goal of each player is to maximize their expected payoff, Players could play independently by selecting strategy according to their
Eaea Lae ((a) marginal or (a,)) over joint strategies, such that (a)) (ap) However this is limiting because it does not allow players to coordinate. mediator called a correlation device could be employed to allow players to execute arbitrary joint strategies (a) that do not necessarily factorize into their marginals. Such a mediator would sample from a publicly known joint o (a) and secretly communicate to each player their recommended strategy. Game theory is most developed in subset of games: those with two players and a restriction on the payoffs, Gi Gi(a,, (2) = - Ga(a, 02). known as zero- sum. Particularly in N-player, general-sum games, it is difficult to define single criterion to find solutions to games. One approach is instead to consider joints that are in equilibrium: distributions such that no player has incentive unilaterally deviate from a recommendation.
Equilibrium Solution Concepts Correlated Equilibria (CEs) K can be defined in terms of linear inequality constraints. The deviation gain of a player is the change in payoff the player achieves when deviating to action d, from a recommended action a", when the other players play a.p.
- Gp - Gp(ak, app)
ap = al otherwise
A (app an, a) = -A (o ah, ap p) = 10
(I)
A distribution, (()). is in e-CE if the deviation gain is no more than some constant 6p S for every pair of recommendation, añ, and deviation strategies, alz. for every player, p. These linear constraints geometrically form a convex polytope of feasible solutions.
eCCE:
Σ ( (a/ dh S REAA
[1. d # a E Ap
(2)

---

Coarse Correlated Equilibria (CCEs) 45 are similar to CEs but player may only consider deviating before receiving recommended strategy. Therefore the deviation gain for CCEs can be derived from the CE definition by summing over all possible recommended strategies dg.
Ap A (d)) a)
A (d EA
Σ
Gpldp, a-p) Gp(a)
(3)
distribution, a(a), is in e-CCE if the deviation gain is no more than some constant Ep S for every deviation strategy, a/p and for every player, p.
e-CCE:
CCR
(d).
vp [1, Ap
(4)
NEs 46 have similar definitions to CCEs but have extra constraint: the joint distribution factorizes 3p (pp) = (a), resulting in nonlinear constraints
e-NE:
(
Vp e [1. E Ap
(5)
aEA
Note that the definition of the NE uses the same deviation gain the CCE definition. Another remarkable fact is that the marginals of any joint CCE in two-player constant-sum games, (ap))
Ee_p (a), is also an NE, when c Therefore we can use CCE machinery to solve for NEs in
such classes of games.
When a distribution is in equilibrium, no player has incentive to unilaterally deviate from it to achieve a better payoff. There can however be many equilibria in a game, choosing amongst these is known as the equilibrium selection problem (20). For (C)CEs, the valid solution space is convex (Figure D so any strictly convex function will suffice (in particular, Maximum Entropy (ME) 4 and Maximum Gini (MG) 40 have been proposed). For NEs, the solution space is convex for only certain classes of games such as two-player constant-sum games. Indeed, NEs are considered fundamental in this class where they have powerful properties, such as being unexploitable, interchangeable, and tractable to compute. However, for N-player general-sum games (C)CEs may more suitable as they remain tractable and permit coordination between players which results in higher-welfare equilibria. If cp 2 O, there must exist at least one NE, CE, and CCE for any finite game, because NE always exists and NE CE C CCE. Learning NEs
44 and CCEs [2] single game is well studied.
Neural Network Solvers Approximating NEs using neural networks is known to be PAC learnable
[4] There is also work learning (C)CEs 4
22 and training neural networks approximate NEs 14 22] on subclasses of games. Learned NE meta-solvers have been deployed in PSRO [[7]. Differentiable neural networks have been developed to learn QREs (37 NEs for contextual games
have been learned using fixed point (deep equilibrium) networks 24 A related field, 1.20 7 aims learn iterative optimizer more suited to particular distribution of inputs, while this work focuses on learning a direct mapping. To the best of our knowledge, no work exists training general approximate mapping from the full space of games to (C)CEs with flexible selection criteria.
3 Maximum Welfare Minimum Relative Entropy (C)CEs
Previous work has argued that having unique objective to solve for equilibrium selection is important. The principle of maximum entropy 30 has been used to find unique equilibria 4S] In maximum entropy selection, payoffs are ignored and selection is based on minimizing the distance to the uniform distribution. This has two interesting properties: (i) it makes defining unique solutions easy, (ii) the solution is invariant transformations (such as offset and positive scaling) of the payoff tensor. While these solutions are unique, they both result in weak and low payoff equilibria because they find solutions the boundary of the polytope. Mcanwhile, the literature tends to favour Maximum Welfare (MW) because it results in high value for the agents and is a linear objective, however in general it is not unique. We consider a composite objective function composed of (i) Minimum Relative Entropy (MRE, also known as Kullback-Leible divergence) between a target joint, o(a),
'This why NEs are harder to compute than (C)CEs.
3

---

and the equilibrium joint, (()), (ii) distance between target approximation. Ep. and the equilibrium
approximation. Sp, (ii)) maximum of linear objective, W (a). The objective constrained by the (i)
distribution constraints (2a a (a) 1 and (a) 2 0) and, (ii) either CCE constraints (Equation
or CE constraints (Fquation
((aa 8(a) Σ ($ - <p)nn P
6 Ep exp(1) (c) -
arg max (a(a)W(a 0.tp
Σ (a) acA
aEA
(6)
The approximation weight, P. and welfare weight, Ja, are hyperparameters that control the balance of the optimization. The maximum approximation parameter, ep is another constant that is usually chosen to equal to the payoff scale (Section A.I.. The approximation term is designed to have similar form to the relative entropy and is maximum when ép Ep. We refer to this equilibrium selection framework as Target Approximate Maximum Welfare Minimum Relative Entropy (2- MWMRE).
3.1 Dual of c-MWMRE (C)CEs
Rather than performing constrained optimization, it is easier to solve the dual problem, arg min T/OOC (derived in Section A). where 07 (d a²)) 0 are the dual deviation gains (.5((2)
corresponding the CE constraints, and ap (((E(dd)) 2 0 are the dual deviation gains corresponding to the CCE constraints. Note that we do not need optimize over the primal joint, a (a)) Choosing one of the elements in the curly brackets, the Lagrangian is defined:
(CCC L = In Σ G(a) exp
ACCA ((a) (1a))
+Σ++ c
CE appdps a²), Σ appia
Σ
CCE, aplap) - >
OCCE
+
KEEA
a
The logits (a) are define::
(CCC ((a) = = H > ((a) - -
CCE OCE
apld ap) Ap of a), Op (p(c))
(8)
The primal joint and primal approximation parameters are defined:
ICCC ((a)
-
1) (10)
(CCC (a))
((a) exp
(9)
(C)CE Cp
- exp
Σ
aplan, an))
CE Eaplo
CCE
aplan)
+
(C)CE ((a)
o
(a) exp
aEA
Neural Network Training
The network maps the payoffs of game, Gy(a), and the targets (6(a), ép. W(a)) to the dual deviation gains, a (CCCC that define the equilibrium. The duals significantly more space efficient objective target (Ep 1Ap12 for CEs and Σp |Apl for CCEs) than the full joint (I (App)). particularly when scaling the number strategies and players. The joint, (a), and approximation, éps can be computed analytically from the dual deviation gains and the inputs using Equations ! and (O).. The
network is trained by minimizing the loss, / CCC (Equation 7)). We call the resulting architecture a Neural Equilibrium Solver (NES).
4.1 Input and Preprocessing
The MRE objective, and the (C)CEs constraints are invariant to payoff offset and scaling. Therefore we can assume that the payoffs have been standardized without loss of generality. Fach player's payoff should have mero-mean. Furthermore, should be scaled such that the Tam = || !| norm of the payoff tensor equals Zm, where Zm is scale hyperparameter chosen such that the elements of

---

WW
30
0C
(a) Traffic Lights
(b) Pure Coordination
(c) Prisoner's Dilemma
Figure 1: Diagrams for three 2 normal-form games, showing their (C)CE solution polytope on the joint simplex (in two-strategy games CEs and CCEs are equivalent). An MWME NES, trained by sampling over the space payoff's and welfare targets, is used to approximate the MW(C)CE solution (x). An MRE NES, trained by sampling over the space of payoff's and joint targets, is used to approximate the ME(C)CE (-), and all pure joint target MRE(C)CEs (o). The networks have never trained on these games.
the inputs have unit variance (a property that ensures neural networks train quickly with standard parameter initializations [8].. We will ensure both these properties by including preprocessing layer in NES. The preprocessed inputs (G)(a), ā (a), &p. (()) are then broadcast and concatenated together so that they result an input of shape [C, N, [AI,,... [Ax]], where the channel dimension
C' = 4, if all inputs are required.
4.2 Training Distribution
The literature favours sampling games from the uniform normal distribution. This introduces two problems: (i) it biases the distribution of games solvable by the network, and (ii) unnecessarily requires the network to learn offset and scale invariance in the payoffs. Recall that the space of equilibria are invariant to offset and positive scale transformations to the payoff. Zero-mean and La norm scaling geometrically results in the surface of (IAA) 1)-ball centered the origin (Section D.4. We propose using this invariant subspace for training. We choose the norm scaling constant, Zo VIAI, such that the elements of the payoffs maintain unit variance.
4.3 Gradient Calculation
The gradient update is found by taking the derivative of the loss (Equation with respect to the dual variables, a. Note that computing gradient does not require knowing the optimal joint a (a). so the network can be trained in an unsupervised fashion, from randomly generated inputs, ()(a), & (()), ép. and (a).
aLOCKE
(C)CI Ep
CCF Σ Aplo Ap ld (c. a(a)
(CKE
(11)
a af CB (a () a
The dual variables, (a d,), ap eters Gradients for these parameters can be derived using the chain rule:
CUE (a()) are outputs of the neural network, with learned param-
CXE
OLCCCE
θ (F (dp.""")) aa), OCF (a)))
00
θ (a ay),, (a))
00
Backprop efficiently calculates these gradients, and many powerful neural network optimizers can be leveraged update the network parameters.
5 4
and ML frameworks
4.4 Equivariant Architectures
The ordering of strategies and players normal-form game is unimportant, therefore the output of the network should be equivariant under two types of permutation; (i) strategy permutation, and (ii)
5

---

player permutation. Specifically, for some strategy permutation Tp Tp(1),..., Tpp (1Ap)) applied to each element of player's imputs (payoffs, target joint, and welfare), the outputs must also have permuted dimensions: (Ap(0p) Op (T((T((p)) and o² (a1..., (d.) = (n (a1),... TN (ax) ))). Likewise, for some player permutation r(1), -..,, T(N), the outputs must be transposed: (a (ap) (r(p)) (p)()) and o" (a1,.... av) ((ar(1),..... (r(N))). The latter equivariance can only be exploited by network if all players have the same number of strategies ("cubic games"). There are |Apl! possible
strategy permutations for each player and N! player permutations, resulting in N! (1AAp!)* possible equivariant permutations of each sampled payoff. Note that this is much greater than the number of joint strategies in a game, N! (IAp)!)*
>> App!" which an encouraging observation when considering how this approach will scale to large games. Utilizing an equivariant [52] [2] architecture therefore crucial scale large games because each sample represents many possible inputs. Equivariant architectures have been used before for two-player games [22
Payoff's Transformations The main layers of the architecture consist of activations with shape N, [Ail..., [A which is the same shape as a payoff tensor (with a channel dimension). We refer layers with this shape "payoff" layers. We consider transformations of the form:
10 Σ
9++1 (1411. aN) f
w (((c-.,c)) (os (ai a1..... aN))l + b(((+)
(12)
where f is any equivariant nonlinearity are learned network weights, b are learned network biases, and Φ; is one of many possible equivariant pooling functions (Section [ and Con is the concatenate function along the channel dimension. For example, consider one such function, o; =E,, Lay" which invariant across any permutation of a1 (similar to sum-pooling in CNNs), and equivariant over permutations of p, (a....., a. In general and max-pon mnax-pooling are good choices). If all players have an equal number of strategies, for some funetions, weights can be shared over all p [1 because of symmetry (53) Note that the number of trainable parameters scales with the number of input and output channels, and not with the size of the game (Figure 2 therefore it is possible for the network to generalize games with different numbers of strategies. The basic layer, -I-1, therefore comprises of linear transform of a concatenated, broadcasted set of pooling functions.
use & (r-a.....ax >...ax))(ppp g9 a1: ..., a,v) (mean-pooling
Payoffs to CCE Duals Transformations Payoffs can transformed to CCE duals, CCE (ct+ 1, af)). by using a combination of subset of the equivariant functions Φ; discussed above that sum over at least -p. If the number of strategies are equal for each player, the transformation weights can be shared and the duals can be stacked into single object for more efficient computation in later layers: OCE (CC+((C p, d() = Stackp (ag CCE (c4+1,4))):
Payoffs to CE Duals Transformations The transformation to produce the CE duals is more complex. CE duals, a CCC((c44 aw. dp), need be symmetrically equivariant. This property can be obtained by (i) independently generating two CCE duals and, (ii) taking outer operations, E (for example sum or product), over them.
0 (E(Ce41, ai ab))= f (a CCE (C+11, ap
CCE (c+)).)()))
(13)
Where f is any equivariant nonlinearity with zero diagona We know that the diagonal is zero because it represents the dual of the deviation gain when deviating from a strategy to itself, which is zero, and therefore cannot be violated. This is useful property which will be exploited in later dual layers. These can also be stacked if players have equal number of strategies: a CCB CCC P, dy. a²)) = Stack, (OCCE(Ctt)) dg a.)).
Because the payoff activations are high-dimensionnl, it is worthwhile to operate on them in dual space. When transforming CCE duals we consider a mapping:
CCE Duals Transformations
I0,
CCE a (ct1,,, f
Σ
(()+,,,)) [os (afC + b(c(+1)
(14)
*Common nonlincarities such as dlement-wise. (ReLU, tanh, sigmoid), and SoftMax are all equivariant. Masking sufficient: e.g. f(ap. d²)) [(ap I d²), where is the identity matrix.

---

Preprocessed Input Gp(a),
Payoffs To Payotts Layers
Payolls To Duals
Duals Duals Layers an a culb,c,p,, af. o [B,C.N,IAp) or CBC.NN 1Ap1 IApll
9i(b, di, an) [B, 4, N; (Al [AN]] [B,C, AAA..../AA
d(a), W(a)
Figure 2: Network urchitecture showing the name, indices and shape (Batch, Channels, Number of players, Actions per player) of each layer layer. Other architectures are possible, for example some of the inputs (target approximation, target joint, or welfare) could be passed in at a later layer.
where is any equivariant nonlincarity, and Φ; is from set (Section C.2 of only two possible cquivariant transformation functions (and two more if the game is cubic). For the final layer, we use SoftPlus nonlinearity to ensure the output is nonnegative and has gradient everywhere.
CE Duals Transformations
When transforming CE duals we consider functions the form:
TCi Σ
a (c11,.4, d.)) =
c()n [os (af (c, ab)1 + b(((+))
(15)
For the CE case, the equivariant linear transformations are more complex: symmetric over recommended and deviation strategies. Fortunately this is well studied equivariance class [56].
which can be fully covered by combining seven transforms (Section C which comprise of different sums and transpositions of the input.
Activation Variance Because the equivariant network possibly involves summing over dimensions of the inputs, activations are no longer independent of one another, so extra care needs to be taken when initializing the network to avoid variance explosion. To combat this we use three techniques: (i) inputs are scaled to unit variance described previously (Section 4.1p, (ii) the network is randomly initialized with variance scaling to ensure the variance at every layer is one, and (iii) we BatchNorm
29 between every layer. We also used weight decay regularize the network.
Advanced Architectures
More advanced architectures such as ResNet 23 or Transformers 58 possible. An example of the final architecture is summarized in Figure
4.5 Parameterizations
The composite objective framework allows us to define a number of combinations of auxiliary objectives. We highlight several interesting specifications (Appendix Table 33. The most basic is Maximum Entropy (ME) which simply finds the unique equilibrium closest to the uniform distribution according the relative entropy distance. This distribution need not be uniform, it could be any target distribution. We could instead favour a welfare objective parameterized on the payoffs to find Maximum Welfare (MW) solution. The previous solutions be generalized solve for any welfare (Maximum Welfare Maximum Entropy (MWME)) or any target (Minimum Relative Entropy (MRE)). Furthermore need not limit ourselves approximation parameters equal to zero, for example by finding the minimum possible approximation parameter we have the Maximum Strength (MS) solution. Finally, discussed so far (G-WWEE and (-MR)).
find solutions for any approximation parameter for the solutions
Performance Experiments
Traditionally performance NE, and (C)CE solvers has focused on evaluating time converge to a solution within some tolerance. Feedforward neural networks can produce batches of solutions quickly and deterministically. For non-trivial games this is much faster than what an iterative solver could hope to achieve. We therefore focus our evaluation on the trade-offs of the neural network
'We found inference,
Suich to be around Lus hardware.
step time
7

---

157
147
10"
MIE
Uneer
33
50
100
100
100
100
Doration
Barstin
Bannsoo
Taratinn
(a) Equilibrium Selection
(b) Shapes
Solution Concepts
(d) Ablation
Figure 3: Sweeps and ablation studies showing the average solver gap of three experiment seeds evaluated over 512 sampled games against the number of train steps. Subfigure (a) shows 4 x games over different equilibrium selection, (b) shows MECCE over games with different numbers of players and strategies, (c) shows CE and CCE concepts on games, and (d) shows ablation experiments MECCE 4 4 x 4 games.
solver, namely (i) how long it takes to train, and (ii) how accurate the solutions are. For the latter we use two metries:
Solver Gap: (o) a()
(C)CE Gap:
Σ max Σ (App(,a) o(a)
The first (Solver Gap) measures the distance to the exact unique solution found by an iterative solve o² (a), and is bounded between O and 1, and is zero for perfect prediction. The second ((C)CE Gap) measures the distance the equilibrium solution polytope, and is zero if it is within the polytope.
Parameterization Sweeps We show performance across a number of parameterizations, including (i) different equilibrium selection criteria (Figure Sap. (ii) different shapes of games (Figure 3b). and (iii) different solution concepts (Figure 3c
Classes Games It is known that some distributions of game payoffs are harder for some methods to solve than others [1 We compare performance across number of classes of transfer games (Appendix Table 4 for a single MECCE and a single MECE 48 Neural Equilibrium Solver trained on 8 x 8 games. Figure E shows the worst, mean, and best performance over 512 samples from each class in terms of (i) distance to any equilibrium, and (ii) distance to the target equilibrium found by an iterative solver. We also plot the performance of uniform joint naive baseline, the gap can be artificially reduced by scaling the payoffs. In regards to equilibrium violation, ME is tricky because it lies the boundary of the polytope, setting. The plots showing the failure rate and run time of the iterative solver are to intuit difficult solve
some violation is expected in approximate
classes. The baseline iterative solver take about 0.05s solve single game, the network batch 4096 games in 0.0025s. We see that for most classes the NES is very accurate with a solver gap of around 10 Some classes of games are indeed more difficult and these align with games that iterative equilibrium solvers struggle with. This hints that difficult games are ill-conditioned.
Ablations We show the performance (Figure 3dh of the proposed method compared with (i) a linear network, and (ii) no invariant pre- pre-processing with naive payoff sampling (each element sampled using a uniform distribution). Both result significant reduction in performance.
Scaling Due to the size of the representation of the payoffs, Ga the inputs and therefore the activations of the network grow significantly with the number of joint strategies in the game. Therefore without further work on sparser payoff representation. NES is limited by size of payoff inputs. For further discussion see Section / Nevertheless, Table shows good performance when scaling to moderately sized games. Note that the "solver gap" metric is incomplete larger games because the ECOS evaluation solver fails to converge.
We use implementation in CVXPY 12 2 which leverages the ECOS
1R solver.
8

---

Paraline Sorver tperorioge
Rordin Sakee
107
Saleee Ohp
30
104
100
100
105
102
1044
100
D17
0000
033
Figure 4: Worst, mean, and best performance of MECCE (left in pair) and MECE (right in pair)
over 512 samples on the three classes introduced in this paper (Section T. and on subset 150 of transfer GAMUT [47] games (Appendix Table 4 The network only trained the "L2 invariant subspace" distribution games. The gray range indicates the performance under a uniform distribution baseline.
Table Scaling experiments showing the gaps of five NES models for larger games, with uniform baseline, over 128 samples. The ECOS solver used to evaluate "solver gap" fails on large games.
CCE Gap
CCE Gap under NES
Solver Gap
Solver Gap Success
Game
under uniform
under uniform
under NES Fraction
X
1.1006
0.0274
0.3552
0.0120
100%
x
1.0043
0.0163
0.2513
0.0054
99%
16 x 16
0,8861
0.0173
0.2014
0.0034
98%
32 x 32
0.7376
0.0215
0%
64 x
0.5864
0.0288
0%
Generalization An interesting property of the NES architecture is that its parameters do not depend on the number of strategies in the game. Therefore we test the generalization ability of the network zero-shot on games with different numbers of strategies (Table 2 There are two observations: (i) NES only weakly generalizes to other game sizes under the solver gap metric, and (ii) NES strongly generalizes to larger games under the CCE gap. remarkably achieving zero violation. Therefore the network retains the ability to reliably find CCEs in larger games, but does struggle accurately select the target MWMRE equilibrium. This could be mitigated by training the network on a mixture of game sizes, which leave to future work.
6 Applications
With Neural Equilibrium Solvers (NES) it is possible quickly find approximate equilibrium solutions using a variety selection criteria. This allows the application solution concepts into areas that would otherwise be too time-expensive and are not sensitive approximations.
Inner Loop of MARL Algorithms For algorithms 28
where speed is critical, and the size of games is modest, but numerous, and approximations can be tolerated.
39
Warm-Start Iterative Solvers Many iterative solvers start with guess of the parameters and refine them over time find an accurate solution [14] possible use NES warm-start iterative solver algorithms, potentially significantly improving convergence.

---

Table 2: Generalization experiments showing how an network generalizes to games with different number of strategies, over 128 samples.
CCE Gap
CCE Gap under NES
Solver Gap
Solver Gap under NES
Success Fraction
Game
under uniform
under uniform
X
1.1006
4.4445
0.3552
0.1500
100%
8 x 8
1.0043
0.0163
0.2513
0.0054
99%
16 x 16
0,8861
0,0000
0.2014
0.1089
98%
32 x 32
0.7376
0.0000
0%
64 x 64
0.5864
0.0000
0%
Polytope Approximation The framework can be used to approximate the full space of solutions by finding extreme points of the convex polytope. Because convexity, any convex mixture of these extreme points is also valid solution. Two approaches could be used to find extreme points (i) using different welfare objectives (ii) or using different target joint objectives. For example, using pure joint targets:
W(a) f1
a = à 0. otherwise
{1 a(a) - 10+, otherwise
if à
These could be computed a single batch, and would cover reasonably large subset of full polytope of solutions (the latter approach is demonstrated in Figure DD. It would be easy to develop an algorithm that refines the targets at each step to gradually find all vertices of the polytope, desired.
Differentiable Model and Mechanism Design Mechanism design (MD) is sub-field of economics often described as "inverse game theory", where instead of studying the behavior of rational payoff maximizing agents on given game, we are tasked with designing game so that rational payoff maximizing participants will exhibit behaviours al equilibriam that we deem desirable. The field has long history to which it is near impossible to do justice; see 42 for review. The work presented here could impact MD in two ways. First, by making it casy to compute equilibrium strategies, NES could widen the class of acceptable output games, relaxing the restrictive requirements (c.g. strategic dominance) often imposed of the output games out of concern more permissive solution concepts could be hard for participants compute. Second, NES maps payoffs joint strategies and it is differentiable, one could imagine turning a mechanism design task to a optimization problem that could be solved using standard gradient descent (e.g. design general-sum game where strategies cquilibrium maximize some non-linear function of welfare and entropy, with payoff lying in a useful convex and closed subset). A related idea is to find game that produces certain equilibrium [37] Given an equilibrium, payoff could be trained through the differentiable model that results in the desired specific behaviour.
7
Discussion
The main limitation of the approach is that the activation space of the network is large, particularly with a large number of players and strategies which limits the size of games that can be tackled. Future work could look at restricted classes of games, such polymatrix games [IO or graphical games BT. which consider only local payoff structure and have much smaller payoff representations. This a promising direction because NES otherwise has good scaling properties: (i) the dual variables space efficient, (ii) there are relatively few parameters, (iii) the number of parameters is independent of the number of strategies in the game, (iv) equivariance means each training sample is equivalent to training under all payoff permutations, and (v) there are promising zero-shot generalization results to larger games.
Solving for equilibria has the potential to promote increased cooperation in general-sum games, which could increase the welfare of all players. However, if powerful and unethical actor had influence on the game being played, welfare gains of some equilibria could unfairly come at the expense of other players.
10

---

References
[1] M. Abadi, A. Agarwal, P. Barham, E. Brevdo, Z. Chen, C. Citro, G. S. Corrado, A. Davis,
J. Dean, M. Devin, S. Ghemawat, I. Goodfellow, A. Harp, G. Irving, M. Isard, Y. Jia, R. Joze- fowicz, L. Kaiser, M. Kudlur, J. Levenberg, D. Mané. R. Monga, S. Moore, D. Murray, C. Olah, M. Schuster, Shlens, B. Steiner, Sutskever, K. Talwar, P. Tucker, V. Vanhoucke, V. Vasudevan, F. Viégas, O. Vinyals, P. Warden, M. Wattenberg, M. Wicke, Y. Yu, and
X. Zheng. TensorFlow: Large-scale machine learning heterogeneous systems, 2015. URL https://wwy https://ww..ennooffoo.. tewsorfoor
org/ Software available from tensorflow.org.
[2] A. Agrawal, R. Verschueren, S. Diamond, and S. Boyd. A rewriting system for convex optimization problems. Journal of Control and Decision, 5(1):42-60, 2018.
[3] R. Aumann. Subjectivity and correlation in randomized strategies. Journal of Mathematical Economics, 1(1):67-96, 1974.
[4] Y. Bai, C. Jin, and T. Yu. Near-optimal reinforcement learning with self-play. CoRR, abs/2006. 12007, 2020. /tttpp::/arrivv.orr//aa//// 12007
[5] J. Bradbury, R. Frostig, P. Hawkins, M. Johnson, C. Leary, D. Maclaurin, G. Necula, A. Paszke, J. VanderPlas, Wanderman-Milne, and Q. Zhang. JAX: composable transformations of Python+NumPPy programs, 2018. URL http: /ttt:://gituut //ghttttuuub... www. googl//ja
[6] A. Brock, S. De, L. Smith, and K. Simonyan. High-performance large-scale image recognition without normalization. CoRR, abs/2102.06171, 2021. URL U 06171
[7] T. Chen, X. Chen, W. Chen, H. Heaton, J. Liu, 2. Wang, and W. Yin. Learning to optimize: A primer and a benchmark, 2021. URL https://arxiv www.oor/////aaeeeeee.eeeee absp///.... 12828
[8] X. Chen, X. Deng, and S.-H. Teng. Settling the complexity of computing two-player Nash equilibria. Journal of the ACM (JACM), 56()) 2009.
[9] C. Daskalakis, P. Goldberg, and C. Papadimitriou. The complexity of computing a Nash equilibrium. SIAM J. Comput., 39:195-225 2599, 02 2009.
[10] A. Deligkas, J. Fearley, T. P. Igwe, and R. Savani. An empirical study computing equilibria in polymatrix games. arXiv preprint arXiv:1602.06865. 2016.
[11] A. Deligkas, J. Fearnley, R. Savani, and P. Spirakis. Computing approximate nash equilibria in polymatrix games. Algorithmica, 77(2):887-514, 2017.
[12] S. Diamond and S. Boyd. CVXPY: A Python-embedded modeling language for convex optimization. Journal of Machine Learning Research, 17(83):1-5, 2016
[13] A. Domahidi, E. Chu, and S. Boyd. ECOS: An SOCP solver for embedded systems. In European Control Conference (ECC), pages 3071-3076, 2013.
[14] Z. Duan, Y. Du, Wang, and X. Deng, Towards the pac learnability of nash equilibrium. CoRR, Abs/2108.07472. 2021. URL httpttppee//.w...rr//aaaaat////e hbtp://bs// 07472
[15] Duchi, E. Hazan, and Y. Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 120ul):2121-2155 2011.
[16] H. Fargier, P. Jourdan, and R. Sabbadin. path-following polynomial equations systems approach for computing nash equilibria. In Proceedings of the 21 International Conference on Autonomous Agent and Multiagent Systems, pages 4184414444 426,426610 2022.
[17] X. Feng, O. Slumbers, Z. Wan, B. Liu, S. McAleer, Y. Wen, J. Wang, and Y. Yang. Neural auto-curricula in two-player zero-sum games. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 3504-3517. Curran Associates, Inc., 2021. URL.

---

[18] X. Glorot and Y. Bengio. Understanding the difficulty of training deep feedforward neural networks. In W. Teh and M. Titterington, editors, Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, volume 9 of Proceedings of Machine Learning Research, pages 149-256, Chia Laguna Resort, Sardinia, Italy, 13-15 May 2010. PMLR. BRRLhttps:. http:a::///ccceeeeeeeeeee mlr wwwpspeee/epppe.p wlooott html http://eeennnn..rrrrrrsss//////e
[19] A.
Greenwald and K. Hall. Correlated-q learning. pages 242-249, 2003.
[20] J. Harsanyi and R. Selten. A General Theory of Equilibrium Selection in Games, volume 1. The MIT Press, edition, 1988.
[21] S. Hart and A. Mas-Colell. A simple adaptive procedure leading to correlated equilibrium. Econometrica, (8(5):1127-111 2000.
[22] J. S. Hartford, J. R. Wright, and K. Leyton-Brown. Deep learning for predicting hu- man strategic behavior. In D. Lee, M. Sugiyama, U. Luxburg, Guyon, and R. Gar- nett, editors, Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016. URL htttps:/pproceedingg neurips httpppppp..ppppppppppppppp wt/papper/201/fiiile @abccbeaa441eeebbbeeeeaaaa
[23] K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. CoRR, abs/1512.00388. 2015. URL http://arxxi..org/ absa /512. 03385
[24] H. Heaton, D. McKenzie, Q. Li, W. Fung, J. Osher, and W. Yin. Learn to predict equilibria via fixed point networks. CoRR, abs/2106.00906, 2021. URL httpps///axivi...ot wrg. abs/
1106.00906)
[25] T. Hennigan, T. Cai, T. Norman, and I. Babuschkin. Haiku: Sonnet for JAX, 2020. URL http://ght /itthbb com/ /wtp//ee/dndd///////ee//. headdddm-hatte ha-ha
[26] M. Hessel, D. Budden, F. Viola, M. Rosca, E. Sezener, and T. Hennigan. Optax: composable gra- com/ deepmind/
dient transformation and optimisation, in jax!, 2020. URL optax
[27] J. Hu and M. Wellman. Nash q-learning for general-sum stochastic games. Journal of Machine Learning Research, 4: 1:19,9-0669, 01 2003. doi: 10. 10.116//552444041187777
[28] J. Hu and M. P. Wellman. Multiagent reinforcement learning: Theoretical framework and an algorithm. In Proceedings of the Fifteenth International Conference on Machine Learning, ICML '98, page 242-250, San Francisco, CA, USA, 1998. Morgan Kaufmann Publishers Inc. ISBN 1558605568.
[29] S. loffe and C. Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. CoRR, abs/1 2015. URL http::/arxiv..rrgeeeee.e/// wwwp://gg//abbbbboee/.o abs///0s 03167
[30] E. T. Jaynes.
Information theory and statistical mechanics. Phys. Rev. 106:620-6333 630, May 1957.
[31] A. X. Jiang, K. Browon, and N. A. Bhat. Action- games. Games and Economic Behavior, 71(1):141-173 2011. ISSN 0899-8256. doi: 012. Special Issue In Honor of John Nash.
[32] C. Jin, Q. Liu, Wang, and T. Yu. V-learning A simple, efficient, decentralized algorithm for multiagent RI.. CoRR, 10./2210.14555 2021. URL htttps://arxiin org/abs/ haabs///10.. 2110. 14555
[33] N. Jouppi, D. Yoon, G. Kurian, S. Li, N. Patil, Laudon, C. Young, and Patterson. domain-specific supercomputer for training deep neural networks. Communications of the ACM, 63:67-78, 06 2020. doi: 10.1145/3360307.
[34] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. CoRR, 2014. http:/ttp:///d/ mniitriir..o www.treeeeerriieeee httaee/ed/////aaaaa////rrrrrrrr htm Stm1#KingmaBB4
12

---

[35] M. Lanctot, V. Zambaldi, A. Gruslys, A. Lazaridou, K. Tuyls, J. Perolat, D. Silver, and Graepel. A unified game- theeetheoretic approach to multiagent reinforcement learning. In NIPS. 2017.
[36] C. Lemke and J. Howson, Jr. Equilibrium points of bimatrix games. Journal of the Society for industrial and Applied Mathematics, 12(2))413 -233,, 1964.
[37] C. K. Ling, F. Fang, and J. Z. Kolter. What game are we playing? end-to-end learning in normal and extensive form games. CoRR, abs/1 800.005.0000 805.02777, 2018. URL lttpp://arxiv wrg. /
1805. 02777
[38] S. Liu, M. Lanctot, L. Marris, and N. Heess. Simplex neural population learning: Any- mixture Bayes-optimality in symmetric zero-sum games. In K. Chaudhuri, Jegelka, L. Song, C. S.eeeesvari, G. Niu, and S. Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 13793- 13806. PMLR, 17-23 Jul 2022. URL https: htttps://proceeding. mlr paress/v1e/liuue html
[39] S. Liu, L. Marris, D. Hennes, J. Merel, N. Heess, and T. Graepel. NeuPL: Neural population learning. In International Conference on Learning Representations, 2022. URL https
/ //openeeiew ret/ForuunId-MMISSDD.
[40] L. Marris, P. Muller, M. Lanctot, K. Tuyls, and T. Graepel. Multi-agent training beyond zero-sum with correlated equilibrium meta-solvers. CoRR, abs/2106.09435, 2021. URL
https://arxiv org/ abs/aaas......// 09435
[41]
L. Marris, P. Muller, M. Lanctot, K. Tuyls, and T. Graepel. Multi-agent training beyond zero-sum with correlated equilibrium meta-solvers. In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 7480-7491, PMLR, 18-24 Jul 2021. URL http::t/poc/ceee///
mlr. wwwpppesssssiee hatsss/v119//naen v13////rra/a/11a..a///// html
[42] E. S. Maskin, Mechanism design: How to implement social goals. American Economic Review, 98(3):567-76, 2008.
[43] R. D. McKelvey, A. M. McLennan, and T. L. Turocy. Gambit: Software tools for game theory, version 16.0.1, 2016.
[44] H. B. McMahan, G. J. Gordon, and A. Blum. Planning in the presence of cost functions controlled by an adversary. In Proceedings the 20th International Conference on Machine Learning (ICML-03), pages 536-543, 2003.
[45] H. Moulin and J.-P. Vial. Strategically zero-sum games: the class of games whose completely mixed equilibria cannot be improved upon. International Journal of Game Theory, 7(3-4): 201-221, 1978.
[46] Nash. Non-cooperative games. Annals of Mathematics, 54(2):286-295 1951.
[47] E. Nudelman, Wortman, Y. Shoham, and Leyton-Brown Run the gamut: comprehensive approach to evaluating game-theoretic algorithms. In Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems Volume 2, AAMAS '04, page 880-887, USA, 2004. IEEE Computer Society, ISBN 1581 138644.
[48] L. E. Ortiz, R. E. Schapire, and S. M. Kakade. Maximum entropy correlated equilibria. In M. Meila and X. Shen, editors, Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics, volume 2 of Proceedingy of Machine Learning Research, pages 347-354, San Juan, Puerto Rico, 21-24 Mar 2007. PMLR.
[49] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf, E. Yang, Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, I.. Fang, J. Bai, and S. Chintala. Pytorch: An imperative style, high- performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché- Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32,
13

---

pages 8024 8035. Curran Associates, Inc., 2019. URL http::/ppppp http://ppppprrr.nnrrrsss..c.///p 9015-
an- htw.a//ww............/eeeeaaaear
1ibrary
pdf
[50] R. Porter, E. Nudelman, and Y. Shoham. Simple search methods for finding nash equilibrium.
Games and Economic Behavior, 63(2):642-662, 2008. ISSN 0899-8256. doi: hups://doi.org aciencedirect.......mmmccoo.iii. http://cinnnearrricoom p111/50899255060000000 Second World Congress of the Game Theory Society.
(ttp://...ee.22003.0000000 URL BRL.https:
[51] R. Porter, E. Nudelman, and Y. Shoham. Simple search methods for finding nash equilibrium. Games and Economic Behavior, 63(2):642-662, 2008.
[52] J. Shawe-Taylor. Symmetries and discriminability in feedforward network architectures. IEEE transactions on neural networks, 5:816-26 1993.
[53]
Shawe-Taylor. Introducing invariance: a principled approach to weight sharing, 1994.
[54] D. Silver, A. Huang, J. Maddison, A. Guez, L. Sifre, G. Van Den Driessche, J. Schrittwieser, Antonoglou, V. Panneershelvam, M. Lanctot, et al. Mastering the game go with deep neural networks and tree search. nature, 529(7587):484 2016.
[55] D. Silver, T. Hubert, Schrittwieser, Antonoglou, Lai, A. Guez, M. Lanctot, L. Sifre, D. Kumaran, T. Graepel, T. Lillicrap. K. Simonyan, and D. Hassabis. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 362(6419): 1140-1 1 144. 2018. doi: 10. 10.1126/see http://cienc...r64000. URL https: htops://wwww //www/ science.ecc...cecc... org/doi/
abs/ 1126/ wwwpn//ccccce.e.eeeeeeeeeeo aar6404
[56] E. H. Thiede, T. Hy, and R. Kondor. The general theory of permutation equivariant neural networks and higher order graph variational encoders. CoRR, abs/2004.03990, 2020. URL https://arxi: org/ abs/ /004//200.0000 03990
[57] T. Tieleman, G. Hinton, al. Lecture 6.5-rmsprop: Divide the gradient by running average of its recent magnitude. COURSERA: Neural networks for machine learning, 4(2):26-31 2012.
[58] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. u. Kaiser, and Polosukhin. Attention all you need. Guyon, U. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL http:ttt//poooeeddiiiie neeuuiip Paper pdf
neurips
[59] O. Vinyals, I. Babuschkin, W. Czarnecki, M. Mathieu, A. Dudzik, J. Chung, D. Choi, R. Powell, T. Ewalds. P. Georgiev, J. Oh, D. Horgan, M. Kroiss, Danihelka, A. Huang, L. Sifre, T. Cai, J. Agapiou, M. Jaderberg, and D. Silver. Grandmaster level in starcraft using multi-agent reinforcement learning. Nature, 575, 11 2019.
[60] W. Walsh, R. Das, G. Tesauro, and J. Kephart. Analyzing complex strategic interactions in multi-agent systems. 01 2002.
[61] M. P. Wellman. Methods for empirical game-theoretic analysis. In Proceedings, The Twenty- First National Conference on Artificial Intelligence and the Eighteenth Innovative Applications of Artificial Intelligence Conference, July 16-20, 2006. Boston, Massachusenss, USA, pages 1552- 248
1556. AAAI Press, 2006. URL http:htt:///ww aaai. org//iibrarryAAM////0///aaasea php
[62] Wood and Shawe- Taylor. Representation theory and invariant neural networks. Discrete Applied Mathematics. 69(1):333-6) 60, 1996. ISSN 0166-211 218X. doi: https://doi.rg//00.000 1016/ 0166- 2 1166-2218X(95500075-33 URL hhttps: //wpw.///ww..../ www.:ssceeeerrreecooooooo/// htw.a///eeeeeettccccccccc/eaaaaa
pii p11/00662218X95007755

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] Main limitation is that the
activation space of the network is very large.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] We briefly discuss the abuse of equilibria could cause harm if used by malicious actor, well as the obvious benefits. We think most of game theory can abused this way. Users must make sure they apply any work in an ethical way.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] We have no ethics concerns.
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] Proofs are in appen- dices.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material as URL)? [No] We have not included code. We have described the approach in enough detail that a competent practitioner should be able reproduce results in less than week.
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (c.g., with respect the random seed after running periments multiple times)? [Yes] We did not run with multiple random seeds due to computation constraints. We do, however, report the worst, mean, and best case performance over many examples.
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes] In the appendix.
4. If you using existing assets (e.g., code, data, models) curating/releusing
assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] We use third party code which we cite (e.g. GAMUT).
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "QUbPi4nY8PU", "reviewer": "Reviewer_duLd", "summary": "This paper aims to create a method for training NNs to solve for NE, CE, and CCE across a set of games with a fixed action space for each player.  This is achieved through considering the dual formulation of the LP resulting from each of these equilibria concepts, and preforming gradient decent on the NN given random games in with that action space size so that the strategies the network produce satisfy the constraints of the LP.", "questions": "How were the hyperparmeters selected for your approach v.s the baselines? \n", "limitations": "The limitations were adequately addressed except to the extent mentioned above.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\nThe strengths of this paper are \n* The novel (to my knowledge) idea to train solvers of games in the dual LP space rather than the primal.  This is an interesting approach, which could be promising and should be explored.\n* The idea to train one solver for all games of a given shape rather than solving each game on-by-one\n* Equivariant networks and payoff invariances which are shown to improve performance.\n\n**Weaknesses:**\nThe main weaknesses I see are:\n* The motivation that other approaches in the space cannot solve for CE seems weak since it seems easy to adapt PSRO or CFRM to such a class.\n* The scaling argument seems weak as the approach of training on all games of a give size seems much much more difficult computationally than solving a particular game in that class.\n* If the argument is that this method is scalable, then I would expect experiments that run on much larger than 8 by 8 games.\n\nMore broadly, as this paper is taking the approach of solving all N by N games at once, but most of the payoff matrices in this space are ones which we don't use in practice, I would expect an evaluation on a \"transfer set\" of games which we do care about to show that it works to solve them correctly.  Otherwise it is difficult to evaluate the method, as it could have \"low error on average\" but not low error on the problems we care about.  \n\nIn the same vein, since we usually care about getting the CE for a particular game, I would be useful to compare to finding the CE for that particular game directly rather than solving all games of that shape first.\n\n**Minor Comments:**\nFigure 4 is hard to understand, given that the  difference between the gray and black error bars are never described.\n\nThe appeal to \"Occam's razor\" on line 93 is very suspect.  It appears this is alluding to something specific (which should be cited), but regardless of what the citation is there has to be a miscommunication somewhere because there \"maximum entropy\" isn't well justified by \"Occam's razor\".  In some sense they could be seen to be the opposite, as \"Occam's razor\" is often phrased as \"preferring the simplest solution\" and \"maximum entropy\" is the most-random solution (under some measure) and thus the least-compressible (under that measure), which could be seen as the \"most complicated\" solution!  Regardless, none of this is necessary, because any method of choosing between equilibria is fine for the purposes of this paper.", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "7VSeZ815aK", "reviewer": "Reviewer_RFxv", "summary": "Games are a useful formalism in machine learning. There are multiple notions of solution to a game; this paper focuses on Correlated Equilibria (CE) and Coarse Correlated Equilibria (CCE). Given the payoffs of a game, the set of all CE (resp. CCE) form a polytope, with number of constraints exponential in the number of players and actions. Thus, solving for a CE (CCE) can be computationally intractable.\n\nThis paper proposes to use a neural network to predict approximate CE (resp. CCE) given the payoffs of all players, as well as some auxiliary data. The authors propose several innovations to make the proposed neural equilibrium solver more efficient and flexible:\n  - several choices of secondary criterion used to select a particular CE (resp. CCE) from within the polytope of all CE (resp. CCE).\n  - A permutation-invariant network architecture, capable of exploiting symmetries in the game (e.g. exchangeability of players, permutations of a players action set).\n  - Focusing on solving the dual problem, which has fewer optimization variables as compared to the primary problem.\n\n", "questions": "Let me elaborate on some of the weaknesses highlighted above. If you can clarify my confusions, I will consider raising my score.\n\n## Training and experiments.\n\n  1. **Training Loss and gradients** I don't quite understand how you trained the proposed network. What is the loss function? Also, how do you propose computing gradients with respect to the network parameters? (Eq. 11 gives a formula for a gradient, yes, but it is not with respect to the parameters of the neural network.)\n \n  2. **Training data** Can you tell me more about the training data set you used? As far as I can understand, you randomly generated a fresh i.i.d batch of 4096 $8\\times 8$ games (I guess by randomly sampling payoff matrices) each iteration. Is this correct? Also, I found Section 4.2 a bit hard to follow, for example, what is meant by the first sentence \"Zero-mean and constant norm scale geometrically results in the edge of a disc.\"?  \n\n3. **Train time and network size**  As you mention in Section 5, the train time is an important metric when evaluating learned solvers. Could you comment on how long (in wall-clock time) it took to train your NES for $8\\times 8$ games? Also, how many parameters in total did this network have?\n\n 3. **Scalability** I am a little skeptical that your approach will scale to large games. Indeed, your experiments seem to target small games ($4\\times 4$, $8\\times 8$). Could you run an experiment for truly large games, e.g. $100\\times 100$ or $1000\\times 1000$? If no, could you clarify the intended use-case of the proposed NES?\n\n## Relation to Learn to Optimize literature\n\nI appreciated the reduction of determining a CE/ CCE to a convex optimization problem. I also think the use of duality to reduce the number of variables is clever. However after this reduction, the problem you're proposing: learning a solver for an optimization problem is well-studied in the Learn-to-Optimize (L2O) literature. Thus, the relation of your work to this literature should be discussed (see, for example [1] and citations therein). Using some of the terminology in [1] may help to describe your training set-up and resolve my questions above.\n\n## Relation to Learning to solve Games literature.\n\nSeveral recent works [2,3,4] have proposed uses gradient-based learning in conjunction with game solvers. The focus of these papers is slightly different to yours---closer to the inverse game theory literature briefly alluded to in the conclusion. Nevertheless, the relation between your work and these papers should be discussed. \n\n## Minor Comments\n  1. Lines 19--21 are needlessly repetitive: \"take a non-deterministic amount of time to converge\", \"take a prohibitive amount of time to do so\", and \"do not scale\" are all essentially the same point.\n\n  2. Citation [10] should be updated. It seems the paper has changed name. A related comment: the citation numbers in the main article and the supplementary do not match. \n\n  3. In line 101, when introducing relative entropy, you should mention that this concept is also known as Kullback-Liebler divergence (you actually do this in the appendix). \n\n  4. Line 106. Typo in the word \"hyperparameter\".\n\n  5. Line 113--114 I think it is more precise to say you solve the dual problem instead of \"optimize the dual Lagrangian\".\n\n  6. In line 131--132 you mention $Z_m$, but it's not clear what this is yet. You could clarify that this is just some user-defined scale parameter.\n\n  7. Line 137. I found this sentence hard to understand, as mentioned above.\n\n  8. Line 215. Is \"Maximum Utilitarian\" the same as \"Maximum welfare\"?\n\n  9. What do the axes mean in Figure 3? Is the y-axis average solver gap over a test set of games? Is the x-axis number of training iterations?\n\n  10. Line 252--253. \"would be otherwise be too time-expensive\" has an extra \"be\".\n\n## Bibliography\n[1] Chen *et al* Learning to Optimize: A Primer and A Benchmark (2021)\n\n[2] Ling *et al* What game are we playing? End-to-end learning in normal and extensive form games (2018)\n\n[3] Li *et al* End-to-End Learning and Intervention in Games (2020)\n\n[3] Heaton *et al* Learn to Predict Equilibria via Fixed Point Networks (2021)\n\n", "limitations": "These are adequately addressed.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n  - Predicting/ computing NE/CE/CCE is certainly a worthy topic.\n  - I appreciated the use of strong duality for convex optimization! \n  - Experiments are thorough.\n\n## Weaknesses\n  - Overlooks certain important aspects of the literature.\n  - I found it hard to follow how the proposed network is actually trained.\n  - Scalability of proposed approach to even moderately sized games is unclear.\n\n##Edit\nChanged score to 7 after rebuttal.", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "4UjaaTk2vwn", "reviewer": "Reviewer_5ivh", "summary": "The authors demonstrate a method to perform unsupervised amortized optimization of game solvers that seemingly leads to sharp speedups. They also design an architecture that respects the equivariances of the problem and perform ablations demonstrating that this is useful. ", "questions": "- Your solver gap has not asymptoted on any of the graphs. Is there a small experiment you can run to check if they do asymptote in any reasonable number of iterations? (I am not asking you to run this experiment to improve review score) This would make clear if there’s significant progress to be made or if simply continuing to run your solver training would lead to continual improvement.\n- Is lower-case w (used throughout section 4.4) defined anywhere in the text?\n- Is there a section comparing the run-time of conventional solvers to your method? If not, this would be neat to include.\n- What is “naive payoff sampling” in the ablations?", "limitations": "Yes.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The technique seems useful and I could imagine it being helpful in MARL settings\n- That the objective is \"unsupervised\" (i.e. you don't need the actual optimal strategy) is very neat\n- The invariant architectures should be useful for other attempts at this problem.\n\nThe main weaknesses are in the writing of the paper, I highlight some problems below:\n\n- The superscripts in Line 133 come out of nowhere; for example, why does $\\hat{\\sigma}$ have the $L_1$ norm as a superscript? I’m not sure what these superscripts mean on a first read.\n- Someone from an adjacent field might not know what an NxN game is, I think it’d be worth explaining.\n- The citation links are broken and link back to the title instead of to the actual citation\n- Are Table 1 and 2 actually included in this paper? I see them in the supplement, are those the same tables you’re referring to in the paper body?\n- On figure 4 it’s not clear what “left” and “right” mean\n- In Figure 4 caption it’s worth pointing out (as you do in the text) that the arms correspond to worst, mean, best\n- The term MECCE is introduced but not defined anywhere in the main paper\n- The stack function in Equation 12 does not appear to be defined in the main text\n- The equivariant architectures section was quite hard to follow; it is unclear what the underlying logic behind each of the transformations is. I would love to see a more expanded version of this section in the appendix or with the extra page if the paper is accepted.\n- Equivariant is misspelled on line 193\n- Figure 4 is somewhat hard to read where the bars overlap, you might consider using different colors and making the arm sizes of one of the bars different than the other?", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept