Title: FINDING MIXED STRATEGY NASH EQUILIBRIUM FOR CONTINUOUS GAMES THROUGH DEEP LEARNING Anonymous

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.

1. INTRODUCTION:

Nash equilibrium (Nash, 1950) is one of the most important solution concepts in game scenario with multiple rational participants. It 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. In this paper, we focus on games with continuous action spaces, which include the famous application for Generative Adversarial Networks (GANs) (Goodfellow et al., 2014) , as well as many important game types such as the colonel blotto game (Gross & Wagner, 1950) , Cournot competition (R, 1996) . We develop a solution which significantly improves the status-quo.

There have been several successful approaches to compute Nash equilibrium for multi-player (mostly 2-player) continuous game (Raghunathan et al., 2019; Balduzzi et al., 2018; Letcher et al., 2018) . These works seek Nash equilibria corresponding to pure strategies, in which each player takes a 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 equilibrium 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 specific types of games. On the contrary, it is known that mixed strategy Nash equilibria always exist under mild conditions. And note that any pure strategy Nash equilibrium is also a mixed strategy Nash equilibrium, which means the latter one is a much more desired solution concept.

However, a 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 a 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 a (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 a density function in closed-form.

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 (Bogachev, 2007) . Specific to a continuous game, the probability distribution corresponding to a mixed strategy is obtained via a mapping parameterized by neural nets from a multi-dimensional uniform distribution.

With this pushforward representation, we generalize the Gradient-based Nikaido-Isoda (GNI) function introduced by Raghunathan et al. ( 2019), to handle mixed strategy Nash equilibria. The original GNI function can be viewed as a measure for the distance between any joint strategy profile and a Nash equilibrium after applying the payoff functions of players. With proper generalization and modification, we develop its mixed strategy version as a proper measure for a 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 GNI 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-Dirac GAN (in appendix), which outperforms other baselines.

2. BACKGROUND AND PROBLEM DESCRIPTION:

The discrete action space Nash equilibrium computation has been most widely studied in the literatures. Most well-known being the Lemke-Howson algorithm (Lemke & Howson, 1964) for solving the bimatrix game. The state-of-art theoretical work of Tsaknakis & Spirakis (2007) provided a solution of 1/3 approximation in polynomial time . And empirical work (Fearnley et 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 methods 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 a 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 to compute or store.

Game-theoretical approach has had useful applications to machine learning such as the optimization of GAN network training (Daskalakis et al., 2017; Gidel et al., 2018) and adjustment on 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 computation. Our work is motivated by the utilization of the Nikaido-Isoda (NI) function for loss function minimization (Uryas' ev & Rubinstein, 1994; Raghunathan et al., 2019) . We start to establish a theoretical formulation of the extend mixed strategy continuous action space Nash equilibrium as a result of the minimization on a functional variation-based Nikaido-Isoda function.

2.1. CONTINUOUS GAME NASH EQUILIBRIUM:

EQUATION

Here N denotes the number of players, and x i ∈ R ni the strategy of the i-th player where n i is the dimension of its action space. Let n = N i=1 n i , and

x = (x 1 , x 2 , • • • , x N ) ∈ R n denotes the joint pure strategy among all players while x -i = (x 1 , • • • , x i-1 , x i+1 , • • • , x N ) ∈ R n-ni

the joint pure strategy among players except i. f i : R n → R denotes the utility function (cost) of i-th player. A solution x * to (1) is called a pure strategy Nash equilibrium.

2.2. NIKAIDO-ISODA (NI) FUNCTION:

In the paper by Nikaidô et al. (1955) , Nikaido-Isoda (NI) function is introduced as:

EQUATION

From the Equation (2), we know φ(x) 0 for ∀x ∈ R n , and φ(x) = 0 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.

On the other hand, the infimum can be unbounded below in some games, for example the twoplayer bi-linear games, where

f 1 (x) = x T 1 M x 2 = -f 2 (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-based Nikaido-Isoda (GNI) function.

2.3. GRADIENT-BASED NIKAIDO-ISODA (GNI) FUNCTION:

If we calculate local infimum in the NI function φ(x) instead of global infimum, the time complexity and unbounded infimum are no longer shortcomings. To be precise, given the local radius λ, local infimum can be approximated by steepest descent direction, and we get the following GNI function:

V (x; λ) = N i=1 f i (x) -f i (x 1 , • • • , x i-1 , x i -λ∇ i f i (x), x i+1 , • • • , x N )

By minimizing V (x, λ), a stationary Nash point x * , where ∇ xi f i (x * ) = 0 for ∀i, can be approximated efficiently. Furthermore, if all the utility functions f i 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 on continuous games (Mixed-GNI), which is used to get an approximated solution of the following optimization problem.

Find

EQUATION

Before we solve this optimization problem, there is another fundamental question, which is how we should represent (or parametrize) a distribution π i . The simplest way to do so is to parametrize its density function. However, not every distribution has its density function, such as Dirac distribution, and it will be inconvenient for us to do sampling from only a density function. Therefore, we introduce another way, adopting the pushforward measure to represent a distribution.

Given a distribution µ 0 and a mapping g(•), data x drawn from µ 0 can be transported into a new distribution µ 1 (constituted by g(x)). Technically speaking, µ 1 is called the pushforward measure of µ 0 by mapping g, denoted by µ 1 = g # (µ 0 ).

Here, for ∀j ∈ [N ], we prepare each distribution π j a corresponding pushforward function g j : R d → R nj , and we have:

π j = g # j (U )

where U stands for the uniform distribution on [0, 1] d . Each time we want to sample from distribution π i , we only need to sample several ω i ∈ [0, 1] d from distribution U and calculate g i (ω i ). Then, these g i (ω i ) form a sample set from distribution π i . And optimization problem (3) becomes:

Find

EQUATION

To solve the optimization problem above, we consider the following Gradient-based Nikaido-Isoda function of Mixed strategy on Continuous games (Mixed-GNI), generalized from the GNI function introduced above, and we call this function V the local regret:

EQUATION

Here, δ gi F i stands for the 1-st order variation of functional F i on element function g i and

F i (g 1 , g 2 , • • • , g N ) = E ωj ∼U, ∀j [f i (g 1 (ω 1 ), g 2 (ω 2 ), • • • , g N (ω N ))]

By minimizing the functional V (g 1 , g 2 , • • • , g N ; λ), we can approximately get stationary Nash points (SNP), and even get Nash equilibrium if all the utility functions f i are convex. We will prove them in the next section.

In practice, we further parametrize these pushforward functions as: g i (•) = g i (•, θ i ), to efficiently calculate derivatives instead of variations. For simplicity, we denote g i as g θi . In order to obtain a better expressibility, we use neural networks as the architecture to parametrize these pushforward functions. Then, Mixed-GNI function V can be transformed to:

V (g θ1 , g θ2 , • • • , g θ N ; λ) = N i=1 F i (g θ1 , g θ2 , • • • , g θ N ) -F i (g θ1 , • • • , g θi-1 , g θi-λ∂ θ i Fi , • • • , g θ N )

Finally, the Mixed-GNI function can be estimated by sampling the points from distribution U as an estimator of these F i and minimized by implying gradient descent on these function parameters

θ i , i ∈ [N ],

the convergence of which is proved in the next section.

4 THEORETICAL ANALYSIS OF MIXED-GNI

4.1. THE SUFFICIENT AND NECESSARY CONDITION OF STATIONARY NASH POINT:

As a mixed strategy of an N -player continuous game,

(π 1 , π 2 , • • • , π N ) = (g # 1 U, g # 2 U, • • • , g # N U

) is a stationary Nash point (SNP) if and only if for ∀i ∈ [N ], the 1-st order variation δ gi (F i )[σ(x)] = 0 (6) holds at each direction σ(x). Here:

F i (g 1 , g 2 , • • • , g N ) = E ωj ∼U, ∀j [f i (g 1 (ω 1 ), g 2 (ω 2 ), • • • , g N (ω N ))]

is 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.

EQUATION

where:

G(ω i ) = E ωj ∼U, ∀j =i [∇ i f i (g 1 (ω 1 ), g 2 (ω 2 ), • • • , g N (ω N ))]

For SNP, Equation (6) holds at each direction σ(x), i.e. G(ω i ) ≡ 0. Therefore, we have

Theorem 1. π = (π 1 , π 2 , • • • , π N ) = (g # 1 U, g # 2 U, • • • , g # N U

) is a stationary Nash point (SNP) for an N -player continuous game if and only if:

E ωj ∼U, ∀j =i [∇ i f i (g 1 (ω 1 ), g 2 (ω 2 ), • • • , g N (ω N ))] ≡ 0, ∀ω i ∈ R d holds for all i ∈ [N ].

From Equation (7), we also know that:

δ gi (F i )[σ(ω i )] = G(ω i ), σ(ω i )

In other words, the steepest direction is:

δ gi (F i ) = G(ω i ) = E ωj ∼U, ∀j =i [∇ i f i (g 1 (ω 1 ), g 2 (ω 2 ), • • • , g N (ω N ))]

Then we show the relationship between stationary Nash point and Nash equilibrium.

Theorem 2. Denote S SN P , S N E as the set of SNPs and NEs of a particular N -player continuous game. Obviously, S N E ⊆ S SN P . If all utility functions f i are convex, we have:

S N E = S SN P Proof. Suppose π = (π 1 , π 2 , • • • , π N ) = (g # 1 U, g # 2 U, • • • , g # N U

) is an SNP, we will prove it an NE when all functions f i are convex. According to the convexity and the condition of SNPs, we know that for ∀i ∈ [N ] and any other pushforward function gi :

F i (g 1 , g 2 , • • • , g N ) -F i (g 1 , • • • , gi , • • • , g N ) = E ωj ∼U, ∀j [f i (g 1 (ω 1 ), • • • , gi (ω i ), • • • , g N (ω N )) -f i (g 1 (ω 1 ), g 2 (ω 2 ), • • • , g N (ω N ))] E ωj ∼U, ∀j (g i (ω i ) -g i (ω i )) T • ∇ i f i (g 1 (ω 1 ), g 2 (ω 2 ), • • • , g N (ω N )) = E ωi∼U [(g i (ω i ) -g i (ω i )) T • E ωj ∼U, ∀j =i [∇ i f i (g 1 (ω 1 ), g 2 (ω 2 ), • • • , g N (ω N ))]] = E ωi∼U [(g i (ω i ) -g i (ω i )) T • δ gi (F i )] = 0 (8) which leads to our conclusion, that π = (g # 1 U, g # 2 U, • • • , g # N U

) is a global Nash equilibrium.

Next, we show the relationship between the zeros of Mixed-GNI function

V (g 1 , g 2 , • • • , g N ) and

SNPs of the N -player continuous game. Lemma 1. Assume f : R d → R is a twice differentiable function, and its 1-st order gradient ∇f is L f -Lipschitz continuous. Then for ∀x, y ∈ R d , we have:

|f (y) -f (x) -∇f (x), y -x | 1 2 L f y -x 2 2

Proof. According to the condition of f , there holds the following equations.

|f (y) -f (x) -∇f (x), y -x | = 1 0 ∇f (x + τ (y -x)) -∇f (x), y -x dτ 1 0 | ∇f (x + τ (y -x)) -∇f (x), y -x | dτ 1 0 ∇f (x + τ (y -x)) -∇f (x) • y -x dτ 1 0 L f τ y -x 2 2 dτ = 1 2 L f y -x 2 2 (9)

With this lemma, we can show that each global minimum of V (g 1 , g 2 , • • • , g N ) is also an SNP. Theorem 3. If each utility function f i is twice differentiable and its 1-st order gradient ∇f i is L f -Lipschitz continuous. Then:

λ 2 δ gi F i (g 1 , g 2 , • • • , g N ) 2 V i (g 1 , g 2 , • • • , g N ; λ) 3λ 2 δ gi F i (g 1 , g 2 , • • • , g N ) 2

holds when 0 < λ 1 L f . Here, • 2 is a functional norm which means:

f 2 = [0,1] d f (ω i ) 2 2 dω i = E ωi∼U f (ω i ) 2 2 Proof. V i (g 1 , g 2 , • • • , g N ; λ) =F i (g 1 , g 2 , • • • , g N ) -F i (g 1 , • • • , g i -λδ gi F i , • • • , g N ) = E ωj ∼U, ∀j [f i (g 1 (ω 1 ), g 2 (ω 2 ), • • • , g N (ω N )) -f i (g 1 (ω 1 ), • • • , g i (ω i ) -λδ gi F i (ω i ), • • • , g N (ω N ))]

(10) Then, according to Lemma 1:

V i (g 1 , g 2 , • • • , g N ; λ) E ωj ∼U, ∀j λ(δ gi F i (ω i )) T ∇ i f i (g 1 (ω 1 ), g 2 (ω 2 ), • • • , g N (ω N )) + L f 2 λ 2 δ gi F i (ω i ) 2 =λ E ωi∼U δ gi F i (g 1 , g 2 , • • • , g N )(ω i ) 2 2 + L f 2 λ 2 E ωi∼U δ gi F i (g 1 , g 2 , • • • , g N )(ω i ) 2 2 3λ 2 δ gi F i (g 1 , g 2 , • • • , g N ) 2 (11)

And the other side of this inequality is similar.

The theorem above tells us that, V (g 1 , g 2 , • • • , g N ; λ) is always non-negative as long as λ 1 L f . And its global minima, or in the other words, its zeros, are surely SNPs, because for ∀i ∈ [N ]:

V i (g 1 , g 2 , • • • , g N ; λ) = 0 ⇔ δ gi F i (g 1 , g 2 , • • • , g N ) = 0

Finally, we analyze the stability of SNPs. In the following theorem, we show that the 2-nd order variation of functional V is a positive semidefinite operator, which confirms the stability of SNPs.

Theorem 4. The 2-nd order variation δ 2 V (g * ; λ) is a positive semidefinite operator for ∀g * ∈ S SN P and 0 λ

1 L f .

Proof. The 1-st and 2-nd order variation of V i (g; λ) satisfy:

EQUATION

) where g = (g 1 , g 2 , • • • , g N ), g = (g 1 , • • • , g i-1 , g i -λδ gi F i , • • • , g N ) and D i = Diag(0 n1×n1 , • • • , 0 ni-1×ni-1 , I ni×ni , 0 ni+1×ni+1 , • • • , 0 n N ×n N ) is a n × n matrix. Given g * ∈ S SN P , then δF i (g * ) = 0. δ 2 V i (g * ; λ) = λ δ 2 F i (g * )[2D i -λD i δ 2 F i (g * )D i ]δ 2 F i (g * ) λ δ 2 F i (g * )[2D i -λL f D 2 i ]δ 2 F i (g * ) λ δ 2 F i (g * )D i δ 2 F i (g * ) = λ (δ 2 F i (g * )D i ) T (δ 2 F i (g * )D i ) (13)

which is positive semidefinite. Therefore:

δ 2 V (g * ; λ) = N i=1 δ 2 V i (g * ; λ)

is also positive semidefinite.

4.2. CONVERGENCE ANALYSIS:

In this section, we analyze the convergence analysis of gradient descent: k) ; λ) According to the definition of functional V (g; λ), it can be rewritten as the following form:

g (k+1) = g (k) -ρ • δV (g (

V (g; λ) = E ωj ∼U, ∀j∈[N ] [G V (g 1 (ω 1 ), g 2 (ω 2 ), • • • , g N (ω N ))]

where

G V = N i=1 f i (y 1 , y 2 , • • • , y N ) -f i (y 1 , • • • , y i-1 , y i -λ∇ i f i (y 1 , y 2 , • • • , y N ), • • • , y N ). Theorem 5. Suppose ∇G V (x) is L G -Lipschitz continuous.Through gradient descent, the function sequence g (k) converges sublinearly to a stationary Nash point (SNP) g * if ρ < 1 L G , λ 1 L f .

Proof. According to Lemma 1, we have:

V (g (k+1) ; λ) V (g (k) ; λ) - E ωj ∼U, ∀j∈[N ] ρ ∇G V ((g 1 (ω 1 ), g 2 (ω 2 ), • • • , g N (ω N )) • δV (g (k) ; λ) + E ωj ∼U, ∀j∈[N ] L G 2 ρ 2 δV (g (k) ; λ) 2 = V (g (k) ; λ) -(ρ - L G 2 ρ 2 ) δV (g (k) ; λ) 2 = V (g (k) ; λ) - 2ρL G -(ρL G ) 2 2L G δV (g (k) ; λ) 2 (14) Let k = 0, 1, • • • , K,

and add them up, we have: K+1) ; λ) 0 by Theorem 3, we have

V (g (K+1) ; λ) V (g (0) ; λ) - 2ρL G -(ρL G ) 2 2L G K k=0 δV (g (k) ; λ) 2 Since λ 1 L f , we know that V (g (

K k=0 δV (g (k) ; λ) 2 2L G 2ρL G -(ρL G ) 2 V (g (0) ; λ) ⇒ min k∈[K] δV (g (k) ; λ) 2 2L G 2ρL G -(ρL G ) 2 V (g (0) ; λ) K + 1 (15)

which completes our proof.

5. EXPERIMENTS:

To evaluate the practical performance of our approach, we apply it to three types of games, twoplayer 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 ρ = 1e-2 and momentum κ = 0.9. The network architecture we use for the pushforward functions g θ 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 is the dimension of each player's action space. From forward to 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 (Raghunathan et al., 2019) (gradGNI in short), Symplectic Gradient Adjustment algorithm (Balduzzi et al., 2018) (SGA in short), and Stable Opponent Shaping (Letcher et al., 2018) (SOS in short) as they outperformed other existing algorithms applicable to continuous game settings. For all these methods, we either follow the standard hyper-parameters mentioned in the original papers, or the ones resulting in the best convergence.

5.1. TWO-PLAYER QUADRATIC GAME:

The two-player quadratic game is defined by the the players' payoff functions f i (i = 1, 2):

EQUATION

) where Q i ∈ R (n1+n2)×(n1+n2) , r i ∈ R n1+n2 , x = (x 1 , x 2 ) and x i ∈ R ni . In our experiments, we choose n 1 = n 2 ∈ {3, 5, 10}. For each pair of n i , we randomly generate 100 instances for the matrix Q i and r i for i = 1, 2. Each item in each matrix Q i and each vector r i follows the uniform distribution on [0, 1] independently.

We show the converging process of all algorithms for one game instance (n 1 = n 2 = 3) in Fig. 1 (a) as an example. As we can see, our approach effectively converges to a stationary Nash equilibrium point. While gradGNI also converge in this instance, its result has larger local regret. In other words, it obtain worse approximation to Nash equilibrium, which coincides with the essential difference 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. 1. 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.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 a blotto game, player 1 and 2 (sometimes known as two colonels) have a budget of resource X 1 , X 2 respectively. W.l.o.g we set X 1 ≤ X 2 . There are m battlefields in total. In each battlefield j, when two players allocate x 1j , x 2j resource on it, the payoff of player i is:

EQUATION

where -i denotes the player other than player i. Each player's payoff across all m battlefields is the sum of the payoffs across the individual battlefields. For each player i, a feasible pure strategy

x i = (x i1 , . . . , x im ) ∈ R m + must also satisfies m j=1 x ij ≤ X i .

Here we adopt the generalized 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 ∈ {3, 5, 10}. For each m, we randomly generate 100 instance for the budget X i , following the uniform distribution on [0, 1] independently.

We show the converging process of all algorithms for one game instance (m = 3) in Fig. 1 (b) as an 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.

1. 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, we apply our method on the game instance generated by the comprehensive GAMUT suite of game generators designated for testing game-theoretic algorithms (Nudelman et al., 2004) . GAMUT includes a 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 to a multi-player version, where r i = 0, and 100 game instances with 4 players are generated.

For each instance, one of the distributions from the GAMUT set is selected, and each item in each matrix Q i is sampled according to it independently.

We show the converging process of all algorithms for one game instance in Fig. 1(c ). Both Mixed-GNI and SGA converge, but SGA has a much worse final result than our Mixed-GNI. 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 in Table 1 .

From these different games, we know that our Mixed-GNI 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 continuous 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.

A EXPERIMENTS ON DELTA-DIRAC GANS As a two-player game, the payoff functions for the two players are listed as follows: f 1 (x 1 , x 2 ) = log(1 + θx 1 ) + log(1 + exp(x 1 x 2 )) f 2 (x 1 , x 2 ) = -log(1 + exp(x 1 x 2 )) (18

)

where the θ is the location of the Dirac spike. In Figure 2 , we show the converging process of all algorithms for one game instance (i.e. for a single θ). 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 θs) 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. 

:



Figures and Tables:

Figure 1: Local Regret of Various Games. Mixed-GNI (ours) gradGNI SGA SOS Quadratic (ni = 3) (1.63 ± 1.20)e-3 (1.01 ± 0.03)e-1 2.59 ± 0.17 1.86 ± 0.36 Quadratic (ni = 5) (2.84 ± 1.95)e-3 (2.95 ± 0.19)e-1 3.92 ± 0.22 2.89 ± 0.37 Quadratic (ni = 10) (3.76 ± 3.02)e-3 (1.47 ± 0.08)e-1 2.54 ± 0.09 2.46 ± 0.12 Blotto (m = 3) (6.32 ± 4.97)e-6 (2.62 ± 0.38)e-5 (5.26 ± 0.91)e-5 (7.31 ± 0.82)e-5 Blotto (m = 5) (4.52 ± 3.09)e-6 (1.10 ± 0.06)e-5 (1.21 ± 0.18)e-5 (7.39 ± 2.33)e-6 Blotto (m = 10) (3.62 ± 2.39)e-6 (7.60 ± 0.49)e-6 (5.94 ± 0.26)e-6 (5.02 ± 0.28)e-6 GAMUT (ni = 3) (4.95 ± 0.42)e-3 (4.80 ± 0.81)e-1 (0.94 ± 0.13)e-1 (0.96 ± 0.17)e-1 GAMUT (ni = 5) (8.90 ± 0.79)e-3 (1.52 ± 0.27)e-1 (2.59 ± 0.60)e-1 (2.67 ± 0.81)e-1 GAMUT (ni = 10) (1.54 ± 0.86)e-2 (1.84 ± 0.48)e-1 (1.76 ± 0.32)e-1 (1.90 ± 0.47)e-1

Gidel et al. (2018) introduce a one-dimensional GAN where the real data follows a Dirac-Delta distribution. This experiment is also conducted in our baseline paper by Raghunathan et al. (2019).

Figure 2: Local Regret of Dirac-Delta GAN Game.

Comparison results.

Table content: <table/>

Comparison Results

Table content: <table/>

Peer review (iclr2020):
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. My 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. The optimization rule for GNI is different than standard update rules: specifically, there are two step sizes lambda and ho, 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. The 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). Nits: - MC-GNI is a confusing name because MC usually refers to *Monte Carlo* in this context - 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. - I don*t see lambda mentioned on the RHS of the last equation in sec. 3.