Online Mechanisms for Charging Electric Vehicles in Settings with Varying Marginal Electricity Costs

Keiichiro Hayakawa, Enrico H. Gerding, Sebastian Stein, Takahiro ShigaIJCAI 2015

Abstract

As electric vehicle (EV) adoption grows, managing the intermittent nature of renewable energy becomes critical. This paper introduces a novel class of online incentive mechanisms for EV charging aggregators. It is the first to guarantee dominant strategy incentive compatibility (DSIC) while accounting for varying marginal electricity costs and multi-dimensional user preferences. Realistic simulations demonstrate that the proposed mechanism achieves approximately 98% of optimal social welfare.

Introduction: The Challenge of EV Charging Coordination

The transition to renewable energy sources like wind and solar introduces significant supply volatility. To maintain grid stability, demand response aggregators must incentivize EV owners to shift charging to periods of high supply or low demand. However, existing systems often place a high cognitive burden on users, requiring them to monitor prices and strategically report their needs.

Previous research into online mechanism design has struggled to balance efficiency with the reality of increasing marginal costs—where charging additional vehicles becomes progressively more expensive as higher-cost generators are activated. Furthermore, many existing models are prone to inefficiencies, such as canceling charging sessions at the last minute. This research seeks a mechanism that is computationally efficient, handles marginal costs, and ensures that "truthful reporting" is the optimal strategy for every user.

Methodology: The Generic Mechanism Framework

The authors propose a Generic Mechanism that decouples the pricing rule from the scheduling algorithm. This framework addresses uncertainty and strategic behavior through several key innovations:

  1. Non-Decreasing Price Constraint: To prevent users from delaying their reports to wait for lower prices, the mechanism ensures that quoted prices for future time slots can only remain stable or increase over time.
  2. Marginal Payment Vectors: Payments are calculated based on the "externality" an agent imposes on the system, similar to the Vickrey-Clarke-Groves (VCG) mechanism.
  3. Scheduling Constraints: The system employs two specific constraints—a "temporarily assigned number of units" and an "upper limit allocation"—to ensure feasibility and prevent the revocation of previously promised energy.
  4. MIP Optimization: While pricing uses a heuristic approach for speed, the final scheduling is determined via a Mixed Integer Program (MIP) to maximize social welfare across all active agents.

Experimental Evaluation

The mechanism was evaluated using real-world data from Japan, including hourly electricity prices from the Japan Electric Power Exchange (JEPX), household demand profiles, and EV user behavior surveys from Nagoya City. Synthetic marginal valuations were assigned to simulate diverse user priorities.

Key Results and Insights

Efficiency and Near-Optimality

In simulations with up to 300 agents, the proposed mechanism consistently achieved approximately 98% of the theoretical maximum social welfare (the "Optimal" foresight scenario). It significantly outperformed other DSIC baselines, such as "Greedy with Cancellation" (GCOD), which often suffers from wasted energy due to revoked allocations.

Efficiency comparison of the proposed mechanism against various baselines (left) and a zoomed-in view of high-performance regimes (right).

Balancing Welfare and Profit

A critical feature of the proposed mechanism is its tunability. By scaling the costs used in the pricing rule, an aggregator can trade off a small amount of social welfare to generate higher profits. This makes the system a viable tool for commercial entities.

Trade-off between social welfare (efficiency) and aggregator profit for the Proposed and FCFS mechanisms.

As shown in the figures, the proposed mechanism maintains high efficiency while allowing for a sustainable business model, generating roughly 44% more profit than FCFS in tuned scenarios.

Conclusion and Future Directions

This paper provides a robust framework for automated EV charging that respects both grid constraints and user incentives. By ensuring DSIC, it removes the need for users to "game" the system. Future work will look to expand the model to include variable charging rates, "all-or-nothing" user preferences, and stochastic modeling of renewable generation to better handle price uncertainty.

Summary updated

BibTeX
@inproceedings{hayakawa2015online,
  author = {Keiichiro Hayakawa and Enrico H. Gerding and Sebastian Stein and Takahiro Shiga},
  title = {{Online Mechanisms for Charging Electric Vehicles in Settings with Varying Marginal Electricity Costs}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure