Finding Mixed Strategy Nash Equilibrium for Continuous Games through Deep Learning
Authors: Zehao Dou
Xiang Yan
Dongge Wang
Xiaotie Deng
Venue:  (2020)
Keywords: Mixed strategy Nash Equilibrium
Continuous Game
Pushforward Measure
NI Function

Abstract: Nash equilibrium has long been a desired solution concept in multi-player games, especially for those on continuous strategy spaces, which have attracted a rapidly growing amount of interests due to advances in research applications such as the generative adversarial networks. Despite the fact that several deep learning based approaches are designed to obtain pure strategy Nash equilibrium, it is rather luxurious to assume the existence of such an equilibrium. In this paper, we present a new method to approximate mixed strategy Nash equilibria in multi-player continuous games, which always exist and include the pure ones as a special case. We remedy the pure strategy weakness by adopting the pushforward measure technique to represent a mixed strategy in continuous spaces. That allows us to generalize the Gradient-based Nikaido-Isoda (GNI) function to measure the distance between the players' joint strategy profile and a Nash equilibrium. Applying the gradient descent algorithm, our approach is shown to converge to a stationary Nash equilibrium under the convexity assumption on payoff functions, the same popular setting as in previous studies. 
In numerical experiments, our method consistently and  significantly outperforms recent works on approximating Nash equilibrium for quadratic games, general blotto games, and GAMUT games.

Under review as a conference paper at ICLR 2020
FINDING MIXED STRATEGY NASH EQUILIBRIUM FOR CONTINUOUS GAMES THROUGH DEEP LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Nash equilibrium has long been desired solution concept in multi-player games. especially for those on continuous strategy spaces, which have attracted a rapidly growing amount of interests due to advances in research applications such as the generative adversarial networks. Despite the fact that several deep learning based approaches are designed to obtain pure strategy Nash equilibrium, it rather lux- urious to assume the existence of such an equilibrium. In this paper, we present a new method to approximate mixed strategy Nash equilibria in multi-player con- tinuous games, which always exist and include the pure ones special case. We remedy the pure strategy weakness by adopting the pushforward measure tech- nique represent a mixed strategy in continuous spaces. That allows to gen- eralize the Gradient-base Nikaido-Isoda (GNI) function to measure the distance between the players' joint strategy profile and Nash equilibrium. Applying the gradient descent algorithm, our approach is shown to converge to a stationary Nash equilibrium under the convexity assumption on payoff' functions, the same popular setting as in previous studies. In numerical experiments, our method con- sistently and significantly outperforms recent works on approximating Nash equi- librium for quadratic games, general blotto games, and GAMUT games.
INTRODUCTION
Nash equilibrium Nash 1950) is one of the most important solution concepts in game scenario with multiple rational participants. plays an important role in theoretical analysis of games to guide rational decision-making processes in multi-agent systems. With the recent success of machine learning applications in games, it attracts even more research interests on applying machine learning technique for unsolved game theory problems, for example, computation of Nash equilibrium for multi-player games. this paper, we focus on games with continuous action spaces, which include the famous application for Generative Adversarial Networks (GANs) (Goodiellow as well as many important game types such as the colonel blotto game (Gross & Wagner 1950), Cournot competition RR 1996). We develop solution which significantly improves the quo.
al., 2014),
There have been several successful approaches to compute Nash equilibrium for multi-player (mostly 2-player) continuous game (Raghunathan et al., 2019: Balduzzi al., 2018 Letcher al.) 2018). These works seek Nash equilibria corresponding to pure strategies, in which each player takes specific action to achieve its best payoff given other players' actions. A major concern for such a solution concept is its possible non-existence. As a result, the convergences to a Nash equi- librium for these approaches were proven under the assumption for the existence of a pure strategy Nash equilibrium, which can hardly be checked in practice, and their applicability is limited to spe- eific types of games. On the contrary, is known that mixed strategy Nash equilibria always exist under mild conditions. And note that any pure strategy Nash equilibrium is also mixed strategy Nash equilibrium, which means the latter one is much more desired solution concept.
However, key challenge that obstructs the study of computing a mixed strategy Nash equilibrium, especially for a continuous game, lies on how to design an efficient method to represent the mixed strategy. To be precise, a pure strategy can be represented by single variable choosing from some region. But as a distribution on each player's ' action space, a mixed strategy with respect to the player is defined in (subspace of) real space R. More generally, exact representation for a mixed strategy of a player usually requires many variables in a continuous space. In addition, the corresponding probability distribution may not have density function in closed-form.

---

