#  Learning Pure Nash Equilibrium in Smart Charging Games

B. Sohet and Y. Hayel and O. Beaude and A. Jeandin B. Sohet and O. Beaude and
A. Jeandin are with EDF Labs, France<EMAIL_ADDRESS>Hayel is with
LIA/CERI, Avignon University, France<EMAIL_ADDRESS>
###### Abstract

Reinforcement Learning Algorithms (RLA) are useful machine learning tools to
understand how decision makers react to signals. It is known that RLA converge
towards the pure Nash Equilibria (NE) of finite congestion games and more
generally, finite potential games. For finite congestion games, only separable
cost functions are considered. However, non-separable costs, which depend on
the choices of all players instead of only those choosing the same resource,
may be relevant in some circumstances, like in smart charging games. In this
paper, finite congestion games with non-separable costs are shown to have an
ordinal potential function, leading to the existence of an action-dependent
continuous potential function. The convergence of a synchronous RLA towards
the pure NE is then extended to this more general class of congestion games.
Finally, a smart charging game is designed for illustrating convergence of
such learning algorithms.

###### Index Terms:

Reinforcement learning, Finite congestion games, Non-separable costs, Smart
charging

##  I Introduction

Understanding how decision makers react to signals is the basement of complex
systems analysis. In such systems where decision makers are selfish and the
outcome of each individual depends on the decision of others (typically a game
theoretical framework), it is important to compute the equilibrium situation
(i.e., Nash Equilibrium, NE) but also to understand how each player will adapt
her strategy through time and therefore learn to play her Nash strategy.
Learning algorithms in game theoretical settings have been known for several
years [1]. Many techniques are based on the well known best response principle
like fictitious play [2], which assumes that players choose a best reply to
the observed empirical distribution of past actions of the other players. The
main drawback of such techniques is the computation of the best action, which
can be computationally complex and also needs specific information (utility
functions, set of actions, …). Other types of algorithms, based on
reinforcement mechanisms, have also been employed in game theoretical
problems. These types of decentralized learning techniques, based on
experiments as in repeated games, proved to be efficient in particular games
such as congestion games and more generally potential games, which have
convergence properties, as illustrated recently in machine learning community
with different feedback information [3].

Congestion games are a specific type of non-cooperative games in which the
cost of a commodity depends on the number of players choosing it [4]. Some
costs functions are said non-separable, like the energy cost for Electic
Vehicle (EV) users, when it relies on a smart dynamic pricing. This means that
the cost perceived by an individual choosing one commodity or route, depends
on the choices of all players and not only on the one choosing the same
commodity. Non-separability property is not present in standard congestion
games where cost is only due to congestion. Few papers deal with congestion
games with non-separable cost functions because of the non-existence of a
Beckmann function [5], except in particular cases [6]. Most of them focus on
the Price of Anarchy, which is a measure of the performance induced by a
decentralized system compared to centralized optimization. Learning techniques
in congestion games are not very studied because it mainly considers non-
atomic games, i.e. a population of players like an infinite number of decision
makers. In [7], the authors adapt the reinforcement learning algorithm (RLA)
described in [8] to atomic congestion games, i.e. with a finite number of
decision makers. In their adaptation of the RLA, costs functions are
separable. In this paper, this assumption is relaxed and non-separable costs
are considered, such as energy costs in smart charging games. In [14], it is
shown that an asynchronous RLA converges for ordinal potential games.

Smart charging EV is a particularly interesting environment to implement
online learning algorithms to deal with different degrees of uncertainty and
randomness of future knowledge. Most papers related to smart charging consider
machine learning techniques from a centralized point of view [9]. Deep
learning techniques are suggested in [10] to study EV charging navigation and
to minimize the total travel time and the charging cost at charging stations,
with also a centralized point of view. In [11], the NE of the constrained
energy trading game among players with incomplete information is found using a
RLA. This game however does not consider a smart charging context. In our
paper, we adapt RLA techniques to a finite smart charging game and show
convergence to a pure NE. The contributions of this paper are the following:

  * •

Proof of potentiality of an atomic congestion game with non-separable cost
functions;

  * •

Proof of RLA convergence for this game;

  * •

Application to a smart charging game and numerical example.

The paper is organized as follows: finite congestion games with non-separable
costs are introduced in Section II and an action-dependent continuous
potential is defined. This leads to convergence results of RLA in such games
in Section III. This methodology is applied to a smart charging game described
in Section IV in which numerical illustrations show its convergence. Finally
Section V concludes the paper.

##  II Potential functions in finite congestion games with non-separable costs

In the atomic game $\mathcal{G}$ considered in this work, there are $N$
players. Each player $i\in\mathcal{N}\triangleq\\{1,\dots,N\\}$ chooses her
resource $r_{i}$ among the same set $\mathcal{R}$. This set $\mathcal{R}$ of
pure strategies is made of $M$ resources, so that this game is finite. Note
that the following study applies directly to the case where each player $i$
chooses a set $\mathcal{R}_{i}\subset\mathcal{R}$ of resources. In a classical
congestion game [12], a player $i$ choosing resource $r_{i}$ would have to pay
for a cost $c_{r_{i}}\left(n_{r_{i}}(\bm{r})\right)$ which depends on the
number of players having chosen the same resource, $n_{r_{i}}(\bm{r})$,
defined as:

$\forall a\in\mathcal{R}\,,\quad
n_{a}\left(\bm{r}\right)\triangleq\\#\left\\{i\in\mathcal{N}\leavevmode\nobreak\
|\leavevmode\nobreak\ r_{i}=a\right\\}\,,$ (1)

