Biswarup Mukherjee
email: biswarup.mukherjee@mines-paristech.fr

Georges Kariniotakis
email: georges.kariniotakis@mines-paristech.fr

Fabrizio Sossan
email: fabrizio.sossan@mines-paristech.fr

Smart Charging, Vehicle-to-Grid, and Reactive Power Support from Electric Vehicles in Distribution Grids: A Performance Comparison

Keywords: Electric vehicles, Distribution grids, Uncoordinated charging, Smart charging, Vehicle-to-grid, Optimal scheduling

This paper compares different charging strategies for electric vehicles (EVs) and mechanisms to support local distribution grids. First, a general scheduling problem for EVs based on convex optimization and linearized power grid models is presented. Then, it is shown how it can be adapted to model different charging strategies. These include: i) uncoordinated charging, where EVs maximize a local utility function regardless of grid constraints; ii) smart charging, where a charge schedule of all EVs is determined by maximizing their utility function subject to grid constraints; iii) vehicle-to-grid, where bidirectional power from the EVs is allowed; and iv) reactive power support, where 2-and 4-quadrant EV chargers can provide reactive power. The performance of these strategies are investigated considering the CIGRE benchmark system for medium-voltage distribution grids. It shows that, in the proposed scenario, smart charging with reactive power support is conducive to the shortest global recharging time.

I. INTRODUCTION

The transport sector is responsible for over one-third of the global greenhouse gas emissions and 27% within Europe in 2017 [START_REF]National institute of statistics and economic studies[END_REF]. Electric vehicles (EVs) will play an important role in reducing emissions of the road transport sector as well as dependency on fossil fuels [START_REF]EU 2030 climate & energy framework[END_REF], [START_REF] Irena | Innovation outlook: Smart charging for electric vehicles[END_REF]. The increasing adoption of EVs requires efficient ways to manage their charge. Indeed, the simultaneous charging of a large population of EVs results in a significant increase of the electrical demand and may cause violations of distribution grids' operational constraints, possibly requiring expensive grid reinforcements to distribution system operators (DSOs), as for example highlighted in [START_REF] Elnozahy | A comprehensive study of the impacts of phevs on residential distribution networks[END_REF] for distribution grid transformers. Smart charging has been widely proposed in the existing literature to cope with the issues of uncoordinated charging, helping DSOs with congestion management (e.g., [START_REF] Irena | Innovation outlook: Smart charging for electric vehicles[END_REF], [START_REF] Lopes | Integration of electric vehicles in the electric power system[END_REF]). Smart charging consists in scheduling the charging process of EVs to avoid grid congestions. Vehicle-to-grid (V2G) with bi-directional chargers is one step further and refers to allowing EVs to discharge their batteries and inject power into the grid to support operations of both distribution and transmission grids (e.g., [START_REF] López | V2g strategies for congestion management in microgrids with high penetration of electric vehicles[END_REF], [START_REF] Zecchino | Largescale provision of frequency control via v2g: The bornholm power system case[END_REF]). Both unidirectional and bidirectional chargers can provide reactive power to the grid, which can be used to support local voltage regulation, e.g., [START_REF] Knezović | Robust multi-objective pq scheduling for electric vehicles in flexible unbalanced distribution grids[END_REF], [START_REF] Paudyal | Optimal coordinated ev charging with reactive power support in constrained distribution grids[END_REF].

This paper investigates the performance of different EV charging strategies (uncoordinated, smart charging, V2G, and reactive power support) considering a medium-voltage (MV) grid and their impact on the recharging times. All these scheduling problems are derived from a baseline convex optimization problem that embeds linearized grid constraints from the existing literature [START_REF] Christakou | Efficient computation of sensitivity coefficients of node voltages and line currents in unbalanced radial electrical distribution networks[END_REF]. The performance comparison of these strategies in a common setting and a unified algorithmic framework to accommodate multiple scheduling problems stand as the main contributions of this paper. The rest of this paper is organized as follows. Section II states the problem and introduces the models. Section III and IV describes the methods. Section V and VI present the case study and the results, and Section VII concludes the paper.

II. PROBLEM STATEMENT AND MODELS

A. Problem statement

We consider a distribution grid (e.g., Fig. 1) with loads (including EV chargers), and possibly distributed generation. The simultaneous charging of many EVs might cause violations of its operational constraints. These constraints include ensuring suitable nodal voltage magnitudes, line currents below cable ampacities, and power flow at the substation below the transformer rating. This paper aims to compare different charging strategies for EVs and evaluate how they impact grid constraints and recharging times. The considered recharging strategies are: uncoordinated charging (EVs recharge as soon as they are plugged in), smart charging (charge is scheduled to ensure that grid constraints are respected), V2G (as smart charging, but EVs are allowed to discharge to support the grid, if necessary), and reactive power support (as smart charging, but chargers can adjust reactive power injections). Grid constraints are modelled with a linearized grid model, as described next.

B. Power grid model

Let n = 1, . . . , N , denote the index of the node of the network, where N is the total number of nodes. The index t = 1, . . . , T refers to the time interval, with T total samples. The time horizon 1, . . . , T refers to the recharging horizon for the EVs. In the rest of this paper, we will refer to overnight charging, although the formulation is general and can be applied to other cases. Time dynamics need to be considered to model both time-variant power demand, and because the EVs' charging process is inherently time dependant due to the state-of-charge constraints of the EVs. The active and reactive power nodal injections at node n and time interval t is:

P tn = P (net)
tn + P (EV nodal) tn (1a)

Q tn = Q (net) tn + Q (EV nodal) tn (1b)
for all nodes of the grid, where P (net) tn is the net demand, i.e., power demand minus local renewable generation and P (EV nodal) tn is the total power demand of EVs. The former is an input of the problem, whereas the latter depends on the charging policy and is modelled as described in section II C.

Voltage levels at the nodes of the grid and the current values in the lines (voltage magnitudes, and line current magnitudes) depend on the grid topology, cables' parameters, voltage at the slack node, and nodal injections. They are modelled with load flow equations, that we generically denote in the following with functions f n for the voltage magnitudes and h l for line current magnitudes:

