Dawen Wu
email: dawen.wu@centralesupelec.fr

Abdel Lisser
email: abdel.lisser@l2s.centralesupelec.fr

CCGnet: A deep learning approach to predict Nash equilibrium of chance-constrained games

Keywords: Chance-constrained game, Nash equilibrium, Neural network, Neurodynamic optimization

This paper proposes a novel method for efficiently finding the Nash equilibrium in a chance-constrained games (CCG). Conventional numerical integration methods require significant computational time to solve multiple instances of CCG. We introduce CCGnet, a deep learning approach which can solve efficiently multiple instances of CCG in a one-shot manner. CCGnet uses a specialized network structure and training algorithm based on neurodynamic optimization. We present the strong performance of CCGnet in practice and show that our proposed method outperforms conventional methods.

Introduction

Game theory analyzes the strategic interactions between rational individuals in situations involving conflict or cooperation [START_REF]Algorithmic Game Theory[END_REF]. A Nash equilibrium is a state in which no player can improve his payoff by changing his strategy unilaterally. von Neumann [START_REF] Neumann | Zur theorie der gesellschaftsspiele[END_REF] demonstrated the existence of a saddle point for two-person zerosum games through the minimax theorem. Nash [START_REF] Nash | Equilibrium points in n-person games[END_REF] showed that an equilibrium also exists in multi-player non-zero-sum games commonly called Nash equilibrium.

The games mentioned above are all deterministic. However, many real-world situations involve games where the player's payoff function or strategy set contains randomness. Such a game with randomness is called a stochastic Nash game. Ravat & Shanbhag [START_REF] Ravat | On the characterization of solution sets of smooth and nonsmooth convex stochastic nash games[END_REF] characterized the solution set for various types of stochastic Nash games. If players are assumed to be risk-neutral, the expected payoff criterion can be used to handle the randomness in the game [START_REF] Ravat | On the characterization of solution sets of smooth and nonsmooth convex stochastic nash games[END_REF][START_REF] Jiang | Distributed computation of equilibria in misspecified convex stochastic nash games[END_REF].

When considering a risk-averse case, the randomness in a game can be addressed through the chance constraint programming approach, known as a chance constraint game [START_REF] Singh | A characterization of nash equilibrium for the games with random payoffs[END_REF][START_REF] Singh | A second-order cone programming formulation for two player zero-sum games with chance constraints[END_REF][START_REF] Nguyen | Random games under elliptically distributed dependent joint chance constraints[END_REF]. In a chance constraint game (CCG), players are guaranteed to receive payoffs with a certain confidence level. For example, Singh & Lisser [START_REF] Singh | A second-order cone programming formulation for two player zero-sum games with chance constraints[END_REF] studied a two-person zero-sum game with a random strategy set and characterized the saddle point as a primal-dual pair of second-order cone programs when the random variable follows an elliptical distribution.

Neurodynamic optimization uses ordinary differential equation (ODE) systems to solve optimization problems. Hopfield & Tank [START_REF] Hopfield | neural" computation of decisions in optimization problems[END_REF] proposed Hopfield networks for solving linear programming problems. Kennedy & Chua [START_REF] Kennedy | Neural networks for nonlinear programming[END_REF] developed an approach based on the penalty function method for solving nonlinear programming problems. However, this approach involves a penalty parameter and the optimal solution can only be obtained when the penalty term tends to infinity.. Since then, neurodynamic optimization has been well established for solving various optimization problems, such as convex optimization problems [START_REF] Xia | A new neural network for solving nonlinear projection equations[END_REF][START_REF] Nazemi | A new neural network framework for solving convex second-order cone constrained variational inequality problems with an application in multi-finger robot hands[END_REF], pseudoconvex problems [START_REF] Liu | A projection neural network to nonsmooth constrained pseudoconvex optimization[END_REF][START_REF] Liu | A one-layer recurrent neural network for nonsmooth pseudoconvex optimization with quasiconvex inequality and affine equality constraints[END_REF], distributed optimization problems [START_REF] Lv | Differentially private distributed optimization for multi-agent systems via the augmented lagrangian algorithm[END_REF][START_REF] Zou | A dual-population algorithm based on alternative evolution and degeneration for solving constrained multi-objective optimization problems[END_REF][START_REF] Wang | Distributed cooperative optimization for multiple heterogeneous euler-lagrangian systems under global equality and inequality constraints[END_REF][START_REF] Xu | Resilient penalty function method for distributed constrained optimization under byzantine attack[END_REF], and Nash equilibrium computation [START_REF] Shi | Distributed nash equilibrium computation in aggregative games: An eventtriggered algorithm[END_REF][START_REF] Wu | A dynamical neural network approach for solving stochastic two-player zero-sum games[END_REF].

Deep learning is a type of machine learning that involves the use of deep neural networks, which consist of multiple layers of interconnected nodes, to identify complex patterns and relationships in data. It has been applied successfully to various fields, including computer vision [START_REF] Raza | Deep learning for computer vision: A comprehensive review[END_REF], natural language processing [START_REF] Tan | Deep learning for natural language processing: A review[END_REF], bioinformatics [START_REF] Hu | Deep learning in bioinformatics: A comprehensive survey[END_REF], game theory [START_REF] Wu | Using cnn for solving two-player zero-sum games[END_REF][START_REF] Wu | Mg-cnn: A deep cnn to predict saddle points of matrix games[END_REF], and operation research [START_REF] Wu | A deep learning approach for solving linear programming problems[END_REF][START_REF] Nair | Solving mixed integer programs using neural networks[END_REF][START_REF] Bengio | Machine learning for combinatorial optimization: a methodological tour d'horizon[END_REF]. However, deep learning also has limitations, and researchers are working to improve its performance and address challenges such as bias and interpretability.

Approximation methods using deep learning for differential equations were first studied in the 1990s.

Dissanayake & Phan-Thien [START_REF] Dissanayake | Neural-network-based approximations for solving partial differential equations[END_REF] used a neural network as an approximate solution to a differential equation, where the neural network was trained to satisfy the given differential equation and boundary conditions. Lagaris et al. [START_REF] Lagaris | Artificial neural networks for solving ordinary and partial differential equations[END_REF] proposed a neural network model that can satisfy boundary conditions by construction.

They discussed the use of this method on ODE and PDE problems, respectively. This method was extended to irregular boundaries [START_REF] Mcfall | Artificial neural network method for solution of boundary value problems with exact satisfaction of arbitrary boundary conditions[END_REF]. In recent years, with the rapid development of deep learning, these methods have been further extended for solving high-dimensional PDEs [START_REF] Yu | The deep ritz method: a deep learning-based numerical algorithm for solving variational problems[END_REF][START_REF] Han | Solving high-dimensional partial differential equations using deep learning[END_REF]. Flamant et al. took the parameters of the ODE system as the input variables of the neural network, allowing the neural network to be used as the solution for a group of ODE systems [START_REF] Flamant | Solving differential equations using neural network solution bundles[END_REF]. The rapid development of this research direction has been made possible by automatic differentiation tools, which facilitate the computation of derivatives [START_REF] Baydin | Automatic differentiation in machine learning: a survey[END_REF][START_REF] Paszke | Pytorch: An imperative style, high-performance deep learning library[END_REF].

Contributions and paper outline

The main contributions of this paper can be summarized as follows:

• Our proposed CCGnet is able to receive instances of different parameters and solve them directly without any iterative process. In terms of computational time, CCGnet outperforms traditional solution approaches. This advantage becomes even more significant when solving multiple instances. For example, for 10,000 instances, the CCGnet model solves within 1.53 ms CPU time, while traditional numerical solvers take at least 22,500 ms CPU time.

• CCGnet transforms a CCG problem into a neural network training problem. Since our CCGnet model is based entirely on deep learning infrastructure, we can solve CCG without using any standard numerical solvers.

The remaining sections of this paper are organized as follows: Section 2 presents the background knowledge needed for understanding the paper, including the introduction of CCG and the neurodynamic optimization approach. Section 3 presents our proposed CCGnet approach. Section 4 gives numerical results of using CCGnet for solving CCG. Section 5 summarizes the paper and gives future directions. Variable of a NPE Φ(z) : R 2n → R 2n

An ODE system, dz dt = Φ(z) z(t) : R → R 2n

A state solution ẑ(t, θ; w)

A CCGnet model with model weight w

(t 0 , z 0 ) ∈ R 2n+1 An initial point [t 0 , T ] ⊂ R A time range θ ∈ Θ CCG parameter

Preliminaries

Section 2.1.1 introduces the CCG problem, including the definition of a CCG and the existence theorem of Nash equilibria. Section 2.1.2 introduces a specific type of CCG, namely stochastic cournot games among electrical firms, and shows how to reformulate this CCG as an nonlinear projection equation (NPE). Section 2.2 introduces the neurodynamic optimization approach for solving the NPE.

Chance-constrained game

The model

Let an n-player game with continuous action and random payoffs be defined as a tuple I, X i i∈I , r i i∈I , where

