Online Mechanism Design for Vehicle-to-Grid Car Parks

1 Introduction

Recent years have seen increasing interest in electric vehicles (EVs) as a key technology in the transition to a lowcarbon transportation future. In AI and particularly multiagent systems, recent work has discussed how the charging of EVs can be scheduled, e.g., to avoid bottlenecks in local distribution grids [Valogianni et al., 2015; Robu et al., 2013] or at EV charging stations [Gerding et al., 2013; Rigas et al., 2013]. However, EVs can also help ensure grid stability, especially as generation is shifting towards intermittent renewable resources. This is achieved through the socalled vehicle-to-grid (V2G) concept, whereby EVs are able to sell energy back to the grid during periods of scarcity and when energy prices are high.

Sebastian Stein

University of Southampton, UK ss2@ecs.soton.ac.uk

Valentin Robu

Heriot Watt University, UK

V.Robu@hw.ac.uk

In this paper, we use techniques from mechanism design and online scheduling to address the problem of charging and discharging multiple EVs. The setting we study is one of a public car park, where EVs arrive dynamically and stay for a period of time - during which they wish to be charged to a particular state of charge (SOC), but can also be used for V2G. Similar to existing work [Recalde Melo et al., 2014; Kahlen and Ketter, 2015], the reason to focus on this setting is that car parks have a larger size and "visibility" to the grid and hence are more likely to be offered an advantageous contract, or are able to trade in the wholesale market.

A crucial concern in addressing this problem, however, is that discharging has a cost for each EV, as it affects the remaining useful lifetime (RUL) of its battery. These costs are often EV-specific, as different vehicles have different types of batteries and age, and they are private to each EV driver. Moreover, when designing a charging/discharging schedule of each EV, a number of other constraints need to be taken into account, such as the driver's intended departure time and desired state of charge when leaving.

There has been considerable related work on V2G charging, typically focusing on how a demand response aggregator (such as a car park, or a local microgrid) can optimise its trading/balancing strategy using a number of available EVs (see also Section 2). However, many of the proposed solutions do not consider heterogeneous EVs with different costs for discharging, arrivals and SOC constraints. In addition, existing approaches assume the information about individual EVs to be known by the aggregator. In contrast, we consider EV owners to be self-interested agents with privately known preferences and constraints, who may misreport this information if this is to their benefit. Hence, we need to design incentives to truthfully elicit this information. Truthfulness (defined here using the strong notion of ex-post dominantstrategy incentive compatibility) is an important property, as it removes the strategic burden from EV owners. Moreover, since the information is used to optimise the balancing strategy, it results in more efficient outcomes.

Specifically, the contributions of our work are as follows:

• ÷ We formalise, for the first time, the V2G problem as an online mechanism design problem. Specifically, we consider a car park setting, where arriving EVs have differ-

ent discharging costs, required SOC and intended departure times, and this information is privately known. The aggregator (e.g., car park owner) decides on a charging and discharging scheduling algorithm and compensates agents for their incurred discharging costs to (1) incentivise truthful reporting, (2) minimise overall costs.

• ÷ We provide sufficient conditions for any scheduling and payment mechanism to be truthful in this setting.
• ÷ We propose two specific truthful mechanisms and a third mechanism, which is not necessarily truthful, but allows EVs to rely more on internal trading rather than with the grid. All three algorithms are scalable and can be used for large settings.
• ÷ Finally, we compare the performance of our three mechanisms experimentally using simulations, showing that they can achieve positive profits even when EVs do not pay for the charge they receive.

2 RelatedWork