v tn = f n (P t1 , . . . , P tN , Q t1 , . . . , Q tN , v 0 , Y ) (2) i tl = h l (P t1 , . . . , P tN , Q t1 , . . . , Q tN , v 0 , Y ) , ( 3
)
where Y is the admittance matrix of the grid (built using the grid topology information and cable parameters), and v 0 is the voltage at the slack bus. Load flow equations are nonlinear and their inclusion in optimization problems determines nonconvex formulations. To increase tractability, we linearize (2) and (3) using the method proposed in [START_REF] Christakou | Efficient computation of sensitivity coefficients of node voltages and line currents in unbalanced radial electrical distribution networks[END_REF] based on sensitivity coefficients, whose performance has been investigated in [START_REF] Gupta | Performance assessment of linearized opf-based distributed real-time predictive control[END_REF], and as done in [START_REF] Sossan | Impact of the charging demand of electric vehicles on distribution grids: a comparison between autonomous and non-autonomous driving[END_REF].

C. Modelling the charging of EVs

Let v = 1, . . . , V denote the index of a vehicle, where V is the total number of vehicles. The state-of-charge of EV v is modelled as the following function:

SOC t+1,v (P EV 1v , . . . , P EV tv ) = SOC 0v + + t τ =1 η v P EV τ v + - 1 η v P EV τ v - T s E v (4)
where SOC 0v is the initial SOC, P EV tv is the EV charging power, operators [•]

+ and [•] -denote respectively the positive and negative arguments of the charging power (1 ), T s is the sampling time (in hours), E v is the nominal energy capacity of the EV's battery in kWh), and η v is the charging/discharging efficiency (possibly different across the population according to the charger model and battery status).

The charging power of vehicle v is limited by the rated power of the converter, denoted by S EV v (in kVA). We assume the capability of the charger is independent from the voltage of the AC grid and of the DC bus. The apparent power limit of the charger can be expressed as:

P EV tv 2 + Q EV tv 2 ≤ S EV v 2 (5)
where Q EV tv is the charger's reactive power. The link between the nodal injections of EVs, P (EV nodal) tn , Q (EV nodal) tn in [START_REF]National institute of statistics and economic studies[END_REF], and the charging of the single vehicles P EV tv is given by the charging location where the EVs charge. The charging location of EV v is encoded in the sequence of binary variables b 1v , b 2v , . . . , b N v , that contains a "1" in the node where the EV charges, and N-1 "0" at all other nodes. In this way, the nodal EV injections are given by:

P (EV nodal) tn = V v=1 b nv P EV tv (6) Q (EV nodal) tn = V v=1 b nv Q EV tv (7)
for all n. The N × V binary matrix b nv for all n, v can be interpreted as a map reporting the recharging spots of all EVs. It is an input to the problem.

III. GENERAL FRAMEWORK

This section describes a general formulation of the charge scheduling problem for the EVs that includes both V2G and reactive power support. The next section discusses how this formulation is modified to accommodate various scheduling strategies, which are finally compared in the results section.

The objective of this problem is determining a charging schedule for all EVs so that they can achieve a target stateof-charge while respecting grid constraints. The scheduling problem is formulated as a constrained optimization problem, whose constraints and cost function are described next. The EV chargers can possibly use reactive power and discharge the vehicles if this is conducive to improve the cost function.

For exemplifying the context, we consider a scenario where the EVs recharge overnight to achieve a target SOC level (e.g., a full recharge) necessary to meet the driving demand starting from an initial SOC value, smaller than the target SOC. The initial SOC is given by the state at which the EVs arrive at their parking (and charging) location. Both the initial SOC level and the target SOC level are inputs to the problem. They are respectively denoted by SOC 0v and SOC v .

A. Cost function

The cost function of the problem can be formulated to represent several operational objectives, such as minimizing the total charging time or minimizing the cost of electricity in a price-taking setting. Without losing generality, we choose to minimize the charging time; other cost function can be implemented too.

Let p = [P EV tv for all t, v] be a vector collecting all the charging power of all vehicles and time intervals, and p

(t) v = [P EV
1v , . . . , P EV tv ] a vector collecting the charging power from the initial time interval to t for EV v. We minimize the charging time by penalizing, for each vehicle, deviations of its state of charge from its target value, SOC v . This reads as:

J (p) = T t=1 V v=1 SOC tv p (t-1) v -SOC * v 2 , (8)
where SOC tv (•) is computed as in ( 4). The positive-and negative-part operators in (4) are non-linear and lead to a nonconvex formulation. Several linearizations are possible, e.g. splitting the charging power into mutually exclusive positive and negative terms (with binary variables, or penalization terms in the cost function) or embedding resistive losses in a virtual line, as in [START_REF] Stai | A receding horizon control approach for re-dispatching stochastic heterogeneous resources accounting for grid and battery losses[END_REF]. We opt for exclusive terms penalized in the cost function, as explained next, as it does not involve the use of binary variables.

B. Linear model of the EVs state-of-charge

Decision variable P EV tv is replaced with two new nonnegative variables:

P EV tv = P EV+ tv -P EV- tv . ∀v, t (9)
In this way, the state-of-charge can be defined as the linear expression: SOC t+1,v (P EV+ 1v , . . . , P EV+ tv , P EV- 1v , . . . , P EV-

tv ) = = SOC 0v + t τ =1 η v P EV+ vτ - 1 η v P EV- vτ T s E v . ( 10
)
As a charger can either charge or discharge an EV, the two terms in (9) should be mutually exclusive. This is achieved by augmenting the cost function in [START_REF] Knezović | Robust multi-objective pq scheduling for electric vehicles in flexible unbalanced distribution grids[END_REF] with a new term that penalizes P EV+ and P EV-. This augmented cost function reads as:

J(p + , p -) = J (p + , p -) + k T t=1 V v=1 P EV+ + P EV-, (11)
where p + = [P EV+ tv for all t, v] and p -= [P EV- tv for all t, v], the cost function J (p + , p -) follows from expressing SOC model [START_REF] Knezović | Robust multi-objective pq scheduling for electric vehicles in flexible unbalanced distribution grids[END_REF] with model [START_REF] Christakou | Efficient computation of sensitivity coefficients of node voltages and line currents in unbalanced radial electrical distribution networks[END_REF], and k is a weight. As the second term of the cost function corresponds to the SOC's model relaxation and does not have a specific physical meaning, k should be small to not significantly alter the original cost function. The impact of k on the algorithm performance and on the original problem objective is small, as shown in the results.