• I = {1, 2, . . . , n} is a set of players.
• For each i ∈ I, let A i be a finite action set of player i together with its generic element a i . A vector a = (a 1 , a 2 , • • • , a n ) denotes an action profile of the game. Let A=× n i=1 A i be the set of all action profiles of the game. Denote, A -i =× n j=1;j̸ =i A j , and a -i ∈ A -i is a vector of actions a j , j ̸ = i. x i ∈ R Ai is a strategy of player i. x ∈ R A is a strategy profile. x -i ∈ R A-i is a strategy profile without x i . X i , X -i and X are feasible set for x i , x -i and x, respectively.

• Let (Ω, F, P ) be a probability space. ξ i : Ω → R li is a random vector, and f i : X → R li is a function determining player i's payoff. Consider a strategy profile x ∈ X and an event ω ∈ Ω, the payoff of player i is

r i (x, ω) = f i (x) • ξ i (ω). ( 1
)
The CCG defines the payoff function of player i as

u αi i (x) = sup γ | P ω | r i (x, ω) ≥ γ ≥ α i , (2)
where α i ∈ [0, 1] is a confidence level of player i, and α = (α i ) i∈I ∈ [0, 1] n . A strategy profile x * is a Nash equilibrium, if the following holds

u αi i x i * , x -i * ≥ u αi i x i , x -i * , ∀x i ∈ X i . (3)
We consider the case where each random vector ξ i , ∀i ∈ I follows an elliptically symmetric distribution, i.e., Ellip (µ i , Σ i , φ i ). µ i is a location parameter. Σ i is a positive definite matrix and φ i is a characteristic generator function. Then, the payoff function of player i is

u αi i (x) = µ T i f i (x) + Σ 1/2 i f i (x) ϕ -1 Zi (1 -α i ) , (4)
where ϕ -1 Zi (•) is the quantile function of the distribution Ellip (µ i , Σ i , φ i ).

Assumption 1. The following conditions hold for each player i.

• X i ⊂ R ji is a non-empty, convex and compact set.

• f i k : R j → R is a continuous function, for all k = 1, 2, . . . , l i .

• For a given x -i ∈ X -i , f i k •, x -i is an affine function, for all k = 1, 2, . . . , l i . Or, for a given x -i ∈ X -i , f i k •, x -i is an non-positive and concave function, for all k = 1, 2, . . . , l i , and all elements of µ i and Σ i are non-negative.

Theorem 1 (Singh & Lisser [37], Theorem 1). Consider a chance constrained game I, X i i∈I , r i i∈I . For each player i ∈ I, the random vector ξ i follows an elliptical distribution Ellip (µ i , Σ i , φ i ). Let Assumption 1 holds. There exists a Nash equilibrium for this chance constrained game with any α ∈ (0.5, 1] n .

Stochastic cournot competition

We now consider an example of CCG, namely stochastic cournot competitions among electricity firms.

We show how this CCG can be reformulated as an nonlinear projection equation.

Consider an electricity market with n competing firms. x i ∈ X i ⊂ R + denote an amount of electricity generated by firm i. Each firm i has a finite capacity C i , i.e., X i = 0, C i . x = x 1 , x 2 , . . . , x n ∈ R n denote a strategy profile. Let (Ω, F, P ) be a probability space. The unit market price is determined by x and an event ω,

P (x, ω) = a -b • n i=1 x i + ζ(ω), (5)
where ζ : Ω → R is a random variable, and a ∈ R and b ∈ R + are two market price factors.

The payoff function of firm i is

r i (x, ω) = x i • P (x, ω) -c i x i , (6)
where c i x i is the cost of firm i to produce x i amount of electricity, and c i (•) is assumed to be differentiable and convex.

85

The chance-constraint payoff function for player i with confidence level α i is defined as

u αi i (x) = sup    γ | P      ω | x i   a -b • n j=1 x j   + x i • ζ(ω) -c i x i ≥ γ      ≥ α i    . (7)
If x i > 0, ∀i ∈ I, we have

u αi i (x) = sup    γ | P      ω | ζ(ω) ≤ γ -x i a -b • n j=1 x j + c i x i x i      ≤ 1 -α i    = sup    γ | γ ≤ x i   a -b • n j=1 x j   -c i x i + x i ϕ -1 ζ (1 -α i )    = x i   a -b • n j=1 x j   -c i x i + x i ϕ -1 ζ (1 -α i ) . (8)
If x i = 0, ∀i ∈ I, we have

u αi i (x) = -c i x i . (9)
Therefore, for a given x and α i , the payoff of firm i is

u αi i (x) = x i   a -b • n j=1 x j   -c i x i + x i ϕ -1 ζ (1 -α i ) . ( 10
) Definition 1. The nonlinear complementarity problem N CP (F ) is to find a vector y * ∈ R m such that 0 ≤ y * ⊥ F (y * ) ≥ 0, ( 11
)
where F : R m → R m .

Theorem 2 ([37]

). Denote a decision vector y = x 1 , . . . , x n , λ 1 , . . . , λ n ∈ R 2n , and let F (y) = (F 1 (y), . . . , F 2n (y)),

where

F i (y) =    -a -b n j=1;j̸ =i x j + 2bx i + dci(x i ) dx i -ϕ -1 ζ (1 -α i ) + λ i , if i = 1, . . . , n C i-n -x i-n , if i = n + 1, . . . , 2n. (12)
The strategy profile x * of y * = (x * , λ * ) is a Nash equilibrium of the CCG if and only if y * is a solution of the N CP (F ).

Proposition 1 ( [START_REF] Harker | Finite-dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications[END_REF][START_REF] Eaves | On the basic theorem of complementarity[END_REF]). The nonlinear projection equation N P E(F ) is to find a vector y * ∈ R m such that

(y * -F (y * )) + = y * , (13)
where F : R m → R m is a continuous function, (y) + = max(0, y). y * is the solution of N CP (F ) if and only if y * is the solution of N P E(F ).

By Theorem 1, a Nash equilibrium exists for this CCG with any α ∈ (0.5, 1] n . By Theorem 2 and Proposition 1, the Nash equilibrium of this CCG can be obtained by solving the N P E(F ). Note that NPEs are equivalent to variational inequalities and generalized complementarity problems, the proof is given by Browder fixed-point theorem [START_REF] Harker | Finite-dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications[END_REF][START_REF] Eaves | On the basic theorem of complementarity[END_REF]. Here, Proposition 1 considers a simpler case, i.e., the equivalence between NPE and NCP.

Neurodynamic optimization

Xia & Feng [START_REF] Xia | A new neural network for solving nonlinear projection equations[END_REF] proposes the following ODE system to solve the N P E(F )

dz dt = -F (z) + + (z) + -z. (14)
The ODE system ( 14) can be simplified as dz dt = Φ(z). Let z * be an equilibrium point of the ODE system, i.e., Φ(z * ) = 0. Then, we have

z * = -F (z * ) + + (z * ) + (15)
Applying the projection operator (•) + on both side, we have

(z * ) + = -F (z * ) + + (z * ) + + , (16)
and hence the point (z * ) + is a solution of N P E(F ).

Definition 2. Consider an ODE system dz dt = Φ(z), Φ(z) : R m → R m , and a given initial point (t 0 , z 0 ) ∈ R m+1 . A vector value function z(t) : R → R m is called a state solution, if it satisfies the initial condition z(t 0 ) = z 0 and the ODE system dz dt = Φ(z).

Definition 3. An ODE system dz dt = Φ(z) converges globally to a solution set Z * if for any given initial point, the state solution z(t) satisfies

lim t→∞ dist (z(t), Z * ) = 0, ( 17
)
where dist (z(t),

Z * ) = inf z * ∈Z * ∥z(t) -z * ∥,
α i i (x)
is given by [START_REF] Kennedy | Neural networks for nonlinear programming[END_REF]. In the middle box of NPE, y * represents the solution of the NPE, and the function F (y) is given by [START_REF] Nazemi | A new neural network framework for solving convex second-order cone constrained variational inequality problems with an application in multi-finger robot hands[END_REF]. In the right box of IVP, z(t), t ∈ [t 0 , T ] represents the state solution, and the ODE system Φ(z) is given by [START_REF] Liu | A one-layer recurrent neural network for nonsmooth pseudoconvex optimization with quasiconvex inequality and affine equality constraints[END_REF].

Theorem 3 (Xia & Feng [11], Theorem 1). If ∇G(z) is symmetrical and positive semi-definite, then the ODE system (14) converges globally to the solution set of N P E(K, G). In particular, if N P E(K, G) has only one solution z * , then z * is globally asymptotically stable.

CCGnet

In Section 3.1, we summarize the reformulation of a CCG to an initial value problem (IVP) and present a method for parametrizing CCG instances using θ. Section 3.2 introduces the CCGnet model and its associated loss function. Section 3.3 presents the training algorithm and discusses newly introduced hyperparameters.

Problem setup

