An Efficient Game for Coordinating Electric Vehicle Charging

A novel class of auction-based games is formulated to study coordination problems arising from charging a population of electric vehicles (EVs) over a finite horizon. To compete for energy allocation over the horizon, each individual EV submits a multidimensional bid, with the dimension equal to two times the number of time-steps in the horizon. Use of the progressive second price (PSP) auction mechanism ensures that incentive compatibility holds for the auction games. However, due to the cross elasticity of EVs over the charging horizon, the marginal valuation of an individual EV at a particular time is determined by both the demand at that time and the total demand over the entire horizon. This difficulty is addressed by partitioning the allowable set of bid profiles based on the total desired energy over the entire horizon. It is shown that the efficient bid profile over the charging horizon is a Nash equilibrium of the underlying auction game. An update mechanism for the auction game is designed. A numerical example demonstrates that the auction process converges to an efficient Nash equilibrium. The auction-based charging coordination scheme is adapted to a receding horizon formulation to account for disturbances and forecast uncertainty.