C. Problem constraints

The problem constraints include: state-of-charge model [START_REF] Christakou | Efficient computation of sensitivity coefficients of node voltages and line currents in unbalanced radial electrical distribution networks[END_REF] and limits (denoted by SOC and SOC); EV charger rating in [START_REF] Lopes | Integration of electric vehicles in the electric power system[END_REF]; EV charging-to-nodal injections models in ( 6)-( 7), with P EV tv given by ( 9) and grid nodal injection models in (1a), (1b); linear grid constraints, i.e., voltage lower and upper limits v, v at all nodes, cable ampacity i l of all lines l, and transformer power rating

P 2 t0 + Q 2 t0 ≤ S 2 0
. The formulations are discussed next.

D. Complete formulation

The complete problem formulation is now presented. Problem's decision variables are p + , p -and the newly defined vector q = [Q EV tv for all t, v] that collects all the reactive power injections of all chargers over time. The problem reads as:

arg min p + ,p -∈R T ×V +0 ,q∈R T ×V J(p + , p -) (12a)
subject to:

SOC model (10) ∀v, t (12b) SOC ≤ SOC tv ≤ SOC ∀t, v (12c)
P EV+ tv -P EV- tv 2 + Q EV tv 2 ≤ S EV v 2 ∀t, v (12d)
Nodal injections ( 6), ( 7), ( 9),(1a), (1b) ∀t, n, v (12e)

Linear grid models (2)-(3) ∀t, n, l (12f) v ≤ v tn ≤ v ∀t, n (12g) |i tl |≤ i l ∀t, l (12h)
P 2 t0 + Q 2 t0 ≤ S 2 0 ∀t. (12i)
IV. VEHICLE-TO-GRID, SMART-CHARGING, AND UNCOORDINATED CHARGING

A. Vehicle-to-grid problem

The optimization problem in [START_REF] Gupta | Performance assessment of linearized opf-based distributed real-time predictive control[END_REF] determines the charging schedule of all EVs so that the total charging time across the EV population is the smallest while subject to grid constraints. The decision variables are the charging power, the discharging power, and the reactive power. Although both the discharging power and the reactive power do not contribute to recharge the EVs directly (reactive power does not appear in (10)), their contribution might be useful to alleviate network congestions, ultimately allowing other EVs to recharge and improving the global charging time across the population. Problem [START_REF] Gupta | Performance assessment of linearized opf-based distributed real-time predictive control[END_REF] refers to the V2G scheduling problem with reactive power support. The reactive power support can be excluded by either forcing q to zero with equality constraints or remove the associated decision variables from the problem and constraints.

B. Smart charging problem

The smart charging problem can be derived from ( 12) by either forcing p -to zero or removing p -from the decision variables. We opt for the second way. In this case, the cost function J (•) can be dropped in favor of J(•). Both the smart charging and V2G problems are centralized, in the sense that -in order to be solved -require collecting all the information into a single optimization problem. This is due to the grid constraints that depend on all nodal injections and are therefore coupling constraints.

C. Uncoordinated charging

In uncoordinated charging, each vehicles seek to minimize its charging time regardless of the grid constraints. This simplified problem can be derived from [START_REF] Gupta | Performance assessment of linearized opf-based distributed real-time predictive control[END_REF] and reads as:

arg min p + J (p + ) (13a) subject to SOC tv = SOC t-1v + η v T S E v P (EV) tv
for all t and v (13b) 0 ≤ SOC tv ≤ 100%, for all t and v (13c)

0 ≤ P EV tv ≤ S EV v for all t and v. ( 13d
)
This problem is separable because it has no coupling constraint. In other words, solving this problem is equivalent to solving V optimization problems (one per vehicle) with local information only. The uncoordinated charging problem is used as benchmark scenario to evaluate the impact of grid constraints.

V. CASE STUDY

A. Grid

The CIGRE benchmark system for MV grids (European version) [START_REF]Benchmark systems for network integration of renewable and distributed energy resources[END_REF] is used as a case study (Fig. 1). The MV grid comprises low-voltage (LV) systems connected at the various nodes that are modelled in terms of their aggregated contributions. It is assumed that there are no grid constraint violations in the LV grids. The MV grid is modelled with a single-phase equivalent assuming a balanced grid with transposed conductors. The nodal nominal powers, the power factors, and the number of parked EVs at each node are reported in Table I. The time-varying active power demand is modeled with the load coincidence factor model defined in [START_REF]Benchmark systems for network integration of renewable and distributed energy resources[END_REF]. The reactive power demand is modeled as the product between the active power and the tangent of arc-cosine of the power factor in Table I. Line ampacities are according to the conductor diameter. Allowed voltage levels are within 1 per unit ± 3%. Computing sensitivity coefficients for the linear grid models requires nominal active and reactive nodal injections to compute the linearization, for which we use the nodal power injections of the net demand from the CIGRE specifications. The EV input data are discussed next.

B. EVs input data

The number of EVs per node is reported in Table I. It is estimated considering approx. 1.4 EVs per household 2 , where the number of households is estimated by dividing the nominal nodal power by the single-phase household contractual power (6 kVA). This results in total 878 EVs for the whole grid. These values are aligned with the existing technical literature: the work in [START_REF] Johansson | Investigation of the impact of large-scale integration of electric vehicles for a swedish distribution network[END_REF] considers 1.3 EVs per household, with number of household per node estimated as the ratio between the nominal power of each residential node and the contractual power of a household (6 kVA); work [START_REF] Leemput | Mv and lv residential grid impact of combined slow and fast charging of electric vehicles[END_REF] value inverse ( shape -0.06, scale 0.85, location 17.3), Weibull (scale 7.67, shape 21.83) and Gaussian (mean 0.49, standard deviation 0.04) distributions respectively as used in [START_REF] Andersen | Intelligent electric vehicle integration-domain interfaces and supporting informatics[END_REF], [START_REF]Test-an-EV project: Electrical Vehicle (EV) Data[END_REF]. The energy capacity of the EV batteries, and the chargers' rated power, efficiency, and power factor are assumed constant across their population and are 3.6 kVA, 0.9 and 1, respectively. The target SOC levels are also uniform across the population and assumed to be 100%.