In this work, we consider the stochastic cournot game as introduced in Section 2.1.2. The CCG problem can be reformulated as an NPE where the solution y * = (x * , λ * ) includes the Nash equilibrium x * of the CCG. The neurodynamic approach, introduced in Section 2.2, models this NPE as an IVP, resulting in a state solution z(t) for t ∈ [t 0 , T ]. According to the global convergence theorem, as T approaches infinity, z(T ) converges to y * . Figure 1 summarizes this reformulation from a CCG to an IVP.

Next, we consider the case of multiple instances. We parameterize a CCG instance by θ ∈ Θ, where a different θ leads to a different CCG instance. The set Θ is typically an uncountably infinite set that represents a range of possible values for θ. For example, in the stochastic cournot game, θ can be the market price factor a or b, and Θ can be [START_REF]Algorithmic Game Theory[END_REF][START_REF] Jiang | Distributed computation of equilibria in misspecified convex stochastic nash games[END_REF]. We denote the CCG instance for θ as CCG θ , the corresponding NPE as N P E θ , and the IVP as IV P θ .

CCGnet framework

The CCGnet model is defined by the following equation:

ẑ (t, θ; w) = z 0 + (1 -e -(t-t0) )N (t, θ; w) , ( 18
)
where t is an input time that falls within the time range [t 0 , T ] ⊂ R. (t 0 , z 0 ) is an initial point. N (t, θ; w) is a fully-connected neural network with weight w. We put θ ∈ Θ as an input to the neural network, allowing the CCGnet model to solve multiple CCG instances. The terms z 0 and 1 -e -(t-t0) in [START_REF] Xu | Resilient penalty function method for distributed constrained optimization under byzantine attack[END_REF] ensure that the CCGnet model satisfies the initial condition (t 0 , z 0 ) by construction, i.e., ẑ (t 0 , θ; w) = z 0 . This construction method for handling initial conditions was introduced by Lagaris et al [START_REF] Lagaris | Artificial neural networks for solving ordinary and partial differential equations[END_REF]. We use an exponential multiplier of 1 -e -(t-t0) , which has been shown to achieve better convergence than the Lagaris method [START_REF] Mattheakis | Hamiltonian neural networks for solving equations of motion[END_REF].

The CCGnet model solves CCG θ , N P E θ and IV P θ , for any θ ∈ Θ, as shown in Figure 2-(A). For a given instance of parameter θ, the CCGnet model's predicted state solution for the IV P θ is ẑ (t, θ; w), where t ∈ [t 0 , T ]. This is obtained by using t as a variable and keeping θ constant. The predicted solution for the N P E θ is ẑ (T, θ; w) = [x 1 , . . . , xn , λ1 , . . . , λn ], which is obtained by using a constant value of T and a constant value of θ. The predicted Nash equilibrium for the

CCG θ is [x 1 , . . . , xn ]. Figure 2-(B) illustrates
how the CCGnet model gives predictions for these three problems.

The loss function is defined by the following equation:

L(t, θ; w) = e (-τ (t-t0)) ℓ ∂ ẑ(t, θ; w) ∂t , Φ θ (ẑ(t, θ; w)) . ( 19
)
Φ θ is the ODE system corresponding to CCG θ . ∂ ẑ(t,θ;w) ∂t is the partial derivative of the CCGnet model with respect to time t. ℓ(•, •) is an error metric, e.g., mean square error. The term ℓ ∂ ẑ(t,θ;w) ∂t , Φ θ (ẑ(t, θ; w))

represents how well the CGGnet model solves the ODE system Φ θ at time t. The weighting function e (-τ (t-t0))

is an exponentially decaying function with respect to time t, with τ ∈ R as a hyperparameter. We include this weighting function to avoid initial errors which might increase the global errors exponentially [START_REF] Flamant | Solving differential equations using neural network solution bundles[END_REF]. For a given instance of parameter θ ∈ Θ and a time t ∈ [t 0 , T ], the computational flow of the loss value L(t, θ; w) is shown in Figure 2-(C). The batch loss is defined as follows:

L(T, θ; w) = 1 |T| t∈T L(t, θ; w), (20)
where T ⊂ [t 0 , T ] is the batch of t, and |T| represents the batch size.

Loss

(C) The objective function of the CCGnet model is given by the following equation:

E(w) = θ∈Θ t∈[t0,T ] L(t, θ; w), dt, dθ. (21)
The goal of training the CCGnet model is to minimize the objective function, i.e., min w E(w).

The loss value L(t, θ; w) measures the error of the instance with θ at time t. The objective value E(w) measures the overall error for all instances of θ ∈ Θ over the time range [t 0 , T ].

CCGnet training

Algorithm 2 presents the training of a CCGnet model for solving CCG θ ∀θ ∈ Θ. At each training iteration, a value of θ is randomly sampled from the set Θ, and a batch of time points T is randomly sampled from the time range [t 0 , T ], forming a training data (θ, T). The CCGnet model is then trained using this batch of data, and once the iteration finishes, the batch is discarded. The goal of the algorithm is to minimize the objective function E(w), and the batch loss L(T, θ; w) is an estimate of E(w).

The time range [t 0 , T ] is a hyperparameter that affects both the prediction accuracy and training difficulty of the CCGnet model. Given a CCG θ and its corresponding N P E θ with solution y * , the initial value problem IV P θ with time range [t 0 , T ] has state solution z(t), where z(T ) ≈ y * . The predicted state solution ẑ(t, θ; w)

approximates z(t) on [t 0 , T ], such that ẑ(T, θ; w) ≈ z(T ) ≈ y * . Increasing the time range [t 0 , T ] leads to higher accuracy for z(T ) and, subsequently, a higher accuracy limit for ẑ(T, θ; w). However, a larger time range also makes training more challenging as the model has a larger input space to learn.

The size of the time range is a trade-off that must be considered carefully. If the time range is too small, the model will have a lower accuracy limit and will not be able to surpass it, regardless of the number of training iterations. If the time range is too large, the model will require more iterations to reach its accuracy limit. Thus, it is important to choose a time range that is appropriate for the number of training iterations.

Numerical results

We conducted our experiments using the Google Colab platform and built the neural network with Pytorch 1.9.1 and the ODE system with JAX 0.3.13 [START_REF] Bradbury | JAX: composable transformations of Python+NumPy programs[END_REF]. The hyperparameters for training are as follows:

• The ADAM optimizer [START_REF] Kingma | A method for stochastic optimization[END_REF] was used for training with a learning rate of 0.001 and a batch size of 512.

The maximum number of iterations was set to 10,000.

• The CCGnet model consists of a fully connected neural network with three hidden layers, each containing 100 neurons and using the tanh activation function.

• The time range for the model was set to the interval [0, 1] with an initial point of (0, 0).

• The mean squared error (MSE) was used as the error metric and the weighting hyperparameter was set to τ = 0.5.

The CCGnet model was compared to four numerical integration methods: RK45, LSODA, BDF, and DOP853 [START_REF] Dormand | A family of embedded runge-kutta formulae[END_REF][START_REF] Petzold | Automatic selection of methods for solving stiff and nonstiff systems of ordinary differential equations[END_REF][START_REF] Shampine | The matlab ode suite[END_REF][START_REF] Hairer | Solving ordinary differential equations[END_REF]. These four methods can be accessed using Scipy [START_REF] Virtanen | SciPy 1.0 Contributors, SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python[END_REF]. We consider a concrete example of stochastic cournot competitions as introduced in Section 2.1.2. The number of electricity firms are n = 5, and the cost function of firm i is defined as c i x i = x i 2 . The random variable follows the normal distribution ζ ∼ N µ, σ 2 . The Nash equilibrium of this game can be reformulated as the following NPE

P Y (y -(M y + q)) = y, ( 23
) b b b b 2b + 2 0 0 0 0 1 -1 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0       -a -ϕ -1 ζ (1 -α 1 ) -a -ϕ -1 ζ (1 -α 2 ) -a -ϕ -1 ζ (1 -α 3 ) -a -ϕ -1 ζ (1 -α 4 ) -a -ϕ -1 ζ (1 -α 5 ) C 1 C 2 C 3 C 4 C 5                          
.

The two market price factors are a = 1 and b = 2, The capacity of each firm is

C 1 = C 2 = C 3 = C 4 = C 5 = 5.
The confidence level of each firm are α 1 = α 2 = α 3 = α 4 = α 5 = 0.6. The mean and the variance of the normal distribution is µ = 1 and σ 2 = 2.

We use the following metric to evaluate the accuracy of the prediction ŷ

ϵ = ∥P Y (ŷ -(M ŷ + q)) -ŷ∥. ( 24
)
We consider three different ways to parameterize this CCG problem. Subsection 4.1 parameterize the market price factor a as a variable. Subsection 4.2 parameterize the market price factor b as a variable.

Subsection 4.3 parameterize the confidence level ᾱ as a variable. We construct three independent CCGnet models, each corresponding to one subsection, then train and test these three models separately. We developed a CCGnet model, denoted as:

