# An Efficient and Incentive-Compatible Mechanism for Energy Storage Markets

Bharadwaj Satchidanandan and Munther A. Dahleh

###### Abstract

A key obstacle to increasing renewable energy penetration in the power grid is
the lack of utility-scale storage capacity. Transportation electrification has
the potential to overcome this obstacle since Electric Vehicles (EVs) that are
not in transit can provide battery storage as a service to the grid. This is
referred to as EV-Power grid integration, and could potentially be a key
milestone in the pathway to decarbonize the electricity and the transportation
sectors. We first show that if EV-Power grid integration is not done
carefully, then contrary to improving the cost efficiency of operating the
grid, it could in fact be counterproductive to it. This fundamentally occurs
due to two phenomena operating in tandem – the randomness of EV usage patterns
and the possibility of strategic behavior by EV operators. We present a
market-based solution to address this issue. Specifically, we develop a
mechanism for energy storage markets using which the system operator can
efficiently integrate a fleet of strategic EVs with random usage patterns into
the grid, utilize them for storage, and satisfy the demand at minimum possible
cost.

###### Index Terms:

Storage markets, Electric Vehicles, Stochastic deadlines, Incentive compatible
mechanism.

##  I Introduction

A major impediment to high renewable energy penetration in the power grid is
the scarcity of energy storage capacity in the grid. Utility-scale battery
storage is expensive at current technology, and so any energy that is
generated must be consumed immediately. This paradigm could change
substantially with increased Electric Vehicle (EV) penetration since EVs that
are not in transit can provide battery storage as a service to the grid. Prior
studies estimate that on an average, a car is parked for more than $95\%$ of
the time [1], indicating the huge potential for EVs to double as energy
storage resources in the grid. As an illustration, take the example of the
state of Massachusetts. It consumes an average of $146$GWh of electric energy
per day [2]. On the other hand, the battery capacity of a Tesla Model S EV is
about $100$kWh. This implies that about $1.4$ million EVs possess enough
battery capacity to power Massachusetts for an entire day. This amounts to
less than $64\%$ of the vehicles registered in Massachusetts today [3]. The
situation is similar in most other parts of the US and the world, indicating
that even moderate levels of EV penetration could provide significant storage
capacity.

The time periods during which an EV can lease its battery to the grid are
private knowledge of the EV operator. In particular, it is unknown to the
Independent System Operator (ISO). However, the ISO requires this information
to optimally operate the grid, or more precisely, to determine the optimal
power dispatch of the generators and the optimal storage schedule of the EVs.
Consequently, the ISO requests the EV operators to report to it in the day-
ahead market the time periods during which they can lease their battery the
following day. However, this brings forth two challenges that need to be
addressed.

The first challenge is that the travel times of people are in general random,
and so the EV operators may not precisely know in the day-ahead market the
time periods during which they can lease their batteries the following day.
Rather, they may know these time periods only with some uncertainty. To
account for this, we model the time periods during which an EV can lease its
battery as a random variable, and require that the EV operators only report
the probability distribution of this random variable in the day-ahead market.

The second challenge is that the EV operators could be strategic, and so they
may not report the aforementioned probability distribution truthfully. As we
elaborate in Section III, each EV operator has associated with it a utility
function, and the EV operators bid strategically so as to maximize their
respective utilities. Moreover, having bid some probability distribution in
the day-ahead market, an EV may not remain connected to the grid until its
deadline the following day if there is possibility for it to obtain a higher
utility by doing so than by disconnecting at its deadline. Such behavior could
potentially be counterproductive to the cost- and energy-efficient operation
of the grid. The following example illustrates this issue.

######  Example 1.

Suppose that a day consists of two time periods, and suppose that the demand
sequence $\mathbf{d}$ of the load in these time periods is
$\mathbf{d}=\\{0,1\\}.$ Let the production function $c^{g}$ of the generator
be such that $c^{g}(\\{1,0\\})=0$ and $c^{g}(\\{0,1\\})=2.$ That is, it costs
the generator $0$ to produce $1\mathrm{J}$ of energy at time period $1$ and
$0\mathrm{J}$ of energy at time period $2$, and so on. The cost $c^{g}$ for
all other $2$-tuples is infinite. We suppose that this generator has a low
ramping rate – a characteristic that is typical of high-efficiency generators
– and so its power dispatch must be scheduled well in advance of the time of
power delivery. Specifically, its power dispatch must be scheduled in the day-
ahead market.

The system also consists of a reserve generator which has a high ramping rate
which can produce and sell energy in the spot market to balance real-time
demand-supply mismatches. Let the production function $c^{s}$ of the reserves
be such that $c^{s}(\\{0,0\\})=0$ and $c^{s}(\\{0,1\\})=11.$ The cost $c^{s}$
for all other $2$-tuples is infinite.

Suppose that there is only one EV in the system with a battery capacity of
$1\mathrm{J}$. As we elaborate in Section III, the usage pattern of an EV on
any given day is specified by a quantity known as its “deadline” on that day.
An EV’s deadline on a given day is defined as the time period until which the
EV can lease its battery to the grid on that day. Then, the usage pattern of
an EV being random is equivalent to its deadline being random. Suppose that
the EV’s deadline takes the value $1$ with probability $p$ and the value $2$
with probability $1-p$.

As elaborated in Section III, each EV has a cost function associated with it.
Suppose that the cost incurred by an EV is equal to the negative of the net
energy injected into it during the time that it is connected to the grid.

Now, the ISO is confronted with two options to meet the demand. The first
option is for it to schedule the generator to produce the energy sequence
$\mathbf{g}=\\{0,1\\}$ and use it to serve the load. This results in a total
cost of meeting the demand — defined as the sum of the costs incurred by the
generator, the EV, and the reserves — to be equal to $2$.

The second option is to schedule the generator to produce the energy sequence
$\mathbf{g}=\\{1,0\\}$ and store the energy generated in the first time step
in the EV. If the EV remains connected to the grid in the second time step,
then the ISO discharges it to satisfy the demand, resulting in a total cost of
$0$. On the other hand, if the EV disconnects at time step $1$, then the ISO
purchases $1\mathrm{J}$ in the spot market at time step $2$ at cost
$c^{s}(\\{0,1\\})=11$ to satisfy the demand, thereby resulting in a total cost
of $10$. Hence, if the EV disconnects at its true deadline, then the total
cost of meeting the demand equals $0$ with probability $1-p$ and equals $10$
with probability $p$. Hence, the total expected cost of meeting the demand if
the ISO decides on the second option is equal to $10p$.

Now, the goal of the ISO, as we elaborate in Section III, is to minimize the
total expected cost of meeting the demand, and so it must choose the first
option if $2\leq 10p$ and the second option if $2>10p.$ However, the
difficulty is that the ISO does not know the value of $p,$ and must rely only
on the value $\widehat{p}$ reported by the EV in the day-ahead market in order
to make the decision. The EV bidding $\widehat{p}=p$ is not a dominant
strategy. To see this, suppose that $p=0.21.$ If the EV bids
$\widehat{p}=0.21,$ then the ISO would decide on the first option, and so the
cost incurred by the EV would be equal to $0.$ On the other hand, if the EV
bids $\widehat{p}=0.19,$ then that causes the ISO to decide on the second
option, thereby resulting in the EV being charged with $1\mathrm{J}$ in the
first time step. If the EV then disconnects at its deadline, then it would
exit the system with a charge of $1\mathrm{J}$ with probability $0.21$ and a
charge of $0\mathrm{J}$ with probability $0.79.$ This would result in it
incurring an average cost of $-0.21$, which is lesser than the average cost of
$0$ that it would incur if it bids $p$ truthfully. However, the total expected
cost of meeting the demand as a result of the EV’s false bid is equal to
$2.1,$ which is greater than the total cost of $2$ that would result if the
ISO simply decides to never utilize the EV for storage.

The above example illustrates a scenario wherein the EV can lower its average
cost by misreporting only its deadline distribution. However, the EV could
also misreport its deadline realization to lower its cost. To see this,
consider the case when $p=0.19$ and suppose that the EV reports
$\widehat{p}=p$ truthfully in the day-ahead market. It follows from the above
discussion that the ISO would decide on the second option. Now, if the EV
reports its deadline truthfully in real time, then the expected cost that it
would incur is equal to $-0.19$. On the other hand, by misreporting its
deadline realization to be equal to time step $1$, the EV can exit the system
with $1\mathrm{J}$ of charge, thereby resulting in it incurring a lower cost
of $-1$. Since the ISO is not privy to the EV’s deadline realization, it
cannot ascertain if the EV disconnects at the first time step due to its
deadline arriving at that time or due to strategic behavior. The total
expected cost of meeting the demand as a result of the EV’s false report would
equal $10,$ which is greater than both the total expected cost of $1.9$ that
would result if the EV reports its deadline realization truthfully, and also
the total cost of $2$ that would result if the ISO simply decides to never
utilize the EV for storage.

The above example illustrates how strategic EV behavior not only defeats the
purpose of utilizing EVs as energy storage units, but could also be
counterproductive to the cost- and energy-efficient operation of the grid
since it could potentially result in real-time supply shortages which in turn
increases the ISO’s dependence on the expensive and energy-inefficient
reserves. Therefore, if EVs are to be efficiently integrated for storage, it
is imperative to devise incentive structures that drive EV operators towards
truthful behaviors. Specifically, it is necessary to devise mechanisms that
(i) incentivize the EVs report the probability distribution of their usage
patterns truthfully in the day-ahead market, so that the ISO can optimally
plan the power dispatch and storage schedules, and (ii) incentivize the EVs to
remain plugged into the grid until their actual deadlines, so that there are
no untoward supply shortages in real time. In this paper, we present a
mechanism that achieves both of these objectives.

At a high level, the mechanism consists of a decision rule that specifies an
optimal power dispatch sequence of the generator and an optimal energy storage
policy for each EV as a function of the deadline distributions that the EVs
report in the day-ahead market, and a payment rule that incentivizes EVs to
report their deadline distributions _and_ deadline realizations truthfully.
The payment rule consists of two components — (i) a “day-ahead payment” that
reflects the expected cost savings in operating the grid due to the storage
opportunity that the EVs are expected to provide as per their reported
deadline distributions, and (ii) a carefully designed “end-of-the-day
settlement” that adjusts the transfers meted out to each EV based on a
comparison of what it had reported in the day-ahead market and the actual
departure profiles of the EVs in real time. One of the functionalities of the
end-of-the-day settlement is to penalize EVs for deviations of their
empirically observed behavioral patterns from what is expected as per the
probability distributions that they report in the day-ahead market. We show
how the composite payment rule renders truthful bidding in both the day-ahead
market and in real time a dominant strategy for every EV, thereby enabling the
ISO to satisfy the demand at minimum possible cost. To the best of our
knowledge, we are unaware of any other work that addresses the problem of
integrating a fleet of _strategic_ EVs with _random usage patterns_ into the
grid, encompassing both engineering and economic aspects of the composite
system.

Notation: Given a vector $\mathbf{x},$ we denote by $x(i)$ the $i^{th}$
component of $\mathbf{x}.$ Given a vector $\mathbf{x}(\boldsymbol{\theta})$
which is a function of the variable $\boldsymbol{\theta}$, we denote its
$i^{th}$ component by $x(i;\boldsymbol{\theta})$. Given a vector $\mathbf{x},$
we denote by $\mathbf{x}_{-i}$ the vector $\mathbf{x}$ with its $i^{th}$
component removed, and by $[y,\mathbf{x}_{-i}]$ the vector whose $i^{th}$
component is $y$ and the other components are $\mathbf{x}_{-i}.$ Given a
sequence $\\{\mathbf{x}(1),\mathbf{x}(2),\ldots\\},$ we use $\mathbf{x}^{l}$
to denote the $l-$length sequence $\\{\mathbf{x}(1),\ldots,\mathbf{x}(l)\\},$
and $\mathbf{x}^{\infty}$ to denote the entire sequence. We occasionally use
$[x_{i}^{\infty},\mathbf{x}_{-i}^{\infty}]$ to denote $\mathbf{x}^{\infty}$,
especially when it is necessary to draw attention to the $i^{th}$ component of
the vectors. We denote by $\mathds{1}_{\\{\mathrm{Statement}\\}}$ the
indicator function that takes the value $1$ if $\mathrm{Statement}$ is true
and takes the value $0$ otherwise.

##  II Related Work

Technologies that utilize EVs as energy storage resources are broadly referred
to as vehicle-to-grid technologies, and a large body of literature exists on
this topic. Reference [4] provides a feasibility study of vehicle-to-grid
systems. Reference [5] presents a framework for vehicle-to-grid
implementation. Among other aspects, it recognizes the need for incentive
mechanisms to ensure adequate participation of EV operators. Mechanisms to
elicit private valuations of EVs under a variety of settings and to achieve
various objectives are presented in [6, 7, 8, 9, 10, 11] among many other
papers. However, most of the existing literature fail to model at least one,
if not all, of the following aspects of EVs: (i) the heterogeneity of EV
deadlines, (ii) the stochasticity of EV deadlines, (iii) the storage
opportunity provided by EVs, and (iv) the possibility of strategic behavior by
EV operators. The concoction of aspects (ii) and (iv) demands particular
attention since the stochastic nature of EV deadlines provides EVs significant
leeway for strategic behavior since the grid operator cannot ascertain whether
an EV’s departure at any given time on any given day is a consequence of its
deadline arrival or is a consequence of strategic behavior. In this paper, we
model all of the aforementioned aspects in a holistic framework and address
them thoroughly.

##  III Problem Formulation

Consider a power system with a single generator, a single load, and $n_{s}$
storage units or EVs. In addition to EVs, the storage units could also include
devices such as Powerwalls [12] that individual households and firms could
have installed. We divide time into days, and divide a day into $T$ time
intervals. Denote by $d_{l}(t)$ the energy demand of the load on the $l^{th}$
day at time $t,$ $l\in\mathbb{Z}_{+}$ and $t\in\\{1,\ldots,T\\}.$ The demand
sequence $\mathbf{d}_{l}\coloneqq\big{[}d_{l}(1),\ldots,d_{l}(T)\big{]}$ is a
random variable and can typically be forecast in the day-ahead market to an
accuracy of within $5\%$ [13]. However, in order to minimize clutter and
expose the main ideas clearly, we assume that it is known exactly in the day-
ahead market, and furthermore, that it remains the same on all days.
Consequently, we drop the subscript $l$ and denote the demand sequence simply
as $\mathbf{d}=[d(1),\ldots,d(T)].$ We describe in Section VI how this
assumption can be relaxed.

###  III-A EV Deadlines

On any day $l,$ $l\in\mathbb{Z}_{+},$ the time intervals in which an EV $i$
can lease its battery to the grid are characterized by a parameter
$\delta_{i}(l)\in\\{1,\ldots,T\\}$ called EV $i$’s “deadline” on day $l.$ An
EV $i$ on day $l$ is said to have deadline $\delta_{i}(l)$ if it can lease its
battery to the grid at all times lesser than or equal to $\delta_{i}(l)$ and
incurs a large cost for remaining connected beyond time $\delta_{i}(l)$.

####  III-A1 Deadline distributions

The deadline $\delta_{i}(l)$ is modeled as a random variable, and we suppose
that the deadline sequence $\\{\delta_{i}(1),\delta_{i}(2),\ldots,\\}$ is
Independent and Identically Distributed (IID). Since $\delta_{i}(1)$ takes
values from the set $\\{1,\ldots,T\\}$, the set of distributions that it can
assume is parameterized by the $\mathbb{R}^{T}$\- dimensional probability
simplex $\overline{\Theta}$. We denote by $\theta_{i}\in\overline{\Theta}$ the
parameter vector corresponding to EV $i$’s deadline distribution, and by
$\mathbb{P}_{\theta_{i}}$ the probability distribution of the deadline. That
is, for any $t\in\\{1,\ldots,T\\},$ the quantity $\mathbb{P}_{\theta_{i}}(t)$
denotes the probability that $\delta_{i}(1)$ equals $t.$

While in general, $\theta_{i}$ could take any value in $\overline{\Theta},$ we
assume for certain technical reasons that there exists $\epsilon_{\theta}>0$
such that for all $i\in\\{1,\ldots,n_{s}\\}$ and for all
$t\in\\{1,\ldots,T\\},$ $\mathbb{P}_{\theta_{i}}(t)\geq\epsilon_{\theta}.$
Consequently, given $\epsilon_{\theta},$ we define the set

$\displaystyle\Theta\coloneqq\\{\theta\in\overline{\Theta}\mathrel{\mathop{\mathchar
58\relax}}\mathbb{P}_{\theta}(t)\geq\epsilon_{\theta}\;\;\mathrm{for\;all}\;\;t\in\\{1,\ldots,T\\}\\},$

so that for all $i\in\\{1,\ldots,n_{s}\\},$

$\displaystyle\theta_{i}\in\Theta.$ (1)

We assume that the deadlines of different EVs are independent random variables
so that the joint distribution of the EVs’ deadlines on any given day is the
product distribution
$\mathbb{P}_{\theta_{1}}\times\ldots\times\mathbb{P}_{\theta_{n_{s}}}.$ We
define $\boldsymbol{\theta}\coloneqq[\theta_{1},\ldots,\theta_{n_{s}}].$

####  III-A2 Deadline realizations

We suppose that for every $i\in\\{1,\ldots,n_{s}\\}$ and every
$l\in\mathbb{Z}_{+},$ the realization of $\delta_{i}(l)$ is drawn “by nature”
at the beginning of day $l$ according to $\mathbb{P}_{\theta_{i}}$ and is
revealed to EV $i$ at the beginning of day $l.$ In particular, the realization
of $\delta_{i}(l)$ is unknown in the day-ahead market corresponding to day
$l.$ The details of the day-ahead market are described in later subsections.

###  III-B Cost functions

We denote by $c^{g}\mathrel{\mathop{\mathchar 58\relax}}\mathbb{R}_{\geq
0}^{T}\to\mathbb{R}$ the production function of the generator so that
$c^{g}(\mathbf{g})$ is the cost incurred by the generator for producing the
energy sequence $\mathbf{g}=\big{[}g(1),\ldots,g(T)\big{]}$ on any given day,
where $g(t)$ denotes the amount of energy produced at time $t$.

Demand-supply mismatches that occur in real-time are typically compensated by
the ISO by purchasing additional energy in the spot market. We denote by
$c^{s}\mathrel{\mathop{\mathchar 58\relax}}\mathbb{R}^{T}\to\mathbb{R}$ the
production function of the reserves so that $c^{s}(\mathbf{g}_{s})$ is the
cost incurred by it if it produces the energy sequence
$\mathbf{g}_{s}=[g_{s}(1),\ldots,g_{s}(T)].$. We allow for the reserves to
also consume excess energy, and so a negative value of $g_{s}(t)$ denotes an
absorption of $g_{s}(t)$ units of energy at time $t$, $t\in\\{1,\ldots,T\\}$.
In case it is infeasible for the reserves to absorb energy in real time, the
cost of $T-$tuples that contain negative entries are set to infinity.

For any EV $i$, we mean by the term “storage sequence of the EV $i$ on day
$l$” a $T-$length sequence that specifies the energy stored in EV $i$ at each
time of the day. Note that the storage sequence of an EV uniquely specifies
how much energy must be injected or consumed from the EV at each time of the
day — a decision that, as we will see shortly, the ISO must make for every EV
for optimal operation of the grid. Every EV $i$ has associated with it a cost
function $c_{i}^{EV}\mathrel{\mathop{\mathchar
58\relax}}\\{1,\ldots,T\\}\times\\{1,\ldots,T\\}\times\mathbb{R}^{T}\to\mathbb{R}$
that specifies the cost incurred by the EV on any day $l$ as a function of (i)
its deadline $\delta_{i}(l)$ on that day, (ii) the actual time
$\widehat{\delta}_{i}(l)$ at which it disconnects from the grid on that day,
and (iii) its storage sequence $\mathbf{h}_{i,l}$ on that day, and is defined
as