The concept of V2G has received considerable attention in the area of power systems and energy economics. In this vein, the seminal work by [Kempton and Tomi´c, 2005] quantifies the revenues that EVs could achieve by participating in different electric markets: peak power shaving, spinning reserves and regulation services, but they do not design actual control algorithms for EV charging and discharging. Work which does consider such algorithms includes [Shafie-khah et al., 2016; Kamboj et al., 2011; Han et al., 2010; Shi and Wong, 2011; Vasirani et al., 2013]. [Shafie-khah et al., 2016] use stochastic programming to provide a strategy for a plug-in EV aggregator agent to profitably participate in a demand response market. They consider several methods to reason about prices and to account for domain constraints (such as those coming from transformer loading). However, their analysis is done from the perspective of the aggregator, rather than individual EVs. Taking a multi-agent perspective, [Kamboj et al., 2011] model a number of EVs providing anciliary services to the grid as a coalition, and discuss how coalitional game theory techniques could be used to divide the resulting rewards. [Han et al., 2010] and [Shi and Wong, 2011] model the problem of EV charging as an MDP. Specifically, [Han et al., 2010] use EVs for frequency regulation, and EVs are rewarded for the time they are available, irrespective of how much their battery capacity is discharged/recharged during their stay, unlike our approach, in which effort is measured proportionally to the amount discharged. Furthermore, none of the above approaches consider the problem of strategic EVs, requiring an appropriate mechanism to ensure participating EVs report their costs truthfully.

Online mechanism design has previously been applied to EV charging, e.g., [Robu et al., 2013; Stein et al., 2012; Valogianni et al., 2015], but these approaches do not consider V2G settings. Other work considers a number of EVs working together as a virtual power plant (VPP), either to balance a renewable resource [Vasirani et al., 2013] or to sell electricity in the balancing market. In this vein, [Kahlen and Ketter, 2015] consider a car sharing service, in which drivers rent and return vehicles at different locations. The system operators can decide which vehicles parked at each spot to use for rental, and which to use as part of the VPP to provide regulation services to the grid. Both of these consider the optimisation problem from the perspective of the VPP aggregator, and do not guarantee truthfulness of individual EVs.

3 Formal Model

We consider the problem of a single smart car park, henceforth called the aggregator, where electric vehicles, henceforth called agents, arrive and leave over time.

The Agents. Let I denote the set of agents. An agent i 2 I arrives at time ai and has a privately-known type ✓i = hdi↪ qi↪ cii representing the agent preferences and constraints, where di is the (actual) departure time, qi is the required amount of electricity by the departure time, and ci is a discharging cost parameter (more details below). Importantly, note that, in this model, the required charge is a hard constraint and, as a result, we do not need to include the value derived from a certain amount of charge.

In addition, the agent's battery has a (known) state of charge at time t, denoted by SoCi↪t and the current charging rate is denoted by ri↪t = dSoCi↪t◁dt, where ri↪t > 0 means the battery is charging and ri↪t < 0 means it is discharging. The entire charging and discharging schedule is denoted by ri. Furthermore, limits are given by SoC max i , SoC min i , rmax i and rmin i . For simplicity we assume these limits are known by the aggregator, but they could also be elicited (i.e., be included as part of the private type). Given this, we can describe the total amount charged and discharged by time t as q+ i↪t (ri) = R t ai max(0↪ ri↪t0)dt0 and qi↪t (ri) = - R t ai min(0↪ ri↪t0 )dt0 respectively, noting that both these values are positive.

Charging and discharging a battery incurs a monetary cost, since capacity generally decreases for each charge and discharge cycle. This loss depends on many factors, but the main ones are the state of charge and the rate of charge [Divya and Ostergaard, 2009]. This translates into monetary costs when the battery needs to be replaced, but also the inconvenience of having a battery with lower capacity and requiring more frequent charging. In general, we model the slope of the capacity loss by w(SoCi↪t↪ ri↪t), which is assumed to be common knowledge, and the total capacity loss incurred up until time t is Wi(ri) = R di ai w(SoCi↪t↪ ri↪t)dt. Using game-theoretic terminology, this loss is also referred to as the amount of work incurred [Archer and Tardos, 2001]. Importantly, we assume that the costs are linear w.r.t. to ci, and therefore the total cost incurred by an agent is ci ·Wi(ri). For some of the results and in the simulations, we furthermore assume a constant loss per unit of (dis)charge, i.e., w(SoCi↪t↪ ri↪t) = a · ri↪t, for some constant a. This is a reasonable approximation if the state of charge never gets too low (i.e., if SoC min i is sufficiently high). By putting charging and discharging costs together (i.e., any discharging needs to be compensated by charging to reach the required charge qi), the work function simplifies to Wi(ri) = a · qi↪di (ri).