ẑ(t, a; w), t ∈ [0, 1], a ∈ [1, 5], (25)
to solve for the case when the market price factor a is a variable with a parameter set of Θ = [START_REF]Algorithmic Game Theory[END_REF][START_REF] Jiang | Distributed computation of equilibria in misspecified convex stochastic nash games[END_REF]. At each iteration, a market price factor a is uniformly sampled from the interval [START_REF]Algorithmic Game Theory[END_REF][START_REF] Jiang | Distributed computation of equilibria in misspecified convex stochastic nash games[END_REF], and a batch of time T is uniformly sampled from the time range [0, 1], together forming the batch (a, T) to train the model. Figure 3-(A) shows the loss value during training, which decreases from an initial value of 91.75 to 0.05.

We selected four different values of a to represent four different instances and used the CCGnet model to solve them. Denote ẑ(t, a; w) = x(t, a; w), λ(t, a; w) . In the following results, we only present the results of x(t, a; w). Figure 3-(B) shows the predicted state solutions for x(t, a = 1.37; w), x(t, a = 3.27; w),

x(t, a = 2.53; w), and x(t, a = 4.20; w). Table 1 shows the predicted Nash equilibria for these four instances at t = 1, i.e., x(t = 1, a = 1.37; w), x(t = 1, a = 3.27; w), x(t = 1, a = 2.53; w), and x(t = 1, a = 4.20; w).

Index b

CCGnet

Case 2: b as variable

We developed a CCGnet model, denoted as:

ẑ(t, b; w), t ∈ [0, 1], b ∈ [1, 5], (26)
to solve for the case when the market price factor b is a variable with a parameter set of Θ = [START_REF]Algorithmic Game Theory[END_REF][START_REF] Jiang | Distributed computation of equilibria in misspecified convex stochastic nash games[END_REF]. At each iteration, a market price factor b is uniformly sampled from the interval [START_REF]Algorithmic Game Theory[END_REF][START_REF] Jiang | Distributed computation of equilibria in misspecified convex stochastic nash games[END_REF] We studied the case where the confidence level is a variable and assumed that α 1 = α 2 = α 3 = α 4 = α 5 .

We denote this common value as ᾱ and build a CCGnet model, denoted as:

ẑ(t, α; w), t ∈ [0, 1], α ∈ [0.5, 0.9], (27)
to solve for this case when ᾱ is a variable with a parameter set of Θ = [0.5, 0.9]. At each iteration, a value of ᾱ is uniformly sampled from the interval [0.5, 0.9] and a batch of time points, denoted as T, is uniformly sampled from the time range [0, 1]. These two samples, (ᾱ, T), form a batch used to train the model. Figure 5-(A) shows the loss value during training, which decreases from an initial value of 74.39 to 0.03.

We tested this CCGnet model on four example instances with different values of ᾱ, specifically 0.60, 0.90, 0.67, and 0.75. Figure 5-(B) shows the predicted state solutions for x(t, ᾱ = 0.60; w), x(t, ᾱ = 0.90; w),

x(t, ᾱ = 0.67; w), and x(t, ᾱ = 0.75; w). Table 5 shows the predicted Nash equilibria for these four instances at t = 1, i.e., x(t = 1, ᾱ = 0.60; w), x(t = 1, ᾱ = 0.90; w), x(t = 1, ᾱ = 0.67; w), and x(t = 1, ᾱ = 0.75; w).

Discussion

The main advantage of the CCGnet model is its computational performance. It can directly predict the Nash equilibrium without any iterative process, making it much faster than numerical integration methods.

This advantage becomes even more significant when there are a large number of instances to solve. For example, when solving 10,000 different instances, the CCGnet model can predict all the Nash equilibria in a one-shot manner with only 1.5 ms, while numerical methods require more than 20,000 ms to solve each instance one after another. Additionally, the CCGnet model can utilize a GPU to further accelerate the solution process, while GPU-based numerical methods are still under development.

One limitation of the CCGnet model is its prediction accuracy compared to exact solutions obtained through numerical integration methods. While numerical integration methods can provide exact solutions given sufficient computational time, the CCGnet model can only provide predictions. The accuracy of these predictions depends on technical details such as the neural network structure, training algorithm, and hyperparameter settings, which are active areas of research in machine learning and deep learning. As these areas progress, the CCGnet model has the potential to improve its prediction accuracy.

Conclusion

This paper presents a deep learning approach called CCGnet for solving chance-constrained games.

CCGnet is based on neurodynamic optimization, which models a chance-constrained game as an ODE system. One of the key benefits of CCGnet is its ability to solve multiple instances in a very short amount of CPU time, significantly faster than traditional methods. The paper provides a detailed description of the proposed method, including the parametrization of CCG instances, the model framework, the training algorithm, and a discussion of hyperparameters.

However, it is important to note that the proposed method should not be considered a replacement for standard solvers like RK45 and BDF. These methods have been well-developed over many years. Our purpose is to link the machine learning community and CCG. We believe that with the rapid growth of research on machine learning, both methodologically and experimentally, this paper will continue to contribute to the efficient solution of CCG problems.

There are many potential avenues for future research. Some examples include: 1) Choosing the hyperparameter initial point to be all zero may not always lead to the best computational performance. Is it possible to find other choices that lead to better results? 2) We used a uniform distribution to sample the dataset.

Could other sampling methods lead to better results? 3) We used a fully-connected network structure. How can we design a more suitable neural network structure and activation function?

Bibliography

Figure 1 :

 1 Figure 1: The problem reformulation from a CCG to an IVP via an NPE. We use the stochastic cournot competition for illustration. In the left box of CCG, x * represents the Nash equilibrium, and the payoff function u

Figure 2 :Algorithm 1 :

 21 Figure 2: CCGnet framework. (A) One CCGnet model to solve multiple CCG instances. (B) The CCGnet predictions for the CCG θ , N P E θ and IV P θ . (C) The computation flow of the CCGnet loss.

3 while iter ≤ Max iteration do 4 θ 5 T 6 Φ 7 Forward 2 :

 345672 ∼ Θ: Uniformly sample a confidence level α ∈ Θ ∼ [t 0 , T ]: Uniformly sample a batch of times T from the time range [t 0 , T ] θ : Derive the ODE system Φ θ associated with the instance CCG θ propagation: Compute the batch loss L(T, θ; w) 8 Backward propagation: Update the weight w of the CCGnet model by ∇ w L(T, θ; w) Training of a CCGnet model for solving CCG θ ∀θ ∈ Θ Hyperparameters: Time range [t 0 , T ]; Initial point (t 0 , z 0 ) Result : The CCGnet model after training 1 Function Main(): 2 Initialize a CCGnet model.

3 while iter ≤ Max iteration do 4 θ 5 T 6 Φ 7 Forward

 34567 ∼ Θ: Uniformly sample a θ from the set Θ ∼ [t 0 , T ]: Uniformly sample a batch of time T from the time range [t 0 , T ] θ : Derive the ODE system Φ θ related to the instance CCG θ propagation: Compute the batch loss L(T, θ; w) 8 Backward propagation: Update the weight w of the CCGnet model by ∇ w L(T, θ; w)

Figure 3 :

 3 Figure 3: Case 1: a as variable. (A) The training loss versus the number of iterations. (B) The predicted state solutions for the four example instances. The top-left, top-right, bottom-left, and bottom-right show the results of a = 1.37, a = 3.27, a = 2.53, and a = 4.20, respectively.

Figure 4 :

 4 Figure 4: Case 2: b as variable. (A) The training loss versus the number of iterations. (B) The predicted state solutions for the four example instances. The top-left, top-right, bottom-left, and bottom-right show the results of b = 3.83, b = 3.90, b = 2.34, and b = 1.46, respectively.

  and a batch of time points, denoted as T, is uniformly sampled from the time range [0, 1]. These two samples, (b, T), form a batch used to train the model. Figure 4-(A) shows the loss value during training, which decreases from an initial value of 76.51 to 0.01. We tested this CCGnet model on four example instances with different values of b, specifically 3.83, 3.90, 2.34, and 1.46. Figure 4-(B) shows the predicted state solutions for x(t, b = 3.83; w), x(t, b = 3.90; w), x(t, b = 2.34; w), and x(t, b = 1.46; w).

Figure 5 :

 5 Figure 5: Case 3: ᾱ as variable. (A) The training loss versus the number of iterations (B) The predicted state solutions for the four instances The top-left, top-right, bottom-left, and bottom-right show the results of ᾱ = 0.60, ālpha = 0.90, ᾱ = 0.67, and ᾱ = 0.75, respectively.

Table 1 :

 1 Case

	4.1. Case 1: a as variable
	Index a	CCGnet prediction	Nash equilibrium
	1	1.37 [0.16, 0.16, 0.16, 0.16, 0.16] [0.14, 0.14, 0.14, 0.14, 0.14]
	2	3.27 [0.29, 0.29, 0.29, 0.29, 0.29] [0.28, 0.28, 0.28, 0.28, 0.28]
	3	2.53 [0.24, 0.24, 0.24, 0.24, 0.24] [0.23, 0.23, 0.23, 0.23, 0.23]
	4	4.20 [0.36, 0.35, 0.36, 0.35, 0.36] [0.35, 0.35, 0.35, 0.35, 0.35]