$\displaystyle
c_{i}^{EV}(\delta_{i}(l),\widehat{\delta}_{i}(l),\mathbf{h}_{i,l})=-h_{i,l}(\widehat{\delta}_{i}(l))$
$\displaystyle\mathds{1}_{\\{\widehat{\delta}_{i}(l)\leq\delta_{i}(l)\\}}$
$\displaystyle+$ $\displaystyle
J_{m}\mathds{1}_{\\{\widehat{\delta}_{i}(l)>\delta_{i}(l)\\}},$ (2)

where $J_{m}\in\mathbb{R}_{>0}$ denotes the cost incurred by the EV if it
misses its deadline. In other words, if EV $i$ has deadline $\delta_{i}(l)$
but disconnects from the grid only after its deadline, then it incurs a cost
$J_{m}$ for missing its deadline, but on the other hand, if it disconnects
from the grid before its deadline, then the cost that it incurs is
proportional to the net energy injected into it, viz.,
$-h_{i,l}(\widehat{\delta}_{i}(l))$. The above cost function models a
situation in which the deadlines of EVs are hard constraints as defined in
Section III-A. Relaxing this assumption would entail defining the cost for
missed deadlines to gradually increase as a function of the duration by which
the deadline is missed.

###  III-C Storage Policy

The stochasticity of EV departure times necessitates the ISO to devise a
storage policy in order to determine the storage sequence of each EV on each
day. The storage policy, in general, could be a randomized policy.
Specifically, a storage policy $\boldsymbol{\pi}$ is specified by a
probability space
$(\Omega_{\boldsymbol{\pi}},\mathcal{F}_{{\boldsymbol{\pi}}},\mathbb{P}_{\boldsymbol{\pi}})$
and collection of functions $\\{\pi_{1},\ldots,\pi_{n_{s}}\\}$ where the
$i^{th}$ function $\pi_{i}\mathrel{\mathop{\mathchar
58\relax}}\\{1,\ldots,T\\}\times\\{1,\ldots,T\\}^{n_{s}}\times\Omega_{\boldsymbol{\pi}}\to\mathcal{[}0,B_{i}]$
specifies the energy that must be stored in EV $i$ at each time of the day as
a function of (i) the departure profiles of the EVs on that day, and (ii) a
variable that serves as the source of randomness of the policy. More
precisely, if $\widehat{\boldsymbol{\delta}}(l)\in\\{1,\ldots,T\\}^{n_{s}}$
denotes the vector of departure times of EVs on day $l$, then
$\pi_{i}(t,\widehat{\boldsymbol{\delta}}(l),\omega_{\boldsymbol{\pi}}(l))$
specifies the energy that must be stored in EV $i$ at time $t$ on day $l$,
where $\omega_{\boldsymbol{\pi}}(l)\in\Omega_{\boldsymbol{\pi}}$ is a random
variable that the policy draws on day $l$ according to
$\mathbb{P}_{\boldsymbol{\pi}}$ independently of all other random variables
realized until that day. We denote by

$\displaystyle\boldsymbol{\pi}_{i}(\widehat{\boldsymbol{\delta}}(l),\omega_{\boldsymbol{\pi}}(l))\coloneqq[\pi_{i}(1,\widehat{\boldsymbol{\delta}}(l),\omega_{\boldsymbol{\pi}}(l))\ldots\pi_{i}(T,\widehat{\boldsymbol{\delta}}(l),\omega_{\boldsymbol{\pi}}(l))]$

the storage sequence of EV $i$ on day $l$ as a function of the EVs’ departure
profiles $\boldsymbol{\widehat{\delta}}(l)$ and the “coin flip”
$\omega_{\boldsymbol{\pi}}(l)$ of the storage policy.

For a storage policy $\boldsymbol{\pi}$ to be implementable by the ISO, it
must not charge or discharge any EV after it disconnects from the grid. That
is, the policy $\boldsymbol{\pi}$ must satisfy the condition that for every
$i\in\\{1,\ldots,n_{s}\\}$, every
$\widehat{\boldsymbol{\delta}}(l)\in\\{1,\ldots,T\\}^{n_{s}},$ and every
$\omega_{\boldsymbol{\pi}}(l)\in\Omega_{\boldsymbol{\pi}},$

$\pi_{i}(t,\widehat{\boldsymbol{\delta}}(l),\omega_{\boldsymbol{\pi}}(l))=\pi_{i}(\widehat{\delta}_{i}(l),\widehat{\boldsymbol{\delta}}(l),\omega_{\boldsymbol{\pi}}(l))$

for all $t\geq\widehat{\delta}_{i}(l).$ We denote by $\Pi$ the set of all
implementable storage policies.

###  III-D The Independent System Operator’s Objective

Prior to each day, the ISO runs a day-ahead market in which it must decide the
energy dispatch sequence of the generator and the storage policy of the EVs
for that day. As mentioned before, the deadlines of the EVs for any given day
realize only after the day-ahead market for that day closes, and so the only
information on which the ISO can base its day-ahead market decisions are the
deadline distributions that the EVs bid in the market. Suppose for a moment
that the EVs are not strategic and that they bid the deadline distributions
$\boldsymbol{\theta}$ truthfully. How should the ISO compute the energy
dispatch sequence and the storage policy? Since the ISO does not know the
deadline realizations in the day-ahead market, it chooses these quantities so
as to minimize the expected cost of meeting the demand on the following day.
This is elaborated in more detail below. Note that since the deadline
distributions of the EVs are assumed to remain the same on all days, it
suffices for the ISO to compute these quantities just once, namely, in the
day-ahead market prior to day $1,$ and reuse them on all days. We describe in
Section VI how to address the more general scenario wherein the deadline
distributions could be different on different days.

Suppose that the ISO decides the generator’s energy dispatch sequence to be
$\mathbf{g}=[g(1),\ldots,g(T)]$ and the storage policy to be
$\boldsymbol{\pi}$ in the day-ahead market. Then,

$\displaystyle{{g}_{s}}(t,{\boldsymbol{\delta}}(l),\mathbf{g},\boldsymbol{\pi},\omega_{\boldsymbol{\pi}}(l))\;\;\;\;\;\;\;\;\;\;\;\;\;\;$
$\displaystyle=d(t)-\bigg{[}g(t)+\sum_{i=1}^{n_{s}}\bigg{(}\pi_{i}($
$\displaystyle t-1,{\boldsymbol{\delta}}(l),\omega_{\boldsymbol{\pi}}(l))$
$\displaystyle-\pi_{i}(t,{\boldsymbol{\delta}}(l),\omega_{\boldsymbol{\pi}}(l))\bigg{)}\bigg{]}$
(3)

is the real-time demand-supply mismatch at time $t$ on day $l$. Hence, the ISO
has to purchase the energy sequence

$\displaystyle\mathbf{g}_{s}({\boldsymbol{\delta}}$
$\displaystyle(l),\mathbf{g},\boldsymbol{\pi},\omega_{\boldsymbol{\pi}}(l))$
$\displaystyle=$
$\displaystyle[{g}_{s}(1,{\boldsymbol{\delta}}(l),\mathbf{g},\boldsymbol{\pi},\omega_{\boldsymbol{\pi}}(l)),\ldots,{g}_{s}(T,{\boldsymbol{\delta}}(l),\mathbf{g},\boldsymbol{\pi},\omega_{\boldsymbol{\pi}}(l))]$

in the spot market on day $l$ at price
$c^{s}({\mathbf{g}_{s}}({\boldsymbol{\delta}}(l),\mathbf{g},\boldsymbol{\pi},\omega_{\boldsymbol{\pi}}(l))).$
Therefore, the total cost of satisfying the demand on day $l$ – defined as the
sum of the costs incurred by the generator, the reserves, and the EVs – is

$c^{g}(\mathbf{g})+c^{s}({\mathbf{g}_{s}}({\boldsymbol{\delta}}(l),\mathbf{g},\boldsymbol{\pi},\omega_{\boldsymbol{\pi}}(l)))-\sum_{j=1}^{n_{s}}\pi_{j}(\delta_{j}(l),\boldsymbol{\delta}(l),\omega_{\boldsymbol{\pi}}(l)).$

Since $\boldsymbol{\delta}(l)$ and $\omega_{\boldsymbol{\pi}}(l)$ are random
variables, this cost is a random variable for any energy dispatch sequence
$\mathbf{g}$ and any storage policy $\boldsymbol{\pi}$ that the ISO chooses in
the day-ahead market. The ISO’s objective is to minimize the total expected
cost of meeting the demand, and therefore it chooses the energy dispatch
sequence $\mathbf{g}^{*}$ and the storage policy $\boldsymbol{\pi}^{*}$ as a
solution to the stochastic program

$\displaystyle\underset{\mathbf{g}\in\mathbb{R}^{T},\boldsymbol{\pi}\in\Pi}{\mathrm{Minimize}}\;\;\mathbb{E}_{(\boldsymbol{\delta},\omega_{\boldsymbol{\pi}})\sim\mathbb{P}_{\boldsymbol{\theta}}\times\mathbb{P}_{\boldsymbol{\pi}}}\Big{[}c^{g}(\mathbf{g})+c^{s}$
$\displaystyle\big{(}{\mathbf{g}_{s}}({\boldsymbol{\delta}},\mathbf{g},\boldsymbol{\pi},\omega_{\boldsymbol{\pi}})\big{)}$
$\displaystyle-$
$\displaystyle\sum_{j=1}^{n_{s}}{{\pi}_{j}(\delta_{j},\boldsymbol{\delta},\omega_{\boldsymbol{\pi}})}\Big{]}.$
(4)

We introduce a few definitions to compactify the notation. Define

$\displaystyle\widehat{c^{s}}({\boldsymbol{\delta}},\mathbf{g},\boldsymbol{\pi})\coloneqq\mathbb{E}_{\omega_{\boldsymbol{\pi}}\sim\mathbb{P}_{\boldsymbol{\pi}}}\big{[}c^{s}(\mathbf{g}_{s}({\boldsymbol{\delta}},\mathbf{g},\boldsymbol{\pi},\omega_{\boldsymbol{\pi}}))\big{]},$
(5)

which has the interpretation as the average cost of energy purchase in the
spot market if the generator produces the energy sequence $\mathbf{g},$ the
EVs disconnect at times $\boldsymbol{\delta},$ and the ISO employs the storage
policy $\boldsymbol{\pi}.$ Here, the averaging is carried out over the random
choices made by the storage policy $\boldsymbol{\pi}$. Similarly define

$\displaystyle\widehat{\pi}_{i}(t,{\boldsymbol{\delta}})\coloneqq\mathbb{E}_{\omega_{\boldsymbol{\pi}}\sim\mathbb{P}_{\boldsymbol{\pi}}}[\pi_{i}(t,{\boldsymbol{\delta}},\omega_{\boldsymbol{\pi}})]$
(6)

and let
$\widehat{\boldsymbol{\pi}}_{i}({\boldsymbol{\delta}})\coloneqq\big{[}\widehat{\pi}_{i}(1,{\boldsymbol{\delta}}),\ldots,\widehat{\pi}_{i}(T,{\boldsymbol{\delta}})\big{]}.$
Finally define

$\displaystyle\beta(\boldsymbol{\delta},\mathbf{g},\boldsymbol{\pi})\coloneqq
c^{g}(\mathbf{g})+\widehat{c^{s}}(\boldsymbol{\delta},\mathbf{g},\boldsymbol{\pi})-\sum_{j=1}^{n_{s}}{\widehat{\pi}_{j}(\delta_{j},\boldsymbol{\delta})}.$
(7)

The ISO’s problem (4) can then be expressed compactly as

$\displaystyle\underset{\mathbf{g}\in\mathbb{R}^{T},\boldsymbol{\pi}\in\Pi}{\mathrm{Minimize}}\;\;\mathbb{E}_{\boldsymbol{\delta}\sim\mathbb{P}_{\boldsymbol{\theta}}}\bigg{[}\beta(\boldsymbol{\delta},\mathbf{g},\boldsymbol{\pi})\bigg{]}.$
(8)

We define three functions based on (8). First, we define
$\mathbf{g}^{*}\mathrel{\mathop{\mathchar
58\relax}}\Theta^{n_{s}}\to\mathbb{R}^{T}$ as a function that maps the EV
parameters to an energy dispatch sequence that solves (8). Specifically, for
$\psi\in\Theta^{n_{s}},$ $\mathbf{g}^{*}(\boldsymbol{\psi})$ denotes an
optimal energy dispatch sequence that solves (8) if the EV parameters are
$\boldsymbol{\psi}.$ Similarly, we define
$\boldsymbol{\pi}^{*}\mathrel{\mathop{\mathchar
58\relax}}\Theta^{n_{s}}\to\Pi$ as the function that maps the EVs’ parameters
to an optimal storage policy that solves (8). Finally, we define
$q^{*}\mathrel{\mathop{\mathchar 58\relax}}\Theta^{n_{s}}\to\mathbb{R}$ as the
function that maps the EVs’ parameters to the optimal average cost so that
$q^{*}(\boldsymbol{\psi})$ denotes the optimal value of (8) if the EV
parameters are $\boldsymbol{\psi}.$ We will assume throughout that the cost
functions $c^{g}$ and $c^{s}$ are such that for some $\overline{Q}<\infty$ and
for all $\boldsymbol{\psi}\in\Theta^{n_{s}},$

$\displaystyle q^{*}(\boldsymbol{\psi})\leq\overline{Q}.$ (9)

Hence, the ISO’s objective in the day-ahead market is to compute the functions
$\mathbf{g}^{*}$ and $\boldsymbol{\pi}^{*}$ at the point
$\boldsymbol{\theta}.$ However, if the EVs are strategic, then they may not
bid their deadline distributions truthfully in the day-ahead market, and so
the ISO has the additional task of eliciting $\boldsymbol{\theta}$ truthfully.
We will discuss how the ISO can do this in an ensuing subsection.

Note also that if the EVs report their deadline realizations truthfully every
day, then the decisions $\mathbf{g}^{*}(\boldsymbol{\theta})$ and
$\boldsymbol{\pi}^{*}(\boldsymbol{\theta})$, when used on all days, almost
surely minimize the time-averaged cost of meeting the demand. That is, the
long-term average cost of operating the grid

$\displaystyle\limsup_{L\to\infty}\frac{1}{L}\sum_{l=1}^{L}\bigg{[}\beta(\boldsymbol{\delta}(l),\mathbf{g}^{l},\boldsymbol{\pi}^{l})\bigg{]}$
(10)

where $\mathbf{g}^{l}$ denotes the energy dispatch sequence on day $l$ and
$\boldsymbol{\pi}^{l}$ denotes the storage policy used on day $l,$ is
minimized by setting $\mathbf{g}^{l}=\mathbf{g}^{*}(\boldsymbol{\theta})$ and
$\boldsymbol{\pi}^{l}=\boldsymbol{\pi}^{*}(\boldsymbol{\theta})$ for all $l.$
The minimization could be carried out over all adapted policies that determine
$\mathbf{g}^{l}$ and $\boldsymbol{\pi}^{l}$ on each day $l$.

###  III-E The EV Operator’s Objective

On each day $l$, each EV $i$ receives a payment $p_{i}(l)$ from the ISO in
return for leasing its battery to the grid. Denoting by $\mathbf{h}_{i,l}$ the
storage sequence of EV $i$ on day $l$, its utility on that day is defined as

$\displaystyle u_{i}(\delta_{i}(l),\widehat{\delta}_{i}(l),$
$\displaystyle\mathbf{h}_{i,l})\coloneqq
p_{i}(l)-c_{i}^{EV}(\delta_{i}(l),\widehat{\delta}_{i}(l),\mathbf{h}_{i,l}).$

Each EV $i$’s objective is to maximize its long-term average utility defined
as
$\liminf_{L\to\infty}\frac{1}{L}\sum_{l=1}^{L}{u_{i}(\delta_{i}(l),\widehat{\delta}_{i}(l),\mathbf{h}_{i,l})}.$

###  III-F The Market Process

EVs report $\boldsymbol{\phi}$ISO
computes$(\mathbf{g}^{*}(\boldsymbol{\phi}),\boldsymbol{\pi^{*}(\boldsymbol{\phi}))}$Generation
$\mathbf{g}^{*}(\boldsymbol{\phi})$scheduled for day $1$EVs observe
$\boldsymbol{\delta}(1)$EVs report$\widehat{\boldsymbol{\delta}}(1)$ISO
computesstorage sequencefor day $1$Day $1$Generation
$\mathbf{g}^{*}(\boldsymbol{\phi})$scheduled for day $2$EVs observe
$\boldsymbol{\delta}(2)$EVs report$\widehat{\boldsymbol{\delta}}(2)$ISO
computesstorage sequencefor day $2$Day
$2$$\boldsymbol{\ldots}$$\boldsymbol{\ldots}$Time

Figure 1: The market chronology: In the day-ahead market before day $1$, each
EV $i$ reports a deadline distribution to the ISO, based on which the latter
computes the energy dispatch sequence and the storage policy. Then, at the
commencement of any day $l$, $l\in\mathbb{Z}_{+},$ each EV $i$ observes its
deadline $\delta_{i}(l)$ for that day. Following this, EV $i$ reports
$\widehat{\delta}_{i}(l)$ as its deadline, which could potentially be adapted
to
$\delta_{i}^{l},\widehat{\delta}_{i}^{l-1},\boldsymbol{\delta}_{-i}^{l},\widehat{\boldsymbol{\delta}}_{-i}^{l},\boldsymbol{\theta},$
and $\boldsymbol{\phi}.$ Based on $\widehat{\boldsymbol{\delta}}(l)$, the ISO
computes the storage schedule for each EV for that day using the storage
policy. Day $l$ then progresses, and the process repeats on day $l+1$.

There are two impediments to the ISO operating the grid at the optimal cost
$q^{*}(\boldsymbol{\theta}).$ The first is the ISO’s nescience of the
parameter vector $\boldsymbol{\theta},$ which renders it incapable of
computing the optimal decisions $g^{*}(\boldsymbol{\theta})$ and
$\boldsymbol{\pi}^{*}(\boldsymbol{\theta})$ in the day-ahead market. As
mentioned before, an EV’s deadline distribution is its private knowledge and
unknown to the ISO. Consequently, the ISO requests each EV to report its
parameter in the day-ahead market so that it can compute the optimal energy
dispatch sequence and storage policy. However, since the objective of any EV
is only to maximize its own utility, it may misreport its parameter if there
is a possibility for it to extract a higher utility by doing so than by
bidding truthfully. Consequently, we denote by $\phi_{i}\in\Theta$ the
parameter reported by EV $i$ in the day-ahead market, which may or may not be
equal to $\theta_{i}.$

Based on the reported parameters
$\boldsymbol{\phi}\coloneqq[\phi_{1},\ldots,\phi_{n_{s}}],$ the ISO computes
the energy dispatch as $\mathbf{g}^{*}(\boldsymbol{\phi})$ and the storage
policy as $\boldsymbol{\pi}^{*}(\boldsymbol{\phi})$. As mentioned before,
since the deadline distributions of the EVs are assumed to remain the same on
all days, it suffices for the EVs to report their parameters just once, and
for the ISO to run the day-ahead market just once, namely, before day $1$, to
compute the above decisions. Once the ISO computes these quantities, it reuses
them on all days.