The above results in the agent utility:

if the following constraints are met:

• ÷ 8t 2 [ai↪ di] : SoC min i  SoCi↪t  SoC max i and rmin i  ri↪t  rmax i
• ÷ SoCi↪di ≥ qi

and is ui(ri↪ ⌧i) = -1 otherwise, where ⌧i are monetary transfers from the aggregator, detailed in Section 4.

The Aggregator The aggregator determines the charging and discharging schedules and the transfers, and sells any excess elecricity to the grid and purchases any shortfall. We assume that electricity prices change over time and the buy and sell prices can also differ. Let pbuy t ≥ psell t denote the buy and sell prices at time t and furthermore let rI↪t(ri) = Pi2I ri↪t denote the overall/net (dis)charge at t. Given this, we can compute the aggregator utility, uagg, as follows:

where T is a time interval, e.g., 24 hours.

4 The MechanismDesign Problem

As is common in the mechanism design literature, the main goal is to maximise the social welfare, SW, which equals the sum of utilities of all agents (Equation 1) and the aggregator's utility (Equation 2) [Nisan et al., 2007, Ch.9]. 1 Maximising this is also known as maximising market efficiency. Noting that transfers cancel out, this results in:

subject to individual agent constraints.

Although obtaining optimal social welfare is generally not possible (due to uncertainty of prices and future arrivals, as well as tractability issues, as discussed in Section 5), in order to be effective, the aggregator first needs to elicit the private information from the agents. To this end, on arrival each agent i is asked to report their type, where the report is denoted by ˆ ✓i = h ˆ di↪ ˆ qi↪ ˆ cii. 2 We assume that the aggregator can observe the arrival time, ai, of the agents and their state of charge. Furthermore, it can verify the departure time, di, ex-post, meaning once the agent has actually departed. Given this, the mechanism design problem is to determine the charging rate ri↪t at each time ai  t  di and transfers (payments to the agents) such that the agents have an incentive to report truthfully, i.e., such that reporting ˆ ✓i = ✓i is a dominant strategy for each agent i. Such a mechanism is also said to be truthful. Next we provide sufficient conditions for a mechanism to be truthful in our setting.

1 An alternative goal is to maximise aggregator utility and, while here we focus on social welfare, we do measure the aggregator profit in the empirical evaluation (see Section 7).

2 There is a subtle difference with traditional online mechanism design, where agents are also asked to report their arrival. In the parking scenario, the physical arrival and departure can be observed by the aggregator. However, to produce a (dis)charging schedule, the aggregator needs to know the intended departure, which is what ˆ di signifies here.

Our results are an extension of [Archer and Tardos, 2001]. In [Archer and Tardos, 2001], necessary and sufficient conditions are given for a setting where the type is given by parameter ci only. To account for the remaining parameters, let ≻ define an ordering over types such that ✓0i ≻ ✓i means that either q0i < qi, d0i > di or c0i < ci (intuitively, ✓0i is a 'better' type for the mechanism in one of the dimensions). Furthermore, let fi(ˆ ✓i) = fi( ˆ di↪ ˆ qi↪ ˆ ci) determine agent i's allocation as a function of his reported type, i.e., ri = fi(ˆ ✓i). Given this, we obtain the following result:

Theorem 1. The mechanism is truthful if the following conditions are met:

1. (Monotonicity of Work) Whenever ✓0i ≻ ✓i then Wi(fi(✓0i )) ≥ Wi(fi(✓i))
2. The transfers are computed on (observed) departure and are given by:

where W 0 i is the minimum required work to get to the state of charge on departure (i.e., without additional discharging), and hi is a constant which does not depend on the report (but could, e.g., depend on the observed arrival and departure). Note that transfers are calculated based on actual departure, which we assume the mechanism can observe ex-post.