with
$\bm{r}\triangleq\left(r_{1},\dots,r_{N}\right)=\left(r_{i},\bm{r}_{-i}\right)$
the vector of actions and $\bm{r}_{-i}$ the vector of actions of the players
other than $i$. Here, the costs are non-separable [13], meaning that the cost
$c_{a}$ of a resource $a$ does not only depend on $n_{a}$, but also on the
number of players $n_{b}$ choosing other resources
$b\in\mathcal{R}\smallsetminus\\{a\\}$. More precisely, we can prove the
existence of a potential function for specific non-separable costs:

######  Definition 1.

Linearly non-separable congestion costs $c_{a}$, for all resources
$a\in\mathcal{R}$ and vectors of actions $\bm{r}\in\mathcal{R}^{N}$, are
defined as:

$c_{a}(\bm{r})\triangleq\alpha_{a}\lambda\big{(}L\left(\bm{r}\right)\big{)}\,,$
(2) $\text{with:}\quad\begin{cases}\alpha_{a}\geq 0\,,\text{ constant,}\\\
\lambda:\mathbb{R}_{+}\rightarrow\mathbb{R}_{+}\,,\text{ an increasing
function,}\\\
L\left(\bm{r}\right)\triangleq{\sum_{i=1}^{N}\alpha_{r_{i}}=}\sum_{b\in\mathcal{R}}\alpha_{b}n_{b}(\bm{r}).\end{cases}$

Note that we chose the term “linearly” because of function $L(\cdot)$, which
is a linear combination of the number of players $n_{a}(\cdot)$ choosing each
resource $a$, while $\lambda$ may be non-linear.

######  Remark 1.

Here, the game is supposed symmetric (between the players), meaning that the
cost of a player $i$ only depends on her choice, and not on the player
herself. However, note that the following study can be extended to a non-
symmetric case where player $i$ gets the cost
$c_{i,r_{i}}\triangleq\alpha_{i,r_{i}}\lambda\left(\sum_{j=1}^{N}\alpha_{j,r_{j}}\right)$,
which is the same as (2) when $\alpha_{i,a}=\alpha_{a}$ for all $i,a$.

In this particular context of atomic congestion game with non-separable cost
functions, we are able to find potential properties for the game, which is a
powerful tool for the study of NE in pure strategy and convergence of learning
procedures [14].

###  II-A Potential function of pure strategies

Following Definition 1 of linearly non-separable congestion costs
$\left(c_{a}\right)_{a\in\mathcal{R}}$, it is possible to extend the ordinal
potential property of separable congestion games [15] to the non-separable
game
$\mathcal{G}\triangleq\left(\mathcal{N},\mathcal{R}^{N},\left(c_{a}\right)\right)$.

######  Definition 2.

An ordinal potential for game $\mathcal{G}$ is a function
$P:\mathcal{R}^{N}\rightarrow\mathbb{R}$ verifying $\forall
i\in\mathcal{N},\forall\bm{r}_{-i}\in\mathcal{R}^{N-1},\forall
a,b\in\mathcal{R}$,

$c_{a}\left(a,\bm{r}_{-i}\right)<c_{b}\left(b,\bm{r}_{-i}\right)\Leftrightarrow
P\left(a,\bm{r}_{-i}\right)<P\left(b,\bm{r}_{-i}\right)\,.$ (3)

This definition follows the idea that an ordinal potential function follows
the sign of the difference of cost for any player that changes her action
unilaterally. Even if our game $\mathcal{G}$ is not a standard congestion game
due to the non-separability of costs functions, it is possible to show the
existence of an ordinal potential function.

######  Proposition 1.

The finite non-cooperative congestion game $\mathcal{G}$ with non-separable
costs defined in (2) has the following ordinal potential function:

$\forall\bm{r}\in\mathcal{R}^{N}\,,\quad
P(\bm{r})\triangleq\lambda\left(L\left(\bm{r}\right)\right)\,.$ (4)

###### Proof.

Let $i\in\mathcal{N}$ be any player and
$a,b\in\mathcal{R},\bm{r}_{-i}\in\mathcal{R}^{N-1}$ any actions.

Firstly, note that
$L\left(a,\bm{r}_{-i}\right)=L\left(b,\bm{r}_{-i}\right)+\alpha_{a}-\alpha_{b}$,
by definition. Then, as function $\lambda$ is increasing:

$\displaystyle\lambda\big{(}L\left(a,\bm{r}_{-i}\right)\big{)}$
$\displaystyle<\lambda\big{(}L\left(b,\bm{r}_{-i}\right)\big{)}$
$\displaystyle\iff\alpha_{a}-\alpha_{b}<0\,,$ $\displaystyle\text{i.e.}\qquad
P\left(a,\bm{r}_{-i}\right)$ $\displaystyle<P\left(b,\bm{r}_{-i}\right)$
$\displaystyle\iff\alpha_{a}<\alpha_{b}\,,$

by definition of $P=\lambda\circ L$.

Secondly, function
$C_{\bm{r}}:\alpha\mapsto\alpha\times\lambda\big{(}\alpha+\sum_{j\neq
i}\alpha_{r_{j}}\big{)}$ is increasing on $\mathbb{R}_{+}$ as a product of
positive increasing functions, meaning that:

$\displaystyle\alpha_{a}\lambda\Big{(}\alpha_{a}+\sum_{j\neq
i}\alpha_{r_{j}}\Big{)}$
$\displaystyle<\alpha_{b}\lambda\Big{(}\alpha_{b}+\sum_{j\neq
i}\alpha_{r_{j}}\Big{)}$ $\displaystyle\iff\alpha_{a}<\alpha_{b}\,,$
$\displaystyle\text{i.e.}\qquad c_{a}\left(a,\bm{r}_{-i}\right)$
$\displaystyle<c_{b}\left(b,\bm{r}_{-i}\right)$
$\displaystyle\iff\alpha_{a}<\alpha_{b}\,.$

∎

The existence of a potential implies the existence of a pure NE in such non-
cooperative games, which is defined here:

######  Definition 3.

A pure strategy Nash Equilibrium (NE) of game $\mathcal{G}$ is a vector of
actions $\bm{r}^{*}\in\mathcal{R}^{N}$ which verifies:

$\forall i\in\mathcal{N}\,,\forall a\in\mathcal{R}\,,\quad
c_{r^{*}_{i}}\left(r^{*}_{i},\bm{r}^{*}_{-i}\right)\leq
c_{a}\left(a,\bm{r}^{*}_{-i}\right)\,.$ (5)

In other words, a NE is a strategy vector such that no player can reduce her
cost by changing her strategy unilaterally. Note that the existence of pure NE
is not a standard result, but it is true for games with an ordinal potential
function. Indeed, as the sets of actions are compact, the minimum of the
potential exists and corresponds to a pure NE of the game [16]. In this
particular non-separable atomic congestion game, pure NE can be fully
characterized. Let us define the set of resources
$\mathcal{R}^{+}\triangleq\\{a\in\mathcal{R}\leavevmode\nobreak\
|\leavevmode\nobreak\
\alpha_{a}>\min_{s\in\mathcal{R}}\left(\alpha_{s}\right)\\}$.

######  Proposition 2.

The NE of $\mathcal{G}$ are the $\bm{r}^{*}\in\mathcal{R}^{N}$ such that:

$\forall a\in\mathcal{R}^{+}\,,\quad n_{a}\left(\bm{r}^{*}\right)=0\,.$ (6)

###### Proof.

First, let $\bm{r}^{*}\in\mathcal{R}^{N}$ verify (6). Then, for any player
$i\in\mathcal{N}$ and any resource $a\in\mathcal{R}$,
$\alpha_{r^{*}_{i}}=\min_{s\in\mathcal{R}}\left(\alpha_{s}\right)$, by
definition of $\bm{r}^{*}$. Thus, $\alpha_{r^{*}_{i}}\leq\alpha_{a}$ and
$C_{\bm{r}^{*}}\left(\alpha_{r^{*}_{i}}\right)\leq
C_{\bm{r}^{*}}\left(\alpha_{a}\right)$, with increasing function
$C_{\bm{r}^{*}}:\alpha\mapsto\alpha\times\lambda\left(\alpha+\sum_{j\neq
i}\alpha_{r^{*}_{j}}\right)$ defined in proof of Prop. 4. This is equivalent
to $c_{r^{*}_{i}}\big{(}r^{*}_{i},\bm{r}^{*}_{-i}\big{)}\leq
c_{a}\left(a,\bm{r}^{*}_{-i}\right)$.

Secondly, let $\bm{r}^{*}\in\mathcal{R}^{N}$ be such that there exists
$a\in\mathcal{R}^{+}$ with $n_{a}(\bm{r}^{*})\geq 1$. Let $i$ be one of the
players having chosen resource $a$. Let $b\in\mathcal{R}$ be such that
$\alpha_{b}=\min_{s\in\mathcal{R}}(\alpha_{s})$. Then, $\alpha_{a}>\alpha_{b}$
by definition of $\mathcal{R}^{+}$, and
$c_{r^{*}_{i}}\left(r^{*}_{i},\bm{r}^{*}_{-i}\right)>c_{b}\left(b,\bm{r}^{*}_{-i}\right)$
using again function $C_{\bm{r}^{*}}$. ∎

This proposition shows that in games following Definition 1, pure NE
correspond to situations where all players choose the resource $a$ with the
lowest coefficient $\alpha_{a}$.

This parameter may not be known by players in advance, hence the need of
learning algorithms by players in order to optimally adapt their actions. Such
RLA are fully decentralized and are based on updates, for each player, of
probability distributions over pure strategies (called mixed strategies). It
is shown in [8] that there is a link between the potential function in pure
strategies and the one in mixed strategies for common payoff games. This
result is extended to more general games and is fundamental in order to prove
the convergence of RLA to pure NE.

###  II-B Action-dependent continuous potential

Let $\pi_{i,a}$ denote the probability with which player $i$ chooses pure
strategy $a\in\mathcal{R}$, $\bm{\pi}_{i}\in\Delta_{i}$ the mixed strategy
vector of player $i$ in a simplex $\Delta_{i}$ of $\mathbb{R}^{M}$ and
$\bm{\pi}\in\Delta=\prod_{i}\Delta_{i}$ the mixed strategies of all players.
The mixed strategy notation of player $i$ playing pure strategy $a$ is
$\bm{\pi}_{i}=\bm{e}_{a}$, with $\bm{e}_{a}$ the null vector except for the
$a$-th component, equal to 1. The expected cost $\overline{c_{i,a}}$ for
player $i$ playing pure strategy $a$ is:

$\displaystyle\overline{c_{i,a}}(\bm{\pi})\triangleq\mathbb{E}_{\bm{\pi}}\big{[}c_{a}|\pi_{i}=\bm{e}_{a}\big{]}=\sum_{\bm{r}_{-i}}\Big{(}c_{a}(a,\bm{r}_{-i})\prod_{j\neq
i}\pi_{j,r_{j}}\Big{)}\,,$ (7)