In the day-ahead market corresponding to any day $l$, the ISO schedules the
generator to produce the energy sequence $\mathbf{g}^{*}(\boldsymbol{\phi})$
on day $l$ and decides on the storage policy
$\boldsymbol{\pi}^{*}(\boldsymbol{\phi})$ for day $l.$ After the day-ahead
market closes, the EVs observe their respective deadlines for that day. The
ISO requests the EVs to report their deadline realizations at the commencement
of day $l$. Based on the reported deadlines, the ISO computes the storage
sequence of each EV for that day using the policy
$\boldsymbol{\pi}^{*}(\boldsymbol{\phi})$. Being strategic, the EVs may not
bid their deadline realizations truthfully, and so we denote by
$\widehat{\delta}_{i}(l)$ the deadline reported by EV $i$ on day $l.$ Having
bid $\widehat{\delta}_{i}(l)$ as its deadline, EV $i$ is obliged to remain
connected to the grid until time $\widehat{\delta}_{i}(l)$ on day $l.$ The
entire chronology is illustrated in Fig. 1.

###  III-G The Mechanism Design Problem

Having fixed $\mathbf{g}^{*}(\boldsymbol{\phi})$ and
$\boldsymbol{\pi}^{*}(\boldsymbol{\phi})$ in the day-ahead market, the long-
term average utility that EV $i$ accrues is

$\displaystyle u_{i}^{\infty}(\phi_{i}$
$\displaystyle,\widehat{\delta}_{i}^{\infty},\boldsymbol{\phi}_{-i},\widehat{\boldsymbol{\delta}}_{-i}^{\infty},\omega^{\infty}_{\boldsymbol{\pi}^{*}(\boldsymbol{\phi})})$
$\displaystyle\coloneqq$
$\displaystyle\liminf_{L\to\infty}\frac{1}{L}\sum_{l=1}^{L}u_{i}\big{(}\delta_{i}(l),\widehat{\delta}_{i}(l),{\boldsymbol{\pi}}^{*}_{i}(\widehat{\boldsymbol{\delta}}(l),\omega_{\boldsymbol{\pi}^{*}(\boldsymbol{\phi})}(l);\boldsymbol{\phi})\big{)},$
(11)

where
$\boldsymbol{\pi}^{*}(\widehat{\boldsymbol{\delta}}(l),\omega_{\boldsymbol{\pi}^{*}(\boldsymbol{\phi})}(l);\boldsymbol{\phi})$
denotes the function $\boldsymbol{\pi}_{i}^{*}(\boldsymbol{\phi})$ evaluated
at
$\big{(}\widehat{\boldsymbol{\delta}}(l),\omega_{\boldsymbol{\pi}^{*}(\boldsymbol{\phi})}(l)\big{)}.$
Note that in addition to $\phi_{i}$, the long-term average utility
$u_{i}^{\infty}$ is also a function of the times
$\widehat{\delta}_{i}^{\infty}$ that EV $i$ reports. Consequently, if there
exists
$(\boldsymbol{\phi}_{-i},\widehat{\boldsymbol{\delta}}^{\infty}_{-i},\omega^{\infty}_{\boldsymbol{\pi}^{*}(\boldsymbol{\phi})})$
such that EV $i$ obtains a higher value for (11) by misreporting either or
both $\theta_{i}$ and $\delta_{i}^{\infty}$, then it may do so. However,
unless all EVs report their respective parameters truthfully in the day-ahead
market and report their respective deadlines truthfully “almost all days,” the
ISO cannot ensure that the long-term average cost of meeting the demand
defined in (10) approaches the optimal value $q^{*}(\boldsymbol{\theta})$.
This brings us to the central problem that is addressed in the paper, namely,
that of designing mechanisms that incentivize EVs to report not only their
deadline distributions truthfully in the day-ahead market, but also report
their deadline realizations truthfully almost all days. Specifically, we aim
to design a mechanism that renders truth-telling a dominant strategy so that
for every EV $i$, its average utility
$u_{i}^{\infty}(\phi_{i},\widehat{\delta}_{i}^{\infty},\boldsymbol{\phi}_{-i},\widehat{\boldsymbol{\delta}}_{-i}^{\infty},\omega^{\infty}_{\boldsymbol{\pi}^{*}(\boldsymbol{\phi})})$
is maximized by setting $\phi_{i}=\theta_{i}$ and
$\widehat{\delta}_{i}(l)=\delta_{i}(l)$ for all $l\in\mathbb{Z}_{+},$
regardless of what
$(\boldsymbol{\phi}_{-i},\widehat{\boldsymbol{\delta}}_{-i}^{\infty},\omega^{\infty}_{\boldsymbol{\pi}^{*}(\boldsymbol{\phi})})$
is. The next section develops the mechanism and establishes the incentive and
optimality properties guaranteed by it.

##  IV Mechanism for Trading Storage Capacity of EVs with Stochastic Deadlines

In this section, we develop a mechanism that renders truth-telling an
individually rational dominant strategy for every EV.

First, the ISO computes $\mathbf{g}^{*}(\boldsymbol{\phi})$ and
$\boldsymbol{\pi}^{*}(\boldsymbol{\phi})$ in the day-ahead market as the
generator’s energy dispatch sequence and the storage policy. Recall that these
quantities solve the stochastic program

$\displaystyle\underset{\mathbf{g},\boldsymbol{\pi}}{\mathrm{Min.}}\;\;c^{g}(\mathbf{g})+\mathbb{E}_{\boldsymbol{\delta}\sim\mathbb{P}_{\boldsymbol{\phi}}}\Big{[}\widehat{c^{s}}(\boldsymbol{\delta},\mathbf{g},\boldsymbol{\pi})-\sum_{j=1}^{n_{s}}\widehat{\pi}_{j}(\delta_{j},\boldsymbol{\delta})\Big{]},$
(12)

and note that the solutions of (8) and (12) coincide if
$\boldsymbol{\phi}=\boldsymbol{\theta}.$

We now describe the payment rule. The payment rule consists of each EV
receiving two payments on each day, namely, a “day-ahead payment” that is
determined based on the parameters reported to the ISO in the day-ahead
market, and an “end-of-the-day settlement” that is determined at the end of
each day based on a comparison of the the actual departure profile of the EVs
with the deadline distributions reported in the day-ahead market.

###  IV-A The Day-Ahead Payment

The day-ahead payment takes the form of a VCG payment. For each
$i\in\\{1,\ldots,n_{s}\\},$ define
$\mathbb{P}_{\boldsymbol{\phi}_{-i}}\coloneqq\mathbb{P}_{\phi_{1}}\times\ldots\times\mathbb{P}_{\phi_{i-1}}\times\mathbb{P}_{\phi_{i+1}}\times\ldots\times\mathbb{P}_{\phi_{n_{s}}}$
and let $q^{*}(\boldsymbol{\phi}_{-i})$ be the optimal value of the stochastic
program

$\displaystyle\underset{\mathbf{g},\boldsymbol{\pi}}{\mathrm{Min.}}\;\;c^{g}(\mathbf{g})+\mathbb{E}_{\boldsymbol{\delta}_{-i}\sim\mathbb{P}_{\boldsymbol{\phi}_{-i}}}\Big{[}\widehat{c^{s}}(\boldsymbol{\delta_{-i}},\mathbf{g},\boldsymbol{\pi})-\sum_{j\neq
i}\widehat{\pi}_{j}(\delta_{j},\boldsymbol{\delta}_{-i})\Big{]}.$

Note that this is the optimization problem that the ISO would have had to
solve in the day-ahead market if EV $i$ were absent from the system. The day-
ahead payment of EV $i$, $i\in\\{1,\ldots,n_{s}\\},$ is defined as

$\displaystyle p_{i}^{DA}(\phi_{i}$
$\displaystyle,\boldsymbol{\phi}_{-i})\coloneqq
q^{*}(\boldsymbol{\phi}_{-i})-\Bigg{[}c^{g}(\mathbf{g}^{*}(\boldsymbol{\phi}))$
$\displaystyle+$
$\displaystyle\mathbb{E}_{\boldsymbol{\delta}\sim\mathbb{P}_{\boldsymbol{\phi}}}\Big{\\{}\widehat{c^{s}}(\boldsymbol{\delta},\mathbf{g}^{*}(\boldsymbol{\phi}),\boldsymbol{\pi}^{*}(\boldsymbol{\phi}))-\sum_{j\neq
i}\widehat{\pi}_{j}^{*}(\delta_{j},\boldsymbol{\delta};\boldsymbol{\phi})\Big{\\}}\Bigg{]}.$
(13)

###  IV-B The End-of-the-Day Settlement

In addition to the day-ahead payment, the ISO also makes an “end-of-the-day
settlement” to each EV $i$ on each day $l$. A negative value of this quantity
indicates a “penalty” that should be paid by the EV to the ISO.

For $i\in\\{1,\ldots,n_{s}\\}$, $t\in\\{1,\ldots,T\\}$, and
$l\in\mathbb{Z}_{+},$ define

$\displaystyle{f}_{i,t}(l,\widehat{\delta}_{i}^{l},\phi_{i})\coloneqq\bigg{[}\frac{1}{l}\sum_{l^{\prime}=1}^{l}\mathds{1}_{\\{\widehat{\delta}_{i}(l^{\prime})=t\\}}\bigg{]}-\mathbb{P}_{\phi_{i}}(t)$
(14)

where $\mathbb{P}_{\phi_{i}}(t)$, recall, denotes the probability that a
random variable distributed according to $\mathbb{P}_{\phi_{i}}$ takes the
value $t.$ Let $\\{r\\}$ be any nonnegative sequence such that for some
$L_{r}\in\mathbb{N}$ and some $\gamma>\frac{1}{2},$

$\displaystyle{r(l)}\geq\sqrt{\frac{\ln{l^{\gamma}}}{l}}$ (15)

for all $l\geq L_{r},$ and

$\displaystyle\lim_{l\to\infty}r(l)=0.$ (16)

For all $l\in\mathbb{Z}_{+}$ and all $i\in\\{1,\ldots,n_{s}\\}$, define event

$\displaystyle
E_{i}(l,\widehat{\delta_{i}^{l}},\phi_{i})\coloneqq\\{\max_{t\in\\{1,\ldots,T\\}}|{f}_{i,t}(l,\widehat{\delta}_{i}^{l},\phi_{i})|\geq
r(l)\\}.$ (17)

Let $\\{J_{p}\\}$ be any nonnegative sequence such that

$\displaystyle\lim_{l\to\infty}\frac{J_{p}(l)}{l}=\infty.$ (18)

The end-of-the-day settlement of EV $i$ on day $l$ is defined as

$\displaystyle
p_{i}^{S}(l,\boldsymbol{\phi},\widehat{\delta}^{l}_{i},\widehat{\boldsymbol{\delta}}(l),\omega_{\boldsymbol{\pi}^{*}(\boldsymbol{\phi})}(l))\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;$
$\displaystyle\coloneqq\bigg{[}\mathbb{E}_{\boldsymbol{\delta}\sim\mathbb{P}_{\boldsymbol{\phi}}}\\{\widehat{\pi}_{i}^{*}(\delta_{i},\boldsymbol{\delta};\boldsymbol{\phi})\\}-{\pi}_{i}^{*}(\widehat{\delta}_{i}(l),$
$\displaystyle\widehat{\boldsymbol{\delta}}(l),\omega_{\boldsymbol{\pi}^{*}(\boldsymbol{\phi})}(l);\boldsymbol{\phi})\bigg{]}$
$\displaystyle-
J_{p}(l)\mathds{1}_{\\{E_{i}(l,\widehat{\delta}_{i}^{l},\phi_{i})\\}}.$ (19)

The term within the square brackets in the above RHS has the interpretation as
the difference between the expected amount of energy injected into EV $i$ on
day $l$ as determined in the day-ahead market and the actual energy injected
into EV $i$ on day $l$. Note that if all EVs are truthful, then the long-term
average of this quantity approaches zero almost surely. The second component
of the end-of-the-day settlement essentially penalizes EV $i$ for
discrepancies between the empirical distribution of its reported deadlines and
the distribution $\mathbb{P}_{\phi_{i}}$ that it reports in the day-ahead
market.

The total payment $p_{i}$ received by EV $i$ on day $l$ is the sum of its day-
ahead payment and its end-of-the-day settlement:

$\displaystyle p_{i}(l$
$\displaystyle,\phi_{i},\boldsymbol{\phi}_{-i},\widehat{\delta}_{i}^{l},\widehat{\boldsymbol{\delta}}(l),\omega_{\boldsymbol{\pi}^{*}(\boldsymbol{\phi})}(l))$
$\displaystyle=p_{i}^{DA}(\phi_{i},\phi_{-i})+p_{i}^{S}(l,\boldsymbol{\phi},\widehat{\delta}_{i}^{l},\widehat{\boldsymbol{\delta}}(l),\omega_{\boldsymbol{\pi}^{*}(\boldsymbol{\phi})}(l)).$
(20)

Theorem 1 establishes the incentive and efficiency properties of the mechanism
defined by the decision rule (12) and the payment rule (20). Before presenting
the theorem, we explain at a high level why the proposed mechanism provides
the desired incentive properties.

Arbitrarily fix an EV $i$. As mentioned before, one of the functionalities of
the end-of-the-day settlement is to penalize the EV for deviations of its
empirically observed departure times from $\mathbb{P}_{\phi_{i}}$. To enforce
this, on each day $l$ and for each $t\in\\{1,\ldots,T\\},$ the end-of-the-day
settlement function constructs a window of size $r(l)$ centered at
$\mathbb{P}_{\phi_{i}}(t)$ and penalizes the EV if the empirical frequency
$\frac{1}{l}\sum_{l^{\prime}=1}^{l}\mathds{1}_{\\{\widehat{\delta}_{i}(l^{\prime})=t\\}}$
falls outside the window.

Now, the window size must be designed carefully so as to balance two competing
objectives. On the one hand, the window size must approach zero as $l$ tends
to infinity. If not, the set of sequences from which the EV can choose its
real-time bids $\widehat{\delta}_{i}^{\infty}$ without incurring a penalty
would be “large,” thereby resulting in the violation of incentive
compatibility. On the other hand, if the window size shrinks too quickly, then
the aforementioned empirical frequency sequence of truthful bidders will fall
outside the window infinitely often. This would result in truthful bidders
paying a penalty infinitely often, thereby resulting in the violation of their
individual rationality. This brings us to the question of what the appropriate
rate is at which the window size should decay. Condition (15) answers this
question. To provide some intuition for this condition, note that the
empirical frequency
$\frac{1}{l}\sum_{l^{\prime}=1}^{l}\mathds{1}_{\\{\delta_{i}(l^{\prime})=t\\}}$
of EV $i$’s true deadlines is approximately normally distributed for large $l$
with a standard deviation that scales as ${\frac{1}{\sqrt{l}}}$. Hence,
scaling the window size also at the same rate would result in the probability
of empirical frequencies of truthful bids falling outside the window to remain
at some fixed value which does not scale with $l$. To avoid this, the window
size must scale slower than at least ${\frac{1}{\sqrt{l}}}.$ Lemma 1 shows
that by scaling it only “slightly” slower than this rate, namely, at the rate
specified by (15), the truthful bidders are guaranteed to not incur a penalty.

Once an appropriate window sequence is chosen, EV $i$ becomes subject to the
constraint that its real-time bid sequence $\widehat{\delta}_{i}^{\infty}$ has
a histogram that “looks like” $\mathbb{P}_{\phi_{i}}.$ If not, the average
penalty that it would pay will be infinite – a property that stems from (18)
and is established in Lemma 4. We refer to this constraint as C1. Henceforth,
it suffices to restrict attention only to those strategies that satisfy C1.

For $\theta\in\Theta,$ denote by $F_{\theta}$ the cumulative distribution
function corresponding to parameter ${\theta}$. Suppose first that $\phi_{i}$
is such that $F_{\theta_{i}}(t^{\prime})>F_{\phi_{i}}(t^{\prime})$ for some
$t^{\prime}\in\\{1,\ldots,T\\},$ and suppose that the EV reports
$\widehat{\delta}_{i}^{\infty}$ such that C1 is satisfied. Then, it is easy to
see that regardless of how $\widehat{\delta}_{i}^{\infty}$ is fabricated, it
will be larger than the EV’s true deadline $\delta_{i}^{\infty}$ at least
$F_{\theta_{i}}(t^{\prime})-F_{\phi_{i}}(t^{\prime})$ fraction of the days on
average. This is established in Lemma 3. Hence, letting
$\alpha(\theta_{i},\phi_{i})\coloneqq\sup_{t\in\\{1,\ldots,T\\}}F_{\theta_{i}}(t)-F_{\phi_{i}}(t),$
EV $i$ must miss its deadline at least $\alpha(\theta_{i},\phi_{i})$ fraction
of the days on average, thereby incurring a cost of at least
$J_{m}\alpha(\theta_{i},\phi_{i})$ on average for missing its deadlines. What
about the payment that it receives though as a result of bidding such a
$\phi_{i}$? Is there a possibility for the EV to obtain a higher payment by
bidding such a $\phi_{i}$ than by bidding $\theta_{i}$? The answer is in the
affirmative. To elaborate, by remaining connected to the grid beyond its
deadline, the EV could aid the ISO in reducing the cost of meeting the demand.
The VCG payment rule would reflect this positive externality and so the EV
could potentially obtain a larger payment every day in the day-ahead market by
bidding $\phi_{i}$ than by bidding $\theta_{i}$. Now, is the increase in
payment sufficient to outweigh the cost incurred for missing deadlines? The
answer is in the negative, as established in Theorem 1. Basically, the cost
$q^{*}$ possesses a Lipschitz-like property in that the reduction in the ISO’s
cost due false bid $\phi_{i}$ is bounded by a term proportional to
$\alpha(\theta_{i},\phi_{i}).$ This is established in Lemma 3. The composite
payment rule is designed so that the EV’s utility function inherits this
property, and it follows from this that the increase in the payment received
by the EV due to a false bid is upper bounded by a quantity that is
insufficient to make up for the cost incurred by missing deadlines.