Proof. First, note that, due to the second term, the transfers always compensate the agent's costs for any additional work done (i.e., work done on top of getting to the required charge) and, in fact, typically, due to the third term in Equation 4, the agent is better off when doing more work (and is never worse off). As a result, the agent has no incentive to overreport qi and report an earlier di since this will only lead to less work. If the agent truthfully reports di, then he also has no incentive to underreport qi since, due to condition 3, his state of charge would be insufficient and his utility -1. An interesting case is reporting ˆ qi < qi and ˆ di > di when the agent knows the mechanism will temporarily charge above ˆ qi with the intention to discharge later, and this could result in more work. However, since the transfer is based on the actual state of charge and on the actual departure, it is the same as if he had reported ˆ qi = SoCi↪di and ˆ di = di. Therefore, while the agent has done more work, he does not get compensated for it and only incurs the costs. As a result of the above, the agent has no incentive to misreport qi or di. Given this, we can use the result from [Archer and Tardos, 2001, Theorem 4.2] to show that the agent also has no incentive to misreport ci .

5 The Online Scheduling Problem

We now focus on the problem of setting the (dis)charging rate of the EVs in the car park in order to obtain a high social welfare (as defined by Equation 3). Now, optimising this problem is intractable for our setting. An additional challenge is that future arrivals as well as grid prices are generally unknown. To this end, we assume that a probability distribution of the prices is known, that the number of prices is finite and that charging decisions are made at discrete time steps. This way, the problem can be formulated as a Markov decision process (MDP), and solved by dynamic programming. While solving this optimally is tractable for a single EV, with multiple EVs we need to consider all combinations of states for each EV. This leads to an exponential increase in the number of states, which very quickly becomes intractable. Therefore, we propose three different heuristics:

Algorithm 1. This algorithm only bases decisions on current prices and does not consider future prices. Let ⇢low and ⇢high , ⇢low  ⇢high , denote two thresholds. Each EV i currently in the car park will be charged if pbuy t  ⇢low (i.e., if the price is below a threshold) at a constant rate as long as SoCi↪t < qi. Furthermore, an EV will be discharged at a constant rate if psell t - ciw(SoCi↪t↪ ri↪t)◁ri↪t ≥ ⇢high (i.e., if the marginal profit is above a certain threshold) as long as there is sufficient time to recharge to get to the required SOC qi by the departure time.

Algorithm 2. The second algorithm considers future grid price distributions and optimises the expected utility for each vehicle i independently, given the price distributions, and assuming each agent buys and sells directly from the grid, i.e., assuming ⌧i = Pdi t=ai (-min(0↪ ri↪t) · psell t -max(0↪ ri↪t) · pbuy t ). The optimal solution is a policy which specifies a charging schedule for each realisation of the prices, and can be solved using dynamic programming.

Note that, in Algorithms 1 and 2, while the (dis)charging decisions are made independently for each agent, the demand and supply is first aggregated within the car park and electricity is only sold to (bought from) the grid if there is a net surplus (deficit). Therefore, whenever there is a situation where one EV charges and, at the same time, another discharges, instead of buying or selling from the grid, one EV will be used to charge another one, saving pbuy t - psell t ≥ 0. Furthermore, note that Algorithm 2 is globally optimal when 8t : pbuy t = psell t .

Algorithm 3. Algorithm 2 is optimal for an individual EV, but the optimal policy ignores potential benefits that can be achieved by discharing one vehicle in order to charge another one. To address this, Algorithm 3 takes the solution from Algorithm 2 as the basis, but then considers whether the social welfare can be improved further by adjusting the immediate charging rate of the agents. In more detail, let EU ⇤ i↪t (SoCi↪t) denote the expected utlity of agent i from time t onwards given the current state of charge, assuming the agent buys and sells directly from the grid, and using the optimal policy from Algorithm 2. Then:

is the expected utility when agent i (dis)charges at rate ri↪t at time t and then proceeds with the individual agent's optimal policy from time t + 1 onwards (given the updated state of charge according to the current charging rate).

