Two-Sided Online Markets for Electric Vehicle Charging
Enrico H. Gerding
∗
eg@ecs.soton.ac.uk
Sebastian Stein
∗
ss2@ecs.soton.ac.uk
Valentin Robu
∗
vr2@ecs.soton.ac.uk
Dengji Zhao
†
dzhao@scm.uws.edu.au
Nicholas R. Jennings
∗
nrj@ecs.soton.ac.uk
∗
University of Southampton, SO17 1BJ, Southampton, UK
†
Intelligent Systems Lab, University of Western Sydney, Aus
tralia
ABSTRACT
With the growing popularity of electric vehicles (EVs), the
number
of public charging stations is increasing rapidly, allowin
g drivers
to charge their cars while parked away from home or en-route t
o
their destination. However, as a full charge can take a signi
ficant
amount of time, drivers may face queues and uncertainty over
avail-
ability of charging facilities at different stations and ti
mes. In this
paper, we address this problem by proposing a novel, two-sid
ed
market for advance reservations, in which agents, represen
ting EV
owners, report their preferences for time slots and chargin
g loca-
tions, while charging stations report their availability a
nd costs. In
our model, both parties are rational, profit-maximising ent
ities, and
buyers enter the market dynamically over time. Given this, w
e ap-
ply techniques from online mechanism design to develop a pri
cing
mechanism which is truthful on the buyer side (i.e., drivers
have
no incentive to misreport their preferences or to delay thei
r reser-
vations). For the seller side, we adapt three well-known pri
cing
mechanisms and compare them both theoretically and empiric
ally.
Using realistic simulations, we demonstrate that two of our
pro-
posed mechanisms consistently achieve a high efficiency (90
–95%
of optimal), while offering a trade-off between stability a
nd budget
balance. Surprisingly, the third mechanism, a common payme
nt
mechanism that is truthful in simpler settings, achieves a s
ignifi-
cantly lower efficiency and runs a high deficit.
Categories and Subject Descriptors
I.2.11 [
AI
]: Distributed AI—
Multiagent systems
Keywords
Electric vehicles; mechanism design; two-sided markets
1. INTRODUCTION
Recent years have seen increasing interest in electric vehi
cles (EVs)
as a key technology for achieving efficient transportation w
ith low
carbon emissions [1]. However, large-scale use of EVs will r
aise
a host of new challenges for electricity distribution netwo
rks [5,
14]. More specifically, electric vehicles are high electric
ity con-
sumers and, moreover, charging an electric vehicle takes co
nsider-
ably more time than fueling a petrol-powered vehicle.
1
Thus, the
problem of efficiently scheduling the charging of a large num
ber of
EVs at multiple charging stations will become increasingly
press-
ing and challenging, especially as both electric vehicle ow
ners and
charging stations can be seen as self-interested parties, i
nterested
in minimising their costs, or maximising their profits, resp
ectively.
1
Fully charging an EV takes a minimum of half an hour, even with
the fastest available chargers on the market today.
To address this problem, we present the first system where EVs
are matched to charging stations in a two-sided online marke
t. In
this system, agents representing EV drivers enter the marke
tplace
dynamically over time, at which point they place bids for
advance
reservations
on behalf of their owners. Through these bids, agents
express their preferences for different time slots and char
ging sta-
tions. At the same time, charging stations can offer availab
le charg-
ing units through the reservation system, and report their m
inimum
prices for different time slots. The system then allocates b
uyers to
these advance time slots
online
, i.e., as they enter the marketplace.
The proposed system is very general and we show how it can be
used in two specific real-world scenarios: (1)
park ’n charge
, where
the EV is charged while parked at a convenient location away f
rom
home and (2)
en-route charging
, where the EV requires charging
on the way to a destination. In these scenarios, we envision t
hat the
agent is integrated with an automated advice interface and a
route
planner, which enables the agent to trade off price, availab
ility and
distance, and automatically re-routes the user to the relev
ant sta-
tions. Online systems exhibiting some of these features are
already
beginning to emerge. For example,
Google Maps
2
provides interac-
tive directions, allowing drivers to make informed choices
between
multiple routes based on distance, estimated time of drivin
g or fuel
costs. In terms of EV charging, companies such as
PlugShare
3
and
ChargePoint
4
provide interactive maps of available EV charging
points in the US and Canada (including some reservation faci
lities).
Our work is closely related to combinatorial exchanges, whe
re
buyers and sellers are matched based on their (combinatoria
l) pref-
erences. These are mainly concerned with finding allocation
s and
payments that incentivise truthful bidding, while satisfy
ing other
properties such as individual rationality (buyers and sell
ers make
no loss from participating) and budget balance (the system o
r auc-
tioneer makes no loss). A seminal result in this field is by McA
fee
[9], who proposes a payment scheme to achieve truthfulness i
n two-
sided markets with identical goods. Gonen
et al.
[7] extend this to
combinatorial two-sided auction markets, and propose a pro
cedure
called generalised trade reduction in order to ensure sever
al eco-
nomic properties including truthfulness. However, this an
d similar
work assumes a static setting where all buyers and sellers ar
e all
present in the market at the same time. In our setting, on the o
ther
hand, buyers enter the system dynamically and need to be allo
cated
without knowing future demand.
Incentivising truthful behaviour in settings with dynamic
market
entry is studied in the field of
online mechanism design
(see [11,
Ch.16] for a survey). Existing work, such as [12, 6], largely
con-
2
http://maps.google.com/
3
http://www.plugshare.com/
4
http://www.chargepoint.net/
siders one-sided markets (e.g., with one seller and many buy
ers).
In contrast, we look at two-sided markets with multiple buye
rs (the
EVs) and multiple sellers (the charging stations). Online t
wo-sided
markets are studied in [3, 4], but all buyers and sellers are a
ssumed
to trade a single unit of the same commodity. Our setting is mu
ch
more complex, since buyers have different preferences for d
ifferent
sellers and time slots, and sellers can have multiple time sl
ots and
multiple units per time slot. As we will show, this added comp
lex-
ity has significant implications for the properties of the ma
rket.
More recently, some research has attempted to address the EV
charging problem from a cooperative scheduling perspectiv
e. In
this vein, [13, 8] consider constructing an online charging
schedule
which takes into account spatial and temporal constraints.
While
some of these approaches use similar concepts to our work, su
ch as
placing advance reservations while en-route (e.g., [8]), t
hey rely on
a centralised scheduler and fully cooperative agents. In co
ntrast, we
assume that agents are self-interested and can strategise b
y misre-
porting their preferences. Furthermore, we propose a decen
tralised
marketplace where agents perform much of the computation, s
uch
as the routing and computing the EV’s energy requirements. A
small number of papers have studied the EV scheduling proble
m
considering strategic, self-interested agents [6, 16, 15]
. However,
these study a one-sided setting with a single, fixed charging
point.
Against this background, this paper makes the following con
tri-
butions to the existing state of the art:
•
We introduce the first two-sided market architecture for mat
ch-
ing EV owners to charging stations using advance reservatio
ns.
•
For this system, we develop a payment mechanism that is truth
-
ful and individually rational on the buyer side. On the selle
r side,
we outline a number of payment mechanisms and explore their
theoretical properties. As part of this, we present an impos
sibil-
ity result which shows that no payment can always be truthful
for
sellers when a greedy allocation rule is used.
•
We show how our reservation system can be applied to two
realistic scenarios, and we analyse the equilibrium behavi
our of
agents in these scenarios using extensive simulations. We d
emon-
strate that two of our proposed payment mechanisms induce a h
igh
allocative efficiency (around 90–95% of the optimal), and we
show
that one of these achieves a higher stability at the expense o
f run-
ning a small deficit. Surprisingly, we find that a well-known p
ay-
ment mechanism that is truthful for sellers in simpler setti
ngs per-
forms poorly, in terms of both efficiency and deficit.
The remainder of the paper is organised as follows. In Sectio
n 2
we first present our system model. In Section 3 we describe the
al-
location mechanism and several payment mechanisms for our m
ar-
ket, and analyse their theoretical properties. Then, in Sec
tion 4
we instantiate our model in two real-world scenarios. Using
these
scenarios, we evaluate and compare the proposed mechanisms
em-
pirically in Section 5. We conclude in Section 6.
2. AGENT MODELS
The system consists of a set of agents or
buyers
,
B
=
{
1
,
2
, . . .
}
,
who arrive dynamically over time, and are interested in rese
rving a
slot for charging their EV at one of the available charging st
ations,
denoted by the set
S
. W.l.o.g.,
i
′
> i
means that buyer
i
′
enters
the market after
i
. Furthermore, we assume that charging occurs
at discrete time slots (e.g., half-hourly slots), denoted b
y the set
T
,
and that a car is fully charged during such a time slot (theref
ore,
a buyer requires only a single time slot).
5
Each buyer
i
∈
B
can
5
In future work, we plan to extend our model to include setting
s
where buyers can partially charge and/or need several slots
.
have different preferences regarding both the station he wo
uld like
to charge at, as well as the time of the reservation. For examp
le, in
the park ’n charge scenario, the buyer prefers a destination
closer
to his final destination. In the en-route charging scenario,
the buyer
prefers those stations which result in a smaller detour, and
which
are ideally placed between the departure point and the desti
nation
(e.g., if the battery’s state of charge is low, he would requi
re a sta-
tion close to the departure point). We abstractly represent
such
preferences by a matrix
v
i
, where each element
v
i
j,t
denotes the
willingness to pay, or
value
, of an agent
i
for receiving a charging
slot at time
t
∈
T
in station
j
∈
S
. Note that this representation is
very general, and can capture the costs (both in terms of time
and
money) due to a detour, as well as stations or times which are i
nfea-
sible given the battery’s current state of charge (in which c
ase the
value for a particular slot or time is zero or even negative).
These
preferences constitute an agent’s private information (un
known to
other buyers or the stations), also referred to as an agent’s
type
.
On the supply side, each station or
seller
can have multiple charg-
ing units,
K
=
{
1
,
2
, . . .
}
, which means that, for each particular
time slot, possibly several reservations can be sold. Each s
tation
j
has a cost for selling a certain number of time slots through t
he
reservation system, denoted by the matrix
c
j
, where
c
j
t,k
is the cost
of station
j
∈
S
at time
t
∈
T
for the
k
th unit,
k
∈
K
(where
k
= 1
is the reservation for time slot
t
which has been allocated
first,
k
= 2
the second reservation, etc.). If station
j
has at most
k
j
units available at a particular time
t
, we simply set
c
j
t,k
=
∞
for
k > k
j
. In practice, these costs represent an
opportunity cost
, i.e.,
the expected value of instead selling the unit on demand, wit
hout a
reservation. This opportunity cost can be calculated by the
proba-
bility that a certain unit is sold, multiplied by the profit of
selling
the unit on demand. Typically, peak times are expected to be m
ore
profitable (since the probability that the slot is used incre
ases), and
so have a higher opportunity cost. Furthermore, we assume th
at
the marginal cost for additional units is non-decreasing. T
hat is,
∀
j
∈
S, t
∈
T
:
c
j
t,k
+1
≥
c
j
t,k
. This is a natural assumption, as
shown by the following example:
E
XAMPLE
1.
Consider a park ’n charge with 1 time slot and 2
units. On-demand units are always sold at
$10
. The station always
manages to sell at least 1 unit on demand, and sells both units
with probability 50%. Therefore, the opportunity cost of th
e first
reservation is
0
.
5
$10 = $5
, while the opportunity cost for selling
the second unit through the reservation system is
$10
.
These costs differ for each station, and are estimated by the
stations
based on observed past demand. Therefore, the costs constit
ute the
station’s private information or
type
.
Given this, both buyers and sellers are asked to report their
types
to a
centre
(i.e., the reservation system) which then computes an
allocation and payment for each agent. Buyers report their t
ypes as
they enter the market, whereas sellers report their types in
advance
for the entire period
T
.
6
Formally, let
ˆv
i
and
ˆc
j
denote the report
for a buyer
i
and seller
j
respectively,
ˆ
v
and
ˆ
c
the reports of all
buyers and sellers, and
ˆ
v
−
i
(
ˆ
c
−
j
) all buyer (seller) reports except
that of
i
(
j
). We define the
allocation
for buyer
i
∈
B
by a tuple
x
i
=
h
j, t, k
i
, if buyer
i
receives the
k
th unit,
k
∈
K
, of time slot
t
∈
T
from seller
j
∈
S
(note that
k
does not refer to a particular
physical charging unit, but to the order in which the reserva
tion was
allocated), and use
x
i
=
h∅i
to denote the case where the buyer
is not allocated any slot. For the seller, we use
x
j
to denote the
6
In practice, the period can be limited to, e.g., the next 24 ho
urs,
and sellers can update their types as new time slots become av
ail-
able. For simplicity, we assume a single reporting stage.