This leaves the EV with just one option for misreporting in the day-ahead
market, namely, bidding $\phi_{i}$ such that $F_{\phi_{i}}(t)\geq
F_{\theta_{i}}(t)$ for all $t\in\\{1,\ldots,T\\}.$ If this condition holds and
$\phi_{i}\neq\theta_{i}$, we say that $\phi_{i}\prec\theta_{i}$, and term such
a $\phi_{i}$ as an “underbid” for $\theta_{i}$. Now, for every
$\boldsymbol{\phi}_{-i},$ the function
$q^{*}(\;\cdot\;,\;\boldsymbol{\phi}_{-i})$ is monotonic in that if
$\phi_{i}\prec\theta_{i}$, then $q^{*}(\phi_{i},\boldsymbol{\phi}_{-i})\geq
q^{*}(\theta_{i},\boldsymbol{\phi}_{-i}).$ This is established in Lemma 2. The
VCG payment rule would reflect this negative externality and so the EV by
underbidding $\theta_{i}$ would obtain a lower payment every day in the day-
ahead market than by bidding $\theta_{i}$ truthfully. What about the cost that
it incurs though as a result of underbidding? Is there a possibility for it to
incur a lower cost by underbidding $\theta_{i}$ than by bidding it truthfully?
The answer is in the affirmative. Underbidding in the day-ahead market affords
the EV an extensive strategy space in real time using which it can misreport
its deadline realizations without incurring a penalty or missing any
deadlines. The EV may be able to exploit this flexibility to lower its average
cost. This is best illustrated with the help of an example. Suppose that an EV
has a deterministic deadline $\tau,$ where $\tau\in\\{1,\ldots,T\\}.$ Instead
of bidding this truthfully, the EV could bid any distribution that has support
$\\{1,\ldots,\tau\\}.$ Consequently, on any given day, the EV can choose any
value in this set to disconnect from the grid, and every one of these choices
would ensure that it doesn’t miss its deadline. Hence, only C1 remains to be
satisfied, and this constraint is relatively easy to satisfy if the EV on each
day adapts its reported deadline to all deadlines reported in the past. This
still leaves the EV with ample freedom to choose its real time bids, which it
could possibly exploit to disconnect with a higher level of charge, or
equivalently with a lower cost, than the cost it would incur if it bids
truthfully. Now, is the cost reduction sufficient to outweigh the reduced
payments? The answer in the negative, as established in Theorem 1. Basically,
the first term of the end-of-the-day settlement (19) compares the battery
charge with which EV $i$ disconnects on day $l$ with that expected in the day-
ahead market. Any bias in this quantity appears as a debit to the EV at the
end of the day. It follows from this that the cost reduction attained via
strategic real-time bidding is insufficient to outweigh the reduced day-ahead
payments.

In summary, the EV can neither report $\phi_{i}$ such that
$\phi_{i}\prec\theta_{i}$ nor $\phi_{i}$ such that
$\alpha(\theta_{i},\phi_{i})>0.$ The only remaining option is for it to report
$\phi_{i}=\theta_{i}.$ Theorem 1 establishes this rigorously.

We now present the theorem. The first statement of the theorem states that
truthful bidding in both the day-ahead market and in real time is a dominant
strategy for every EV. The second statement states that under a certain mild
condition, truthful bidding is not only a dominant strategy but it is also the
unique dominant strategy in a certain sense. Specifically, under a certain
mild condition, an EV bidding its deadline distribution truthfully in the day-
ahead market and bidding its deadline realization truthfully “almost all days”
is the unique dominant strategy. The third statement states that truthful
bidding is individually rational for every EV regardless of how the other EVs
bid. The final statement shows that the mechanism aligns the EVs’ objectives
with the ISO’s objective in that every EV employing a selfish utility-
maximizing strategy automatically results in the ISO satisfying the demand at
minimum possible cost.

######  Theorem 1.

Suppose that the ISO determines $\mathbf{g}^{*}(\boldsymbol{\phi})$ and
$\boldsymbol{\pi}^{*}(\boldsymbol{\phi})$ as a solution to (12) and determines
the payments according to (20). Then, for $J_{m}$ sufficiently large, the
following hold.

  1. 1.

For every $i\in\\{1,\ldots,n_{s}\\}$ and every $\theta_{i}\in\Theta,$ there
exists $\mathcal{E}_{i}\subset\\{1,\ldots,T\\}^{\infty}$ with
$\mathbb{P}_{\theta_{i}}^{\infty}(\mathcal{E}_{i})=0$ such that for every
$\delta_{i}^{\infty}\notin\mathcal{E}_{i},$

$\displaystyle u_{i}^{\infty}(\theta_{i},{\delta}_{i}^{\infty},$
$\displaystyle{\boldsymbol{\phi}}_{-i},\widehat{\boldsymbol{\delta}}_{-i}^{\infty},\omega^{\infty}_{\boldsymbol{\pi}^{*}(\theta_{i},\boldsymbol{\phi}_{-i})})$
$\displaystyle\geq
u_{i}^{\infty}(\phi_{i},\widehat{\delta}_{i}^{\infty},{\boldsymbol{\phi}}_{-i},\widehat{\boldsymbol{\delta}}_{-i}^{\infty},\omega^{\infty}_{\boldsymbol{\pi}^{*}(\boldsymbol{\phi})})$
(21)

for every $\boldsymbol{\phi}$, $\widehat{\boldsymbol{\delta}}^{\infty}$,
$\omega^{\infty}_{\boldsymbol{\pi}^{*}(\theta_{i},\boldsymbol{\phi}_{-i})},$
and $\omega^{\infty}_{\boldsymbol{\pi}^{*}(\boldsymbol{\phi})}$.

I.e., for every EV $i$, truth-telling is $\mathbb{P}_{\theta_{i}}^{\infty}-$
almost surely a dominant strategy.

  2. 2.

Let $i\in\\{1,\ldots,n_{s}\\}$ and suppose that $\theta_{i}$ is such that for
all $\phi_{i}\neq\theta_{i},$

$\displaystyle q^{*}(\phi_{i},\boldsymbol{\phi}_{-i})\neq
q^{*}(\theta_{i},\boldsymbol{\phi}_{-i})$ (22)

for some $\boldsymbol{\phi}_{-i}\in\Theta^{n_{s}-1}.$ If for some
$\phi_{i}\in\Theta$, there exists
$\mathcal{E}_{i}\subset\\{1,\ldots,T\\}^{\infty}$ with
$\mathbb{P}_{\theta_{i}}^{\infty}(\mathcal{E}_{i})=0$ such that for every
$\delta_{i}^{\infty}\notin\mathcal{E}_{i},$ $\boldsymbol{\phi}_{-i},$
$\widehat{\boldsymbol{\delta}}_{-i}^{\infty},$
$\omega^{\infty}_{\boldsymbol{\pi}^{*}(\boldsymbol{\phi})},$ and
$\omega^{\infty}_{\boldsymbol{\pi}^{*}(\theta_{i},\boldsymbol{\phi}_{-i})},$
there exists $\widehat{\delta}_{i}^{\infty}$ such that

$\displaystyle u_{i}^{\infty}(\phi_{i},$
$\displaystyle\widehat{\delta}_{i}^{\infty},{\boldsymbol{\phi}}_{-i},\widehat{\boldsymbol{\delta}}_{-i}^{\infty},\omega^{\infty}_{\boldsymbol{\pi}^{*}(\boldsymbol{\phi})})$
$\displaystyle=u_{i}^{\infty}(\theta_{i},{\delta}_{i}^{\infty},{\boldsymbol{\phi}}_{-i},\widehat{\boldsymbol{\delta}}_{-i}^{\infty},\omega^{\infty}_{\boldsymbol{\pi}^{*}(\theta_{i}\boldsymbol{\phi}_{-i})}),$
(23)

then,

$\displaystyle\phi_{i}=\theta_{i},$ (24)

and

$\displaystyle\lim_{L\to\infty}\frac{1}{L}\sum_{l=1}^{L}\mathds{1}_{\\{\widehat{\delta}_{i}(l)\neq\delta_{i}(l)\\}}=0.$
(25)

I.e., for every $i\in\\{1,\ldots,n_{s}\\}$ such that (22) holds, truth-telling
in the day-ahead market and truth-telling on almost all days is
$\mathbb{P}_{\theta_{i}}^{\infty}-$ almost surely the unique dominant strategy
for EV $i$.

  3. 3.

For every $i\in\\{1,\ldots,n_{s}\\}$ and every $\theta_{i}\in\Theta,$ there
exists $\mathcal{E}_{i}\subset\\{1,\ldots,T\\}^{\infty}$ with
$\mathbb{P}_{\theta_{i}}^{\infty}(\mathcal{E}_{i})=0$ such that for all
$\delta_{i}^{\infty}\notin\mathcal{E}_{i},$

$\displaystyle
u_{i}^{\infty}(\theta_{i},{\delta}_{i}^{\infty},{\boldsymbol{\phi}}_{-i},\widehat{\boldsymbol{\delta}}_{-i}^{\infty},\omega^{\infty}_{\boldsymbol{\pi}^{*}(\theta_{i},\boldsymbol{\phi}_{-i})})\geq
0$ (26)

for all $\boldsymbol{\phi}_{-i},$
$\widehat{\boldsymbol{\delta}}_{-i}^{\infty},$ and
$\omega^{\infty}_{\boldsymbol{\pi}^{*}(\theta_{i},\boldsymbol{\phi}_{-i})}.$

I.e., for every EV $i,$ truth-telling is $\mathbb{P}_{\theta_{i}}^{\infty}-$
almost surely individually rational.

  4. 4.

If (22) and (23) hold for every $i\in\\{1,\ldots,n_{s}\\},$ then

$\displaystyle\limsup_{L\to\infty}\frac{1}{L}\sum_{l=1}^{L}\beta\big{(}\widehat{\boldsymbol{\delta}}(l),\mathbf{g}^{*}(\boldsymbol{\phi}),\boldsymbol{\pi}^{*}(\boldsymbol{\phi})\big{)}=q^{*}(\boldsymbol{\theta})$
(27)

$\mathbb{P}_{\boldsymbol{\theta}}^{\infty}-$ almost surely.

I.e., if every EV employs a dominant strategy, then the time-averaged cost at
which the ISO satisfies the demand is equal to the optimal average cost at
which it satisfies the demand if all EVs are truthful.

###### Proof.

See Appendix A. ∎

##  V Algorithms and Numerical Results

Implementing the mechanism presented in the previous section and operating the
grid optimally requires the ISO to solve the stochastic program (12) in the
day-ahead market. Note that (12) is essentially an economic dispatch problem
for a power system that has EV storage integrated into it. One of the primary
difficulties in solving (12) arises from the fact that its decision space is
infinite-dimensional; the optimization algorithm must search over the space of
all implementable storage policies in order to solve (12). In what follows, we
show that for an important special case which the ISO frequently encounters in
practice, (12) can be reduced to a finite-dimensional optimization problem.
The special case corresponds to the situation where the production function
$c^{s}$ of the reserves is additively separable over time. In today’s
electricity markets, not only is the function $c^{s}$ additively separable, it
is also linear, and so is the function $c^{g}$. We first present the approach
by which (12) reduces to a finite-dimensional optimization problem, and then
use it in our simulations to compute the expected cost savings.

A production function $c^{s}\mathrel{\mathop{\mathchar
58\relax}}\mathbb{R}^{T}\to\mathbb{R}$ is said to be _additively separable
over time_ if there exist functions
$c^{s}_{1},\ldots,c^{s}_{T}\mathrel{\mathop{\mathchar
58\relax}}\mathbb{R}\to\mathbb{R}$ such that

$\displaystyle
c^{s}([g_{s}(1),\ldots,g_{s}(T)])=\sum_{t=1}^{T}c^{s}_{t}(g_{s}(t))$ (28)

for all $\mathbf{g}_{s}\in[G^{s}_{\mathrm{min}},G^{s}_{\mathrm{max}}]^{T},$
where $G^{s}_{\mathrm{min}}$ and $G^{s}_{\mathrm{max}}$ denote the minimum and
maximum generation capacity of the reserves. Throughout this section, we
assume that $c^{s}$ is of the form (28).

The reduction technique stems from the rather simple observation that the
stochastic program (12) can equivalently be expressed as

$\displaystyle\underset{\mathbf{g}}{\mathrm{Min.}}\bigg{\\{}\underset{\boldsymbol{\pi}}{\mathrm{Min.}}\;\;\mathbb{E}_{\boldsymbol{\delta}\sim\mathbb{P}_{\boldsymbol{\theta}}}\big{[}\beta(\boldsymbol{\delta},\mathbf{g},\boldsymbol{\pi})\big{]}\bigg{\\}},$
(29)

which suggests a two-stage approach to solve the problem. Specifically, if the
“inner program”

$\underset{\boldsymbol{\pi}}{\mathrm{Min.}}\;\;\mathbb{E}_{\boldsymbol{\delta}\sim\mathbb{P}_{\boldsymbol{\theta}}}\big{[}\beta(\boldsymbol{\delta},\mathbf{g},\boldsymbol{\pi})\big{]},\;\;$

can be solved for any $\mathbf{g}$ to result in a storage policy
$\boldsymbol{\pi}^{\dagger}(\mathbf{g})$, then (29) can be solved by solving
the “outer program”

$\displaystyle\underset{\mathbf{g}}{\mathrm{Min.}}\;\;\overline{\beta}(\mathbf{g}),$
(30)

where
$\overline{\beta}(\mathbf{g})\coloneqq\mathbb{E}_{\boldsymbol{\delta}\sim\mathbb{P}_{\boldsymbol{\theta}}}\big{[}\beta(\boldsymbol{\delta},\mathbf{g},\boldsymbol{\pi}^{\dagger}(\mathbf{g}))\big{]}.$
This outer program is finite-dimensional. While it may not be convex or
otherwise solvable by polynomial-time algorithms, the fact that the ISO has to
solve it just once, and that it consists of only few tens of decision
variables in practice, implies that its complexity may not be of significant
concern.

The above reduction technique hinges on the ability to solve the inner program
which is infinite dimensional. For the case when $c^{s}$ is additively
separable, the inner program can be formulated as a finite-horizon Markov
Decision Process (MDP), thereby rendering it solvable via dynamic programming.
In what follows, we define the state space, the action set, the transition
kernels, the stage costs, and the terminal costs which define the MDP.

###  V-A States

On any day $l,$ we define the state $s^{EV}_{i}(t)$ of EV $i$ at the end of
time interval $t$ as $s^{EV}_{i}(t)\coloneqq(e_{i}(t),h_{i}(t))$ where
$e_{i}(t)$ is a $0-1$ variable indicating whether or not EV $i$ is connected
to the grid at the end of time interval $t$, and $h_{i}(t)$ is the amount of
energy stored in EV $i$ at the end of time interval $t.$ If the EV is not
connected to the grid at the end of time interval $t,$ then $h_{i}(t)$ is
defined as the amount of energy that was stored in the EV at the time that it
disconnected from the grid.

We denote by $\mathcal{H}_{i}$ the set of energy levels to which EV $i$’s
battery can be charged. While typically $\mathcal{H}_{i}=[0,B_{i}]$, we allow
for $\mathcal{H}_{i}$ to be more general, namely, we allow for it to be any
subset of $[0,B_{i}].$

Consequently, the state space $\mathcal{S}^{EV}_{i}$ of EV $i$ is

$\mathcal{S}^{EV}_{i}\coloneqq\\{0,1\\}\times\mathcal{H}_{i}.$

The initial state $s^{EV}_{i}(0)$ of every EV $i$ is $(1,0),$ that is, every
EV is connected to the grid at the beginning of time interval $1$, and no
energy has been stored in any EV by the ISO at that time.

Based on the state of each EV, we define the state $\mathbf{s}(t)$ of the
entire EV-integrated power system as

$\mathbf{s}(t)\coloneqq(s^{EV}_{1}(t),\ldots,s^{EV}_{n_{s}}(t)).$

Consequently, the state space $\mathcal{S}$ of the system is

$\displaystyle\mathcal{S}=\mathcal{S}^{EV}_{1}\times\ldots\times\mathcal{S}^{EV}_{n_{s}},$

and its initial state is $\mathbf{s}(0)=\big{(}(1,0),\ldots,(1,0)\big{)}.$

###  V-B Actions

For $i\in\\{1,\ldots,n_{s}\\}$ and $t\in\\{1,\ldots,T\\},$ we define the _EV-
action_ for EV $i$ at time $t$ as the energy storage decision that the ISO
makes for EV $i$ at time interval $t,$ namely, the amount of energy that the
ISO decides to inject into EV $i$ at time $t.$ We denote this by $a_{i}(t),$
and a negative value for $a_{i}(t)$ denotes energy discharge. We define the
_EV-level action set_ $\mathcal{A}^{EV}_{i}$ of EV $i$ as

$\displaystyle\mathcal{A}^{EV}_{i}=[-B_{i},B_{i}],$

which contains every action that the ISO can ever take for EV $i$.

Now, The constraints that (i) the ISO cannot discharge from an EV more energy
than it has stored in the EV, (ii) the ISO cannot exceed the EV’s battery
capacity, (iii) the ISO cannot charge or discharge energy from the EV if it is
no longer connected to the grid, and (iv) the amount of energy stored in any
EV $i$ must belong to $\mathcal{H}_{i}$, translate into constraints on what
actions from the set $[-B_{i},B_{i}]$ the ISO can take when EV $i$ is in a
given state. This results in the EV-level action sets being state-dependent.
Specifically, for $s^{EV}_{i}=(e_{i},h_{i})\in\mathcal{S}^{EV}_{i},$ the set
$\mathcal{A}^{EV}_{s^{EV}_{i}}$ of feasible actions that the ISO can take when
EV $i$ is in state ${s}^{EV}_{i}$ is

$\displaystyle\mathcal{A}^{EV}_{s^{EV}_{i}}\coloneqq\begin{cases}\\{a\in\mathcal{A}^{EV}_{i}\mathrel{\mathop{\mathchar
58\relax}}a+h_{i}\in\mathcal{H}_{i}\\}&;\;\;\mathrm{if}\;\;e_{i}=1,\\\
\;\;\;\;\;\;\;\;\\{0\\}&;\;\;\mathrm{if}\;\;e_{i}=0.\end{cases}$

Based on the sets $\mathcal{A}^{EV}_{1},\ldots,\mathcal{A}^{EV}_{n_{s}}$, we
define the system-level action set $\mathcal{A}$, or simply the action set, as

$\displaystyle\mathcal{A}\coloneqq\mathcal{A}^{EV}_{1}\times\ldots\times\mathcal{A}^{EV}_{n_{s}}.$

The set $\mathcal{A}$ collects every combination of actions that the ISO can
ever take for all EVs.

Since not all actions in the EV-level action sets are feasible for all EV
states, not all actions in the action set are feasible for all system states.
That is, the feasible action sets are state-dependent. It is easy to verify
that for $\mathbf{s}\in\mathcal{S},$ the set $\mathcal{A}_{\mathbf{s}}$ of
feasible actions that the ISO can take when the system is in state
$\mathbf{s}$ is

$\displaystyle\mathcal{A}_{\mathbf{s}}=\mathcal{A}^{EV}_{s_{1}}\times\ldots\times\mathcal{A}^{EV}_{s_{n_{s}}},$

where $s_{i}$ denotes the $i^{th}$ element of $\mathbf{s}.$

###  V-C Transition kernels

Suppose that EV $i$’s state at the end of time interval $t$ is $(1,h_{i}(t)),$
and that the ISO takes a feasible action $\mathbf{a}$ in time interval $t+1.$
Then, the only states that the EV can transit to at the end of time interval
$t+1$ are $(0,h_{i}(t)+a_{i})$ and $(1,h_{i}(t)+a_{i}).$ The probability that
it transits to the state $(0,h_{i}(t)+a_{i})$ is the conditional probability
that EV $i$ disconnects from the grid at time $t+1$ given that it has remained
connected until time $t$, which is equal to
$\frac{\mathbb{P}_{\theta_{i}}(t+1)}{1-F_{\theta_{i}}(t)}$. The probability
that it transits to the state $(1,h_{i}(t)+a_{i})$ is
$1-\frac{\mathbb{P}_{\theta_{i}}(t+1)}{1-F_{\theta_{i}}(t)}$.

On the other hand, if EV $i$ is not connected to the grid at time $t$ so that
its state at time $t$ is $(0,h_{i}(t))$ for some $h_{i}(t)\in\mathcal{H}_{i},$
then, regardless of what feasible action the ISO takes, the only state that
the EV can transit to at time $t+1$ is $(0,h_{i}(t))$, which it does with
probability $1$. This yields the EV-level probability transition law for EV
$i$ as