Note that, in Algorithm 2, the current charging rate is set to r⇤ i↪t = argmaxri↪t EUi↪t(ri↪ SoCi↪t). Instead, here we set the current charging rates of all agents in order to (myopically) maximise the social welfare as follows:

Note that, unlike Algorithm 2, this algorithm may (dis)charge an EV if is not optimal for the individual EV, but when it contributes to the social welfare.

6 AlgorithmProperties

In this section we prove that Algorithms 1 and 2 are truthful when the cost per unit of (dis)charge is constant (i.e., when w(SoCi↪t↪ ri↪t) = a · ri↪t, see also Section 3). Recall that, according to Theorem 1, in order for these algorithms to be truthful, we need to show that ex-post monotonicity of work holds, for each of the type parameters. Note that we can consider each parameter independently, as long as monotonicity holds for a parameter independent of the remaining parameters. If monotonicity holds, the payments defined in Theorem 1 can be used to assure truthfulness.

Towards a proof, we first introduce bounds on the state of charge of a battery at any given time t for an agent i. In more detail, since we require that SoCi↪di = qi to guarantee truthfulness (Theorem 1), and due to the physical constraints on the (dis)charging rate and SOC of the agent, the algorithms above have an upper bound ubi↪t and a lower bound lbi↪t on the state of charge at time t given by:

We are now ready to show the monotonicity properties of the proposed algorithms w.r.t. each type dimension.

Theorem 2. Algorithm 1 guarantees monotonicity of work w.r.t. cost parameter ci, i.e., ci ≥ c0i ! Wi(fi(✓i))  Wi(fi(✓0i )), when the cost per unit charge is constant (i.e., independent of charging speed or state of charge).

Proof. Let ✓i and ✓0i denote two identical types except for the costs ci and c0i respectively, and w.l.o.g. we assume that ci > c0i . In addition, let ri and r0i denote the respective allocations and SoCi↪t and SoC 0 i↪t the respective SOC. Note that SoCi↪ai = SoC 0 i↪ai and SoCi↪di = SoC 0 i↪di = qi. Furthermore, note that the bounds ubi↪t and lbi↪t are the same for the two types ✓i↪ ✓0i because they do not depend on the cost (which is the only difference between them). To prove monotonicity we need to show that: ci ≥ c0i ! Wi(ri)  Wi(r0i ). However, since Wi(ri) = a · qi↪di (ri), it is sufficient to show that qi↪t (ri)  qi↪t (r0i ) for any ai  t  di. For this to hold, we need to show that, for any setting, one of two conditions always holds:

1. If ri↪t > 0 then ri↪t  r0i↪t , or, if ri↪t < 0 then ri↪t ≥ r0i↪t , i.e., ✓0 does at least the same work as ✓.
2. If ri↪t ≥ r0i↪t and ri↪t > 0 then, after charging, the SOC of ✓0i is equal to or higher than the one of ✓i, meaning that q+ i↪t (ri)  q+ i↪t (r0i ), or, if ri↪t  r0i↪t and ri↪t < 0 then, after discharging, the SOC of ✓0i is equal to or lower than the one of ✓i, meaning that qi↪t (ri)  qi↪t (r0i ).

Next, we divide all possible settings into four cases reflecting the fact that, at any time t, the system can either charge (ri↪t > 0) or discharge (ri↪t < 0) and that SoCi↪t is either greater than, equal to, or lower than SoC 0 i↪t . Note that in Algorithm 1 the upper bound ubi↪t is always equal to qi because the algorithm never overcharges the battery, i.e., SoCi↪t  qi and SoC 0 i↪t  qi for any t.

Case 2: SoCi↪t  SoC 0 i↪t and ri↪t < 0. This case is symmetric to Case 1.