The experimental setup for Sections 4.1, 4.2, and 4.3 is the same and each subsection includes the following results:

[START_REF]Algorithmic Game Theory[END_REF]

the training loss of the CCGnet model, (2) the predicted state solutions of four IVPs corresponding to four CCG instances, (3) the predicted solutions to the four CCG instances, and (4) a comparison of CPU time between the CCGnet model and the numerical integration methods. Finally, Section 4.4 compares the advantages and limitations of our method to the numerical integration methods. 1: a as variable. The predicted Nash equilibrium for the four example instances. CCGnet prediction refers to the predicted Nash equilibrium from the CCGnet model. Nash equilibrium refers to the true value.

Table 2

 2 compares the computational performance of the CCGnet model, ẑ(t, a; w), and the neurodynamic approach when solving multiple instances. When solving a single instance, the CCGnet model has a CPU time of less than 1 ms, which is faster than the best result of 2.23 ms for the neurodynamic approach. When solving 10,000 instances, the CCGnet model takes only 1.53 ms of CPU time, significantly faster than the best result of 22,500 ms for the neurodynamic approach. On average, the CCGnet model has an error of

	ϵ = 0.2.

Table 2 :

 2 Case 1: a as variable. The computational performance of the CCGnet model and the neurodynamic approach. Each row represents a test batch of many different instances. With or without GPU, refers to whether the CCGnet model uses CUDA. RK45, LSODA, BDF, and DOP853 are four numerical integration methods.

Table 3 :

 3 Case 2: b as variable. The predicted Nash equilibrium for the four example instances. CCGnet prediction refers to the predicted Nash equilibrium from the CCGnet model. Nash equilibrium refers to the true value.

  Table3shows the predicted Nash equilibria for these four instances at t = 1, i.e., x(t = 1, b = 3.83; w), x(t = 1, b = 3.90; w), x(t = 1, b = 2.34; w), and x(t = 1, b = 1.46; w).

	Instance number	CCGnet CPU time (ms)	CPU time (with GPU) (ms)	ϵ error	Neurodynamic approach RK45 LSODA CPU time CPU time (ms) (ms)	BDF CPU time (ms)	DOP853 CPU time (ms)
	1	< 1	< 1	0.04	3.09	2.64	8.70	3.68
	100	< 1	< 1	0.07	282	247	841	355
	500	1.03	< 1	0.07	1510	1410	4290	1840
	1000	2.02	< 1	0.07	3000	2620	8550	3740
	5000	8.61	1.07	0.07	15000	13000	42700	18500
	10000	17.1	1.50	0.07	30200	26100	84000	36900

Table 4 :

 4 Case 2: b as variable. The computational performance of the CCGnet model and the neurodynamic approach. Each row represents a test batch of many different instances. With or without GPU, refers to whether the CCGnet model uses CUDA. RK45, LSODA, BDF, and DOP853 are four numerical integration methods.

Table 4

 4 compares the computational performance of the CCGnet model, ẑ(t, b; w), and the neurodynamic approach. When solving a single instance, the CCGnet model has a CPU time of less than 1 ms, outperforming the best result of 2.64 ms for the neurodynamic approach. When solving 10,000 instances, the CCGnet model takes only 1.50 ms of CPU time, faster than the best result of 26,100 ms for the neurodynamic approach.

	On average, the CCGnet model has an error of ϵ = 0.07.
	4.3. Case 3: ᾱ as variable
	Index ᾱ	CCGnet endpoint	Nash equilibrium
	1	0.60 [0.11, 0.11, 0.11, 0.11, 0.11] [0.12, 0.12, 0.12, 0.12, 0.12]
	2	0.90 [0.01, 0.01, 0.01, 0.01, 0.01] [0.01, 0.01, 0.01, 0.01, 0.01]
	3	0.67 [0.09, 0.09, 0.09, 0.09, 0.09] [0.10, 0.10, 0.10, 0.10, 0.10]
	4	0.75 [0.06, 0.06, 0.06, 0.07, 0.06] [0.08, 0.08, 0.08, 0.08, 0.08]

Table 5 :

 5 Case 3: ᾱ as variable. The predicted Nash equilibrium for the four example instances. CCGnet prediction refers to the predicted Nash equilibrium from the CCGnet model. Nash equilibrium refers to the true value.

				(B)	0.14									0.14					x1
					0.12									0.12					x2
																			x3
					0.10									0.10					x4
																			x5
	10 2 (A)		x	0.06 0.08							x1	x	0.06 0.08
					0.04							x2		0.04
												x3
		10 1			0.02							x4		0.02
												x5
	M.S.E	10 0			0.00	0.0	0.2	0.4	t	0.6	0.8	1.0		0.00	0.0	0.2	0.4	t	0.6	0.8	1.0
					0.14									0.14
						x1													x1
		10 -1			0.12	x2 x3								0.12					x2 x3
					0.10	x4								0.10					x4
						x5													x5
		0	5000	10000	0.08									0.08
			Iteration	x	0.06								x	0.06
					0.04									0.04
					0.02									0.02
					0.00	0.0	0.2	0.4		0.6	0.8	1.0		0.00	0.0	0.2	0.4		0.6	0.8	1.0
									t									t

Table 6

 6 compares the computational performance of the CCGnet model, ẑ(t, α; w), and the neurodynamic approach. When solving a single instance, the CCGnet model has a CPU time of less than 1 ms, faster than the best result of 2.27 ms for the neurodynamic approach. When solving 10,000 instances, the CCGnet model takes only 1.14 ms of CPU time, significantly faster than the best result of 24,300 ms for the neurodynamic approach. On average, the CCGnet model has an error of ϵ = 0.15.

	Instance number	CCGnet CPU time (ms)	CPU time (with GPU) (ms)	ϵ error	Neurodynamic approach RK45 LSODA CPU time CPU time (ms) (ms)	BDF CPU time (ms)	DOP853 CPU time (ms)
	1	< 1	< 1	0.16	2.57	2.27	8.02	3.47
	100	< 1	< 1	0.15	267	225	838	347
	500	1.02	< 1	0.16	1320	1180	4230	1770
	1000	2.05	< 1	0.15	2640	2420	8440	3540
	5000	8.52	1.08	0.15	13200	12200	42300	17700
	10000	17.9	1.41	0.15	26600	24300	87000	35700

Table 6 :

 6 Case 3: ᾱ as variable. The computational performance of the CCGnet model and the neurodynamic approach. Each row represents a test batch of many different instances. With or without GPU, refers to whether the CCGnet model uses CUDA. RK45, LSODA, BDF, and DOP853 are four numerical integration methods.


Dawen Wu
email: dawen.wu@centralesupelec.fr

Abdel Lisser
email: abdel.lisser@l2s.centralesupelec.fr

MG-CNN: A Deep CNN To Predict Saddle Points Of Matrix Games

Keywords: Convolutional neural network, Saddle point, Matrix game

Finding the saddle point of a matrix game is a classical problem that arises in various fields, e.g., economics, computer science, and engineering. The standard problem-solving methods consist of formulating the problem as a linear program (LP). However, this approach seems to be inappropriate, especially when multiple instances need to be solved. In this paper, we propose a Convolutional Neural Network based approach, which is able to predict both the strategy profile (x, y) and the optimal value v of the game. We call this approach Matrix Game-Conventional Neural Network or MG-CNN for short. Thanks to a global pooling technique, MG-CNN can solve matrix games with different shapes. We propose a specialized algorithm to train MG-CNN, which includes both data generation and model training. Our numerical experiments show that MG-CNN outperforms standard LP solvers in terms of computational CPU time and provides a high quality prediction.

Introduction

Game theory is a theoretical framework to study conflict and cooperation among rational agents in a strategic setting. The assumption behind game theory is that agents choose actions that maximize their own payoffs [START_REF] Fudenberg | Game theory[END_REF]. In this paper, we call matrix game the two-player zero-sum game problem with the following characteristics. Firstly, the players' action sets are discrete and finite. Secondly, 5 for a given choice of actions, the payoff for both players adds up to zero. Matrix games model many real-world problems to help decision-makers make the right decisions in a competitive environment [START_REF] Dixit | Investment under uncertainty[END_REF][START_REF] Simmons | Investment science[END_REF][START_REF] Vega-Redondo | Economics and the theory of games[END_REF][START_REF] Singh | Introduction to Game Theory and Its Application in Electric Power Markets[END_REF]. There are also studies on the situation where games contain random variables [START_REF] Cheng | Random-payoff two-person zero-sum game with joint chance constraints[END_REF][START_REF] Singh | A second-order cone programming formulation for two player zero-sum games with chance constraints[END_REF]Wu & Lisser, 2022a).

The saddle point or Nash equilibrium is the most common way to define the solution concept of a non-10 cooperative game. These solutions describe a situation where no player can improve his payoff by unilaterally changing his strategy. A saddle point refers to the solution of a two-player zero-sum game. von Neumann (1928) proved the minimax theorem, which states that there exists a saddle point for any finite two-person zero-sum game. A Nash equilibrium refers to the solution of a n-player game. [START_REF] Nash | Equilibrium points in n-person games[END_REF] proved that there always exists an equilibrium for any finite n-player games called Nash equilibrium.