VI. RESULTS AND DISCUSSIONS

Five cases are compared. They are:

• Case 1: uncoordinated charging (described in IV-C);

• Case 2 and Case 3: smart charging, without and with reactive power support, respectively (described in IV-B); • Case 4 and Case 5: V2G, without and with reactive power support, respectively (described in IV-A). Fig. 2 shows the nodal voltage magnitudes for Case 1. It compares the cases with simultaneous (at time 16h, top panel) and distributed arrival of the EVs (as described in V-B, bottom panel). The shades of color denote the quantile of the voltage magnitude across the nodes. In both cases, the voltage magnitudes falls below the minimum level because the uncoordinated charging does not take into account grid constraints.

In general, it can be expected that distributed arrivals of EVs induces a natural smoothing of the total charging demand because EVs arrive at different time, thus possibly "desynchronizing" their charging process. Indeed, Fig. 2 shows that, between 16 h and 17 h, there are no voltage violations in the bottom plot, whereas there are in the upper-panel plot. However, in the evening hours, violations are more severe in the bottom panel than in the upper panel (as denoted by the lower voltage magnitude nadir) because the EV charging demand overlaps with the peak hours of conventional demand (reported in [START_REF]Benchmark systems for network integration of renewable and distributed energy resources[END_REF]). The rest of this analysis is performed considering the case with arrival times distributed in time.

Fig. 3 shows the voltage levels for Case 2 -5. In all the cases, the voltage magnitudes are respected thanks to implementing grid constraints in the scheduling problem. Differences among the voltage profiles are due to handling the active and reactive power differently, as discussed next. Current constraints are also respected and omitted for a reason of space.

Fig. 4 shows the mean SOC across the EV population over time. Uncoordinated charging (Case 1) achieves the quickest recharging time. However, this comes at the price of violating grid constraints, as shown earlier. to improve system performance. The difference between the steady-state SOC values of smart charging and V2G is due to the modelling relaxation of the SOC. In particular, the cost function J(•) adopted in the V2G problem trades off achieving the target SOC with charging power, determining a steady-state SOC error. This can be reduced by decreasing the value of k in [START_REF]Benchmark systems for network integration of renewable and distributed energy resources[END_REF]. The best-performing schedulers are smart charging and V2G with reactive power support (Case 3 and Case 5). In this case too, V2G does not help to shorten charging times. To show the impact of reactive power support on the grid performance, Fig. 5 shows the voltage magnitude obtained from a (linearized) load flow that features the same active power demand of Case 3 but with the reactive power contributions from the chargers forced to zero. It is visible that voltage constraints are violated, showing that reactive power here plays an important role in keeping acceptable voltage levels in the MV feeders. The same results and conclusions were found by changing the target SOC levels to lower values (90% and 80%).

VII. CONCLUSIONS

This work compared the performance of uncoordinated charging, smart charging, V2G, and reactive power support from the chargers for EVs. The problem formulation of all the schedulers is derived from a common (convex) optimization problem accounting for (linearized) grid constraint, charging/discharging efficiency, and 4-quadrant (and 2-quadrant unidirectional) chargers, allowing for an efficient comparison among them. The performance of the schedulers is investigated considering the CIGRE system for MV grids with 878 EVs distributed at the various nodes according to the nominal nodal power. The results show that: 1) uncoordinated charging determines violations of grid constraints; 2) smart charging is effective to reduce congestions; 3) the V2G feature is never activated; and 4) reactive power support from the chargers achieves to reduce voltage congestions, ultimately leading to charge more EVs and shorten the global charging time.

Fig. 1 .

 1 Fig.1. Topology of the CIGRE European MV distribution network benchmark for residential system[START_REF]Benchmark systems for network integration of renewable and distributed energy resources[END_REF].

Fig. 3 .

 3 Fig. 3. Nodal voltage magnitudes over time for Case 2 (first panel from the top), Case 3 (second panel), Case 4 (third panel) and Case 5 (fourth panel). The dashed lines is the lower voltage limit. The shaded bands denote different quantile intervals across the nodes.

Fig. 5 .

 5 Fig. 5. Voltage magnitude computed by assuming the same active power demand as Case 3 but reactive power contribution from the EVs forced to zero.

TABLE I NODAL

 I NOMINAL DEMAND PER NODE AND NUMBER OF EVS

	Node Apparent Power Power factor Number of EVs
		[kVA]
	1	15'300	0.98	0
	2	0	0	0
	3	285	0.97	68
	4	445	0.97	106
	5	750	0.97	178
	6	565	0.97	134
	7	0	0	0
	8	605	0.97	144
	9	0	0	0
	10	490	0.97	116
	11	340	0.97	81
	12	15'300	0.98	0
	13	0	0	0
	14	215	0.97	51

  Case 1: nodal voltage magnitudes over time with arrival time at 16h for all vehicles (top panel), and with distributed arrival time (bottom panel). The dashed lines is the lower voltage limit. The shaded bands denote different quantile intervals across the nodes.

		1
	vmag (pu)	0.98					Q0.00-Q1.00 Q0.33-Q0.67 Q0.5
							V lower bound
		0.96					V upper bound
			19	21	23	25	27	29	31
				Time (hour of the day)
		1
	vmag (pu)	0.98					Q0.00-Q1.00 Q0.33-Q0.67 Q0.5
		0.96					V lower bound V upper bound
		17	19	21	23	25	27	29	31
				Time (hour of the day)
	Fig. 2.
									considers 2'340 EVs
									for a 5 MVA MV residential grid, denoting that more intense
									grid loading situations due to EVs may exist.
									Arrival times, departure times and initial SOCs of EVs are
									sampled from the following distributions: generalized extreme

  Smart charging and V2G (Case 2 and Case 4) achieves the slowest recharging time. This denotes that V2G does not conduce, in this case

		1
	SOC (pu)	0.8 0.6					V2G + reactive power V2G Smart charging + reactive power Smart charging
							Uncoordinated charging
		0.4		19	21	23	25	27	29	31
					Time (hour of the day)
	Fig. 4. Average SOC across the EVs population for different charging policies.
		1
	V mag (pu)	0.98						Q0.00-Q1.00 Q0.33-Q0.67 Q0.5
								V lower bound
								V upper bound
		0.96	17	19	21	23	25	27	29	31
					Time (hour of the day)