Case 1: SoCi↪t ≥ SoC 0 i↪t and ri↪t > 0. The fact that the mechanism decides to charge type ✓i means that the price pbuy t is advantageous for ✓i given her cost parameter ci. Since ci > c0i , this necessarily implies that charging is the optimal choice also for ✓0i . Indeed, assume that the optimal decision for ✓0i is r0i↪t < ri↪t. This implies that pbuy t is more advantageous for ✓i then for ✓0i . Since the price pbuy t is the same for both types, the one with the highest benefit is the one with the lower cost, i.e., ci < c0i . However, this contradicts our assumption that ci > c0i . Thus, ri↪t  r0i↪t . Note that, if ubi↪t constrains r0i↪t , then also ri↪t is constrained by it because SoCi↪t ≥ SoC 0 i↪t . Thus, Condition 1 is satisfied.

Case 3: SoCi↪t  SoC 0 i↪t and ri↪t > 0. First note that, given the results of cases 1 and 2 and the fact that ubi↪t = qi, we have that SoCi↪t  SoC 0 i↪t ! q+ i↪t (ri)  q+ i↪t (r0i ). Now, as with case 1, if it is optimal to charge ✓i then charging is the optimal decision also for ✓0i . However, in this case ubi↪t may impose a constraint on r0i↪t but not on ri↪t, i.e., ri↪t > r0i↪t . Nevertheless, note that it is never possible that, after charging, the SOC of ✓i is higher than the one of ✓0i because ubi↪t affects ✓0i only when her SOC becomes equal to qi. Consequently, the decision of charging ✓i at t never leads to the case in which q+ i↪t⇤ (ri) > q+ i↪t⇤(r0i ) at a future time t⇤ . Thus, Condition 2 is satisfied.

Case 4: SoCi↪t ≥ SoC 0 i↪t and ri↪t < 0. This case is symmetric to Case 3.

Theorem 3. Algorithm 2 guarantees monotonicity of work w.r.t. the cost parameter, i.e., ci ≥ c0i ! Wi(fi(✓i))  Wi(fi(✓0i )), when the cost per unit charge is constant (i.e., independent of charging speed or state of charge).

Proof. The structure of this proof, the notation used, and the logical steps are the same as the ones in the proof of Theorem 2. The only difference is the analysis of the four cases that we now present.

Case 1: SoCi↪t ≥ SoC 0 i↪t and ri↪t > 0. First note that the upper bound ubi↪t never constrains r0i↪t to be lower than ri↪t because SoCi↪t ≥ SoC 0 i↪t .

The mechanism chooses to charge type ✓i as this option is optimal for her, i.e., given the current buying price pbuy t and the expected future buying and selling prices, it is optimal for ✓i to buy electricity at time t.

Assume that SoCi↪t ≥ qi and that the optimal option for ✓0i is ri↪t > r0i↪t , i.e, ✓0i is not charged as much as ✓i at time t . This naturally implies that ✓0i has a better buying opportunity in the future. If not, since ci > c0i , ✓0i would have charged the battery at t at least as much as ✓ because this would have guaranteed her at least the same benefit that ✓i gets. However, note that ✓i and ✓0i have the same market opportunities in terms of buying and selling prices because these prices are independent of the agents type. Thus, if there is a better buying option for ✓0i than the current one, the same option would have been available and optimal also for ✓i. But this contradicts the initial assumption. Thus, we proved that ri↪t  r0i↪t , i.e., Condition 1 holds.

Now observe that, when SoCi↪t < qi, the decision of charging ✓i is taken without considering that the electricity will be sold because SoCi↪di < qi. Given this, the choice of charging is optimal as long as the state of charge is below qi. However, this situation correspond to the one discussed in Case 3 of Theorem 2 where we show that the decision of charging ✓i at t never leads to the case in which q+ i↪t⇤(ri) > q+ i↪t⇤(r0i ) at a future time t⇤ , hence Condition 2 holds.

Case 2: SoCi↪t  SoC 0 i↪t and ri↪t < 0. The analysis of this case can be easily derived from the one of Case 1, as the two cases are symmetrical.

Case 3: SoCi↪t  SoC 0 i↪t and ri↪t > 0. The only difference between this and Case 1 is that SoCi↪t  SoC 0 i↪t . The only effects of this difference is that ri↪t  r0i↪t may not be possible. However, what was discussed in Case 3 of Theorem 2 can be applied here with the only difference that ubi↪t ≥ qi (instead of ubi↪t = qi).

