Vehicle-to-grid (V2G) is a promising approach whereby electric vehicles (EVs) are used to store excess electricity supply (e.g., from renewable sources), which is sold back to the grid in times of scarcity. In this paper we consider the setting of a smart car park, where EVs come and go, and can be used for V2G while parked. We develop novel allocation and payment mechanisms which truthfully elicit the EV owners' preferences and constraints, including arrival, departure, required charge, as well as the costs of discharging due to loss of efficiency of the battery. The car park will schedule the charging and discharging of each EV, ensuring the constraints of the EVs are met, and taking into consideration predictions about future electricity prices. Optimally solving the global problem is intractable, and we present three novel heuristic online scheduling algorithms. We show that, under certain conditions, two of these satisfy monotonicity and are therefore truthful. We furthermore evaluate the algorithms using simulations, and we show that some of our algorithms benefit significantly from V2G, achieving positive benefit for the car park even when agents do not pay for using it.

@en

Following previous work on payment redistribution in static mechanisms, we develop the theory of redistribution in online mechanisms (e.g., [2, 10, 8]). In static mechanisms, redistribution is important as it increases social welfare in scenarios with no residual claimant. Many online scenarios also do not have a natural residual claimant, and redistribution there is equally important. In this work, we adopt a fundamental online mechanism design model where a single expiring item is allocated in each of T periods. Agents with unit demand are present in the market between their arrival and departure periods, which are private information along with the value an agent attributes to the item. For this model, we derive a number of properties characterizing redistribution in online mechanisms (including revenue monotonicity properties, and quantifying the effect an agent can have on the total revenue). We then design two redistribution functions. The first one generalizes the static redistribution proposed by Cavallo [2] making redistribution after the departure of the last agent. For this redistribution function we provide theoretical worst-case guarantees. The second function is truly "online" making redistribution to each agent on her departure. The performance of both functions is evaluated using numerical simulations.@en