$\displaystyle P^{EV}_{i}$
$\displaystyle\big{(}s^{EV}_{i}(t+1)\big{|}s^{EV}_{i}(t),a_{i}(t+1)\big{)}$
$\displaystyle=$
$\displaystyle\begin{cases}\frac{\mathbb{P}_{\theta_{i}}(t+1)}{1-F_{\theta_{i}}(t)}\mathds{1}_{h_{i}(t+1)=h_{i}(t)+a_{i}(t+1)}&{;}\;\begin{bmatrix}e_{i}(t)\\\
e_{i}(t+1)\end{bmatrix}=\begin{bmatrix}1\\\ 0\end{bmatrix}\\\
[1-\frac{\mathbb{P}_{\theta_{i}}(t+1)}{1-F_{\theta_{i}}(t)}]\mathds{1}_{h_{i}(t+1)=h_{i}(t)+a_{i}(t+1)}&{;}\;\begin{bmatrix}e_{i}(t)\\\
e_{i}(t+1)\end{bmatrix}=\begin{bmatrix}1\\\ 1\end{bmatrix}\\\
\mathds{1}_{\\{s^{EV}_{i}(t+1)=s^{EV}_{i}(t)\\}}&{;}\;\;\;\;e_{i}(t)=0.\end{cases}$

The transition kernel for the entire system can be computed based on the above
EV-level probability transition laws. Specifically, for
$t\in\\{0,\ldots,T-1\\},$ if the system is in state $\mathbf{s}$ at the end of
time interval $t$ and the ISO takes action
$\mathbf{a}\in\mathcal{A}_{\mathbf{s}}$ at time interval $t+1,$ then the
probability that it transitions to state $\mathbf{s}^{\prime}$ at the end of
time interval $t+1$ is

$\displaystyle
P_{t+1}(\mathbf{s}^{\prime}|\mathbf{s},\mathbf{a})\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;$
$\displaystyle\coloneqq\mathrm{Pr}(\mathbf{s}(t+1)=\mathbf{s}^{\prime}|\mathbf{s}(t)=\mathbf{s},$
$\displaystyle\mathbf{a}(t+1)=\mathbf{a})$
$\displaystyle=\prod_{i=1}^{n_{s}}P_{i}^{EV}(s^{\prime}_{i}\big{|}s_{i},a_{i}),$
(31)

where $s_{i}^{\prime},s_{i},$ and $a_{i}$ denote the $i^{th}$ component of
$\mathbf{s}^{\prime},\mathbf{s}$ and $\mathbf{a}$ respectively.

###  V-D Stage costs

The stage costs capture the costs incurred by the reserves at each time
interval. For $t\in\\{0,\ldots,T-1\\},$ the stage cost
$c_{t+1}(\mathbf{s}(t),\mathbf{a}(t+1))$ is defined as the cost incurred by
the reserves at time interval $t+1$ if action $\mathbf{a}(t+1)$ is taken at
that time. The demand-supply mismatch at time interval $t+1$ if action
$\mathbf{a}(t+1)$ is taken is equal to
$d(t+1)+\sum_{i=1}^{n_{s}}a_{i}(t+1)-g(t+1),$ and this energy must be produced
by the reserves. Hence, the stage cost at time $t+1$ equals

$\displaystyle c_{t+1}(\mathbf{s}(t$ $\displaystyle),\mathbf{a}(t+1))$
$\displaystyle=c^{s}\big{(}g(t+1)-d(t+1)-\sum_{i=1}^{n_{s}}a_{i}(t+1)\big{)}.$
(32)

###  V-E Terminal costs