Case 4: SoCi↪t ≥ SoC 0 i↪t and ri↪t < 0. The analysis of this case can be easily derived from the one of Case 3, as the two cases are symmetrical.

Theorem 4. Algorithm 1 and Algorithm 2 guarantee monotonicity of work w.r.t. departure time di, i.e., di  d0i ! Wi(fi(✓i))  Wi(fi(✓0i )), and required amount of electricity qi, i.e., qi ≥ q0i !Wi(fi(✓i)) Wi(fi(✓0i )).

Proof. Sketch Let ✓i and ✓0i denote two types which are identical except for either departure time, and in this case, w.l.o.g., we assume di  d0i , or for required amount of electricity, in this case, w.l.o.g., we assume qi ≥ q0i . The proofs by contradiction used in Theorem 2 and Theorem 3 hold also in case of departure time and required amount of electricity, i.e., if there is no constraint imposed by ubi↪t and lbi↪t then ✓0 is (dis)charged at least as ✓. However, in this case ubi↪t and lbi↪t may be different from ub0i↪t and lb0i↪t , i.e., the bounds may depend on the agent type. Nevertheless, the way in which an earlier departure and a higher requested amount of electricity affect these bounds is by making them more strict, i.e., ubi↪t  ub0i↪t and lbi↪t ≥ lb0i↪t . The proof follows from the fact that stricter bounds naturally impose stricter constraints on an agent's work.

7 Empirical Evaluation

In this section, we empirically evaluate our algorithms in a range of realistic settings, in order to determine their potential for implementing smart car parks. We are particularly interested in two key metrics: social welfare (Equation 3) and aggregator utility (Equation 2).

7.1 Experimental Setup

We simulate a large car park over a period of 24 hours, where most cars arrive in the morning, representing a typical workplace. Specifically, time is discretised into 1-hourly time slots, and the number of arrivals at every hour is drawn from a Poisson distribution with a mean that varies over time and peaks at 8am. Unless specified otherwise, the expected number of arrivals over the entire day is 100 cars, and each car stays in the car park for between 1 and 16 hours (drawn uniformly at random) or until midnight, whichever is earlier.

We discretise a car's battery into units representing 3 kWh each, which we assume is the electricity that can be charged or discharged in one hour. To determine the initial state of charge of agent i, SoCi↪ai , and its maximum state of charge, SoC max i , we draw two integers from the interval 1 to 8 and assign the smaller to SoCi↪ai and the larger to SoC max i . This means that vehicles have a battery capacity of up to 24 kWh, which is the typical capacity of current EVs. The required charge qi is determined by randomly picking a feasible charge given the vehicle's duration of stay and maximum capacity. We assume constant capacity losses for charging and discharging a unit of electricity (a in Section 3) and draw these for each agent from a uniform distribution on [$0▷01↪ $0▷03]. Finally, the cost parameter ci is drawn from the interval [1↪ 5], discretised into steps of 0.1. 3

Grid prices are simulated using a Markov chain that randomly starts in one of four states. Each state s is associated with a buying price pbuy↪s (respectively, these are $0.03, $0.15, $1.20 and $3.00 for states 1-4) and a selling price psell↪s = 0▷75pbuy↪s . With probability 0.5, this Markov chain remains in the current state and otherwise transitions to one of its direct neighbours. These states represent off-peak and peak times, with some intermediate steps.

To test Algorithm 1, we consider a range of thresholds based on the prices that can occur in the various states. Specifically, we set ⇢low = ⇢high = pbuy↪s for each state s. In addition to Algorithms 2 and 3, we also consider a NoV2G algorithm, which does not allow discharging but charges to minimise the overall expected cost. This represents a baseline benchmark against which we compare our algorithms, in order to quantify the benefit of using V2G for smart car parks.

3 This is to facilitate the computation of the transfers, as given in Theorem 1. In practice, the method described in [Babaioff et al., 2010] could be used instead.

7.2 Results