This project has received funding in the framework of the joint programming initiative ERA-Net Smart Energy systems' focus initiative Integrated, Regional Energy Systems, with support from the European Union's Horizon 2020 research and innovation programme under grant agreement No 775970, in the context of the EVA project.

In smart charging, the charging power is typically positive only, whereas, in V2G, it can be negative too when EVs are called to support the grid.

Except for nodes 1 and 12, which have no EVs to reduce the number of optimization variables. This approximation is deemed reasonable because these nodes are near upper grid's connection, so less critical for grid constraints violations.


Dawen Wu
email: dawen.wu@centralesupelec.fr

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

Using CNN for

Keywords: Two-player Zero-sum Game, Saddle point, Convolutional neural network, Machine learning

published or not. The documents may come

Introduction

A two-player zero-sum game or matrix game is a game, where there are only two players and one player wins whatever the other player loses. It can be reduced to a matrix form A = (a i,j ) n×m , where the number of rows and columns represent the size of the action set of the row player and column player, respectively. The row player and the column player choose a pure strategy (i, j) will get a return (a ij , -a ij ), respectively. A is the payoff function of the row player, and, -A is the payoff function of the column player.

The saddle point in a two-player zero-sum games describes a situation when two players optimize their payoff functions simultaneously. The definitions of the saddle point and its value are (x * , y * ) = arg max x arg min

y x T Ay , (1)
v * = max x min y x T Ay . (2)
The saddle point equilibrium in [START_REF] Neumann | Zur theorie der gesellschaftsspiele[END_REF] can be solved by linear programs [START_REF] Myerson | Game theory[END_REF] and [START_REF] Dixit | Games of Strategy: Fifth International Student Edition[END_REF]. The minimax Theorem [START_REF] Neumann | Zur theorie der gesellschaftsspiele[END_REF] states that the optimal objective values v in those two linear programs are equal.

(P1) max v

s.t. A T x ≥ ve m e n T x = 1, x ≥ 0, (3)
where e k is a k-dimensional vector with all elements equal to 1.

A neural network is a statistical model that can acquire predictive ability after learning from data. CNN represents a class of deep neural networks widely used in the computer vision area. A CNN model is a function [START_REF] Hauert | Game theory and physics[END_REF] with the components: model parameters θ, input A, true value v and predicted value v. The input A of a CNN model is usually a three-dimensional array with size (c, h, w), where c, h, and w represent the number of channels, the height, and the width, respectively. The output of a CNN model v is a real value or a vector representing the model's prediction. The training for the CNN model aims at minimizing the expected risk (6) w.r.t parameters θ. However, due to its inaccessibility, we usually minimize the empirical risk [START_REF] Gibbons | Game theory for applied economists[END_REF]. Our paper's objective is to use the current popular and powerful model CNN to solve two-2 player zero-sum games, i.e., the problems (1) and [START_REF] Neumann | Theory of games and economic behavior[END_REF].

f θ (A) = v (5)
L D (θ) = E D (f θ (A), v) (6)
L n (θ) = 1 n n i=1 (f θ (A i ), v i ) (7)
The rest of the paper is organized as follows. In Section 2, we give a literature review for two-player zero-sum games, CNN, the recent progressing connection between these two areas, and two regret minimization learning algorithms. In Section 3, we present our CNN method for solving two-player zero-sum games.

In Section 4, we provide the numerical results for using CNN in two aspects, computation speed and accuracy, and compare it to linear programming, and two learning algorithms. In Section 5, we sum up the paper and give directions for future works.

The notation used in the paper can be summarized as follows.

• A denotes the payoff matrix of the two-player zero-sum game.

• x and y denote a row player and column player strategies, respectively, either pure or mixed.

• n and m denote the sizes of the action set of row player and column player, respectively.

• (x * , y * ) denotes the strategy profile of the saddle point.

• v * denotes the value of the saddle point.

• f θ (•) denotes a CNN model, where θ is the model parameter.

• denotes a loss function used in training.

• D denotes a matrix game generating distribution.

Literature review

As a mathematical model of conflict and cooperation, game theory studies the situations where a set of self-motivated players act to maximize its own profit. Since the pioneering results of John von Neumann and Oskar Morgenstern [START_REF] Neumann | Zur theorie der gesellschaftsspiele[END_REF][START_REF] Neumann | Theory of games and economic behavior[END_REF], game theory has been widely developed both from theoretical and practical points of view [START_REF] Myerson | Game theory[END_REF][START_REF] Dixit | Games of Strategy: Fifth International Student Edition[END_REF][START_REF] Hauert | Game theory and physics[END_REF][START_REF] Charilas | A survey on game theory applications in wireless networks[END_REF][START_REF] Gibbons | Game theory for applied economists[END_REF]. In a two-player zero-sum context, saddle point [START_REF] Neumann | Zur theorie der gesellschaftsspiele[END_REF] states a situation where the outcome is maximum for one player and is minimum for the other. Later, in a finite multiple players general-sum context, Nash [START_REF] Nash | Equilibrium points in n-person games[END_REF] proved that there is at least one mixed strategy profile where no player can improve his/her payoff by changing his strategy unilaterally, namely Nash equilibrium.

Two-player Zero-sum games or matrix games are a basic type of game, plays a central role in game theory development. A fundamental useful mathematical theorem for zero-sum games is the Minimax Theorem [START_REF] Neumann | Zur theorie der gesellschaftsspiele[END_REF][START_REF] Fan | Minimax theorems[END_REF], which guarantees that the interchange of the orders max-min and min-max in (2) would not affect the result. Two-player Zero-sum games model many real-world situations in order to help decision-makers to take the good decisions in a competitive environment, including business [START_REF] Dixit | Investment under uncertainty[END_REF][START_REF] Luenberger | Investment science[END_REF], economics [START_REF] Bacharach | Economics and the Theory of Games[END_REF], and engineering [START_REF] Singh | Introduction to game theory and its application in electric power markets[END_REF].