It follows from the discussion in Section V-C that for any EV $i,$ the term
$h_{i}(T)$ in its final state $s^{EV}_{i}(T)$ specifies the amount of energy
stored in it at the time that it disconnects from the grid. This allows us to
capture the costs incurred by the EVs by means of a terminal cost function .
Specifically, for any state
$\mathbf{s}=\big{(}(e_{1}(T),h_{1}(T)),\ldots,(e_{n_{s}}(T),h_{n_{s}}(T)\big{)}\in\mathcal{S},$
we define the terminal cost $v_{T}(\mathbf{s})$ as

$\displaystyle v_{T}(\mathbf{s})\coloneqq\sum_{i=1}^{n_{s}}-h_{i}(T),$ (33)

which equals the sum of the costs incurred by all EVs in the system.

###  V-F Computing an optimal storage policy

Consider the Markov Decision Process defined by
$\big{(}\mathcal{S},\\{\mathcal{A}_{\mathbf{s}}\\},\\{P_{t}(\mathbf{s}^{\prime}|\mathbf{s},\mathbf{a})\\},\\{c_{t}\\},v_{T}\big{)}.$
That the MDP admits an optimal policy that is deterministic and Markovian can
be established using routine arguments from Markov decision theory, see for
example [14, Section 5.4]. Consequently, the MDP can, in principle, be solved
optimally using dynamic programming, which uses the following backward
recursion to compute the value function and an optimal policy:

$\displaystyle
v_{t}(\mathbf{s})=\min_{\mathbf{a}\in\mathcal{A}_{\mathbf{s}}}\big{[}c_{t+1}(\mathbf{s},\mathbf{a})+\sum_{\mathbf{s}^{\prime}\in\mathcal{S}}P_{t+1}(\mathbf{s}^{\prime}\big{|}\mathbf{s},\mathbf{a})v_{t+1}(\mathbf{s}^{\prime})\big{]}$
(34)

for all $\mathbf{s}\in\mathcal{S}$ and $t=T-1,\ldots,0$. It is easy to verify
that $c^{g}(\mathbf{g})+v_{0}(\mathbf{s}(0))=\overline{\beta}(\mathbf{g})$,
and that the policy obtained by collecting an argument that minimizes the RHS
of (34) at each state and each time is an optimal policy
$\boldsymbol{\pi}^{\dagger}(\mathbf{g})$.

To summarize, the stochastic program (12) when the production function $c^{s}$
is additively separable reduces to a finite-dimensional optimization program
which has embedded in it a dynamic program. We have used this reduction in our
simulations to compute an optimal energy dispatch, storage policy and cost
savings.

Figure 2: The total expected cost of satisfying the demand is plotted as a
function of varying levels of EV penetration for five different profiles of EV
deadline distributions. The solid curve corresponds to the scenario where all
EVs can lease their battery to the grid for the entire day, and denotes the
minimum possible cost at which the ISO can satisfy the demand.

In our simulations, we have divided a day into a total of five time intervals.
The simulation parameters are specified in Table I. In order to obtain
conservative estimates of the cost reduction, we have assumed all EVs to have
a capacity of $10\mathrm{kWh},$ which is an order of magnitude lesser than the
battery capacity of many EVs that are commercially available today. With the
view of rendering the dynamic program to have a finite state space and action
set, we have quantized the energy levels to which the EVs can be charged.
Specifically, we have assumed $\mathcal{H}_{i}=\\{0,10\mathrm{kWh}\\}$. We
have also quantized the generator’s energy output so that at any time, the
generator can only produce an integer multiple of $10\;\mathrm{kWh}$. This
renders the outer program to be finite. In our simulations, we have solved the
outer program using a combination of heuristics and exhaustive search.

The production functions that are used in the simulations are

$\displaystyle c^{g}(\mathbf{g})=\sum_{t=1}^{5}c_{t}^{g}(t)g(t)$

and

$\displaystyle
c^{s}(\mathbf{g}_{s})=\sum_{t=1}^{5}\big{[}c^{s}_{t}g_{s}(t)\mathds{1}_{\\{g_{s}(t)\geq
0\\}}+c^{s}_{t}g_{s}^{2}(t)\mathds{1}_{\\{g_{s}(t)<0\\}}\big{]}$

where the numerical values for $[c_{1}^{g}\;\ldots\;c^{g}_{5}]$ and
$[c^{s}_{1}\;\ldots\;c^{s}_{5}]$ are specified in Table I. The coefficients
$c^{g}_{1},\;\ldots\;,c^{g}_{5}$ have been drawn at random and sorted, and the
range from which they have been drawn has been obtained from the range of
locational marginal prices at which electricity was traded in October 2020 in
ISO New England’s day-ahead market [15]. The function $c^{s}$ can be thought
of as indicating that it is in some sense easier for the reserves to produce
energy in real time than to consume it.

Fig. 2 plots the total cost $q^{*}(\boldsymbol{\theta})$ at which the ISO
satisfies the demand for four different deadline distribution profiles
$\boldsymbol{\theta}$ of the EVs. In all cases, the expected cost of
satisfying the demand decreases almost linearly with EV penetration in the
considered regime. Moreover, the distribution $\theta_{D}$ corresponds to
larger deadlines than the distribution $\theta_{C}$ in that
$F_{\theta_{D}}(t)\leq F_{\theta_{C}}(t)$ for all $t\in\\{1,\ldots,5\\}$.
Similarly, we also have $F_{\theta_{D}}(t)\leq F_{\theta_{B}}(t)\leq
F_{\theta_{A}}(t)$ for all $t\in\\{1,\ldots,5\\}$. Hence, in addition to
showing the reduction in costs due to increased EV penetration, Fig. 2 also
illustrates the value that larger EV deadlines provide in reducing the
operating cost. Note that these cost reductions are only lower bounds in that
solving the dynamic program and the outer program with finer or even no
discretization would result in cost reductions that are higher than those
indicated in Fig. 2.

Finally and most importantly, these cost reductions can be attained only if
the EVs bid their deadline distributions and deadline realizations truthfully,
which in turn is guaranteed only in the presence of a mechanism that renders
truth-telling a dominant strategy both in the day-ahead market and in real
time. As illustrated in the example in Section I, in the absence of such a
mechanism, strategic behavior of EVs could result in total costs in Fig. 2
that are in excess of $6.5$ for all EV penetration levels and all deadline
distributions, implying that the ISO would be better off not utilizing the EVs
at all for storage. The magnitude of the cost excess depends on the specifics
of each EV’s bidding strategy, which in turn could be unpredictable in the
absence of a unique dominant strategy.

TABLE I: Simulation parameters Variable | Value | Units
---|---|---
$\mathbf{d}$ | $[36.7387\;38.5138\;56.6975\;73.9188\;57.6061]$ | kWh
$c^{g}$ | $[12.4198\;18.8367\;19.1754\;31.0088\;33.3978]$ | $/MWh
$c^{s}$ | $[27.8936\;28.2861\;29.3702\;30.5788\;34.3765]$ | $/MWh
${\theta}_{A}$ | $[0.2000\;\;0.2000\;\;0.2000\;\;0.2000\;\;0.2000]$ |
${\theta}_{B}$ | $[0.0770\;\;0.2442\;\;0.0783\;\;0.0716\;\;0.5290]$ |
${\theta}_{C}$ | $[0.0378\;\;0.2430\;\;0.1449\;\;0.5683\;\;0.0059]$ |
${\theta}_{D}$ | $[0.0212\;\;0.0462\;\;0.1019\;\;0.2061\;\;0.6245]$ |
${\theta}_{E}$ | $[0\;\;0\;\;0\;\;0\;\;1]$ |
$\boldsymbol{\theta}_{1}$ | $[\theta_{A}\;\;\theta_{A}\;\;\theta_{A}\;\;\theta_{A}]$ |
$\boldsymbol{\theta}_{2}$ | $[\theta_{B}\;\;\theta_{B}\;\;\theta_{B}\;\;\theta_{B}]$ |
$\boldsymbol{\theta}_{3}$ | $[\theta_{C}\;\;\theta_{C}\;\;\theta_{C}\;\;\theta_{C}]$ |
$\boldsymbol{\theta}_{4}$ | $[\theta_{D}\;\;\theta_{D}\;\;\theta_{D}\;\;\theta_{D}]$ |
$\boldsymbol{\theta}_{5}$ | $[\theta_{E}\;\;\theta_{E}\;\;\theta_{E}\;\;\theta_{E}]$ |

##  VI Extensions

We have assumed the deadline distributions and the demand sequence to remain
the same on all days. An immediate extension is to address the scenario where
the deadline distributions of the EVs and the demand sequence of the load
could potentially be different on different days. Denote by
$\\{\boldsymbol{\theta}(1),\boldsymbol{\theta}(2),\ldots\\}$ the sequence of
EV parameters on different days, $\boldsymbol{\theta}(l)\in\Theta^{n_{s}},$
and by $\\{\mathbf{d}_{1},\mathbf{d}_{2},\ldots\\}$ the demand sequence on
different days. If the number of distinct elements in
$\\{\boldsymbol{\theta}(1),\boldsymbol{\theta}(2),\ldots\\}$ and
$\\{\mathbf{d}_{1},\mathbf{d}_{2},\ldots\\}$ are finite, then the results of
this paper can be readily extended to this more general setting. Specifically,
by requiring the EVs to report their parameters in the day-ahead market on all
days, categorizing each day into one of a finite number of “bins” such that
the reported deadline distributions and the demand sequence remain the same on
all days belonging to a bin, and instantiating in parallel the mechanism
presented in the paper – one for each bin – we obtain a mechanism that has the
desired incentive and optimality properties.

We have also assumed that the deadlines of all EVs are independent random
variables. Relaxing this assumption and developing an analogous mechanism for
the case where the EV deadlines could be correlated is an important
generalization since it could more accurately model the usage patterns of EVs
in real world. Extending the results to the context of multi-bus power systems
is another important generalization.

##  VII Conclusion

We have considered the problem of integrating a fleet of strategic EVs with
random deadlines into the grid and utilizing them for energy storage. Without
appropriate incentive structures, EV-power grid integration could potentially
be counterproductive to the cost- and energy-efficient operation of the grid.
This fundamentally arises because of two phenomena operating in tandem – the
randomness of EV usage patterns and the possibility of their strategic
behavior. We have shown how this problem can be addressed by means of a
carefully-designed energy storage market. Specifically, we have designed a
mechanism for energy storage markets that guarantees certain incentive and
optimality properties. The mechanism allows the ISO to achieve efficient EV-
power grid integration and satisfy the demand at minimum possible cost.

We have also presented a dynamic programming-based algorithm using which the
ISO can compute its day-ahead market decisions in an EV-integrated power
system. This algorithm has been used to obtain certain numerical results that
demonstrate the cost benefits that EV storage services – unreliable though
they may be – offer the ISO. A few extensions have also been outlined.

## References

  * [1] P. Barter. Cars are parked 95% of the time. Let’s check. Accessed: 01-26-2020. [Online]. Available: https://www.reinventingparking.org/2013/02/cars-are-parked-95-of-time-lets-check.html
  * [2] Sales of Electricity to Ultimate Customers by End-Use Sector. Accessed: 10-10-2020. [Online]. Available: https://www.eia.gov/electricity/annual/html/epa_02_08.html
  * [3] State motor-vehicle registrations - 2017. Accessed: 10-10-2020. [Online]. Available: https://www.fhwa.dot.gov/policyinformation/statistics/2017/mv1.cfm
  * [4] W. Kempton and J. Tomić, “Vehicle-to-grid power fundamentals: Calculating capacity and net revenue,” _Journal of Power Sources_ , vol. 144, no. 1, pp. 268 – 279, 2005. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S0378775305000352
  * [5] C. Guille and G. Gross, “A conceptual framework for the vehicle-to-grid (v2g) implementation,” _Energy Policy_ , vol. 37, no. 11, pp. 4379 – 4390, 2009\. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S0301421509003978
  * [6] V. Robu, E. H. Gerding, S. Stein, D. C. Parkes, A. Rogers, and N. R. Jennings, “An online mechanism for multi-unit demand and its application to plug-in hybrid electric vehicle charging,” _Journal of Artificial Intelligence Research_ , vol. 48, pp. 175–230, 2013.
  * [7] M. M. Nejad, L. Mashayekhy, R. B. Chinnam, and D. Grosu, “Online scheduling and pricing for electric vehicle charging,” _IISE Transactions_ , vol. 49, no. 2, pp. 178–193, 2017. [Online]. Available: https://doi.org/10.1080/0740817X.2016.1213467
  * [8] S. Zou, Z. Ma, X. Liu, and I. Hiskens, “An efficient game for coordinating electric vehicle charging,” _IEEE Transactions on Automatic Control_ , vol. 62, no. 5, pp. 2374–2389, 2017.
  * [9] S. Bhattacharya, K. Kar, J. H. Chow, and A. Gupta, “Extended second price auctions for plug-in electric vehicle (pev) charging in smart distribution grids,” in _2014 American Control Conference_ , 2014, pp. 908–913.
  * [10] W. Saad, Zhu Han, H. V. Poor, and T. Başar, “A noncooperative game for double auction-based energy trading between phevs and distribution grids,” in _2011 IEEE International Conference on Smart Grid Communications (SmartGridComm)_ , 2011, pp. 267–272.
  * [11] B. Satchidanandan and M. A. Dahleh, “A market for trading energy and battery capacity in day-ahead electricity markets,” _2021 American Control Conference, Under review_ , 2021.
  * [12] Powerwall. Accessed: 02-01-2020. [Online]. Available: https://www.tesla.com/powerwall
  * [13] B. Mauch, J. Apt, P. M. Carvalho, and P. Jaramillo, “What day-ahead reserves are needed in electric grids with high levels of wind power?” _Environmental Research Letters_ , vol. 8, no. 3, 2013.
  * [14] J. Taylor. (2012) Markov decision processes: Lecture notes for STP 425. [Online]. Available: https://math.la.asu.edu/~jtaylor/teaching/Fall2012/STP425/lectures/MDP.pdf
  * [15] Markets and Operations. Accessed: 11-10-2020. [Online]. Available: https://www.iso-ne.com/markets-operations

##  Appendix A Proof of Theorem 1

###### Proof.

Arbitrarily fix $i\in\\{1,\ldots,n_{s}\\}$ and $\theta_{i}\in\Theta.$ We begin
the proof with four lemmas.

######  Lemma 1.

There exists $\mathcal{E}_{i}\subset\\{1,\ldots,T\\}^{\infty}$ with
$\mathbb{P}_{\theta_{i}}^{\infty}(\mathcal{E}_{i})=0$ such that for all
$\delta_{i}^{\infty}\notin\mathcal{E}_{i},$

$\displaystyle\lim_{L\to\infty}\frac{1}{L}\sum_{l=1}^{L}J_{p}(l)\mathds{1}_{\\{E_{i}(l,\delta_{i}^{l},\theta_{i})\\}}=0.$
(35)

###### Proof.

See Appendix B. ∎

The next lemma establishes the monotonicity of the optimal cost function
$q^{*}$ in a certain sense.

######  Lemma 2.

Let $\lambda_{i},\widetilde{\lambda}_{i}\in\Theta$ be any two parameters such
that $F_{\widetilde{\lambda}_{i}}(t)\geq F_{{\lambda}_{i}}(t)$ for all
$t\in\\{1,\ldots,T\\}.$ Then,

$\displaystyle q^{*}(\widetilde{\lambda}_{i},\boldsymbol{\phi}_{-i})\geq
q^{*}({\lambda}_{i},\boldsymbol{\phi}_{-i})$

for all $\boldsymbol{\phi}_{-i}\in\Theta^{n_{s}-1}.$

###### Proof.

See Appendix C. ∎

######  Lemma 3.

Suppose that $\phi_{i}$ is such that

$\displaystyle\alpha(\theta_{i},\phi_{i})\coloneqq\sup_{t\in\\{1,\ldots,T\\}}\\{F_{\theta_{i}}(t)-F_{\phi_{i}}(t)\\}>0.$
(36)

Then,

  1. 1.

for some finite $K\geq 0,$

$\displaystyle
q^{*}(\theta_{i},\boldsymbol{\phi}_{-i})-q^{*}(\phi_{i},\boldsymbol{\phi}_{-i})\leq
K\alpha(\theta_{i},\phi_{i}).$ (37)

for all $\boldsymbol{\phi}_{-i}\in\Theta^{n_{s}-1}.$

  2. 2.

There exists $\mathcal{E}_{i}\subset\\{1,\ldots,T\\}^{\infty}$ with
$\mathbb{P}_{\theta_{i}}^{\infty}(\mathcal{E}_{i})=0$ such that for all
$\delta_{i}^{\infty}\notin\mathcal{E}_{i},$

$\displaystyle\lim_{L\to\infty}\frac{1}{L}\sum_{l=1}^{l}\mathds{1}_{\\{\widehat{\delta}_{i}(l)>\delta_{i}(l)\\}}\geq\alpha(\theta_{i},\phi_{i})$
(38)

whenever $\widehat{\delta}_{i}^{\infty}$ is such that
$\sum_{l=1}^{\infty}\mathds{1}_{\\{E_{i}(l,\widehat{\delta}_{i}^{l},\phi_{i})\\}}<\infty.$

###### Proof.

See Appendix D. ∎

######  Lemma 4.

If $\widehat{\delta}_{i}^{\infty}$ such that
$\sum_{l=1}^{\infty}\mathds{1}_{\\{E_{i}(l,\widehat{\delta}_{i}^{l},\phi_{i})\\}}=\infty,$
then,

$\displaystyle\limsup_{L\to\infty}{\frac{1}{L}\sum_{l=1}^{L}J_{p}(l)\mathds{1}_{\\{E_{i}(l,\widehat{\delta}_{i}^{l},\phi_{i})\\}}}=\infty.$
(39)

###### Proof.

See Appendix E. ∎

We are now ready to prove the theorem. We first have

$\displaystyle u^{\infty}_{i}($
$\displaystyle\phi_{i},\widehat{\delta}_{i}^{\infty},\boldsymbol{\phi}_{-i},\widehat{\boldsymbol{\delta}}_{-i}^{\infty},\omega^{\infty}_{\boldsymbol{\pi}^{*}(\boldsymbol{\phi})})$
$\displaystyle=p_{i}^{DA}(\phi_{i},\boldsymbol{\phi}_{-i})$
$\displaystyle\;\;\;\;\;\;+\liminf_{L\to\infty}\frac{1}{L}\sum_{l=1}^{L}\Big{[}p_{i}^{S}(l,\boldsymbol{\phi},\widehat{\delta}_{i}^{l},\widehat{\boldsymbol{\delta}}(l),\omega_{\boldsymbol{\pi}^{*}(\boldsymbol{\phi})}(l))$
$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;\;-c_{i}^{EV}\big{(}\delta_{i}(l),\widehat{\delta}_{i}(l),{\boldsymbol{\pi}}_{i}^{*}(\widehat{\boldsymbol{\delta}}(l),\omega_{\boldsymbol{\pi}^{*}(\boldsymbol{\phi})}(l);\boldsymbol{\phi}\big{)}\Big{]}.$

Substituting (2), (13) and (19) in the above equality and carrying out some
algebra yields

$\displaystyle u^{\infty}_{i}$
$\displaystyle(\phi_{i},\widehat{\delta}_{i}^{\infty},\boldsymbol{\phi}_{-i},\widehat{\boldsymbol{\delta}}_{-i}^{\infty},\omega^{\infty}_{\boldsymbol{\pi}^{*}(\boldsymbol{\phi})})$
$\displaystyle=\big{[}q^{*}(\boldsymbol{\phi}_{-i})-q^{*}(\boldsymbol{\phi})\big{]}$
$\displaystyle\;\;\;\;-\limsup_{L\to\infty}\frac{1}{L}\sum_{l=1}^{L}\Big{[}J_{p}(l)\mathds{1}_{\\{E_{i}(l,\widehat{\delta}_{i}^{l},\phi_{i})\\}}$
$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;+J_{m}\mathds{1}_{\\{\widehat{\delta}_{i}(l)>\delta_{i}(l)\\}}\Big{]}$
$\displaystyle\;\;\;\;-\limsup_{L\to\infty}\frac{1}{L}\sum_{l=1}^{L}\Big{[}{\pi}_{i}^{*}(\widehat{\delta}_{i}(l),\widehat{\boldsymbol{\delta}}(l),\omega_{\boldsymbol{\pi}^{*}(\boldsymbol{\phi})}(l);\boldsymbol{\phi})$
$\displaystyle\;\;\;\;\;\;\;\;\;-\pi_{i}^{*}(\widehat{\delta}_{i}(l),\widehat{\boldsymbol{\delta}}(l),\omega_{\boldsymbol{\pi}^{*}(\boldsymbol{\phi})}(l);\boldsymbol{\phi})\mathds{1}_{\\{\widehat{\delta}_{i}(l)\leq\delta_{i}(l)\\}}\Big{]}.$
(40)

Using the above expression, applying Lemma 1, and carrying out some algebra
implies the existence of $\mathcal{E}_{i}\subset\\{1,\ldots,T\\}^{\infty}$
with $\mathbb{P}_{\theta_{i}}^{\infty}(\mathcal{E}_{i})=0$ such that for all
$\delta_{i}^{\infty}\notin\mathcal{E}_{i},$

$\displaystyle u^{\infty}_{i}$
$\displaystyle(\theta_{i},{\delta}_{i}^{\infty},\boldsymbol{\phi}_{-i},\widehat{\boldsymbol{\delta}}_{-i}^{\infty},\omega^{\infty}_{\boldsymbol{\pi}^{*}([\theta_{i},\boldsymbol{\phi}_{-i}])})$
$\displaystyle-u^{\infty}_{i}(\phi_{i},\widehat{\delta}_{i}^{\infty},\boldsymbol{\phi}_{-i},\widehat{\boldsymbol{\delta}}_{-i}^{\infty},\omega^{\infty}_{\boldsymbol{\pi}^{*}(\boldsymbol{\phi})})$
$\displaystyle\;\;\;\;=\big{[}q^{*}(\phi_{i},\boldsymbol{\phi}_{-i})-q^{*}(\theta_{i},\boldsymbol{\phi}_{-i})\big{]}$
$\displaystyle\;\;\;\;\;\;\;\;+\limsup_{L\to\infty}\frac{1}{L}\sum_{l=1}^{L}\Big{[}J_{p}(l)\mathds{1}_{\\{E_{i}(l,\widehat{\delta}_{i}^{l},\phi_{i})\\}}\Big{]}$
$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;+\limsup_{L\to\infty}\frac{1}{L}\sum_{l=1}^{L}\Big{[}{\pi}_{i}^{*}(\widehat{\delta}_{i}(l),\widehat{\boldsymbol{\delta}}(l),\omega_{\boldsymbol{\pi}^{*}(\boldsymbol{\phi})}(l);\boldsymbol{\phi})$
$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;-\pi_{i}^{*}(\widehat{\delta}_{i}(l),\widehat{\boldsymbol{\delta}}(l),\omega_{\boldsymbol{\pi}^{*}(\boldsymbol{\phi})}(l);\boldsymbol{\phi})\mathds{1}_{\\{\widehat{\delta}_{i}(l)\leq\delta_{i}(l)\\}}\Big{]}$
$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;+\limsup_{L\to\infty}\frac{1}{L}\sum_{l=1}^{L}J_{m}\mathds{1}_{\\{\widehat{\delta}_{i}(l)>\delta_{i}(l)\\}}.$
(41)

We first show that the above random variable is nonnegative, thereby
establishing (21). We do this by considering three cases and showing that (41)
is nonnegative in all the three cases.

We first consider the case when $\widehat{\delta}_{i}^{\infty}$ is such that
$\sum_{l=1}^{\infty}\mathds{1}_{\\{E_{i}(l,\widehat{\delta}_{i}^{l},\phi_{i})\\}}=\infty.$
Note that
$\big{|}q^{*}(\phi_{i},\boldsymbol{\phi}_{-i})-q^{*}(\theta_{i},\boldsymbol{\phi}_{-i})\big{|}<\infty$
owing to (9), and that all other terms in the RHS of (41) are nonnegative.
Consequently, substituting (39) in (41) implies the nonnegativity of the (41).

We next consider the case when $\phi_{i}$ is such that $F_{\theta_{i}}(t)\leq
F_{\phi_{i}}(t)$ for all $t\in\\{1,\ldots,T\\}.$ It then follows from Lemma 2
that $q^{*}(\phi_{i},\boldsymbol{\phi}_{-i})\geq
q^{*}(\theta_{i},\boldsymbol{\phi}_{-i}),$ and so the first term in the RHS of
(41) is nonnegative. Since every other term in the RHS of (41) is nonnegative,
(41) is nonnegative.

We are finally left with the case when $\widehat{\delta}_{i}^{\infty}$ is such
that
$\sum_{l=1}^{\infty}\mathds{1}_{\\{E_{i}(l,\widehat{\delta}_{i}^{l},\phi_{i})\\}}<\infty$
and $\phi_{i}$ is such that $F_{\theta_{i}}(t)>F_{\phi_{i}}(t)$ for some
$t\in\\{1,\ldots,T\\}.$ Lemma 3 applies, and so combining (37) and (38) with
(41) implies that $\mathbb{P}_{\theta_{i}}^{\infty}-$ almost surely,

$\displaystyle
u^{\infty}_{i}(\theta_{i},{\delta}_{i}^{\infty},\boldsymbol{\phi}_{-i},\widehat{\boldsymbol{\delta}}_{-i}^{\infty},\omega^{\infty}_{\boldsymbol{\pi}^{*}([\theta_{i},\boldsymbol{\phi}_{-i}])}$
$\displaystyle)$
$\displaystyle-u^{\infty}_{i}(\phi_{i},\widehat{\delta}_{i}^{\infty},\boldsymbol{\phi}_{-i},\widehat{\boldsymbol{\delta}}_{-i}^{\infty},$
$\displaystyle\omega^{\infty}_{\boldsymbol{\pi}^{*}(\boldsymbol{\phi})})$
$\displaystyle\geq(J_{m}$ $\displaystyle-K)\alpha(\theta_{i},\phi_{i}).$

It follows that for $J_{m}\geq K,$ the LHS is nonnegative, thereby completing
the proof of (21).

We next prove the second statement of the theorem. Suppose that (23) holds.
Using (40) to expand both sides of (23), invoking (35), and simplifying the
result implies that for every $\delta_{i}^{\infty}\notin\mathcal{E}_{i}$,
$\boldsymbol{\phi}_{-i},$ $\widehat{\boldsymbol{\delta}}^{\infty},$
$\omega^{\infty}_{\boldsymbol{\pi}^{*}(\boldsymbol{\phi})},\omega^{\infty}_{\boldsymbol{\pi}^{*}([\theta_{i},\boldsymbol{\phi}_{-i}])}$,
there exists $\widehat{\delta}_{i}^{\infty}$ such that,

$\displaystyle q^{*}($
$\displaystyle\theta_{i},\boldsymbol{\phi}_{-i})-q^{*}(\phi_{i},\boldsymbol{\phi}_{-i})$
$\displaystyle=\limsup_{L\to\infty}\frac{1}{L}\sum_{l=1}^{L}J_{p}(l)\mathds{1}_{E_{i}(l,\widehat{\delta}_{i}^{l},\phi_{i})}$
$\displaystyle\;\;\;\;\;\;+\limsup_{L\to\infty}\frac{1}{L}\sum_{l=1}^{L}\Big{[}{\pi}_{i}^{*}(\widehat{\delta}_{i}(l),\widehat{\boldsymbol{\delta}}(l),\omega_{\boldsymbol{\pi}^{*}(\boldsymbol{\phi})}(l);\boldsymbol{\phi})$
$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;\;-\pi_{i}^{*}(\widehat{\delta}_{i}(l),\widehat{\boldsymbol{\delta}}(l),\omega_{\boldsymbol{\pi}^{*}(\boldsymbol{\phi})}(l);\boldsymbol{\phi})\mathds{1}_{\\{\widehat{\delta}_{i}(l)\leq\delta_{i}(l)\\}}\Big{]}$
$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;+J_{m}\limsup_{L\to\infty}\frac{1}{L}\sum_{l=1}^{L}\mathds{1}_{\\{\widehat{\delta}_{i}(l)>\delta_{i}(l)\\}}.$
(42)

Since the RHS of the above equality is always nonnegative, we have that
$q^{*}(\theta_{i},\boldsymbol{\phi}_{-i})-q^{*}(\phi_{i},\boldsymbol{\phi}_{-i})\geq
0$ for every $\boldsymbol{\phi}_{-i}.$ We show next that this inequality must
hold with equality for all $\boldsymbol{\phi}_{-i}$.

Suppose for contradiction that
$q^{*}(\theta_{i},\boldsymbol{\phi}_{-i})-q^{*}(\phi_{i},\boldsymbol{\phi}_{-i})>0$
for some $\boldsymbol{\phi}_{-i}.$ Lemma 2 implies that
$\sup_{t\in\\{1,\ldots,T\\}}\\{F_{\theta_{i}}(t)-F_{\phi_{i}}(t)\\}=\alpha(\theta_{i},\phi_{i})>0$,
and so Lemma 3 applies. Hence,

$\displaystyle
q^{*}(\theta_{i},\boldsymbol{\phi}_{-i})-q^{*}(\phi_{i},\boldsymbol{\phi}_{-i})\leq
K\alpha(\theta_{i},\phi_{i}).$ (43)

Since the LHS of (42) is finite following (9), the RHS must also be finite.
This implies in particular that the first term of the RHS is finite, and so,
it follows from Lemma 4 that
$\sum_{l=1}^{\infty}\mathds{1}_{\\{E_{i}(l,\widehat{\delta}_{i}^{l},\phi_{i})\\}}<\infty.$
Consequently, (38) holds, and substituting it in (42) implies that
$\mathbb{P}_{\theta_{i}}^{\infty}-$ almost surely,

$\displaystyle
q^{*}(\theta_{i},\boldsymbol{\phi}_{-i})-q^{*}(\phi_{i},\boldsymbol{\phi}_{-i})\geq
J_{m}\alpha(\theta_{i},\phi_{i}).$ (44)

Combining (43) and (44) yields a contradiction for $J_{m}>K.$ Hence, if (23)
holds, then,

$\displaystyle
q^{*}(\theta_{i},\boldsymbol{\phi}_{-i})=q^{*}(\phi_{i},\boldsymbol{\phi}_{-i}).$
(45)

for all $\boldsymbol{\phi}_{-i}.$

Now, since (22) holds, combining it with (45) immediately establishes (24),
i.e., that $\phi_{i}=\theta_{i}.$ Consequently, the RHS of (42) is zero, and
since every term in the RHS of (42) is nonnegative, it follows that every term
is zero. Hence,

$\displaystyle\lim_{L\to\infty}\frac{1}{L}\sum_{l=1}^{L}J_{p}(l)\mathds{1}_{E_{i}(l,\widehat{\delta}_{i}^{l},\theta_{i})}=0$
(46)

and

$\displaystyle\lim_{L\to\infty}\frac{1}{L}\sum_{l=1}^{L}\mathds{1}_{\\{\widehat{\delta}_{i}(l)>\delta_{i}(l)\\}}=0$
(47)

$\mathbb{P}_{\theta_{i}}^{\infty}-$ almost surely.

From (46), we get
$\lim_{L\to\infty}\frac{1}{L}\sum_{l=1}^{L}\mathds{1}_{E_{i}(l,\widehat{\delta}_{i}^{l},\theta_{i})}=0,$
which implies using (17) that for every $t\in\\{1,\ldots,T\\},$

$\displaystyle\lim_{L\to\infty}\frac{1}{L}\sum_{l=1}^{L}\mathds{1}_{\\{|{f}_{i,t}(l,\widehat{\delta}_{i}^{l},\theta_{i})|\geq
r(l)\\}}=0.$ (48)

Since $|{f}_{i,t}(l,\widehat{\delta}_{i}^{l},\theta_{i})|\leq 1,$ we have that
for all $t\in\\{1,\ldots,T\\}$ and all $L\in\mathbb{N},$

$\displaystyle\sum_{l=1}^{L}{|{f}_{i,t}(l,\widehat{\delta}_{i}^{l},\theta_{i})|}\leq\sum_{l=1}^{L}$
$\displaystyle\mathds{1}_{\\{|{f}_{i,t}(l,\widehat{\delta}_{i}^{l},\theta_{i})|\geq
r(l)\\}}$
$\displaystyle+\sum_{l=1}^{L}r(l)\mathds{1}_{\\{|{f}_{i,t}(l,\widehat{\delta}_{i}^{l},\theta_{i})|<r(l)\\}}.$

Dividing this inequality by $L$ and taking the limit as $L\to\infty$ implies
that for all $t\in\\{1,\ldots,T\\},$

$\displaystyle\limsup_{L\to\infty}\frac{1}{L}\sum_{l=1}^{L}$
$\displaystyle{|{f}_{i,t}(l,\widehat{\delta}_{i}^{l},\theta_{i})|}$
$\displaystyle\leq\limsup_{L\to\infty}$
$\displaystyle\frac{1}{L}\sum_{l=1}^{L}\mathds{1}_{\\{|{f}_{i,t}(l,\widehat{\delta}_{i}^{l},\theta_{i})|\geq
r(l)\\}}$
$\displaystyle+\limsup_{L\to\infty}\frac{1}{L}\sum_{l=1}^{L}r(l)\mathds{1}_{\\{|{f}_{i,t}(l,\widehat{\delta}_{i}^{l},\theta_{i})|<r(l)\\}}.$

We have using (16) that the last term of the RHS of the above inequality
equals zero, and using (48) that its first term is zero. Hence, for all
$t\in\\{1,\ldots,T\\},$ we have
$\lim_{L\to\infty}\frac{1}{L}\sum_{l=1}^{L}{|{f}_{i,t}(l,\widehat{\delta}_{i}^{l},\theta_{i})|}=0.$
This implies using (14) that for all $t\in\\{1,\ldots,T\\},$
$\lim_{L\to\infty}\frac{1}{L}\sum_{l=1}^{L}{\bigg{[}\frac{1}{l}\sum_{l^{\prime}=1}^{l}\mathds{1}_{\\{\widehat{\delta}_{i}(l^{\prime})=t\\}}\bigg{]}}=\mathbb{P}_{\theta_{i}}(t).$
Multiplying this equality by $t$, summing both sides over $t$, and simplifying
yields

$\displaystyle\lim_{L\to\infty}\frac{1}{L}\sum_{l=1}^{L}\bigg{[}\frac{1}{l}{\sum_{l^{\prime}=1}^{l}\widehat{\delta}_{i}(l^{\prime})}\bigg{]}=\mu(\theta_{i}),$
(49)

where $\mu(\theta_{i})\coloneqq\sum_{t=1}^{T}t\mathbb{P}_{\theta_{i}}(t)$ is
the expected value of the distribution corresponding to the parameter
$\theta_{i}.$ Next, we use this to show that
$\lim_{L\to\infty}\frac{1}{L}\sum_{l=1}^{L}\mathds{1}_{\\{\widehat{\delta}_{i}(l)<\delta_{i}(l)\\}}=0,$
which when combined with (47) would establish (25).

Suppose for contradiction that for some $\epsilon>0,$

$\displaystyle\limsup_{L\to\infty}\frac{1}{L}\sum_{l=1}^{L}\mathds{1}_{\\{\widehat{\delta}_{i}(l)<\delta_{i}(l)\\}}=\epsilon.$
(50)

Note that

$\displaystyle\limsup_{L\to\infty}\bigg{[}\frac{1}{L}\sum_{l=1}^{L}\widehat{\delta}_{i}(l)\bigg{]}$
$\displaystyle\;\;\>\;\;\;=\limsup_{L\to\infty}\bigg{[}\frac{1}{L}{\sum_{l=1}^{L}\widehat{\delta}_{i}(l)}\mathds{1}_{\\{\widehat{\delta}_{i}(l)=\delta_{i}(l)\\}}\bigg{]}$
$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;\;\;+\limsup_{L\to\infty}\bigg{[}\frac{1}{L}{\sum_{l=1}^{L}\widehat{\delta}_{i}(l)}\mathds{1}_{\\{\widehat{\delta}_{i}(l)<\delta_{i}(l)\\}}\bigg{]}$
$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;+\limsup_{L\to\infty}\bigg{[}\frac{1}{L}{\sum_{l=1}^{L}\widehat{\delta}_{i}(l)}\mathds{1}_{\\{\widehat{\delta}_{i}(l)>\delta_{i}(l)\\}}\bigg{]}.$
(51)

Now,

$\displaystyle\limsup_{L\to\infty}\bigg{[}\frac{1}{L}\sum_{l=1}^{L}$
$\displaystyle\widehat{\delta}_{i}(l)\mathds{1}_{\\{\widehat{\delta}_{i}(l)<\delta_{i}(l)\\}}\bigg{]}$
$\displaystyle<\limsup_{L\to\infty}\bigg{[}\frac{1}{L}$
$\displaystyle{\sum_{l=1}^{L}\widehat{\delta}_{i}(l)}\mathds{1}_{\\{\widehat{\delta}_{i}(l)<\delta_{i}(l)\\}}\bigg{]}+\epsilon$
$\displaystyle=\limsup_{L\to\infty}$
$\displaystyle\bigg{[}\frac{1}{L}{\sum_{l=1}^{L}\big{(}\widehat{\delta}_{i}(l)+1\big{)}}\mathds{1}_{\\{\widehat{\delta}_{i}(l)<\delta_{i}(l)\\}}\bigg{]}$
$\displaystyle\leq\limsup_{L\to\infty}\bigg{[}\frac{1}{L}{\sum_{l=1}^{L}{\delta}_{i}(l)}\mathds{1}_{\\{\widehat{\delta}_{i}(l)<\delta_{i}(l)\\}}\bigg{]},$

where the equality follows from (50). It follows from (47) that the last term
in the RHS of (51) is $\mathbb{P}_{\theta_{i}}^{\infty}-$ almost surely zero,
and so substituting this and the above inequality in (51) implies that
$\mathbb{P}_{\theta_{i}}^{\infty}-$ almost surely,

$\displaystyle\limsup_{L\to\infty}\bigg{[}\frac{1}{L}{\sum_{l=1}^{L}\widehat{\delta}_{i}(l)}\bigg{]}<\limsup_{L\to\infty}\bigg{[}\frac{1}{L}{\sum_{l=1}^{L}{\delta}_{i}(l)}\mathds{1}_{\\{\widehat{\delta}_{i}(l)\leq\delta_{i}(l)\\}}\bigg{]}.$

It follows from (47) and SLLN that the RHS of the above inequality
$\mathbb{P}_{\theta_{i}}^{\infty}-$ almost surely equals $\mu(\theta_{i})$,
and so,
$\limsup_{L\to\infty}\frac{1}{L}{\sum_{l=1}^{L}\widehat{\delta}_{i}(l)}<\mu(\theta_{i}).$
Combining this inequality with (49) yields a contradiction. Hence,
$\lim_{L\to\infty}\frac{1}{L}\sum_{l=1}^{L}\mathds{1}_{\\{\widehat{\delta}_{i}(l)<\delta_{i}(l)\\}}=0,$
and combining this with (47) establishes (25).

We now prove the third part of the theorem. Using (40) to compute
$u^{\infty}_{i}(\theta_{i},{\delta}_{i}^{\infty},\boldsymbol{\phi}_{-i},\widehat{\boldsymbol{\delta}}_{-i}^{\infty},\omega^{\infty}_{\boldsymbol{\pi}^{*}(\theta_{i},\boldsymbol{\phi}_{-i})})$
yields

$\displaystyle u^{\infty}_{i}(\theta_{i},{\delta}_{i}^{\infty},$
$\displaystyle\boldsymbol{\phi}_{-i},\widehat{\boldsymbol{\delta}}_{-i}^{\infty},\omega^{\infty}_{\boldsymbol{\pi}^{*}(\theta_{i},\boldsymbol{\phi}_{-i})})$
$\displaystyle=\big{[}q^{*}(\boldsymbol{\phi}_{-i})-q^{*}(\theta_{i},\boldsymbol{\phi}_{-i})\big{]}$
$\displaystyle\;\;\;\;\;\;\;\;-\limsup_{L\to\infty}\frac{1}{L}\sum_{l=1}^{L}\Big{[}J_{p}(l)\mathds{1}_{\\{E_{i}(l,{\delta}_{i}^{l},\theta_{i})\\}}\Big{]}.$

Substituting (35) in the above equality and noting that
$[q^{*}(\boldsymbol{\phi}_{-i})-q^{*}(\theta_{i},\boldsymbol{\phi}_{-i})]\geq
0$ establishes (26).

Finally, (27) follows by substituting (24) in the LHS of (27) and using (25)
and SLLN to simplify the result. ∎

##  Appendix B Proof of Lemma 1

###### Proof.

Denote by
$\sigma^{2}_{t}=\mathbb{P}_{\theta_{i}}(t)\big{(}1-\mathbb{P}_{\theta_{i}}(t)\big{)}$
the variance of the random variable
$\mathds{1}_{\\{\delta_{i}(1)=t\\}}-\mathbb{P}_{\theta_{i}}(t).$ Since
$\delta_{i}^{\infty}$ is drawn IID from the distribution
$\mathbb{P}_{\theta_{i}},$ it follows from the Central Limit Theorem (CLT)
that for any $z\in\mathbb{R},$

$\displaystyle\lim_{l\to\infty}\sup_{z\in\mathbb{R}}\Big{|}\mathbb{P}\\{\sqrt{l}{f}_{i,t}(l,\delta_{i}^{l},\theta_{i})\leq
z\\}-Q\big{(}\frac{z}{\sigma_{t}}\big{)}\Big{|}=0$ (52)

for all $t\in\\{1,\ldots,T\\},$ where $Q$ denotes the cumulative distribution
function of the standard normal distribution. Define

$\displaystyle\widetilde{r}(l)\coloneqq r(l)\sqrt{l}.$ (53)

It follows from (52) that

$\displaystyle\lim_{l\to\infty}\sup_{q\in\mathbb{N}}\Big{|}\mathbb{P}\\{\sqrt{l}{f}_{i,t}(l,\delta_{i}^{l},\theta_{i})\leq-\widetilde{r}(q)\\}-Q\big{(}\frac{-\widetilde{r}(q)}{\sigma_{t}}\big{)}\Big{|}=0.$

Hence,

$\displaystyle\lim_{l\to\infty}\Big{|}\mathbb{P}\\{\sqrt{l}{f}_{i,t}(l,\delta_{i}^{l},\theta_{i})\leq-\widetilde{r}(l)\\}-Q\big{(}\frac{-\widetilde{r}(l)}{\sigma_{t}}\big{)}\Big{|}=0,$

which using (53) becomes

$\displaystyle\lim_{l\to\infty}\Big{|}\mathbb{P}\\{{f}_{i,t}(l,\delta_{i}^{l},\theta_{i})\leq-{r}(l)\\}-Q\big{(}\frac{-\widetilde{r}(l)}{\sigma_{t}}\big{)}\Big{|}=0.$

The above equality implies that for every $\epsilon_{0}>0,$ there exists
$L_{0}\in\mathbb{N}$ such that for all $l\geq L_{0},$

$\displaystyle-\epsilon_{0}\leq\mathbb{P}\\{{f}_{i,t}(l,\delta_{i}^{l},\theta_{i})\leq{-r(l)}\\}-Q\big{(}\frac{-\widetilde{r}(l)}{\sigma_{t}}\big{)}\leq\epsilon_{0}.$

Using the bound $Q(z)\leq e^{-{z^{2}}/{2}}$ for $z\leq 0,$ the above
inequality implies that for all $l\geq L_{0},$

$\displaystyle\mathbb{P}\\{{f}_{i,t}(l,\delta_{i}^{l},\theta_{i})\leq{-r(l)}\\}\leq
e^{-{\widetilde{r}^{2}(l)}/{2\sigma_{t}^{2}}}+\epsilon_{0}.$

It follows from (15) and (53) that
$\widetilde{r}(l)\geq\sqrt{\ln{l^{\gamma}}}$ for all $l\geq L_{r}.$ Combining
this with the above inequality and simplifying yields that for all
$l\geq\max{\\{L_{r},L_{0}\\}},$

$\displaystyle\mathbb{P}\\{{f}_{i,t}(l,\delta_{i}^{l},\theta_{i})\leq{-r(l)}\\}\leq\frac{1}{l^{(\frac{\gamma}{2\sigma_{t}^{2}})}}+\epsilon_{0},$

and so, letting $\epsilon_{0}\downarrow 0$ and noting that
$2\sigma_{t}^{2}\leq\frac{1}{2}$ implies

$\displaystyle\mathbb{P}\\{{f}_{i,t}(l,\delta_{i}^{l},\theta_{i})\\}\leq{-r(l)}\\}=O\Big{(}\frac{1}{l^{2\gamma}}\Big{)}.$

Since $\gamma>\frac{1}{2},$ the above equality implies

$\displaystyle\sum_{l=1}^{\infty}\mathbb{P}\\{{f}_{i,t}(l,\delta_{i}^{l},\theta_{i})\leq{-r(l)}\\}<\infty.$
(54)

It can be shown by following the same sequence of arguments that

$\displaystyle\sum_{l=1}^{\infty}\mathbb{P}\\{{f}_{i,t}(l,\delta_{i}^{l},\theta_{i})\geq{r(l)}\\}<\infty.$
(55)

Combining (54) and (55) implies

$\displaystyle\sum_{l=1}^{\infty}\mathbb{P}\\{\big{|}{f}_{i,t}(l,\delta_{i}^{l},\theta_{i})\big{|}\geq{r(l)}\\}<\infty.$

Since the above inequality holds for arbitrary $t\in\\{1,\ldots,T\\},$ it
follows that
$\sum_{l=1}^{\infty}\mathbb{P}\\{E_{i}(l,\delta_{i}^{l},\theta_{i})\\}<\infty.$
Invoking the Borel-Cantelli lemma yields

$\displaystyle\sum_{l=1}^{\infty}\mathds{1}_{\\{E_{i}(l,\delta_{i}^{l},\theta_{i})\\}}<\infty$

almost surely, and (35) follows. ∎

##  Appendix C Proof of Lemma 2

###### Proof.

Since $F_{\widetilde{\lambda}_{i}}(t)\geq F_{\lambda_{i}}(t)$ for every
$t\in\\{1,\ldots,T\\},$ there exists a probability space
$(\Omega_{\kappa},\mathcal{F}_{\kappa},\mathbb{P}_{\kappa})$ and a function
$f_{S}\mathrel{\mathop{\mathchar
58\relax}}\\{1,\ldots,T\\}\times\Omega_{\kappa}\to\\{1,\ldots,T\\}$ such that

$\displaystyle f_{S}(t,\zeta)\leq t$ (56)

for all $t\in\\{1,\ldots,T\\}$ and all $\zeta\in\Omega_{\kappa}$, and

$\displaystyle f_{S}(t,\zeta)\sim\mathbb{P}_{\widetilde{\lambda}_{i}}$ (57)

when $t\sim\mathbb{P}_{\lambda_{i}}$ and $\zeta\sim\mathbb{P}_{\kappa}.$

Now, fix $\boldsymbol{\phi}_{-i}$ arbitrarily and define a storage policy
$\boldsymbol{\nu}$ as follows. For each $j\in\\{1,\ldots,n_{s}\\},$ define

$\displaystyle\nu_{j}(t,\boldsymbol{\delta},(\zeta,\omega))=\pi_{j}^{*}\big{(}t,[f_{S}(\delta_{i},\zeta),\boldsymbol{\delta}_{-i}],\omega\;;[\widetilde{\lambda}_{i},\boldsymbol{\phi}_{-i}]\big{)},$
(58)

with
$(\zeta,\omega)\sim\mathbb{P}_{\kappa}\times\mathbb{P}_{\boldsymbol{\pi}^{*}([\widetilde{\lambda}_{i},\boldsymbol{\phi}_{-i}])}.$
In words, the policy $\boldsymbol{\nu}$ is the result of implementing the
policy
$\boldsymbol{\pi}^{*}([\widetilde{\lambda}_{i},\boldsymbol{\phi}_{-i}])$ under
the pretense that the deadline of EV $i$ is $f_{S}(\delta_{i},\zeta)$ when it
is in fact $\delta_{i}.$ It is straightforward to verify using (56) that if
the policy
$\boldsymbol{\pi}^{*}([\widetilde{\lambda}_{i},\boldsymbol{\phi}_{-i}])$ is
implementable, then so is the policy $\boldsymbol{\nu}$. For each
$j\in\\{1,\ldots,n_{s}\\}$, define

$\displaystyle\overline{\nu}_{j}(t,\boldsymbol{\delta},\zeta)\coloneqq\mathbb{E}_{\omega\sim\mathbb{P}_{\boldsymbol{\pi}^{*}([\widetilde{\lambda}_{i},\boldsymbol{\phi}_{-i}])}}\big{[}\nu_{j}(t,\boldsymbol{\delta},(\zeta,\omega))\big{]}$
(59)

and

$\displaystyle\widehat{\nu}_{j}(t,\boldsymbol{\delta})\coloneqq\mathbb{E}_{(\zeta,\omega)\sim\mathbb{P}_{\kappa}\times\mathbb{P}_{\boldsymbol{\pi}^{*}([\widetilde{\lambda}_{i},\boldsymbol{\phi}_{-i}])}}\big{[}\nu_{j}(t,\boldsymbol{\delta},(\zeta,\omega))\big{]}$

so that

$\displaystyle\widehat{\nu}_{j}(t,\boldsymbol{\delta})=\mathbb{E}_{\zeta\sim\mathbb{P}_{\kappa}}\big{[}\overline{\nu}_{j}(t,\boldsymbol{\delta},\zeta)\big{]}$

and

$\displaystyle\mathbb{E}_{(\boldsymbol{\delta},\zeta)\sim\mathbb{P}_{([\lambda_{i},\boldsymbol{\phi}_{-i}])}\times\mathbb{P}_{\kappa}}\big{[}\overline{\nu}_{j}(t,\boldsymbol{\delta},\zeta)\big{]}=\mathbb{E}_{\boldsymbol{\delta}\sim\mathbb{P}_{(\lambda_{i},\boldsymbol{\phi}_{-i})}}\big{[}\widehat{\nu}_{j}(t,\boldsymbol{\delta})\big{]}.$
(60)

Substituting (58) and (6) in (59), we obtain

$\displaystyle\overline{\nu}_{j}(t,\boldsymbol{\delta},\zeta)=\widehat{\pi}^{*}_{j}\big{(}t,[f_{S}(\delta_{i},\zeta),\boldsymbol{\delta}_{-i}];[\widetilde{\lambda}_{i},\boldsymbol{\phi}_{-i}]\big{)},$

and so

$\displaystyle\mathbb{E}_{(\boldsymbol{\delta},\zeta)\sim\mathbb{P}_{(\lambda_{i},\boldsymbol{\phi}_{-i})}\times\mathbb{P}_{\kappa}}\big{[}\overline{\nu}_{j}(t,$
$\displaystyle\boldsymbol{\delta},\zeta)\big{]}$
$\displaystyle=\mathbb{E}_{(\boldsymbol{\delta},\zeta)\sim\mathbb{P}_{(\lambda_{i},\boldsymbol{\phi}_{-i})}\times\mathbb{P}_{\kappa}}$
$\displaystyle\big{[}\widehat{\pi}^{*}_{j}\big{(}t,[f_{S}(\delta_{i},\zeta),\boldsymbol{\delta}_{-i}];[\widetilde{\lambda}_{i},\boldsymbol{\phi}_{-i}]\big{)}\big{]}$
$\displaystyle=$
$\displaystyle\mathbb{E}_{\boldsymbol{\delta}^{\prime}\sim\mathbb{P}_{(\widetilde{\lambda}_{i},\boldsymbol{\phi}_{-i})}}\big{[}\widehat{\pi}^{*}_{j}(t,\boldsymbol{\delta}^{\prime};(\widetilde{\lambda}_{i},\boldsymbol{\phi}_{-i}))\big{]},$

where the last equality follows from the fact that
$f_{S}(\delta_{i},\zeta)\sim\mathbb{P}_{\widetilde{\lambda}_{i}}$ and so
$[f_{S}(\delta_{i},\zeta),\boldsymbol{\delta}_{-i}]\sim\mathbb{P}_{([\widetilde{\lambda}_{i},\boldsymbol{\phi}_{-i}])}$.
Substituting this in (60) yields

$\displaystyle\mathbb{E}_{\boldsymbol{\delta}\sim\mathbb{P}_{(\lambda_{i},\boldsymbol{\phi}_{-i})}}\big{[}\widehat{\nu}_{j}(t,\boldsymbol{\delta})\big{]}=\mathbb{E}_{\boldsymbol{\delta}^{\prime}\sim\mathbb{P}_{(\widetilde{\lambda}_{i},\boldsymbol{\phi}_{-i})}}\big{[}\widehat{\pi}^{*}_{j}\big{(}t,\boldsymbol{\delta}^{\prime};[\widetilde{\lambda}_{i},\boldsymbol{\phi}_{-i}]\big{)}\big{]}.$
(61)

Next, we have for every $t\in\\{1,\ldots,T\\}$ and every
$\boldsymbol{\delta}\in\\{1,\ldots,T\\}^{n_{s}},$

$\displaystyle
g_{s}(t,\boldsymbol{\delta};\mathbf{g}^{*}([\widetilde{\lambda}_{i},\boldsymbol{\phi}_{-i}]),\boldsymbol{\nu},(\zeta,\omega))$
$\displaystyle=d(t)-g^{*}(t;[\widetilde{\lambda}_{i},\boldsymbol{\phi}_{-i}])$
$\displaystyle-\sum_{j=1}^{n_{s}}\bigg{[}\nu_{j}\big{(}t,\boldsymbol{\delta},(\zeta,\omega)\big{)}$
$\displaystyle-\nu_{j}\big{(}t-1,\boldsymbol{\delta},(\zeta,\omega)\big{)}\bigg{]}$
$\displaystyle=d(t)-g^{*}(t;[\widetilde{\lambda}_{i},\boldsymbol{\phi}_{-i}])$
$\displaystyle-\sum_{j=1}^{n_{s}}\bigg{[}\pi^{*}_{j}(t,[f_{S}(\delta_{i},\zeta),$
$\displaystyle\boldsymbol{\delta}_{-i}],\omega;[\widetilde{\lambda}_{i},\boldsymbol{\phi}_{-i}])$
$\displaystyle-\pi^{*}_{j}(t-1,$
$\displaystyle[f_{S}(\delta_{i},\zeta),\boldsymbol{\delta}_{-i}],\omega;[\widetilde{\lambda}_{i},\boldsymbol{\phi}_{-i}])\bigg{]}$
$\displaystyle=g_{s}(t,[f_{S}(\delta_{i},\zeta),\boldsymbol{\delta}_{-i}];\mathbf{g}^{*}($
$\displaystyle[\widetilde{\lambda}_{i},\boldsymbol{\phi}_{-i}]),\boldsymbol{\pi}^{*}([\widetilde{\lambda}_{i},\boldsymbol{\phi}_{-i}]),\omega),$

where the first and the last equalities follow from (3), and the second
equality follows from (58). Hence,

$\displaystyle c^{s}(\mathbf{g}_{s}\big{(}$
$\displaystyle\boldsymbol{\delta}\;;\;\mathbf{g}^{*}([\widetilde{\lambda}_{i},\boldsymbol{\phi}_{-i}]),\boldsymbol{\nu},(\zeta,\omega)\big{)})$
$\displaystyle=c^{s}$
$\displaystyle(\mathbf{g}_{s}\big{(}[f_{S}(\delta_{i},\zeta),\boldsymbol{\delta}_{-i}]\;;\;\mathbf{g}^{*}([\widetilde{\lambda}_{i},\boldsymbol{\phi}_{-i}]),\boldsymbol{\pi}^{*}([\widetilde{\lambda}_{i},\boldsymbol{\phi}_{-i}]),\omega\big{)}).$

Taking expectation on both sides of the equality with respect to
$\omega\sim\mathbb{P}_{\boldsymbol{\pi}^{*}([\widetilde{\lambda}_{i},\boldsymbol{\phi}_{-i}])}$
and using (5) gives

$\displaystyle\mathbb{E}_{\omega\sim\mathbb{P}_{\boldsymbol{\pi}^{*}([\widetilde{\lambda}_{i},\boldsymbol{\phi}_{-i}])}}$
$\displaystyle
c^{s}(\mathbf{g}_{s}(\boldsymbol{\delta};\mathbf{g}^{*}([\widetilde{\lambda}_{i},\boldsymbol{\phi}_{-i}]),\boldsymbol{\nu},(\zeta,\omega)))$
$\displaystyle=\widehat{c^{s}}$
$\displaystyle([f_{S}(\delta_{i},\zeta),\boldsymbol{\delta}_{-i}];\mathbf{g}^{*}([\widetilde{\lambda}_{i},\boldsymbol{\phi}_{-i}]),\boldsymbol{\pi}^{*}([\widetilde{\lambda}_{i},\boldsymbol{\phi}_{-i}]))).$