with $c_{a}$ the linearly non-separable congestion cost of (2).

Considering mixed strategies, the strategy sets are topological spaces and the
expected cost functions given in (7) are continuously differentiable. Moreover
in such continuous games, there may exist continuous potential functions,
defined in [16]: the gradient of these functions correspond to the expected
costs. This type of potential is widely considered in population games [17],
as it serves as a Lyapunov function for strategies’ dynamics, or in games with
non-atomic players [18]. In our particular setting, a generalization of these
potential functions is needed, and defined as follows:

######  Definition 4.

An action-dependent continuous potential is a $\mathcal{C}^{1}$ function $F$
over mixed strategies such that, for all resources $a\in\mathcal{R}$, there
exists a constant $\gamma_{a}$ verifying:

$\forall i,\quad\frac{\partial
F}{\partial\pi_{i,a}}(\bm{\pi})=\gamma_{a}\overline{c_{i,a}}(\bm{\pi})\,.$ (8)

Note that as expected cost are $\mathcal{C}^{1}$ functions, such potentials
$F$ are then $\mathcal{C}^{2}$ functions. Continuous potential functions
verify (8) with $\gamma_{a}=1$ for all resources $a$. Our atomic game
$\mathcal{G}$ considering continuous strategy sets of mixed strategies has an
action-dependent continuous potential function. In fact, this function is the
conditional expectation of the ordinal potential function $P$ when players
choose pure strategies according to the mixed strategy vector $\bm{\pi}$.

######  Proposition 3.

Atomic games $\mathcal{G}$ with linearly non-separable congestion costs have
the following action-dependant continuous potential function (associated to
$\gamma_{a}=\frac{1}{\alpha_{a}},\forall a$):

$F(\bm{\pi})\triangleq\mathbb{E}_{\bm{\pi}}\left[P\right]\,,$ (9)

with $P$ the ordinal potential of $\mathcal{G}$.

###### Proof.

By linearity of the expected value $\mathbb{E}_{\bm{\pi}}\left[P\right]$:

$\displaystyle F(\bm{\pi})$
$\displaystyle=\sum_{i,a}\pi_{i,a}\mathbb{E}_{\bm{\pi}}\left[P\leavevmode\nobreak\
|\leavevmode\nobreak\ \bm{\pi}_{i}=\bm{e}_{a}\right]$
$\displaystyle=\sum_{i,a}\pi_{i,a}\frac{1}{\alpha_{a}}\mathbb{E}_{\bm{\pi}}\big{[}c_{a}\leavevmode\nobreak\
|\leavevmode\nobreak\ \pi_{i}=\bm{e}_{a}\big{]}\,,$

using $c_{a}(\cdot)=\alpha_{a}\lambda(L(\cdot))=\alpha_{a}P(\cdot)$. Then, (8)
is found by differentiating by $\pi_{i,a}$, with
$\gamma_{a}=\frac{1}{\alpha_{a}}$ ($\forall i,a$). ∎

The previous proposition generalizes the particular case studied in [8] for
games with common payoff, while a similar result is obtained in [14] for
continuous potential games. The following proposition gives a more precise
result and shows that only games with particular cost functions admit an
action-dependent continuous potential function.

######  Proposition 4.

Finite games that admit a $\mathcal{C}^{2}$ action-dependant continuous
potential function correspond to finite games with cost functions defined as:

$\forall i,a,\quad c_{i,a}(\bm{r})\triangleq\beta_{a}\mu(\bm{r})\,,$ (10)

with $\beta_{a}$ any constant which depends on the action $a$, and $\mu$ any
function of pure strategies (not necessarily increasing or linearly non-
separable).

###### Proof.

Let $F$ be a $\mathcal{C}^{2}$ perturbed continuous potential function,
associated to constants $\gamma_{a}$ ($\forall a$). Then, by Definition (8) of
$F$ and according to Clairaut-Schwarz theorem (symmetry of second
derivatives):

$\forall
i,j,a,b,\quad\gamma_{a}\frac{\partial\overline{c_{i,a}}}{\partial\pi_{j,b}}=\gamma_{b}\frac{\partial\overline{c_{j,b}}}{\partial\pi_{i,a}}\,,$

which, using (7), leads to (for all mixed strategies $\bm{\pi}$):

$\sum_{\bm{r}_{-ij}}\Big{(}\prod_{k\neq
i,j}\pi_{k,r_{k}}\big{[}\gamma_{a}c_{i,a}-\gamma_{b}c_{j,b}\big{]}(a,b,\bm{r}_{-ij})\Big{)}=0\,.$

For all pure strategies $\bm{r}_{-ij}\in\mathcal{R}^{N-2}$, last equation
considered with $\bm{\pi}_{k}=\bm{e}_{r_{k}}$ ($\forall k\neq i,j$) becomes:

$\gamma_{a}c_{i,a}(a,b,\bm{r}_{-ij})=\gamma_{b}c_{j,b}(a,b,\bm{r}_{-ij})\,.$

Let $\mu=c_{i,a}$ and $\beta_{b}=\frac{\gamma_{a}}{\gamma_{b}}$ ($\forall b$).
Then, (10) is true.