Dantzig [START_REF] Dantzig | Linear programming and extensions[END_REF] shows that solving any matrix game is equivalent to a linear program. Most commercial or academic softwares such as Gurobi, CPLEX, Matlab, Scipy [START_REF] Gearhart | Comparison of open-source linear programming solvers[END_REF], provide tools for linear programming based on interior point method and simplex method [START_REF] Vanderbei | Linear programming[END_REF][START_REF] Nocedal | Numerical Optimization[END_REF]. Besides, there are also some studies on the situation where the game contain randomness [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].

CNN proposed by LeCun [START_REF] Lecun | Convolutional networks for images, speech, and time series, The handbook of brain theory and neural networks[END_REF] is a kind of Deep neural networks [START_REF] Goodfellow | Deep learning[END_REF]. As a type of Feedforward neural networks, it uses the back propagation algorithm for the training step [START_REF] Rumelhart | Learning Representations by Back-propagating Errors[END_REF]. The main characteristic of CNN is its use of shared parameter filters to scan the previous feature maps, which can significantly reduce the size of the parameter space. Since the CNN model Alexnet [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF] won the ImageNet challenge in 2012 [START_REF] Deng | Imagenet: A largescale hierarchical image database[END_REF], there a tremendous amount of research on this topic [START_REF] Li | A survey of convolutional neural networks: analysis, applications, and prospects[END_REF][START_REF] Wiatowski | A mathematical theory of deep convolutional neural networks for feature extraction[END_REF][START_REF] Zhou | Universality of deep convolutional neural networks[END_REF], and more sophisticated CNN structures [START_REF] He | Deep residual learning for image recognition[END_REF][START_REF] Huang | Densely connected convolutional networks[END_REF][START_REF] Howard | Mobilenets: Efficient convolutional neural networks for mobile vision applications[END_REF] have been proposed. CNN has applications in many fields, e.g., image classification [START_REF] Rawat | Deep convolutional neural networks for image classification: A comprehensive review[END_REF], medical image analysis [START_REF] Tajbakhsh | Convolutional neural networks for medical image analysis: Full training or fine tuning?[END_REF], video recognition [START_REF] Karpathy | Large-scale video classification with convolutional neural networks[END_REF], natural language processing [START_REF] Conneau | Very deep convolutional networks for text classification[END_REF]. It is worth noting that the problem we are dealing with in this paper has two characteristics different from most situations: regression rather than classification and varying input size. For regression, it can be viewed as a prediction of the rotation angle of the image [START_REF] Fischer | Image orientation estimation with convolutional networks[END_REF][START_REF] Mahendran | 3d pose regression using convolutional neural networks[END_REF]. For varying input size, there are three approaches for solving game problems: global pooling, variable sized pooling, and padding input images [START_REF] Yamashita | Convolutional neural networks: an overview and application in radiology[END_REF].

More recently, two-player zero-sum games built many connections with deep learning, such as Generative adversarial networks(GAN) [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], with applications in Cybersecurity [START_REF] Mahdavifar | Application of deep learning to cybersecurity: A survey[END_REF][START_REF] Yinka-Banjo | A review of generative adversarial networks and its application in cybersecurity[END_REF]. In GAN [START_REF] Goodfellow | Generative adversarial nets[END_REF], there are two neural network models, generator and discriminator, which can be viewed as two players in a zero-sum game, and the objectives of the two players are opposite. In Adversarial learning, another topic related to game theory besides GAN, the two players are the model parameter and input data, and the objective of this training is to push the neural network model to become more robust [START_REF] Chivukula | Adversarial learning games with deep learning models[END_REF][START_REF] Zhu | A robust zero-sum game framework for pool-based active learning[END_REF]. Moreover, some research work uses the zero-sum game theory framework to promote or understand machine learning algorithms [START_REF] Schuurmans | Deep learning games[END_REF][START_REF] Farnia | Do gans always have nash equilibria?[END_REF]. On the contrary, some research work uses machine learning methods to solve zero-sum games with incomplete observations [START_REF] Ling | What game are we playing? endto-end learning in normal and extensive form games[END_REF][START_REF] Ling | Large scale learning of agent rationality in two-player zero-sum games[END_REF].

A large number of learning algorithms belongs to regret minimization methods family amongst all Fictitious play (FP for short) and Exp3. These algorithms are generally used to solve stochastic games and are often used in multi-armed bandits topic, see [START_REF] Berger | Brown's original fictitious play[END_REF][START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF][START_REF] O'donoghue | Stochastic matrix games with bandit feedback[END_REF] and the references therein.

Methodology

In this section, we give a detailed presentation of our CNN model . Subsec- From the perspective of minimizing the objective function, the separated training minimizes the following empirical risk at each iteration,

The training algorithm

E N (θ) = 1 N N i=1 (f θ (A i ), v i ) , ( 8
)
where N is the number of data samples. The joint training minimizes the following empirical risk at iteration i,

E (i) (θ) = (f θ (A i ), v i ) . (9)
At each iteration, the separated training considers the same empirical risk, while the joint training considers different empirical risks.

Saddle point strategy

Although the CNN model can predict the saddle point's value after the training step, it cannot estimate the corresponding mixed strategies. Since it will be too complicated to modify the CNN model to be able to predict the mixed strategies, we compute the related mixed strategies of the predicted value by solving the following system of equations where A and v are known.

x

T Ay = v, (10)
Getting only one feasible strategy profile (x, y) is sufficient, though several feasible solutions might exist. For example, let Notice that the system (10) can be reduced to the linear systems [START_REF] Bacharach | Economics and the Theory of Games[END_REF] or [START_REF] Singh | Introduction to game theory and its application in electric power markets[END_REF], which can be solved by any linear programming solver. If the predicted value is larger than the true value, [START_REF] Bacharach | Economics and the Theory of Games[END_REF] will have a feasible solution. Otherwise, [START_REF] Singh | Introduction to game theory and its application in electric power markets[END_REF] will have a feasible solution. For [START_REF] Bacharach | Economics and the Theory of Games[END_REF], the related y is a unit vector with only one element of 1 and all other elements of 0, and the position of one is the same as the position of the maximum value in the vector A T x. Similarly, for [START_REF] Singh | Introduction to game theory and its application in electric power markets[END_REF], the position of one in the related unit vector x is the same as the position of the maximum value in the vector Ay. We only need to solve one of the linear systems in order to get the desired strategy profile. However, since the true value is unknown, it is necessary to consider both of them to get the strategy profile.