Under review as a conference paper at ICLR 2020
To address this challenge, we introduce a pushforward measure technique. It is a common tool in measure theory to transfer a measure to some specific measure space (Bogachey 2007). Specific to continuous game, the probability distribution corresponding to mixed strategy is obtained via mapping parameterized by neural nets from a multi-dimensional uniform distribution.
With this pushforward representation, we generalize the Gradient-based Nikaido-Isoda (GNT) func- tion introduced by Raghunathan et al. (2019), to handle mixed strategy Nash equilibria. The original GNI function can be viewed measure for the distance between any joint strategy profile and Nash equilibrium after applying the payoff functions of players. With proper generalization and modification, we develop its mixed strategy version a proper measure for Nash equilibrium. We prove that the distance becomes zero if and only if a stationary mixed Nash equilibrium is obtained. Then we apply the gradient descent algorithm to the general GNT function, which converges to a stationary mixed Nash equilibrium under the convexity assumptions on the payoff functions.
Finally, we compare our method with baseline algorithms in numerical experiments. Our approach shows effective convergence property in all the randomly generated quadratic games, general blotto games, GAMUT games and Delta-Diral GAN (in appendix), which outperforms other baselines.
BACKGROUND AND PROBLEM DESCRIPTION
The discrete action space Nash equilibrium computation has been most widely studied in the litera- tures. Most well-known being the Howson algorithm (Lemke & Howson (964) for solving the bimatrix game. The state-of-art theoretical work of T saknakis & Spirakis (2007) provided a so-
lution of 1/3 approximation in polynomial time. And empirical work (Feamley al. 2015) shows it also performs well against practical game solving methods for the bimatrix game.
However, the continuous action space game computation is widely used in practice, while few meth- ods are known for the general Nash equilibrium computation and all restricted to pure strategies. The GNI function is considered by |Raghunathan et al. (2019) as one possible technique for multi-player continuous game, but they only consider pure strategies. With further assumption that the utility functions of players are twice continuous differentiable, gradient- based algorithms are developed (Balduzzi et al.) 2018 Letcher et al.] 2018). But they do not provide way to parameterize mixed strategy of continuous action space, and even we are able to do so through neural networks, the Hessian of utility functions, necessary in these approaches, is extremely hard compute or store.
Game-theoretical approach has had useful applications to machine learning such as the optimization of GAN network training (Daskalakis al. 2017; Gidel at. 2018) and adjustment the gradient descent method (Balduzzi et al. 2018). However they are limited to 2-player zero-sum games.
We are the first work to study the mixed strategy continuous game Nash equilibrium computa- tion. Our work is motivated by the utilization of the Nikaido-Isoda (NI) function for loss function minimization (Uryas' ev & Rubinstein| 1994] Raghunathan et al., (019). We start to establish theoretical formulation of the extend mixed strategy continuous action space Nash equilibrium as a result of the minimization on functional variation- based Nikaido-Isode function.
2.1 CONTINUOUS GAME NASH EQUILIBRRUM
Find x" (zf x2 .Ny)
S.l. x arg min f(())
(1)
xER"Ix_.x"".
Here N denotes the number of players, and x, E Rnd the strategy of the i-th player where n, is the dimension of its action space. Let n = Em n2, and x = (2,,, pure strategy among all players while x (x1,.... Ii+1,, NN) E g=-n, the joint pure
N E Rn denotes the joint
strategy among players except i. fi I= + R denotes the utility function (cost) of i-th player. A solution x" to (T) is called a pure strategy Nash equilibrium.
2.2
NIKAIDO-ISODA (NI) FUNCTION
In the paper by Nikaidō et al. (1955),
Nikaido- Isoda (NT) function is introduced as:
N
N
o(x) = Σ f((x)
inf = fi(x))
4
Σ (x))
(2)
i=1
2

---

Under review as a conference paper at ICLR 2020
From the Equation 2 know d(x) > 0 for Vx E R", and 6(x) is the global minimum of NI function which can only be achieved at a Nash equilibrium (NE). Therefore, a common algorithm of computing NE points is minimizing the NI function above. However, it is a huge difficulty to handle the global infimum. On one hand, the global infimum can not be obtained in finite time. be unbounded below in player bi-linear games, where (x) = x Mzz = - -x(x). All of the facts above show us the shortcomings of NI function, and in order to rectify them, Raghunathan et al. (2019) introduce the following Gradient-base Nikaido-Isoda (GNI) function.
On the other hand, the infimum
games, for example the two-
2.3 GRADIENT- BASED NIKAIDO-ISODA (GNI) FUNCTION
we calculate local infimum the NI function ((x) instead of global infimum, the time complexity and unbounded infimum are longer shortcomings. To be precise, given the local radius X, local infimum can be approximated by steepest descent direction, and we get the following GNI function:
N
((x - Σ (fi(x) f((=1, I1-1, 14 - 2441, - ,I,N)))))))))))))"")
By minimizing V(x, X), stationary Nash point x", where V., (xx") 0 for Vi, can be approx- imated efficiently. Furthermore, all the utility functions ft are convex, then the stationary Nash points (SNP) obtained are actually Nash Equilibrium (NE).
3 (MIXED-GNI) GRADIENT-BASED NIKAIDO-ISODA FUNCTION OF MIXED STRATEGY ON CONTINUOUS GAMES
In this section, we are going to introduce our novel Gradient-based Nikaido-Isoda function of mixed strategy continuous games (Mixed-GNI), which is used to get approximated solution of the following optimization problem.
Find n (mi, 22: s.t. x arg min E f1 Ø2, ,NN)
x: -T My Vj
Before we solve this optimization problem, there is another fundamental question, which how we should represent (or parametrize) distribution H;. The simplest way do is to parametrize its density function. However, not every distribution has its density function, such as Dirac distribution, and it will be inconvenient for to do sampling from only density function. Therefore, introduce another way, adopting the pushforward measure to represent distribution.
Given a distribution μ4 and mapping g()), data drawn from μl can be transported into new distribution 14 (constituted by gx))). Technically speaking, μ4 is called the pushforward measure of po by mapping g. denoted by μl = g (po).
Here, for Vj E [N] we prepare each distribution Ty corresponding pushforward function gj Rd R and we have:
Jj 9 (U)
where U stands for the uniform distribution on [0. 1]d Each time we want to sample from distribu-
tion ni, only need to sample several w; [0, 1j from distribution U and calculate gı(w;). Then, these gi (wxi form sample set from distribution ग.. And optimization problem becomes:
Find g' = (gf 92. ... ........)....................... :hv)
s.t. g. = arg min
-9 ~ f((g1((1) (W()) g2(w2), ... (9 (wN))
(4)
To solve the optimization problem above, we consider the following Gradient-based Nikaido-Isoda function Mixed strategy on Continuous games (Mixed- GNI), generalized from the GNI function introduced above, and we call this function V the local regret:
(ig 92. .g:i))=
Flgi.g2. 92. .9N) Felgi. 19--1.9 F., ..NN)
(5)
Vi(gi. 92, ... A9n;
3

---

Under review as a conference paper at ICLR 2020
Here, 6g. Fi stands for the 1-st order variation of functional F; element function 9: and = E
, "2. .9N)
[fi (2w)) .9N (wN))
wyrB, vj
By minimizing the functional (i 92 points (SNP), and even get Nash equilibrium if all the utility functions f, are convex. We will prove them in the next section.
92. ... 9N: A), we can approximately get stationary Nash
In practice, we further parametrize these pushforward functions as: 9:(-) = gi(,, f:), to efficiently calculate derivatives instead of variations. For simplicity, we denote 9i as go.- order to obtain better expressibility, we use neural networks as the architecture to parametrize these pushforward functions. Then, Mixed-GNI function V can be transformed to:
: "00, 900: X)
Σ Fi 90.: - ; F; (go ... 90: 1 90, A0a, Far
90,x)
Finally, the Mixed-GNI function can estimated by sampling the points from distribution as an estimator of these F; and minimized by implying gradient descent these function parameters 0,, i e [N]. the convergence which is proved in the next section.
THEORETICAL ANALYSIS OF MIXED-GNI
4.1 THE SUFFICIENT AND NECESSARY CONDITION OF STATIONARY NASH POINT
As mixed strategy an N-player continuous game, (Tı, T2," TN) Ug is a stationary Nash point (SNP) if and only if for Vi E [N], the 1-st order variation
U. 92 U.
U)
9N
8g (F:) =0
(6)
holds at each direction (x). Here:
Fi 92: ... .9N) seyw Vy
E
(W(g)( ge(w)), .. [N())))]
the expectation of the i-th player's utility with the form of N-variable functional. Now, we compute the variation above and deduce the sufficient and necessary condition of SNP.
6g. (F)))(())] = lim (Fil9r,925"" ... .9N) Fi(g1.
e.. -.N.....NN) ,9N))
c0
= E
wirll, [o(wi)"
(.Je(o (2 ... .NN (w()))
= I [o(ws)"
E wy vi (e g2(w2) ... (N(ww)))
G(wi)) / a(wi) G(w;)da 10.1
E (o(us) win0"
where:
G(wi)
E Vefilgn (wi) g2(w2), 99N IN (wN))]
wi-C, Vi For SNP, Equation 6 holds at each direction o (x), i.c. G((i)) = O. Therefore, we have
Theorem 1. π = (m,, T2, ,,)) = (9 U, 92 ...... UU) is stationary Nash point (SNP) for an N N-player continuous game if and only if:
E
(W)) (n.ggw)))) 0,
Vau E Rd
wy Viya holds for all i [N].
From Equation
7p we also know that:
&ge (F))((w)) = (G(w)),
In other words, the steepest direction is:
og (Fi) G(wi) W Vigi
E
V ViJi(gi (w1), g2(w2), "gx((,x)))
Then show the relationship between stationary Nash point and Nash equilibrium.
Theorem 2. Denote SSN NNE as the set of SNPs and NEs of a particular N -lplayer contimuous game. Obviously, SNE SSNP. If all uiiitty functions Se are convex, we have: SN SSNP
4

---

Under review as a conference paper at ICLR 2020
Proof. Suppose (T1, T2. . U. (9) U.... U)
) is an SNP, will prove it an NE
when all functions fi are convex. According to the convexity and the condition of SNPs, we know that for Vi [N] and any other pushforward function 9;:
Filgi, 92, .NN) Fi -h..... .9N) E wy wy Vj
(f(l)(w)) ... -i((w)), (N((wN) fi 92(2)) ... (N((NN)
E wy w vj
[(o:(w))) gi(w))) V.filon(41), (.,(N))
(8)
E [(r(w)) ";((w)))* wyml fi
E
Vili(m (wi (w)), ... ".,N(w)))]]]
mnnh
E [(i(wr)) gi(wi)) 6g (F:) =0
wi-
which leads to our conclusion, that π (of U, o U, (U....9UU)) a global Nash equilibrium.
Next, we show the relationship between the zeros of Mixed-GNY function V(gi 92, .NN) and SNPs of the --player continuous game.
Lemma 1. Assume f _dd + R is twice differeentibbleuuncee
and its 1-st order gradient f is
Lip-iihchitz continuous. Then for Vx, y E R.d, we have:
1 15()) [(x) (VI(x), x> 15.TTslle 1ly flyllyy10 x1
Proof. According to the condition of f, there holds the following equations.
lf(g) f(x) (Vf(z). 2>1
(Vf(z + -(y-z)) Vf(x), 2)
[V - x>) dr
(9)
[V + T(y- - vf(x)] lly - =||dT
LyTlly- Cylll-=2|ßdd , x112
With this lemma, we can show that each global minimum of V 92, ... 9NN ) is also an SNP. Theorem 3. If each utility function fo is twice differentiable and its 1-st order gradient V is Lipsschitt continuous. Then:
X 2/ F15g,F Filg1.92: 92. ..
32
..NN) .IN)ll? < V.(g1. ... .9:: A) < 16, F.(g1. ,9x)]l
2
holds when X t, Here, || 1 a functional norm which means:
|1 = / 1.1.a [1f(w))12 dw;, E (1:)) winl
Proof.
Vi(gi, 92. .9N; A) =F,(gi, 92. ... [N)= [--- Fl(g....
9. 18 Fi, ,9N)
uy-0l vi [f(()((1)) g2(2g)2)))) ... (gN(wN)) (w)) (g(()))) A6 F((w), ... (wNw)))]
IE
(10)
Then, according to Lemma 1
Vi(11. 92.
.9N:
( V (2w)), .g((w))))))))))))))))))))))>)))) + L, 1 F((w))l12
E
w
2
16 Fe 02. .. .nv) + LIX² E || Filyi, 92. gN (w:))1
(1I)
31
116
F..91.92..... .gx)
2
5