Inversely, suppose a game with cost functions verifying (10). Then,
$\overline{c_{i,a}}=\beta_{a}\mathbb{E}_{\bm{\pi}}\left[\mu\leavevmode\nobreak\
|\leavevmode\nobreak\ \pi_{i}=\bm{e}_{a}\right]$, as seen in (7). Let
$F(\bm{\pi})=\mathbb{E}_{\bm{\pi}}\left[\mu\right]$. By linearity of the
expected value,
$F=\sum_{i,a}\pi_{i,a}.\mathbb{E}_{\bm{\pi}}\left[\mu\leavevmode\nobreak\
|\leavevmode\nobreak\ \bm{\pi}_{i}=\bm{e}_{a}\right]$. Therefore, (8) is
verified, with $\gamma_{a}=\beta_{a}$ ($\forall a$). ∎

This type of games is a generalization of common payoff games with action-
dependent cost.

The property of having an action-dependent continuous potential leads to
convergence of simple RLA for which only local information is accessible for
each player (basically her own perceived cost) in order to update her mixed
strategy vector and find her best action. In fact, in most cases, players are
not even aware that they are involved in a game with other players and
interact through their actions. That is why the framework of online learning
in which players make repeated decisions with a priori unknown rules and
outcomes is suitable. In the next section, a simple RLA is described, whose
convergence has already been proven when the game has a continuous potential
function. We prove that there is still convergence in a case of action-
dependent continuous potential and non-separable congestion game as in our
setting.

##  III Reinforcement learning algorithm

In our framework, players possess incomplete information: their only knowledge
is the observation of their cost after taking an action. Note that best
response algorithms can also be applied to game $\mathcal{G}$, but players
require additional information (the exact formulation of their own cost
function). Here, game $\mathcal{G}$ will be repeated so that players learn
what their best strategy is. More precisely, every iteration $n$ is split into
two phases. In the first phase, each player $i$ chooses an action
$r_{i}^{(n)}$ in accordance with her mixed strategy vector
$\bm{\pi}_{i}^{(n)}$. Thus, a vector of actions $\bm{r}^{(n)}$ is induced by
the decisions of all players, which in turn implies a cost for each player
based on the cost functions defined in (2). Then, in the second phase of the
iteration, each player updates her strategy probability vector based on the
unnoisy cost. This update mechanism is a reinforcement mechanism. This type of
RLA, used in stochastic games, is a linear reward-inaction scheme [8]. Each
player $i$ updates her mixed strategy vector $\bm{\pi}_{i}$ as follows (for
any iteration $n$):

$\bm{\pi_{i}}^{(n+1)}=\bm{\pi_{i}}^{(n)}+\delta\times\left(1-\frac{c_{i,a}(\bm{r}^{(n)})}{c_{\max}}\right)\times\left(\bm{e}_{a}-\bm{\pi_{i}}^{(n)}\right)\,,$
(11)

with:

  * •

$0<\delta<1$ the learning parameter, fixed;

  * •

$a=r_{i}^{(n)}$ the action taken by player $i$ at iteration $n$;

  * •

$c_{\text{max}}\triangleq\max_{i,a,\bm{r}}c_{i,a}(\bm{r})$.

The basic idea of the updating rule expressed by equation (11) is to ensure
that actions prompting small or high costs are promoted or not. This update
scheme is decentralized, and the global algorithm is fully distributed. This
is an important property in order to deploy it in large scale complex systems,
typically congestion games with a large number of players. The global
algorithm works as follows:

Input: $\bm{\pi}^{(0)}$, $n=0$

1 while  _not converged_ do

2 Actions $\bm{r}^{(n)}$ according to mixed strategies $\bm{\pi}^{(n)}$;

3 for  _all players $i$_ do

4 Cost $c_{i,a}\big{(}\bm{r}^{(n)}\big{)}$ at $a=r_{i}^{(n)}$ given by (2);

5 Update mixed strategy of $i$ with (11);

6

7 $n\leftarrow n+1$;

8

Algorithm 1 RLA with synchronous global updates

This algorithm converges for games having an action-dependent continuous
potential function. The updating mechanism (11) can be written as:

$\bm{\pi}^{(n+1)}=\bm{\pi}^{(n)}+\delta
G\left(\bm{\pi}^{(n)},\bm{r}^{(n)}\right)\,,$ (12)

with $G$ the updating function. Let us define function
$f(\bm{\pi})\triangleq\mathbb{E}_{\bm{\pi}}[G]$ and for any $\delta$ the
function $\Pi_{\delta}:\mathbb{R}_{+}\rightarrow\mathbb{R}$ as the piecewise-
constant interpolation of sequence $\left(\bm{\pi}^{(n)}\right)_{n}$ of mixed
strategies of all players. A direct application of Theorem 3.1 in [8]
demonstrates that our learning algorithm 1 converges weakly, as $\delta$ tends
to $0$, to the solution $\Pi$ of the following Ordinary Differential Equation
(ODE):

$\frac{dX}{dt}=f(X)\,,\quad X(0)=\bm{\pi}^{(0)}\,.$ (13)

Considering $\Pi=\left(\pi_{i,a}\right)$ and $f(\Pi)=\left(f_{i,a}\right)$,
the ODE (13) can be written element-wise as:

$\displaystyle\forall i,a,\quad\frac{d\pi_{i,a}}{dt}$ $\displaystyle=f_{i,a}=$
$\displaystyle\pi_{i,a}(1-\pi_{i,a})(1-\overline{c_{i,a}}/c_{\max})$
$\displaystyle+\sum_{b\neq
a}\pi_{i,b}(-\pi_{i,a})(1-\overline{c_{i,b}}/c_{\max})$
$\displaystyle=-\pi_{i,a}$ $\displaystyle\sum_{b\neq
a}\pi_{b}\left(\overline{c_{i,a}}-\overline{c_{i,b}}\right)/c_{\max}\,.$