A =      1 0 0 0 1 0 0 0 1      , v = 0.7. (11)
A T x ≥ ve m x T e n = 1, x ≥ 0, (12)
Ay ≤ ve n y T e m = 1, y ≥ 0,

Pros and cons of our CNN method

We give the advantages and disadvantages of the CNN method in comparison with linear programming. The most significant advantage of the CNN method is the computational performances. That is because it directly solves the problems without using any optimization solver. However, the disadvantage is that the solution is approximate, and the model requires training time before use.

Theoretically, a predicting model should only be able to handle a given pool of game sizes and generating distributions known in advance. However, our CNN model can also deal with out of the pool game sizes and generating distributions.

Additionally, in order to compare the performances of our CNN model with existing learning algorithms from the literature, we test two algorithms, namely FP and Exp3. FP is a strategic game learning algorithm which proceeds in rounds manner. In each round, the players play a best response to mixed strategy obtained by previous rounds empirical frequencies of actions. FP was originally introduced by Brown, see [START_REF] Berger | Brown's original fictitious play[END_REF] and references therein. Exp3 is a popular adversarial multiarmed bandits algorithm suggested and studied in this setting by [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF]. Exp3 stands for Exponential-weight algorithm for Exploration and Exploitation, it is based on a list of weights for each of the actions in order to choose randomly the action to be taken next. Exp3 increases the relevant weights in case of good payoff and decreases them otherwise.

Numerical Experiments

In this section, we provide numerical results for solving zero-sum games in order to investigate the performances of our algorithms. Our CNN algorithms are implemented under the Google cloud platform for training and testing tasks.

We use an eight virtual N2D CPU, 64GB of memory, one P100 Nvidia Tesla GPU computer. We use Python 3.8 language for our codes, Gurobi for solving linear programs, Pytorch 1.7.1 as the neural network library to build up our neural network model, and CUDA 10.2 as the GPU computation platform. [START_REF] Fischer | Image orientation estimation with convolutional networks[END_REF]. Besides, we study a more complex generating procedure with two uniform distributions denoted as UU. The UU generating procedure starts with sampling two points l 1 , l 2 from U (0, 75) and U (75, 150) respectively, and a matrix game is generated by

U (l 1 , l 2 )
. Figure 4 shows the obtained saddle point value distributions. Table 1 gives

Accuracy of CNN

As for the CNN training, we use the joint one described in Algorithm 2. The structure of the CNN model is given in Table 2. We use the following setting:

•
• For the CNN model, the loss function is mean square error, and the activation function is rectified linear activation unit generally noted "leaky relu".

• For the hyperparameters, the learning rate is 0.00001. *The mixed distribution P = 0.3 * U (-10, 100) + 0.5 * N (25, 3) + 0.2 * P ois [START_REF] Fischer | Image orientation estimation with convolutional networks[END_REF]. **The mixed distribution P = 1.0 * U (-10, 100) + 1.0 * N (25, 3) + 1.0 * P ois [START_REF] Fischer | Image orientation estimation with convolutional networks[END_REF]. ***Described in section 4.1, a generating procedure with high variance.

Table 5: CNN for untrained game sizes and distributions Tables 4 and5 show that the CNN model receives an excellent predictive ability with a satisfying gap error after training. Moreover, Table 5 shows that the CNN model can even solve a matrix game from an untrained distribution and untrained game size. The difference is not significant for small game sizes since LP is efficient enough to solve small-size linear programs. When the game size is large, the advantage of CNN becomes notable. It is much faster than LP, and the gap error is relatively small. For example, for a 3000*3000 size matrix game, the CNN approach is 200 times faster than LP with a 1.36% gap loss.

Computational performances of CNN

Conclusion

In this paper, we study a two-players zero-sum games with the aim to find the saddle point for any given matrix game. We use a novel machine learning method CNN to achieve the goal and compare it with the traditional linear programming method as well as with two learning algorithms, namely FP and Exp3. We design a specific CNN structure containing a global pooling layer capable of handling varying input game sizes. Hence, we develop a complete pipeline including data generation and model fitting. We study saddle point value distributions for different matrix game generating procedures. Our numerical experiment show that the CNN method outperforms the traditional linear programming method and the two learning algorithms with a reasonable loss. Furthermore, the CNN method can take advantage of parallel computing, which provides high computing performance when solving multiple games simultaneously. Our approach can be extended to other game theory problems, namely n-player games.

(

  P2) min v s.t. Ay ≤ ve n e m T y = 1, y ≥ 0,

tion 3 .

 3 1 introduces the overall pipeline and the specific CNN model. Subsection 3.2 introduces the concrete training algorithm. Subsection 3.3 describes how to solve the corresponding saddle point strategy when the predicted saddle point value v is known. Subsection 3.4 states the advantages and disadvantages of the CNN method compared to linear programming.3.1. The CNN model A CNN model, viewed as a function (5), maps a matrix game A to the predicted saddle point value v. As shown in figure 1, the input matrix game at left-hand side goes through the CNN model to get the predicted value.

Figure 1 :

 1 Figure 1: A CNN model

Figure 2

 2 Figure 2 shows the training procedure for the CNN model. The game sizes pool and the distributions pool represent several game sizes and distributions as highlighted in red in Figure 2. A training data sample has the form (A, v),125

Figure 2 :

 2 Figure 2: The training procedure for the CNN model