With the rapid growth of available data and computing power, deep learning in the form of deep neural networks is used in many areas, such as image processing [START_REF] Krizhevsky | ImageNet classification with deep convolutional neural networks[END_REF][START_REF] Goodfellow | Deep Learning[END_REF], natural language processing [START_REF] Devlin | BERT: pre-training of deep bidirectional transformers for language understanding[END_REF], recommender system [START_REF] Zhang | Deep learning based recommender system: A survey and new perspectives[END_REF], see also [START_REF] Silver | Mastering the game of Go with deep neural networks and tree search[END_REF][START_REF] Jumper | Highly accurate protein structure prediction with alphafold[END_REF] for additional application examples. Convolutional neural networks (CNNs) are deep neural networks that are frequently used in computer vision [START_REF] Lecun | Convolutional networks for images, speech, and time series[END_REF][START_REF] Courville | Deep learning[END_REF]. A CNN uses a shared weight convolutional kernel that slides along the input feature maps. The architecture of a neural network model is crucial for the performance enhancement, and there are specialized network structures for various situations [START_REF] Krizhevsky | ImageNet classification with deep convolutional neural networks[END_REF][START_REF] He | Deep residual learning for image recognition[END_REF][START_REF] Huang | Densely connected convolutional networks[END_REF][START_REF] Tan | Efficientnet: Rethinking model scaling for convolutional neural networks[END_REF][START_REF] Alzubaidi | Review of deep learning: Concepts, cnn architectures, challenges, applications, future directions[END_REF][START_REF] Khan | A survey of the recent architectures of deep convolutional neural networks[END_REF][START_REF] Xu | Convergence of deep convolutional neural networks[END_REF]. PyTorch is an open-source library for building neural network models provided by CUDA support to speed up processing by harnessing the power of GPUs [START_REF] Paszke | PyTorch: An imperative style, high-performance deep learning library[END_REF].

Generative Adversarial Networks (GANs) is a novel deep learning method, widely used for image generation and text generation [START_REF] Goodfellow | Generative adversarial networks[END_REF][START_REF] Zhou | A survey of game theoretic approach for adversarial machine learning[END_REF][START_REF] Dasgupta | A survey of game theoretic approaches for adversarial machine learning in cybersecurity tasks[END_REF][START_REF] Tembine | Deep Learning Meets Game Theory: Bregman-Based Algorithms for Interactive Deep Generative Adversarial Networks[END_REF]. A GAN contains two neural networks, a generator, and a discriminator. These two neural networks are trained by competing against each other. We would like to emphasize the relationship and difference between this paper and GAN. The latter is a two-person zero-sum game with continuous actions. The generator and the discriminator are two players whose model parameters are viewed as actions and have opposite payoff functions. The training purpose for GANs is to find a saddle point (w 1 , w 2 ) of the two neural networks. Our paper considers a two-player zero-sum game with finite actions, and our goal is to use a CNN to predict the saddle point of such a game.

Related works

We present here two approaches for solving matrix games, i.e., the LP approach and the WL-CNN approach [START_REF] Wu | Using cnn for solving two-player zero-sum games[END_REF].

The LP approach. The conventional way to solve a matrix game is to convert it into a linear programming (LP) problem. The LP can then be solved by the simplex method [START_REF] Dantzig | Linear Programming and Extensions[END_REF][START_REF] Bertsimas | Introduction to linear optimization volume 6[END_REF][START_REF] Vanderbei | Integer programming[END_REF], or interior-point methods [START_REF] Wright | Primal-dual interior-point methods[END_REF][START_REF] Karmarkar | A new polynomial-time algorithm for linear programming[END_REF]. Here, We introduce four optimization solvers, i.e., ECOS, GLPK, SCS, and Gurobi. ECOS, embedded conic solver, is an efficient implementation of an interior-point method for second-order cone programming [START_REF] Domahidi | Ecos: An socp solver for embedded systems[END_REF] designed for embedded applications. GLPK is a classical solver first released in 2000, which is dedicated only to LP problems [START_REF] Glpk | GNU Linear Programming Kit[END_REF]. SCS, splitting conic solver, is based on a first-order method to solve convex cone programs, which can scale to large problems and solve many types of convex nonlinear problems [START_REF] Brendan | Operator splitting for conic optimization via homogeneous self-dual embedding[END_REF]. Gurobi is a well-established commercial solver with a large number of applications in the industry, it is known for its good performances in many benchmarks (Gurobi Optimization, LLC, 2021;[START_REF] Mittelmann | Benchmarks of optimization software[END_REF]. These four solvers represent a large part of the state-of-the-art (SOTA) for solving LPs. 1: Three approaches to solve a matrix game The saddle point is divided into two components, the optimal value v * , and the strategy profile (x * , y * ). Our MG-CNN approach predicts both the optimal value and strategy profile by a CNN model. The WL-CNN approach predicts the optimal value by a CNN model and then obtains the strategy profile by calling an optimization solver. The LP approach solves both the optimal value and strategy profile by an optimization solver.

Their computational performance varies depending on the specific problem instances, experimental environment, and parameter choices. [START_REF] Mittelmann | Benchmarks of optimization software[END_REF] provides a platform for testing the performance of different optimization solvers (Jared L, Adair, Kristin L, Detry, Richard J, Durfee, Justin D, Jones & A, Martin, 2012). CVXPY is a modeling package for convex optimization problems, which translates the problem into a standard form and can call sereval optimization solvers [START_REF] Diamond | CVXPY: A Python-embedded modeling language for convex optimization[END_REF].

The WL-CNN approach. [START_REF] Wu | Using cnn for solving two-player zero-sum games[END_REF] proposed a CNN-based method to predict saddle points, which we call in this paper WL-CNN. This approach predicts the saddle point in two steps. First, it uses a CNN model to predict the optimal value v. Then, after getting the prediction v, the related strategy profile (x, y) is obtained by solving a linear system of inequalities.

The LP approach is time-consuming, especially when solving several instances. Although the WL-CNN method shows some computational speed advantages, its CNN model can only predict the optimal value.

It still requires solving an inequalities system to obtain a strategy profile. Unlike WL-CNN, our MG-CNN model can directly predict both the optimal value and strategy profile. Table 1 summarizes how these three approaches obtain the saddle point of a matrix game.

Contributions

The contributions of this paper can be summarized as follows

• Our proposed MG-CNN outperforms both WL-CNN and LP approaches in terms of computational speed. For example, when solving one matrix game of size (10, 10), MG-CNN takes only 5.1 ms, while WL-CNN takes 5.8 ms and LP takes 12.6 ms. When solving multiple instances, the computational advantage becomes much more significant. MG-CNN solves 1000 instances of size (10, 10) in 73.2 ms, WL-CNN in 4520 ms, and LP in 18300 ms.

• Our proposed MG-CNN outperforms WL-CNN in terms of prediction accuracy. For a matrix game of size (20, 20) and generated by U (0, 100), MG-CNN has a mean absolute percentage error of 1.73%, lower than 2.83% of WL-CNN. Additionally, MG-CNN is more reliable across a range of probability distributions and game sizes, whereas WL-CNN fails in many situations.

The remaining of this paper is organized as follows. Section 2 sketches the minimum knowledge to understand the problem, including the matrix game and the LP formulation. Section 3 presents our proposed MG-CNN approach. Section 4 gives the comparative experimental results among the three approaches.

Section 5 discusses the pros and cons of MG-CNN. Section 6 summarizes the whole paper and gives future directions.

Notations

Table 2 presents the notations list of this paper.

Notation Definition

n ∈ N The number of actions for player 1. m ∈ N

The number of actions for player 2. A ∈ R n×m A matrix game represented by the payoff matrix of player 1.

(x * , y * ), x * ∈ R n , y * ∈ R m The strategy profile of the saddle point. v * ∈ R
The optimal value of the saddle point.

MG-CNN(A; w)

The MG-CNN model with parameters w.

(x, y), x ∈ R n , y ∈ R m
The strategy profile prediction from the MG-CNN model. v ∈ R

The optimal value prediction from the MG-CNN model.

L(A; w)

The loss function of the MG-CNN model.

P

The probability distribution used to generate A.

min E A∼P [L(A; w)]
The objective function of the MG-CNN model.

Preliminaries

Matrix game

We denote the two players in a matrix game as players 1 and 2, respectively. Players 1 and 2 have n and m discrete actions, respectively. The action sets of the two players can be written as X = {1, . . . , n}, Y = {1, . . . , m}, respectively. When the row player selects action i ∈ X , the column player selects action j ∈ Y, the payoff for the players 1 and 2 are a ij and -a ij , respectively. Thus, player 1's payoff can be represented by the matrix A (1), while player 2's payoff can be represented by the matrix -A.

Throughout this paper, a matrix game is represented by the payoff matrix A, where

A =         a 11 a 12 . . . a 1m a 21 a 22 . . . a 2m . . . . . . . . . . . . a n1 a n2 . . . a nm         . ( 1
)
We denote x and y as mixed strategies for players 1 and 2, respectively. A mixed strategy is a discrete probability distribution over the player's action set. The vectors x and y should be within probability

simplices, i.e., x ∈ {x ∈ R n : e T n x = 1, x ≥ 0}, y ∈ {y ∈ R m : e T m y = 1, y ≥ 0}, where e k = [1, . . . , 1] T ∈ R k . Theorem 1 (von Neumann (1928)). Let X ⊂ R n and Y ⊂ R m be compact convex sets. If f : X × Y → R is a continuous function that is concave-convex.
Then, the following holds

max x∈X min y∈Y f (x, y) = min y∈Y max x∈X f (x, y). (2)
The saddle point existence of a matrix game is guaranteed by Theorem 1. The optimal strategy profile of a matrix game A is defined as follows,

(x * , y * ) = arg max x arg min y x T Ay , (3)
and the corresponding optimal value is

v * = max x min y x T Ay . (4)

LP to solve Matrix game

The saddle point of a matrix game A can be obtained by solving the primal-dual LP pair ( 5)-( 6),

(P) max v s.t. A T x ≥ ve m e n T x = 1, x ≥ 0, (5)
(D) min v s.t. Ay ≤ ve n e m T y = 1, y ≥ 0. (6)
The primal LP (5) has decision variable (x, v) ∈ R n+1 , one equality constraint and m inequality constraints.

95

The dual LP (6) has decision variable (y, v) ∈ R m+1 , one equality constraint and n inequality constraints.

The optimal solutions for these two LP problems are (x * , v * ) and (y * , v * ), where (x * , y * ) is the desired optimal strategy profile, and v * is the desired optimal value. For the construction and related details, we refer the reader to [START_REF] Dantzig | Linear Programming and Extensions[END_REF].

MG-CNN

Fully convolutional layers

The MG-CNN model uses only convolutional layers and does not contain dense connected layers. By appropriately setting the convolutional kernel size, padding, and stride, the convolutional layers do not change the shape of the input feature map. Other types of operations can be added, as long as they do not affect the shape of the feature map, e.g., pooling layers, batch normalization, or residual connections. MG-CNN does not change the shape of all feature maps between input and output.

Global pooling technique We use a novel pooling technique in order to generate output (x, y) of the desired shape. This pooling technique pools only two dimensions of 3D feature maps, as shown in Figure 1-(b). For example, consider the 3D feature maps of shape (c, n, m). For generating x of shape (n, ), it pools the channel and width dimensions and keeps the length dimension. For generating y of shape (m, ), it pools the channel and length dimensions and keeps the width dimension. The pooling can be average or maximum pooling.

Thanks to the fully convolutional layers and Global pooling technique, the MG-CNN model can accept matrix games A of varied sizes and output (x, y) with desired shapes. This framework is generic and is not specific to the matrix game problem. It can be used in numerous situations when the input shape is not fixed, and a corresponding output shape is needed.

MG-CNN training

The loss of the MG-CNN model is defined as

L(A; w) = ℓ(v, v * ). ( 9
)
The optimal value prediction v is computed by (8). ℓ(•, •) stands for an error function, e.g., mean square error. The loss function is based on the optimal value instead of the strategy profile for two reasons: 1) v and v * are two scalars, while (x, y) and (x * , y * ) are two vectors with possibly high dimensions. 2) A matrix game may have multiple optimal (x * , y * ) values, whereas the optimal v * is unique. Predicting one saddle point among many is inefficient. In contrast, it is more reasonable to predict the unique optimal point.