Thus, the convergence points of our algorithm are related to the solutions of
a particular ODE, which must be characterized in order to prove the
convergence of the RLA to NE of game $\mathcal{G}$. In fact, next proposition
proves that having an action-dependent continuous potential implies
convergence to pure NE of our RLA described in Algorithm 1.

######  Proposition 5.

If a finite game $\mathcal{G}$ has an action-dependent continuous potential
then, for any initial non-pure strategies $\bm{\pi}^{(0)}$, function
$\Pi\triangleq\lim_{\delta\rightarrow 0}\Pi_{\delta}$ converges to a pure NE.

###### Proof.

This proof is inspired by the one of Theorem 3.3 of [8]. Here, the continuous
potential $F$ of game $\mathcal{G}$ is action-dependant and associated with
constants $\gamma_{a}$:

$\displaystyle\frac{dF}{dt}\left(\Pi\right)$
$\displaystyle=-\sum_{i\in\mathcal{N}}\sum_{k=1}^{M}\sum_{l>k}\gamma_{a_{k}}\pi_{i,a_{k}}\pi_{i,a_{l}}\frac{\left(\overline{c_{i,a_{k}}}-\overline{c_{i,a_{l}}}\right)^{2}}{c_{\max}}<0\,,$

with $\mathcal{R}=\\{a_{1},\dots,a_{M}\\}$ the set of resources. Then,
$t\mapsto F(\Pi(t))$ is non-increasing. Therefore, the RLA always converges to
a pure NE. ∎

Note that Algorithm 1 works with synchronous global updates, meaning that all
players update their strategy simultaneously at each iteration. An
asynchronous version of Algorithm 1 can be considered, where only one player
updates her strategy at each iteration. A player $i$ is chosen for iteration
$n$ with uniform probability $p_{i}\triangleq\frac{1}{N}$. The convergence of
such an asynchronous algorithm towards a pure $\varepsilon$-NE111For any
$\varepsilon\geq 0$, a pure strategy vector $\bm{r}^{*}$ is an
$\varepsilon$-Nash Equilibrium if $\forall i,a,\quad
c_{r_{i}^{*}}(\bm{r}^{*})\leq
c_{a}\left(a,\bm{r}_{-i}^{*}\right)+\varepsilon$. has been proven in [14] for
games having an ordinal potential function. This result can be applied
directly to our framework of finite congestion games with linearly non-
separable costs, as an ordinal potential function exists (see Prop. 4). In
next Section, we illustrate the convergence of both synchronous and
asynchronous RLA in a finite smart charging congestion game with linearly non-
separable costs.

##  IV A smart charging game

###  IV-A Description

Figure 1: Electrical network (with ENO its operator) containing the three
EVCS.

In this section, the synchronous reinforcement learning algorithm and its
asynchronous version are illustrated on a real-life example of a finite
congestion game with linearly non-separable costs. The players are Electric
Vehicle (EV) users who choose at which Charging Station (EVCS) they charge
their EV battery (here, the EVCS are the resources). These EVCS are part of an
electrical grid network shown in Fig. 1. For simplicity, both the EVCS and the
grid are supposed to be managed by the same Electric Network Operator (ENO).
Note that the learning algorithm of previous section can be applied to more
general grid topologies. At each electric bus $r$, there is some (fixed) power
demand $L_{r}^{0}$ corresponding to other usages than EV charging. Choices of
EV users only depend on the observed cost $c_{r}$ of their charging operation
at EVCS $r$, proportional to the charging unit price $p_{r}$. All users are
supposed to have the same charging need $\rho$ (in kWh) to simplify notations,
but this assumption (symmetric game) can be readily relaxed, in line with
Remark 1. Note that the charging operation is supposed to last exactly one
hour, at constant power (then equal to $\rho$, in kW). Thus, the charging cost
for any EV user at EVCS $r$ is $c_{r}\triangleq\rho\times p_{r}$.

In our framework, the ENO chooses charging unit prices $p_{r}$ as incentives
to reduce its global cost $H$. Here, marginal cost pricing schemes are
considered: $p_{r}\triangleq\partial H/\partial L_{r}$ with $L_{r}\triangleq
L^{0}_{r}+n_{r}(\bm{r})\rho$ the total power demand at EVCS $r$. The ENO
global cost $H$ is defined as the cost of the electricity generation needed to
fulfill the total power need $\bm{\mathcal{L}}\triangleq(L_{r})_{r}$ in the
grid network considered. Typically, this cost is a quadratic function [19] of
the (apparent) power $S_{0}$ at the head of the grid:

$H(\bm{\mathcal{L}})\triangleq\eta S_{0}^{2}(\bm{\mathcal{L}})\,,$ (14)

with $\eta$ a scaling constant. This power can be obtained by running a Power
Flow algorithm, more precisely the Bus Injection Model [20]. This algorithm
solves the power balance equation at each bus (between the given power
production/load $S_{0,k}$ at bus $k$ and power flows $S_{k}$ from/to the bus):

$S_{0,k}=U_{k}\sum_{m\in
X_{k}}\overline{Y_{k,m}}\overline{U_{m}}\leavevmode\nobreak\ (\triangleq
S_{k})\,,$ (15)

with $U_{k}$ the complex voltage at bus $k$, $X_{k}$ the set of buses
connected to bus $k$ and $Y_{k,m}$ the admittance of the line between buses
$k$ and $m$.