Algorithm 1 : 2 A 3 v 5 return b 6 end 7 FunctionAlgorithm 2 : 5 b 6 B.append(b) 7 end 8 for t in T do 9 for 15 Function

 1235725678915 Generate one matrix game and train Input: Game size (m, n); Probability distribution P; CNN model net 1 Function Generate(m, n, P): ∼ P: sample a matrix game A with shape (m, n) from distribution P = LP (A): Find v by solving the LP 4 b = (A, v) Train(b, net): 8 net ← b: Train the CNN model by the sample b. 9 end Different hyperparameters settings can affect the performance in different ways. The learning rate is set between 10 -3 and 10 -6 in our case. In practice, we generate and use data in batches instead of just one sample. Additionally, we introduce a dedicated hyperparameter for the joint training to reuse data, namely training round, which indicates how many times a sample will be used repeatedly. Main procedure: Training for the CNN model Hyperparameters: CNN structure Net; Learning rate α; Training rounds K; Sample size N ; Iterations number T Input : Game sizes pool; Probability distributions pool Output : The CNN model Initialize : net = Net(), B = [ ] 1 Function Separated(net): 2 for n in N do 3 randomly select a game size (m, n) from the game sizes pool 4 randomly select a distribution P from the probability distributions pool = Generate(m, n, P) Joint(net): for t in T do randomly select a game size (m, n) from the game sizes pool randomly select a distribution P from the probability distributions pool b = Generate(m, n, P) for k in K do Train(b, net)

  There are infinitely many feasible strategy profiles, such as x = [1, 0, 0] T , y = [0.7, 0.1, 0.2] T and x = [1, 0, 0] T , y = [0.7, 0.2, 0.1] T .

4. 1 .

 1 Games distribution Definition 4.1 (Saddle point value distribution). Given a generating procedure, generate a number n of instances from it, and solve them to get n saddle point values 1 . A saddle point value distribution of the generating procedure is the distribution of these n values.

Figure 3 :

 3 Figure 3: Saddle point value distribution

  the four first moments of the saddle point value distributions. The first column shows the saddle point value distribution obtained from each generating procedure, e.g., U -10 * 10 represents the saddle point value distribution generated by the uniform distribution for the game size 10 * 10.

  From Normal distribution N (25, 3) (c) From Poisson distribution P (35) (d) From UU generating procedure

Figure 4 :

 4 Figure 4: Saddle point value distribution

  increases, and the distributions are sharper in figure4a, 4b, and 4c. The reducing variance will make the learning method trivial because simply setting the predicted value to the average value can get satisfying accuracy. The UU generating procedure would not occur in such a situation, and the variance remains high in larger game sizes. The generated distribution are generally symmetric and taildness as shown by the Skewness and Kurtosis values which are generally close to zero and three.

  The considered game sizes are: 10 * 10, 30 * 30, 50 * 50, 70 * 70, 100 * 100, and 200 * 200. The considered probability distributions are: U (-10, 100), N (25, 3), P

Figure 5 :

 5 Figure 5: Training Loss of the CNN model

Table 1 :

 1 Moments of saddle point value distributions

	distribution. From table 1, we can see that the variances of the distributions
	from these three generating procedures are getting smaller when the game size

Table 2 :

 2 the structure of the CNN model

Table 3 :

 3 Difference between the separated and the joint training

Table 3

 3 compares the two training options provided in Algorithm 2. We can see that the loss function of the separated training is smaller than the one in the joint training during the first 2000 iterations whilst the loss function of the joint training is smaller than the separated training counterpart when the number of Tables 4 and 5 show the model accuracy results after training. Each entry is averaged from 100 untrained test samples, which can be viewed as a test set.Table 4 presents the results for game sizes and distributions in the training candidate pool. Table 5 show the results when game sizes and generating distributions are not in the training candidate pool. For example, the game size 10 * 10 and the uniform distribution U (-10, 100) in table 4 are considered in the training candidate pool, while the game size 25 * 25 and the mixed distributions in table 5 are not.

	235
	iterations is beyond 2000. Notice that the loss function of the joint training is
	less than one after 5000 iterations.
	We use GAP as the evaluation metric for our model accuracy,
	GAP =|	True value -Predicted value Predicted value	| * 100%.	(14)

Table 4 :

 4 CNN for trained game sizes and distributions

		Mixed [0.3, 0.5, 0.2]* Mixed [1, 1, 1]**	UU generating procedure***
		Mean value Gap	Mean value Gap	Mean value Gap
	10*10	34.03	3.14%	106.42	3.23% 77.32	3.74%
	25*25	32.57	1.60%	102.83	2.32% 74.75	2.35%
	75*75	34.25	3.65%	108.12	2.91% 76.61	2.92%
	150*150 33.82	2.44%	106.80	1.66% 77.00	1.61%

Table 6

 6 compares the computational performances of CNN and LP. Each row entry representing a game size is averaged from 100 instances. It goes from a small game size 10 * 10 to a large game size 3000 * 3000, and gives the mean values of two approaches and gap error of the CNN method. We use GPU for both training and predicting phrases for the CNN model. The computational speed increases by more than 100 times for our case by utilizing GPU.

	Game sizes	LP CPU Time Value CPU Time Value Gap CNN
	10*10	0.0002	44.95 0.0011	45.70 6.79%
	50*50	0.0016	45.02 0.0011	46.47 3.15%
	100*100	0.0066	44.92 0.0011	45.32 1.06%
	500*500	0.2537	45.00 0.0013	45.58 1.27%
	1000*1000	1.3562	44.97 0.0090	45.63 1.45%
	2000*2000	6.4688	45.04 0.0341	45.63 1.27%
	3000*3000	19.2352	45.01 0.0789	45.63 1.36%

Table 6 :

 6 Comparison between LP and CNN

Table 7

 7 shows the simulation results of LP, CNN, FP and Exp3 for 1000*1000 game uniformly generated in interval [-10, 100]. We set the number of rounds for FP and Exp3 to 10000. We can see that our CNN model outperforms LP, FP and Exp3 in terms of CPU time. Notice that FP and Exp3 require a high number of rounds to provide a good approximation of the value of the game which make them less competitive for large size games. Within 10000 rounds Exp3 shows the lowest gap whilst FP requires the highest computing time.

	Algorithms	1000*1000 CPU Time Value	Gap (%)
	LP	1.3035	45.0293 -
	CNN	0.00086	45.6481 1.3553%
	FP	259.3845	47.6020 5.4043%
	Exp3	0.7100	45.0431 0.0304%

Table 7 :

 7 Comparison between LP, CNN and two learning algorithms