The training objective for the MG-CNN model is defined as

min w E A∼P [L(A; w)], (10)
where A ∼ P represents that each element of the matrix A follows the probability distribution P . (2018). Since it is trained on brand-new data each time, the model does not overfit any dataset. Training is over when a certain metric is satisfied. For example, when the loss drops to a threshold or the number of iterations exceeds a given value.

Training data generation

Results

We use the Google Colab Pro+ platform to conduct our experiments. We build and train the neural network model by Pytorch 1.9.1. We use CVXPY to model the LP and call various solvers therein [START_REF] Diamond | CVXPY: A Python-embedded modeling language for convex optimization[END_REF]. We compare MG-CNN with the WL-CNN approach [START_REF] Wu | Using cnn for solving two-player zero-sum games[END_REF] and the LP approach. The LP approach is represented by four optimization solvers, ECOS, GLPK, SCS, and Gurobi [START_REF] Domahidi | Ecos: An socp solver for embedded systems[END_REF][START_REF] Glpk | GNU Linear Programming Kit[END_REF][START_REF] Brendan | Operator splitting for conic optimization via homogeneous self-dual embedding[END_REF]Gurobi Optimization, LLC, 2021).

In Section 4.1, We show how to train an MG-CNN model, including the hyperparameter setting, the model structure, and the training loss. In Section 4.2, we demonstrate the computational speed advantage of the MG-CNN model versus WL-CNN and LP approaches. In Section 4.3, we show the prediction accuracy of the MG-CNN model versus the WL-CNN approach.

Model training

The hyperparameters for training are as follows

• The optimizer for training the neural network is ADAM [START_REF] Kingma | Adam: A method for stochastic optimization[END_REF], with a learning rate of 0.001. • The batch size is 128, and the maximum number of iterations is 30, 000.

• The neural network structure is shown by Table 3.

We initialize an MG-CNN model and train it according to Algorithm 1. We use the game size (20,20) and the uniform distribution U (0, 100) to generate the matrix games. Both training and testing data are randomly generated in the same way. At each iteration, a training batch is generated to train the model.

165

Every 50 iterations, a testing batch is generated to test the model. We use the same training scheme and a similar network structure to train the WL-CNN model, which is used hereafter for comparison purposes. We now test the computational performance of MG-CNN and compare it with the WL-CNN and LP approaches. The MG-CNN computation time is the CPU time of the CNN model for both v and (x, y).

The WL-CNN computation time includes the CPU time of the CNN model for v and the CPU time of the optimization solver for (x, y). The LP computation time is the CPU time of the optimization solver for both v * and (x * , y * ).

We randomly generate six test batches with 1000, 1200, 1400, 1600, 1800, and 2000 instances, respectively.

Each matrix game within the test batch has size (20, 20) and is sampled by the uniform distribution U (0, 100).

Figure 3 shows the CPU time of the three approaches to solve these test batches. When solving 1000 samples, MG-CNN takes 53.3ms, WL-CNN takes 3280ms, and the LP approach takes at least 9570ms. MG-CNN outperforms WL-CNN and is much faster than the four LP solvers. The advantage becomes more significant when dealing with a large number of instances.

Prediction accuracy

We evaluate the accuracy on the basis of the prediction v and the true v * . We use the mean absolute error (MAE), the mean squared error (MSE), and the mean absolute percentage error (MAPE) as metrics, defined by

MAE = 1 B B i=1 |v * i -v i | , (11)
MSE = 1 B B i=1 (v * i -v i ) 2 , ( 12
) MAPE = 1 B B i=1 v * i -v i v i * 100%, (13)
where B refers to the number of instances in a test batch, v * i refers to the true optimal value of a matrix game, which is obtained by the LP approach. v i refers to the prediction of MG-CNN or WL-CNN. We also provide "Mean v * " and "Mean v" used to describe a test batch, defined as

Mean v * = 1 B B i=1 v * i , (14)
Mean v = 1 B B i=1 v i . (15)

Discussion

The MG-CNN approach solves a matrix game differently from WL-CNN and LP approaches. The LP approach formalizes a matrix game problem as an LP problem which is then solved by an optimization solver.

WL-CNN solves a matrix game in two steps. First, it uses a CNN model to predict the optimal value v, then obtains the related strategy profile (x, y) by solving a system of linear inequalities. The MG-CNN model solves a matrix game by directly predicting (x, y) and v. Pros MG-CNN is faster than both the WL-CNN and LP approaches, which is mainly due to the following reasons:

Probability distribution

• MG-CNN can predict the saddle point directly without calling any optimization solver. The LP approach needs to call an optimization solver to obtain both (x * , y * ) and v * , and WL-CNN needs to call an optimization solver to obtain the strategy profile (x, y).

• When dealing with a batch of instances, the inherent parallel solving capabilities allow MG-CNN to solve multiple instances in one shot. In comparison, the LP approach solves sequentially the different instances, and WL-CNN solves sequentially the linear systems to obtain (x, y).

MG-CNN shows acceptable accuracy, which outperforms WL-CNN. MG-CNN also exhibits robustness against untrained game sizes and probability distributions.

Cons The disadvantage of MG-CNN is that it requires training to achieve the desired prediction accuracy.

MG-CNN also shows weaknesses in predicting non-square matrix games, while the LP approach is more reliable in this case. Prediction accuracy depends heavily on technical details, such as neural network structure and training methods, which fall into the general machine learning scope. The numerous ongoing research on these topics can directly benefit MG-CNN.