The charging unit price $p_{r}=\partial H/\partial L_{r}(\bm{\mathcal{L}})$ at
EVCS $r$ is not necessarily a function of a linear combination of the action
vector $\bm{r}$ as in (2), due to the complexity of power flow equations (15).
Therefore, the grid is reduced to only the transformer bus $d$, as if all the
power demand came from it, and the grid topology is replaced by constants
$\bm{\tilde{\alpha}}\triangleq(\tilde{\alpha}_{r})$:

$\vspace{-1mm}\frac{\partial H}{\partial
L_{r}}(\bm{\mathcal{L}})\simeq\frac{\partial H}{\partial
L_{r}}(\bm{\tilde{\mathcal{L}}})\Big{(}=\tilde{\alpha}_{r}\frac{\partial
H}{\partial L_{d}}(\bm{\tilde{\mathcal{L}}})\Big{)}\,,\leavevmode\nobreak\
\text{ with}$ (16)
$\bm{\mathcal{L}}\triangleq(L_{a}\,,L_{b}\,,L_{c}\,,0)\leavevmode\nobreak\
\text{ and }\leavevmode\nobreak\
\bm{\tilde{\mathcal{L}}}\triangleq(0\,,0\,,0\,,\sum_{r}\tilde{\alpha}_{r}L_{r})\,.\vspace{-2mm}$

The meaning of constant $\tilde{\alpha}_{r}$ is that a power demand $L_{r}$ at
EVCS $r$ is equivalent (i.e., yields equal marginal costs) to a power demand
$\tilde{\alpha}_{r}L_{r}$ at the transformer bus $d$. Coefficients
$\bm{\tilde{\alpha}}$ are obtained by solving the following square
minimization:

$\bm{\tilde{\alpha}}\triangleq\operatorname*{arg\,min}_{\bm{\alpha}>0}\int_{0}^{L^{\text{max}}}\Big{[}\frac{\partial
H}{\partial L_{a}}\left(L^{0}_{a}+L_{a}\,,L^{0}_{b}\,,L^{0}_{c}\,,0\right)$
(17) $-\alpha_{a}\frac{\partial H}{\partial
L_{d}}\Big{(}\sum_{r}\alpha_{r}L^{0}_{r}+\alpha_{a}L_{a}\Big{)}\Big{]}^{2}\text{d}L_{a}+\int(b)+\int(c)\,,$

where $\int(b)+\int(c)$ means that the first integral in (17) is repeated for
EVCS $b$ and $c$.

Then, charging unit prices $p_{r}\triangleq\tilde{\alpha}_{r}\partial
H/\partial L_{d}(\bm{\tilde{\mathcal{L}}})$ lead to the following charging
cost $c_{r}$ for EV users choosing EVCS $r$:

$c_{r}=\rho\times\tilde{\alpha}_{r}\frac{\partial H}{\partial
L_{d}}\left(\sum_{s}\rho\tilde{\alpha}_{s}n_{s}(\bm{r})+\sum_{s}\tilde{\alpha}_{s}L_{s}^{0}\right)\,.$
(18)

This cost function verifies Definition 1 with
$\alpha_{r}\triangleq\rho\tilde{\alpha}_{r}$ and $\lambda\triangleq\partial
H/\partial L_{d}$, an increasing function of
$L(\bm{r})=\sum_{s}\rho\tilde{\alpha}_{s}n_{s}(\bm{r})$.

###  IV-B Numerical illustrations

The parameters of the smart charging game are set as follows: a typical French
20kV electrical network has around 1500 customers, with a standard 6kVA
contract power. The total number of EV users is set to $N=1500$ and the energy
need is $\rho=3$kWh, half of the daily mean individual EV consumption in
France222Enquete Nationale Transports et Deplacements:
https://utp.fr/system/files/Publications/UTP_NoteInfo1103_Enseignements_ENTD2008.pdf
(in French).. Based on bus lines characteristics and the grid network topology
considered in Fig. 1, for each EVCS $r$, linear coefficients
$\tilde{\alpha}_{r}$ are obtained solving the square minimization problem (17)
: $\tilde{\alpha}_{a}=1.12$, $\tilde{\alpha}_{b}=1.07$ and
$\tilde{\alpha}_{c}=1.18$. Note that EVCS $a$ and $c$ have a greater impact on
ENO global cost $H$ than EVCS $b$ because they are further away from the
transformer (see Fig. 1). The ENO global cost $H$ is adjusted with
$\eta=5.10^{-3}$ (€/MVA2) so that charging unit prices $p_{r}$ remain between
10 and 20c€/kWh. Regarding learning characteristics, the learning parameter is
set to $\delta=0.5$ and the initial mixed strategies are equally distributed
among resources: $\pi_{i,r}=1/3$ for all users $i$ and EVCS $r=a,b,c$.
Similarly, for the asynchronous version of Algorithm 1, each player $i$ is
chosen with a probability $p_{i}=1/N$ for the update phase.

Figure 2: Evolution of mixed strategies $\bm{\pi}_{i}$ (of only 50 users)
throughout iterations of Algorithm 1. Thicker lines represent the average
(over all users) mixed strategy.