Consequently,

$\displaystyle\widehat{c^{s}}(\boldsymbol{\delta}\;;\;\mathbf{g}^{*}([\widetilde{\lambda}_{i},\boldsymbol{\phi}_{-i}]),\boldsymbol{\nu})$
$\displaystyle\coloneqq\mathbb{E}_{(\zeta,\omega)\sim\mathbb{P}_{\kappa}\times\mathbb{P}_{\boldsymbol{\pi}^{*}(\widetilde{\lambda}_{i},\boldsymbol{\phi}_{-i})}}\big{[}c^{s}(\mathbf{g}_{s}(\boldsymbol{\delta};\mathbf{g}^{*}(\widetilde{\lambda}_{i},\boldsymbol{\phi}_{-i}),\boldsymbol{\nu},(\zeta,\omega)))\big{]}$
$\displaystyle\;\;\;=\mathbb{E}_{\zeta\sim\mathbb{P}_{\kappa}}\big{[}\widehat{c^{s}}([f_{S}(\delta_{i},\zeta),\boldsymbol{\delta}_{-i}];\mathbf{g}^{*}([\widetilde{\lambda}_{i},\boldsymbol{\phi}_{-i}]),\boldsymbol{\pi}^{*}([\widetilde{\lambda}_{i},\boldsymbol{\phi}_{-i}])))\big{]},$