Compared to WL-CNN, MG-CNN can be viewed as an enhanced version, which is more accurate, faster, and robust against various untrained probability distributions and game sizes. Compared to LP, MG-CNN and LP have their pros and cons and are suitable for different scenarios. The LP approach is more suitable when requiring reliability and high accuracy. MG-CNN is more suitable to solve multiple instances with a remarkably reduced computational effort.

Conclusion

We propose a deep learning approach to predict the saddle point of a matrix game, i.e., MG-CNN.

We presented MG-CNN in detail, including the neural network structure, loss function, objective function, training data generation, and training algorithm. We conducted experiments and compared MG-CNN with other solution methods.

We must emphasize that our proposed approach should not be considered as substitute for the classical LP approaches, which have been developed over the last decades and are well established. The traditional LP solution method satisfies the requirements of robustness and reliability needed in practice. Our main contribution is to provide a novel approach for solving matrix games, which shows a great computational potential.

With the rapid development of machine learning or deep learning in methodology and implementation, we believe this work will lead to ongoing contributions to benefit a wide range of practitioners in game theory.

There are many future directions for this work, and we give some examples here. 1) How to design a better model structure to adapt to the matrix game problem? 2) How to migrate this approach to games with

1003. 1 .Figure 1 :Figure 1 -

 111 Figure 1: MG-CNN framework (a) The MG-CNN model structure The input of the model is a matrix game A, and the output is a predicted saddle point (x, y). The predicted optimal value v is computed by v = x T Ay. The computation of loss is based on the predicted optimal value v. (b) The global pooling technique for x and y. Consider a feature map of shape (c, n, m). The global pooling for x only pools the depth and the width dimension and generates a vector of n-dimensional. The global pooling for y only pools the depth and the length dimension and generates a vector of m-dimensional. (c) Explanation of each icon

  The generation of a training matrix game A is governed by two factors: game size (n, m) and probability distribution P , which must be specified prior to training. The game size (n, m) decides the shape of A. The probability distribution P decides how A is sampled. Specifically, each element a ij of A is sampled by the probability distribution P in an i.i.d way. These two factors govern the generation of training data and, consequently, the predictive ability of the MG-CNN model. The optimal Algorithm 1: MG-CNN training Required: Game size (n, m); Probability distribution P ; A LP solver Result : The MG-CNN model 1 Function Main(): 2 Initialize a MG-CNN model. 3 while iter ≤ Max iteration do 4 A ∼ P : sample a matrix game A with shape (n, m) from distribution P 5 (x, y) = CNN(A; w): Predict the saddle point by the MG-CNN model 6 v = x T Ay: Compute the optimal value 7 v * = LP (A): Obtain v * by using the LP solver 8 Forward propagation: Compute the loss L(A; w) = ℓ(v, v * ). 9 Backward propagation: Update w by ∇ w L(A; w) 10 end 11 end value v * of A is provided by an LP solver. A training data sample has the form (A, v * ). Training algorithm The training of MG-CNN is shown in Algorithm 1, which is essentially an optimization process for (10). During each iteration, a training batch is created and trained by the model. The training batch will be used only once and discarded immediately after use. The algorithm trains the model in an unsupervised manner. Instead of training on a fixed dataset, the algorithm incorporates the data generation and model training into the same loop, similar to the meshfree method in Sirignano & Spiliopoulos

Figure 2 :

 2 Figure 2: The training and testing loss versus the number of iterations. M.S.E refers to mean square error.

Figure 2 Figure 3 :

 23 Figure 2 shows the loss computed on the training and testing batch during the training step. The MG-CNN model does not overfit any training data. The training loss and the testing loss have almost the same

Table

	MG-CNN	CNN model	CNN model
	WL-CNN	CNN model	Convex optimization solver
	LP	Convex optimization solver Convex optimization solver

Optimal value v * Strategy profile (x * , y * )

Table 2 :

 2 Notations

Table 3 :

 3 The MG-CNN model details. The MG-CNN model is dived into one main part and two subparts. BN refers to batch normalization. (n, m) refers to the game size of the input matrix game. The final feature maps of the main part is passed to the two subparts.

  MG-CNN takes 84.6ms, WL-CNN takes 6700ms, and the LP approach takes at least 19500ms.In addition, the CPU time of MG-CNN does not grow as fast as WL-CNN and LP. Table 4 presents the CPU time for different numbers of instances and different game sizes. In all cases,

	2000 samples, 185
					CPU time (ms)
	Instance number	Probability distribution	Game size	MG-CNN WL-CNN	LP ECOS GLPK SCS	Gurobi
				5.1	5.8	13.6	12.6	12.7	12.9
				8.6	27.3	102	106	96.7	114
		U(0, 100)	(10*10)	9.2	228	934	982	1040	1080
				18.5	2220	9170	9570	9700	10200
				73.2	4520	18300 19100	20300 20900
		U(0, 100)	(15*15)
									When solving

Table 5 :

 5 Prediction accuracy on training probability distribution and game size. The test batch is generated by U (0, 100) with size (20, 20) but is not trained.

Table 6 :

 6 Table5shows the prediction accuaracy on the training distribution and the game size, i.e., U (0, 100) and 190(20, 20), respectively. Table6and 7 study various probability distributions and game sizes that the models have not trained. Each row in the tables shows the results of a test batch containing 1000 matrix games. In all cases, MG-CNN has a lower error than WL-CNN one, and its predicted Mean v is closer to the Mean v * . Prediction accuracy on untrained probability distributions and game sizes i. U (a, b) refers to the uniform distribution on the interval[a, b]. N (µ, σ 2 ) refers to the normal distribution with mean µ and variance σ 2 . P ois(λ) refers to the Poisson distribution with parameter λ.

	Probability	Game	MG-CNN		WL-CNN			LP
	distribution	size	MAE MSE MAPE Mean v MAE MSE MAPE Mean v Mean v *
		(10, 10) 1.39	3.23	2.80% 49.86	2.89	14.83 5.82%	49.75	49.90
		(15, 15) 0.97	1.51	1.95% 50.04	1.67	4.52	3.35%	49.84	50.00
		(25, 25) 0.74	0.86	1.47% 49.96	1.24	2.45	2.50%	49.88	50.00
	U (0, 100)	(30, 30) 0.62	0.62	1.24% 50.05	1.19	2.30	2.41%	49.89	50.07
		(15, 25) 2.41	7.16	4.97% 48.67	3.71	17.23 7.41%	49.94	46.26
		(25, 15) 2.50	7.51	4.88% 51.28	3.92	18.62 7.88%	49.88	53.77
		(10, 10) 2.35	9.17	4.86% 49.47	5.13	43.63 10.36% 49.64	49.55
		(15, 15) 1.75	5.05	3.56% 49.76	3.21	17.02 6.45%	49.74	49.76
		(25, 25) 1.24	2.45	2.49% 50.05	1.90	5.62	3.81%	49.89	50.03
	N (50, 50)	(30, 30) 1.05	1.82	2.10% 49.98	1.63	4.16	3.28%	49.80	49.96
		(15, 25) 4.35	22.86 9.16% 47.82	6.42	50.52 12.95% 49.85	43.48
		(25, 15) 4.43	23.54 8.54% 52.08	6.64	53.52 13.25% 49.91	56.50
		(10, 10) 0.44	0.33	0.88% 49.89	0.93	1.38	1.87%	49.92	49.87
		(15, 15) 0.31	0.15	0.62% 49.99	1.06	1.81	2.15%	49.88	49.97
		(25, 25) 0.20	0.07	0.41% 49.97	1.30	2.74	2.65%	49.86	50.00
	P ois(50)	(30, 30) 0.17	0.04	0.33% 49.97	1.42	3.28	2.89%	49.83	49.98
		(15, 25) 0.61	0.46	1.22% 49.66	1.48	2.96	2.95%	49.88	49.06
		(25, 15) 0.63	0.50	1.26% 50.26	1.27	2.77	2.60%	49.89	50.88

Table 6 -

 6 7 demonstrates the ability of our MG-CNN to predict untrained probability distributions and game sizes. However, MG-CNN is less accurate in solving non-square matrix games than square matrix games. This is because the neural network model was trained only for square games and not for non-square games.One drawback of WL-CNN is that it only works when Mean v and Mean v * are close to each other. For example, WL-CNN has been trained only on U (0, 100) with Mean v ≈ 50, such that it can only predict matrix games generated by a probability distribution with Mean v ≈ 50 like U (20, 80), N (50, 50) and P ois(50). For the games generated by other distributions, WL-CNN needs to be retrained before prediction. Our MG-CNN does not have this drawback and is robust with a respect to different distributions. As shown in Table7, for the distribution U (50, 100) and size (10, 10), MG-CNN has Mean v = 74.78 with MAPE of 1.15%, while WL-CNN has Mean v = 49.89 with MAPE of 50.09%.

Table 7 :

 7 Prediction accuracy on untrained probability distribution and game size ii U (a, b) refers to the uniform distribution on the interval [a, b]. N (µ, σ 2 ) refers to the normal distribution with mean µ and variance σ 2 . P ois(λ) refers to the Poisson distribution with parameter λ.