In the following, we vary a range of system parameters to test our algorithms in different settings. First, we are interested in how the number of vehicles in the car park affects the performance of the algorithms. To this end, we vary the expected number of arrivals over the course of the day from 10 to 300. Results are shown in Fig. 1a (social welfare) and 1b (aggregator utility).

Here, it is clear that Algorithm 1 performs poorly, even for the best threshold setting. This is mainly because the algorithm does not use a model of how prices evolve in the future and so takes poor decisions that lead to costly charging actions in the future. However, for the right choice of parameters, Algorithm 1 can perform better than the NoV2G baseline, in terms of both aggregator utility and social welfare. Algorithms 2 and 3 perform significantly better than any of the other benchmarks, achieving a positive aggregator utility in most cases. This means that the costs for buying electricity and paying vehicles for providing their battery for V2G are fully covered by the gains of selling electricity when prices are high.

While the utility is low in some settings, it is important to note that the aggregator here does not actually demand a payment for the electricity the agents receive or the parking service itself. In practice, this would be added (e.g., at a fixed rate per unit of required charge and per time parked), increasing the utility further. Furthermore, while the utility and welfare of Algorithms 2 and 3 are similar, their respective behaviours are not. Algorithm 2 tends to trade more with the grid, while Algorithm 3 relies more on charging and discharging internally.

Next, we consider how the availability of agents in the market affects the performance of the system. Specifically, Fig. 1c shows the effect of varying the maximum duration of an agent's stay in the car park. As welfare and aggregator utility are similar in all settings we tested (with utility being consistently higher), we now concentrate on the latter. Here, two opposing effects can be observed. Initially, as the duration increases, agents demand more charge as their feasible options increase, leading to a drop in welfare and aggregator utility (as noted above, this is partially because agents do not pay for the electricity they receive in this setup). However, as it increases further, the flexibility of agents increases, because they have more time beyond what is required to reach their desired charge. This leads to more opportunities for V2G, increasing the aggregator's utility.

We now turn to how features of the electricity market affect the performance of the V2G car park. To investigate this, we vary the probability of staying within a given price state, indicating how static the market is. This is shown in Fig. 1d, where it is clear that a more dynamic market (lower probability), leads to a higher utility for the aggregator. This is because there are more opportunities for buying at low prices and selling at high prices. A static market, in turn, means that the market may remain at a high price state for the entire day, leading to high electricity costs.

Finally, we investigate the relationship between buying and selling prices in Fig. 1e, by setting the selling prices to psell↪s = bpbuy↪s and varying b from 0 to 1. Clearly, a higher selling price results in higher aggregator utility, and it is also evident that Algorithms 2 and 3 perform similarly to the NoV2G algorithm when prices are too low. Interestingly, Algorithm 3 here outperforms Algorithm 2 slightly, as it enables agents to trade electricity internally.

8 Conclusions and FutureWork

To the best of out knowledge, this is the first work that formalises the V2G problem as an online mechanism design problem. We identify sufficient conditions for truthfulness, design three algorithms for this scenario, two of which are proved to be truthful, and empirically evaluate them.

There are several extensions we leave to future work. First, we aim to model more realistic battery types, where the cost increases with the number of charging-discharging cycles and costs are non-linear in the (dis)charged amount of electricity. Other issues relevant for practice include losses during discharging, and batteries with different round-trip efficiencies. Second, a range of other algorithms could be designed or adapted for this problem, such as those recently developed in the field of online stochastic combinatorial optimisation [Scott et al., 2013]. Finally, we aim to evaluate our techniques using a real case study and data, such as modelling the arrival and departure of EVs in a shopping center.

Acknowledgements

This work was supported by the EPSRC-funded ORCHID project (http://www.orchid.ac.uk) and by the European Community's Seventh Framework Programme (FP7/2007-2013) under grant agreement n. 600854 'SmartSociety - Hybrid and Diversity-Aware Collective Adaptive Systems: Where people meet machines to build smarter societies' (http://www.smartsociety-project.eu/). All data supporting this study are openly available from the University of Southampton repository at http://dx.doi.org/10.5258/SOTON/391163.