Figures 2 and 3 show the evolution of mixed strategies $\bm{\pi}_{i}$ (of only
50 users, for visibility) throughout iterations respectively for the
synchronous Algorithm 1 and for the asynchronous version. As mentioned in
Section II-A, although the pure NE of this game (all users choosing EVCS with
lowest impact on grid costs) may seem trivial, EV users need hundreds of
iterations to learn it (see Fig.2), as they have no information on the grid
topology. Considering thicker lines (average mixed strategy over all users),
it can be seen that, while the synchronous algorithm converges in less than
500 iterations (Fig. 2), it takes more than thousand times as many iterations
for the asynchronous one (Fig. 3). This is understandable since in the
asynchronous version, only one player updates her strategy at each iteration,
instead of all players like in the original Algorithm 1. This also explains
why larger number of players lead to slower convergence for the asynchronous
version, while it has no effect on the original Algorithm 1. Note that the
evolution of mixed strategies may slightly vary from one execution to another
(of either algorithm), due to actions randomly chosen from mixed strategies.
Similarly, the number of iterations until convergence depends on the initial
mixed strategies $\bm{\pi}^{(0)}$ and decreases with the learning parameter
$\delta$.

##  V Conclusions and perspectives

In this paper, a reinforcement learning algorithm (RLA) has been applied to
obtain in a fully decentralized manner a pure Nash equilibrium (NE) for a
finite congestion game with non-separable cost functions. Non-separability of
cost functions makes it difficult to prove the existence of pure NE and the
convergence property of RLA in such particular congestion games. When cost
functions are separable, all these results come from the existence of an exact
potential. However, assuming costs are linearly non-separable, we are able to
prove the existence of an ordinal potential function, which can serve as a
Lyapunov function for proving the convergence of simple RLA. Moreover, these
results were applied to a smart charging game in which EV users choose
selfishly a charging station depending on the smart charging price, which is
based on a Power flow solution of the impact of EV charging on the grid. In a
future work, a rationality coefficient for players will be added to the RLA.

Figure 3: Evolution of mixed strategies $\bm{\pi}_{i}$ (of only 50 users)
throughout iterations of asynchronous version of Algorithm 1

## References

  * [1] D. Fudenberg and D. Levine, “The Theory of Learning in Games”, Series on Economic Learning and Social Evolution, vol. 2. MIT Press, Cambridge, MA, 1998.
  * [2] G. Brown, “Iterative solution of games by fictitious play”, Activity Analysis of Production and Allocation, vol. 13. John Wiley & Sons, Inc., New York, pp. 374–376, 1951.
  * [3] J. Cohen, A. Heliou and P. Mertikopoulos, “Learning with Bandit Feedback in Potential Games”, Proceedings of NIPS, 2017.
  * [4] N. Nisan, T. Roughgarden, E. Tardos, and V.Vazirani, Algorithmic Game Theory, Cambridge University Press, 2007.
  * [5] M. J. Beckmann, C. B. McGuire, and C. B. Winsten, Studies in the Economics of Transportation, Yale University Press, 1956
  * [6] B. Sohet, O. Beaude, Y. Hayel and A. Jeandin, “Coupled charging and driving incentives design for electric vehicles in urban networks,” unpublished, arXiv:2001.11758, 2020.
  * [7] D. Barth, J. Cohen, O. Bournez and O. Boussaton, “Distributed learning of equilibria in a routing game”, Parallel Processing Letters, vol. 19, num. 02, pp. 189-204, 2009.
  * [8] PS Sastry, VV Phansalkar and M. Thathachar, “Decentralized learning of Nash equilibria in multi-person stochastic games with incomplete information”, IEEE Trans. on systems, man, and cybernetics, vol. 24 (5), pp. 769-777, 1994.
  * [9] W. Tang, S. Bi and Y. J. Zhang, “Online Charging Scheduling Algorithms of Electric Vehicles in Smart Grid: An Overview”, IEEE Communications Magazine, vol. 54, no. 12, pp. 76-83, 2016.
  * [10] T. Qian, C. Shao, X. Wang and M. Shahidehpour, “Deep Reinforcement Learning for EV Charging Navigation by Coordinating Smart Grid and Intelligent Transportation System”, IEEE Trans. on Smart Grid, vol. 11, no. 2, pp. 1714-1723, March 2020.
  * [11] H. W. Wang, T. W. Huang, X. F. Liao, H. Abu-Rub and G. Chen, “Reinforcement learning for constrained energy games with incomplete information”, IEEE Trans. on Cybernetics, vol. 47(10) 2017.
  * [12] R. Rosenthal, “A Class of Games Possessing Pure-Strategy Nash Equilibria”, International Journal of Game Theory, vol. 2, 1973.
  * [13] C. Chau and K. Sim, “The price of anarchy for non-atomic congestion games with symmetric cost maps and elastic demands”, Operations Research Letters, vol. 31, 2003.
  * [14] O. Bournez and C. Johanne, “Learning equilibria in games by stochastic distributed algorithms”, Computer and information sciences III, Springer, London, 31-38, 2013.
  * [15] I. Milchtaich, “Congestion Games with Player-Specific Payoff Functions”, Games and Economic Behavior, vol. 13, pp. 111–124, 1996.
  * [16] D. Monderer and L. Shapley, “Potential Games”, Games and Economic Behavior, vol. 14, pp. 124-143, 1996.
  * [17] W.H. Sandholm, “Potential games with continuous player sets”, Journal of Economic Theory, 97(1):81-108, 2001.
  * [18] M. Cheung and R. Lhakar, “Nonatomic potential games: the continuous strategy case”, Games and Economic Behavior, vol. 108, 2018.
  * [19] A. H. Mohsenian-Rad, V. W. Wong, J. Jatskevich, R. Schober and A. Leon-Garcia, “Autonomous demand-side management based on game-theoretic energy consumption scheduling for the future smart grid”, IEEE Trans. on Smart Grid, 1.3, 320-331, 2010.
  * [20] J. Hu, Optimization of power system operation, J.Wiley & Sons, 2015