and so

$\displaystyle\mathbb{E}_{\boldsymbol{\delta}\sim\mathbb{P}_{([\lambda_{i},\boldsymbol{\phi}_{-i}])}}\widehat{c^{s}}(\boldsymbol{\delta}\;;\mathbf{g}^{*}($
$\displaystyle[\widetilde{\lambda}_{i},\boldsymbol{\phi}_{-i}]),\boldsymbol{\nu})$
$\displaystyle=\mathbb{E}_{\boldsymbol{\delta}^{\prime}\sim\mathbb{P}_{([\widetilde{\lambda}_{i},\boldsymbol{\phi}_{-i}])}}\big{[}\widehat{c^{s}}($
$\displaystyle\boldsymbol{\delta}^{\prime}\;;\mathbf{g}^{*}([\widetilde{\lambda}_{i},\boldsymbol{\phi}_{-i}]),\boldsymbol{\pi}^{*}([\widetilde{\lambda}_{i},\boldsymbol{\phi}_{-i}]))\big{]},$
(62)

where we have once again used the fact that
$f_{S}(\delta_{i},\zeta)\sim\mathbb{P}_{\widetilde{\lambda}_{i}}$ and so
$[f_{S}(\delta_{i},\zeta),\boldsymbol{\delta}_{-i}]\sim\mathbb{P}_{([\widetilde{\lambda}_{i},\boldsymbol{\phi}_{-i}])}.$

The desired result follows by noting that

$\displaystyle
q^{*}(\lambda_{i},\boldsymbol{\phi}_{-i})\leq\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;$
$\displaystyle
c^{g}\big{(}\mathbf{g}^{*}([\widetilde{\lambda}_{i},\boldsymbol{\phi}_{-i}])\big{)}+\mathbb{E}_{\boldsymbol{\delta}\sim\mathbb{P}_{(\lambda_{i},\boldsymbol{\phi}_{-i})}}\bigg{[}\widehat{c^{s}}(\boldsymbol{\delta};\mathbf{g}^{*}$
$\displaystyle([\widetilde{\lambda}_{i},\boldsymbol{\phi}_{-i}]),\boldsymbol{{\nu}})$
$\displaystyle-$
$\displaystyle\sum_{j=1}^{n_{s}}\widehat{\nu}_{j}(\delta_{j},\boldsymbol{\delta})\bigg{]}$
$\displaystyle\;=q^{*}(\widetilde{\lambda}_{i},\boldsymbol{\phi}_{-i}),$

where the equality follows using (61) and (62). ∎

##  Appendix D Proof of Lemma 3

###### Proof.

Let $\psi$ be that element of $\Theta$ that has the distribution function
$F_{\psi}(t)=\max\\{F_{\theta_{i}}(t),F_{\phi_{i}}(t)\\}.$ It is easy to see
that

$\displaystyle F_{\psi}(t)-F_{\phi_{i}}(t)\geq 0$ (63)

for all $t\in\\{1,\ldots,T\\},$ and that

$\displaystyle\sup_{t\in\\{1,\ldots,T\\}}\\{F_{\psi}(t)-F_{\phi_{i}}(t)\\}=\alpha(\theta_{i},\phi_{i}).$
(64)

Note that for all $t\in\\{1,\ldots,T\\},$
$\mathbb{P}_{\psi}(t)-\mathbb{P}_{\phi_{i}}(t)=F_{\psi}(t)-F_{\psi}(t-1)-\big{(}F_{\phi_{i}}(t)-F_{\phi_{i}}(t-1)\big{)}\leq\big{|}F_{\psi}(t)-F_{\phi_{i}}(t)\big{|}+\big{|}F_{\phi_{i}}(t-1)-F_{\psi}(t-1)\big{|}\leq
2\alpha(\theta_{i},\phi_{i}),$ where the last inequality follows from (63) and
(64). Therefore,

$\displaystyle\sup_{t\in\\{1,\ldots,T\\}}\\{\mathbb{P}_{\psi}(t)-\mathbb{P}_{\phi_{i}}(t)\\}\leq
2\alpha(\theta_{i},\phi_{i}).$ (65)

For $t=1,\ldots,T,$ define

$\displaystyle\beta_{\boldsymbol{\phi},{i}}(t;\mathbf{g},\boldsymbol{\pi})\coloneqq\mathbb{E}_{\boldsymbol{\delta}\sim\mathbb{P}_{\boldsymbol{\phi}}}\big{[}\beta(\boldsymbol{\delta},\mathbf{g},\boldsymbol{\pi})\big{|}\delta_{i}=t\big{]}$
(66)

so that $\beta_{\boldsymbol{\phi},i}(t;\mathbf{g},\boldsymbol{\pi})$ denotes
the conditional expected cost of satisfying the demand given that EV $i$
disconnects from the grid at time $t,$ the EV departure profiles is
distributed according to $\mathbb{P}_{\boldsymbol{\phi}},$ the generator’s
energy dispatch sequence is $\mathbf{g},$ and the storage policy is
$\boldsymbol{\pi}$. Note that the conditional expectation in (66) is well
defined for every $t$, thanks to (1). Note also that

$\displaystyle
q^{*}(\phi_{i},\boldsymbol{\phi}_{-i})=\mathbb{E}_{\delta_{i}\sim\mathbb{P}_{\phi_{i}}}\big{[}\beta_{\boldsymbol{\phi},{i}}(\delta_{i};\mathbf{g}^{*}(\boldsymbol{\phi}),\boldsymbol{\pi}^{*}(\boldsymbol{\phi}))\big{]}.$
(67)

Now,

$\displaystyle\mathbb{E}_{\delta_{i}\sim\mathbb{P}_{\psi}}\big{[}\beta_{\boldsymbol{\phi},{i}}(\delta_{i};\mathbf{g}^{*}(\boldsymbol{\phi}),\boldsymbol{\pi}^{*}(\boldsymbol{\phi}))\big{]}$
$\displaystyle-\mathbb{E}_{\delta_{i}\sim\mathbb{P}_{\phi_{i}}}\big{[}\beta_{\boldsymbol{\phi},{i}}(\delta_{i};\mathbf{g}^{*}(\boldsymbol{\phi}),\boldsymbol{\pi}^{*}($
$\displaystyle\boldsymbol{\phi}))\big{]}$
$\displaystyle=\sum_{t=1}^{T}\big{(}\mathbb{P}_{\psi}(t)-\mathbb{P}_{\phi_{i}}(t)\big{)}\beta_{\boldsymbol{\phi},{i}}($
$\displaystyle
t;\mathbf{g}^{*}(\boldsymbol{\phi}),\boldsymbol{\pi}^{*}(\boldsymbol{\phi}))$
$\displaystyle\leq\Big{[}\sum_{t=1}^{T}(\mathbb{P}_{\psi}(t)-\mathbb{P}_{\phi_{i}}(t))^{2}\Big{]}^{\frac{1}{2}}\Big{[}\sum_{t=1}^{T}$
$\displaystyle\beta^{2}_{\boldsymbol{\phi},{i}}(t;\mathbf{g}^{*}(\boldsymbol{\phi}),\boldsymbol{\pi}^{*}(\boldsymbol{\phi}))\Big{]}^{\frac{1}{2}}$
$\displaystyle\leq 2\sqrt{T}\alpha(\theta_{i},\phi_{i})\Big{[}\sum_{t=1}^{T}$
$\displaystyle\beta^{2}_{\boldsymbol{\phi},{i}}(t;\mathbf{g}^{*}(\boldsymbol{\phi}),\boldsymbol{\pi}^{*}(\boldsymbol{\phi}))\Big{]}^{\frac{1}{2}},$
(68)

where the last inequality follows from (65). It follows from (67) and the
definitions of the functions $\mathbf{g}^{*}$ and $\boldsymbol{\pi}^{*}$ that

$\displaystyle\mathbb{E}_{\delta_{i}\sim\mathbb{P}_{\psi}}\big{[}\beta_{\boldsymbol{\phi},{i}}$
$\displaystyle(\delta_{i};\mathbf{g}^{*}([\psi,\boldsymbol{\phi}_{-i}]),\boldsymbol{\pi}^{*}([\psi,\boldsymbol{\phi}_{-i}]))\big{]}$
$\displaystyle-\mathbb{E}_{\delta_{i}\sim\mathbb{P}_{\psi}}\big{[}\beta_{\boldsymbol{\phi},{i}}(\delta_{i};\mathbf{g}^{*}(\boldsymbol{\phi}),\boldsymbol{\pi}^{*}(\boldsymbol{\phi}))\big{]}\leq
0.$ (69)

Adding (68) and (69) yields

$\displaystyle\mathbb{E}_{\delta_{i}\sim\mathbb{P}_{\psi}}\big{[}\beta_{\boldsymbol{\phi},{i}}(\delta_{i};\mathbf{g}^{*}([\psi$
$\displaystyle,\boldsymbol{\phi}_{-i}]),\boldsymbol{\pi}^{*}([\psi,\boldsymbol{\phi}_{-i}]))\big{]}$
$\displaystyle-\mathbb{E}_{\delta_{i}\sim\mathbb{P}_{\phi_{i}}}$
$\displaystyle\big{[}\beta_{\boldsymbol{\phi},{i}}(\delta_{i};\mathbf{g}^{*}(\boldsymbol{\phi}),\boldsymbol{\pi}^{*}(\boldsymbol{\phi}))\big{]}$
$\displaystyle\leq 2\sqrt{T}\alpha(\theta_{i},\phi_{i})$
$\displaystyle\Big{[}\sum_{t=1}^{T}\beta^{2}_{\boldsymbol{\phi},{i}}(t;\mathbf{g}^{*}(\boldsymbol{\phi}),\boldsymbol{\pi}^{*}(\boldsymbol{\phi}))\Big{]}^{\frac{1}{2}},$

which using (67) implies

$\displaystyle
q^{*}(\psi,\boldsymbol{\phi}_{-i})-q^{*}(\phi_{i},\boldsymbol{\phi}_{-i})\leq
K\alpha(\theta_{i},\phi_{i})$ (70)

where

$K\coloneqq\sup_{\boldsymbol{\phi}\in\Theta^{n_{s}}}2\sqrt{T}\Big{[}\sum_{t=1}^{T}\beta^{2}_{\boldsymbol{\phi},{i}}(t;\mathbf{g}^{*}(\boldsymbol{\phi}),\boldsymbol{\pi}^{*}(\boldsymbol{\phi}))\Big{]}^{\frac{1}{2}}.$

That $K$ is finite follows from (9).

Since $F_{\psi}(t)\geq F_{\theta_{i}}(t)$ for all $t\in\\{1,\ldots,T\\},$ it
follows from Lemma 2 that
$q^{*}(\theta_{i},\boldsymbol{\phi}_{-i})-q^{*}(\psi,\boldsymbol{\phi}_{-i})\leq
0.$ Adding this inequality with (70) establishes (37).

We now turn attention to the second part of the lemma. Let $\phi_{i}$ be such
that (36) holds and denote by $t_{0}$ that element of $\\{1,\ldots,T\\}$ such
that

$\displaystyle
F_{\theta_{i}}(t_{0})-F_{\phi_{i}}(t_{0})=\alpha(\theta_{i},\phi_{i}).$ (71)

We first have using the SLLN that $\mathbb{P}_{\theta_{i}}^{\infty}-$ almost
surely,

$\displaystyle\lim_{L\to\infty}\frac{1}{L}\sum_{l=1}^{L}\mathds{1}_{\\{\delta_{i}(l)\leq
t_{0}\\}}=F_{\theta_{i}}(t_{0}).$ (72)

Now, let $\widehat{\delta}_{i}^{\infty}$ be any sequence such that
$\sum_{l=1}^{\infty}\mathds{1}_{\\{E_{i}(l,\widehat{\delta}_{i}^{l},\phi_{i}\\}}<\infty,$
i.e., $\\{E_{i}(l,\widehat{\delta}_{i}^{l},\phi_{i})\\}$ occurs only finitely
often. Combining this with (17) implies the existence of $L_{0}$ such that
$\sum_{t=1}^{t_{0}}{|{f}_{i,t}(L,\widehat{\delta}_{i}^{L},\phi_{i})|<t_{0}r(L)}$
for all $L\geq L_{0},$ which in turn implies that
$|\sum_{t=1}^{t_{0}}{{f}_{i,t}(L,\widehat{\delta}_{i}^{L},\phi_{i})|<t_{0}r(L)}$
for all $L\geq L_{0}.$ Substituting (14) in this inequality and carrying out
some algebra yields

$\displaystyle L[F_{\phi_{i}}(t_{0})-t_{0}r(L)]<\sum_{l=1}^{L}$
$\displaystyle\mathds{1}_{\\{\widehat{\delta}_{i}(l)\leq t_{0}\\}}$
$\displaystyle<L[F_{\phi_{i}}(t_{0})+t_{0}r(L)]$

for all $L\geq L_{0}.$ Using (16), this implies that

$\displaystyle\lim_{L\to\infty}\frac{1}{L}\sum_{l=1}^{L}\mathds{1}_{\\{\widehat{\delta}_{i}(l)\leq
t_{0}\\}}=F_{\phi_{i}}(t_{0}).$ (73)

Since
$\sum_{l=1}^{L}\mathds{1}_{\\{\delta_{i}(l)<\widehat{\delta}_{i}(l)\\}}\geq\sum_{l=1}^{L}\mathds{1}_{\\{\delta_{i}(l)\leq
t_{0}\\}}-\sum_{l=1}^{L}\mathds{1}_{\\{\widehat{\delta}_{i}(l)\leq t_{0}\\}}$
for any $L\in\mathbb{Z}_{+},$ dividing both sides of the inequality by $L$,
taking the limit as $L\to\infty,$ and using (73) and (72) yields

$\displaystyle\lim_{L\to\infty}\frac{1}{L}\sum_{l=1}^{l}\mathds{1}_{\\{{\delta}_{i}(l)<\widehat{\delta}_{i}(l)\\}}\geq
F_{\theta_{i}}(t_{0})-F_{\phi_{i}}(t_{0})=\alpha(\theta_{i},\phi_{i})$

$\mathbb{P}_{\theta_{i}}^{\infty}-$ almost surely, where the equality follows
from (71). This establishes (38). ∎

##  Appendix E Proof of Lemma 4

###### Proof.

Let

$\mathcal{I}_{L}\coloneqq\\{l\leq L\mathrel{\mathop{\mathchar
58\relax}}\mathds{1}_{\\{E_{i}(l,\widehat{\delta}_{i}^{l},\phi_{i})\\}}=1\\}.$

Denote by $I_{L}^{*}$ the largest element of $\mathcal{I}_{L},$ and note that
if

$\sum_{l=1}^{\infty}\mathds{1}_{\\{E_{i}(l,\widehat{\delta}_{i}^{l},\phi_{i})\\}}=\infty,$

then $I_{L}^{*}=L$ for infinitely many values of $L.$ Now,

$\frac{1}{L}\sum_{l=1}^{L}J_{p}(l)\mathds{1}_{\\{E_{i}(l,\widehat{\delta}_{i}^{l},\phi_{i})\\}}=\frac{1}{L}\sum_{l\in\mathcal{I}_{L}}J_{p}(l)\geq\frac{1}{L}J_{p}({I}^{*}_{L}),$

and so

$\limsup_{L\to\infty}\frac{1}{L}\sum_{l=1}^{L}J_{p}(l)\mathds{1}_{\\{E_{i}(l,\widehat{\delta}_{i}^{l},\phi_{i})\\}}\geq\limsup_{L\to\infty}\frac{J_{p}(I_{L}^{*})}{L}=\infty,$

where the last equality follows from (18) and the fact that $I_{L}^{*}=L$ for
infinitely many values of $L.$ ∎