---

Under review as a conference paper at ICLR 2020
And the other side of this inequality is similar.
The theorem above tells that, Vi91. 92, .N:; X) is always non-negative as long as X & T,y And its global minima, or the other words, its zeros, are surely SNPs, because for vi E [N]:
Vi(g, "2.-- .N: A) 0 + 92 .gN)
Finally, we analyze the stability of SNPs. In the following theorem, we show that the 2-nd order variation of functional V a positive semidefinite operator, which confirms the stability of SNPs.
Theorem 4. The 2-nd order variation (g" SSNP and 0 < E Ls
X) is positive semidefinite operator for Vgg E
Proof. The 1-st and 2-nd order variation of Vi(g: A) satisfy:
(V: A) (g) (g) X (g)
(12)
where g (g), 02, ... 9NN
(g), .. -1 1: 26, Fi, ,9N) and
D. = Diag(On, (0n1 Xn 00 0x Xn, On X8
Onx xnx)
matrix. Given g" ESSNP, then (l.(g")
(g) VV A) (g))
ž \o"Fi(g') D,,,D,)0'
(13)
F A F5 D
A Fi ).); 1020000FFF D.)
which is positive semidefinite. Therefore:
Vg'' Σ vVVi(g";)))
1=1
also positive semidefinite.
4.2 CONVERGENCE ANALYSIS
In this section, we analyze the convergence analysis of gradient descent:
g (l++1) g(*) - p (g())) A)
According to the definition functional Vgg A), it can rewritten as the following form:
Vgg; X) w Vje(N]
GG (g) (w1), (2w2), ... .gN((N))))
where Gy = Ei fe(y, 12, ... ,UN) - fi(y........ ... 11 Vi AV.f((y1. U2. ,UN)... ... NN).
Theorem 5. Suppose VGv(x) is Le-Lipschitz continuous. Through gradient descent, the function
sequence (k) converges sublinearly to stationary Nash point (SNP) g" is < Lo < L.
Proof. According to Lemma
we have:
(ig (k+1);; A) & (g)
E
(W1)) ... [N((w)) (g));
4y VJEIN]
La p² (k))
w VjE[N] 2
La p²) (g (A); :))l
v(g(h) (k) 2) - (p 2
[V((()))) (2pLG - (
|8V (x))
2L.
(14)
Let 0, 1, ... K, and add them up, we have:
(2pLic (2plic-(ptcc)
K
V(g (K+1); & V(g. ();)
Σ
(x)
2LG

---

1e-2 and momentum Under review as a conference paper at ICLR 2020
Since À < i.,, we know that (g 0 by Theorem 3 have
2Lg
[8V
10 ;A)l?
v(glo)
2pLa - -(pL))
(15)
2Lc
((
min kE(K]
18V 11))3 < 2ppha (plia)²
k+1
which completes our proof.
EXPERIMENTS
To evaluate the practical performance of our approach, we apply it to three types of games, two- player quadratic games, general blotto games, and GAMUT games, the most popular games for evaluation of Nash equilibrium algorithms. In all the experiments, we set the local radius 1e-3 and we use gradient descent as our optimization method with step size
x = 0.9. The network architecture we use for the pushforward functions go is a 6-layer fully connected neural network with the size of each layer as: 20, 40, 160, 160, 40, 20. The size of its output layer the dimension of each player's action space. From forward backward, the activation function we use is: tanh, tanh, tanh, ReLU, tanh, tanh.
We mainly compare our approach with three recent studies, gradient descent for GNI function Raghunathaan et al. 2019) (gradGNI in short), Symplectic Gradient Adjustment algorithm (Bal- duzzi et al. 2018) (SGA in short), and Stable Opponent Shaping (Letcher et al., 2018) (SOS in short) they outperformed other existing algorithms applicable continuous game settings. For all these methods, we either follow the standard hyper-parameters mentioned the original papers, or the resulting in the best convergence.
5.1 TWO-PLAYER QUADRATIC GAME
The two-player quadratic game is defined by the the players' payoff functions S4 (i 1,2):
fi(x) x- Q
(16)
where Q, E (+s +22)
x xxmx t22), T2 E 1m x = (x1, and H2 E R". In our experiments,
choose n2 5. 103. For each pair of n,, randomly generate 100 instances for the matrix Q; and r; for = 2. Each item in each matrix Q; and each vector r; follows the uniform distribution on (0, 1] independently.
We show the converging process of all algorithms for one game instance (n1 = n2 = 3) in Fig. ((a) example. As we can see, our approach effectively converges to stationary Nash equilibrium point. While gradGNI also converge in this instance, its result has larger local regret. In other words, Nash equilibrium, which coincides with the essential difference
obtain worse approximation between pure strategy and mixed strategy. The Mixed-GNI approach searches for the equilibrium in the mixed strategy space, which includes the pure strategy space that gradGNI searches in. On the other hand, SGA and SOS diverge in this game instance. We further take the average of the final local regrets after 2000 iterations for all the 100 instances, summarized in Tab. [ All the algorithms show consistency the dimension of action space increases, and Mixed-GNI outperforms others regardless of the randomness of game structures.
5.2 GENERAL BLOTTO GAME
We next consider the general blotto game, which differs from previous games in the action space of each player for which further constraints apply.
In blotto game, player 1 and 2 (sometimes known as two colonels) have a budget of resource X1, X₂ respectively. W.L.o.g we set X1 < X2. There are m battlefields in total. In each battlefield j. when two players allocate Tı #2y resource on it, the payoff of player i is:
U4j = f(.j - x-i;), where f(x) tanh (x). where - denotes the player other than player i. Each player's payoff across all battlefields is the sum of the payoffs across the individual battlefields. For each player i, a feasible pure strategy r, (Ia1,.-. Fim) R must also satisfies ΣØ= Jaj < X,- Here adopt the generalized
(17)
7

---

Under review as a conference paper at ICLR 2020
Miset-GNI
Mixes GNI gradGNi
MivedGGM gPaSGN
1.2
local ragrat (Pe-4)
S05
SGA
local rag (Pa-3)
local Nogret
0.8-
0.2
0.
250 500 1000
250 500
750 1000
1250
750 1096 1250 1500
rounds
(a) n4 = 3. 2-player quadratic
(b) m 2-player blotto
(c) n4 4-plyyr gamut
Figure I: Local Regret of Various Games.
Mixed-GNI (ours)
gradGNI
SGA
SOS
Quadratic (n; = 3)
(1.63 1 e.30)
(1.01 0.03)e-1
2.59 = 0.17
1.86 1 0.36
Quadratic (m: 5)
(2.84 1 1.95)e-
(2.95 1 0-19)
3.92 = 0.22
2.89 1 0.37
Quadratic (n, 10)
(3.76 + 3.0
(1.47 + 0.08)e-
2.54 = 0.09
2.46 = 0.12
Blotto (m = 3)
(6.32 1 4.97)e-6
(2.62 0.38)e-5
(5.26 0.91)e-5
(7.31 1 0.82)e-5
Blotto (m 5)
(4.52 1 3.09)e-6
(1.10 1 0.06)e-5
(1.21 1 0.18)e-5
(7.39 1: e.33)))
Blotto (m = 10)
(3.62 + 2.39)e-6
(7.60 + 0
(5.94 + 0.26)e-6
(5.02 + 0.28)e-6
GAMUT (n,
(1.95 + 0.42)c-3
(1.80 + 0.8)ee1
(0.94 4: 0.13)e-
(0.96 + 0.17)e-1
GAMUT (n; 5)
(8.90 + 0.79))-3
(1.52 0.27)e-1
(2.59 + 0.60)e-1
(2.67 + 0.81)e-1
GAMUT (n, 10)
(1.54 0.86)-22
(1.84 0.48)e-1
(1.76 + 0.32)e-1
(1.90 + 0.47)e-1
Table 1: Comparison results.
blotto game proposed by Golman Page (2009) with continuous payoff functions. The payoff functions in vanilla blotto game is discontinuous, for which our method as well as baselines fails. In our experiments, we set m E {3, 5, 10). For each m, we randomly generate 100 instance for the budget X,, following the uniform distribution on [0, I] independently.
We show the converging process all algorithms for one game instance (m = 3) Fig. I(b) as example. All the algorithms converges for this game, while gradGNI, SGA and SOS converge faster and more smoothly comparing with our Mixed-GNi However, similar to the quadratic game, their final results have larger local regrets. This coincides with the fact that the mixed strategy is a better solution concept than the pure strategy, especially in blotto games. We further take the average of the final local regrets after 2000 iterations for all the 100 instances, summarized in Tab.
[ All the algorithms show consistency as the dimension of action space increases, and Mixed-GNI outperforms others regardless of the randomness of game structures.
5.3 GAMUT GAMES
Finally, apply method the game instance generated by the comprehensive GAMUT suite of game generators designated for testing game-thcoretic algorithms (Nudelman et al. 2004). GAMUT includes group of random distributions, based on each of which the payoff of each player for each pure strategy profile can be drawn independently. To be precise, we extend the quadratic game multi-player version, where r; 0, and 100 game instances with players are generated. For each instance, one of the distributions from the GAMUT set is selected, and each item in each matrix Q is sampled according it independently.
We show the converging process of all algorithms for one game instance in Fig. I(c) Both Mixed- GNI and SGA converge, but SGA has much worse final result than our Mixed-GNV And this time, gradGNI diverges while SOS converges much slower. Furthermore, we take the average of the final local regrets after 2000 iterations for all the 100 instances, shown Table
From these different games, we know that our Mixed-GNe converges and performs better than two baselines in all of the three games, which shows the effectiveness and efficiency of our Mixed-GNI model. As the first algorithm to compute the mixed strategy Nash equilibrium of games with con- tinuous action space, we believe that the technique we introduced here will enable new optimization researches of many exciting interaction domains of algorithmic game theory and deep learning.
8

---

Proceedings of the national academy of Under review as a conference paper at ICLR 2020
REFERENCES
David Balduzzi, Sebastien Racaniere, James Martens, Jakob Foerster, Karl Tuyls, and Thore Grae- pel. The mechanics of n-player differentiable games. arXiv preprint arXiv:180..05642, 2018.
Vladimir Bogachev. Measure theory, volume Springer Science & Business Media, 2007.
Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training gans with optimism. arXiv preprint xrXiv:1711.0014) 2017.
John Fearnley, Tobenna Peter Igwe, and Rahul Savani. An empirical study of finding approximate equilibria in bimatrix games. In International Symposium on Experimental Algorithms, pp. 339- 351. Springer, 2015.
Gauthier Gidel, Hugo Berard, Gaëtan Vignoud, Pascal Vincent, and Simon Lacoste-Julien. A variational inequality perspective on generative adversarial networks. arXiv preprint arXiv:1802. 10551, 2018.
Russell Golman and Scott E Page. General blotto: games of allocative strategic mismatch. Public Choice, 138(3-4):279-299) 2009.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural infor- mation processing systems, pp. 2672-2680, 2014.
Oliver Gross and Robert Wagner. continuous colonel blotto game. Technical report, RAND PROJECT AIR FORCE SANTA MONICA CA, 1950.
Carlton E Lemke and Joseph T Howson, Jr. Equilibrium points of bimatrix games. Journal of the Society for industrial and Applied Mathematics, 12(2):413 423, 1964.
Alistair Letcher, Jakob Foerster, David Balduzzi, Tim Rocktäschel, and Shimon Whiteson. Stable opponent shaping in differentiable games. arXiv preprint arXiv:1811.08466 2018
John F Nash. Equilibrium points in n-person games. sciences, 36(1):48-444 49, 1950.
Hukukane Nikaidô, Kazuo Isoda, et al. Note on non-cooperative convex games. Pacific Journal of Mathematics, 5(Suppl. 1):807-815, 1955.
Eugene Nudelman, Jennifer Wortman, Yoav Shoham, and Kevin Leyton-Brown. Run the gamut: A comprehensive approach to evaluating game-theoretic algorithms. In Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems- Volume 2, pp- 880-887. IEEE Computer Society. 2004.
Varian Hal Intermediate microeconomics: a modern approach, 1996.
Arvind U Raghunathan, Anoop Cherian, and Devesh Jha. Game theoretic optimization via gradient-based nikaido-isoda function. arXiv preprint / 2019.
Haralampos Tsaknakis and Paul G Spirakis. An optimization approach for approximate nash equi-
libria. In International Workshop on Web and Internet Economics, pp. 42-56. Springer, 2007.
Stanislav Uryas' ev and Reuven Y Rubinstein. On relaxation algorithms in computation of nonco- operative equilibria. IEEE Transactions on Automatic Control, 168-:122311166 1994.

---

Under review as a conference paper at ICLR 2020
A EXPERIMENTS ON DELTA-DIRAC GANS
Gidel et al. (2018) introduce a one-dimensional GAN where the real data follows a Dirac-Delt
distribution. This experiment is also conducted in our baseline paper by Raghunathan et (0119)
As two-player game, the payoff functions for the two players are listed as follows: f1 x2) = log(1 + 0x1) + log(1 exp(x122))
(18)
f2(21, #2) - log(1 + exp(x112))
where the the location of the Dirac spike. In Figure 2, we show the converging process of all algorithms for one game instance (i.e. for single 0). As we can see, our Mixed-GNI and original gradGNI algorithms converge while the other two diverge. Compared with gradGNI, our approach is converging much faster. We further take the average of the final local regrets after 2000 iterations for all the 100 instances (i.e. 100 different 0s) and show the results in Table 2. In this experiment, our Mixed-GNI algorithm again outperforms the others, regardless of the randomness of game structures.
1.2
Mixed-GNI
1.0
gradGNI
SGA
local regret (*e-1)
0.8
0.4
0.2
0.0
250
500
750 1000 1250 1500 1750 2000
iteration rounds
Figure 2: Local Regret of Dirac- -eeta GAN Game
Mixed GNI (ours)
gradGNi
SGA
SOS
Dirac-Delta GAN
(7.23 3.70)e-5 (6.52 3.98)e-3
(1.39 0.96)e-2
(1.41 0.87)e-2
Table 2: Comparison Results
10


Reviews:
[{"review_id": "rJg8GDbTFB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a method to learn mixed-strategies Nash equilibrium in multi-player games. To do so they describe a gradient-descent method that aims at minimizing a Kikaido-Isoda function (which is zero if an equilibrium is found). The paper offer proofs of the convergence towards a stationary Nash equilibrium in the case of convex cost functions. It also provides an application with a strategy approximation made with a deep neural network. They authors exemplify the strengths of the method on toy problems that are quite standard in the domain. \n\nI liked the paper very much but I have some concerns. First, I feel that the framework is based on a variational approach which would be well suited for a 0-order optimisation (like a black box or an evolutionary method). I wonder why the authors wanted to use a gradient based approach that adds a second layer of approximation and additional meta parameters to tune. \n\nSecond, I felt the theoretical proofs are not using much more than standard algebra and the convex assumption was a bit unrealistic in most of multi-agent problems. I'd like the authors to comment on this. \n\nI was also wondering how this work can be related to other papers that try to learn a Nash equilibrium (or an \\epsilon-Nash) on the bases of a difference in some norm between the value of the current policy and the value of the NE. For instance \"Learning Nash Equilibrium for General-Sum Markov Games from Batch Data\" by Perolat et al. This work addresses discrete action spaces but seems similar in spirit to me. Could the authors comment on this ?\n\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Skg-r1GKYr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a novel algorithm for finding mixed-strategy Nash equilibria in games with continuous action spaces. The paper proves convergence to a stationary Nash equilibrium under the assumption of convex utility functions. In quadratic games, general blotto games and GAMUT games, the proposed algorithm (MC-GNI) significantly outperforms its competitors. This experimental finding is not surprising, as its competitors were designed to compute pure-strategy Nash-equilibria.\n\nThis paper investigates an important, relatively unexplored problem. Its proposed algorithm appears theoretically justified and to achieve nontrivial performance in practice. However, I feel that there are some issues with this paper. \n\nThere has been a significant amount of recent work on differentiable games. It would benefit readers for the paper to discuss how this work and those works are related. In particular, the latter are motivated by designing gradient-based algorithms for finding parameters of neural networks corresponding to local equilibria. These neural networks may themselves be playing nondeterministic strategies in some underlying game (e.g., GANs). This closely resembles the paradigm of the algorithm proposed in this paper, which finds deterministic parameters for a network that itself induces a nondeterministic strategy. This leads to a number of questions:\n1. In the experiments, the paper’s language suggests that SGA is constrained to pure strategies. Why is it not parameterized by a network producing a stochastic strategy? This seems like the sensible comparison.\n2. How are the convergence guarantees discussed in this paper related to the capacity of the network being used to approximate the policy? Are they lost if the network has insufficient capacity?\n3. The paper mentions that SGA outperforms other existing algorithms applicable to continuous game settings. What about stable opponent shaping??\n\nThe writing in the paper would benefit from revision. While the paper generally gets the point across, much of it feels sloppy. There are also many typos, some of which are listed below.\n \nTypos:\n- Raghunathan et al. (2019) introduces \n- In precise\n- drown\n- for $\\forall$\n- we prepare each distribution πj a corresponding pushforward function\n- Therefore, a common algorithm of computing\n- On the one hand, global infimum can\n- We develop a solution significantly improves the status-quo.\n- of Mixed strategy on Continuous game\n\nOther:\n- The paper alternates between his and it when referring to players\n\nOverall, I think this work is an outline for a nice paper but would like to see \n1) Clarification regarding its relationship to existing work\n2) Experimental baselines in which SGA and stable opponent shaping are parameterized to produce nondeterministic strategies \n3) Cleaner writing", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BklEtuqg5H", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work describes a method for finding mixed-strategy Nash equilibria in (normal form) games with continuous action spaces. Their work builds off (Raghunathan '19), which is a gradient-based method for finding pure-strategy Nash, based on the NI function. (It comes with all the standard caveats of gradient-based methods for finding Nash). The central contribution of this work is to parameterize a mixed strategy via a learned NN mapping from a simple distribution U[0,1]^d to the mixed strategy of interest.\n\nMy first impression on reading this work is that this learned parameterization of the mixed strategy is exactly how the GAN generator produces a distribution of samples (images). The generator network takes a noise vector sampled from U[0,1]^d or some other distribution, and samples an \"action\" (i.e. an image). Indeed, the original GAN paper (Goodfellow, 14) talks about this: \"Generative adversarial nets are trained by simultaneously updating the discriminative distribution so that it discriminates between samples from the *data generating distribution*\" (Fig. 1). It is not the case, as stated in Section 2, that GANs only produce pure strategies. \n\nThe optimization rule for GNI is different than standard update rules: specifically, there are two step sizes \\lambda and \\rho, if \\lambda -> 0 I think it becomes steepest descent but for \\lambda > 0 it is kind of like an optimistic descent method (because each agent takes a gradient step assuming the other agents have already done SD by \\lambda). This update rule has some desirable theoretical properties, which I believe are mostly proven by Raghunathan '19. It would be very useful to state more explicitly which of these properties are not known to be true for e.g. independent steepest descent for each agent.\n\nThe experimental section is nice in that it shows some toy games where mixed strategy continuous equilibria do better than pure-strategy ones, and shows that MC-GNI can find something better than a pure-strategy equilibrium. But if the claim is that GNI has these good equilibrium-finding properties, and you're already using the GAN decoder strategy, why are there no experiments on GANs? Even Raghunathan has experiments on GANs (albeit ones with pure-strategy (delta-function) equilibria).\n\nNits:\n- MC-GNI is a confusing name because MC usually refers to \"Monte Carlo\" in this context\n- I'm confused at the end of section 3 how \"implying (sic) gradient descent on these function parameters\" is performed. Are points sampled from U[0,1]^d and used as an estimator for F_i, as in a GAN? I don't see how the non-MC-sampled F_i can be computed. It would be nice to clarify one way or another.\n- I don't see \\lambda mentioned on the RHS of the last equation in sec. 3.\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents an algorithm to compute mixed-strategy Nash equilibria for continuous action space games. While the paper has some novelty, reviewers are generally unimpressed with the assumptions made, and the quality of the writing. Reviewers were also not swayed by the responses from the authors. Additionally, it could be argued that the paper is somewhat peripheral to the topic of the conference.¨

On balance, I would recommend reject for now; the paper needs more work.
Decision: Reject