TL;DR
This paper introduces a novel price-based iterative double auction mechanism designed to efficiently match electric vehicle (EV) drivers with private charger owners in a sharing economy model. The proposed auction aims to maximize social welfare by considering individual rationality, budget balance, and truthful reporting of charging constraints, while also demonstrating strong performance and scalability compared to existing methods.
What Problem Does This Paper Address?
The rapid growth of electric vehicles (EVs) is placing immense strain on existing charging infrastructure, necessitating innovative solutions. Charger sharing platforms, akin to Airbnb for EV charging, offer a cost-effective way to expand charging networks by connecting private charger owners with EV drivers. However, the success of these platforms hinges on sophisticated mechanisms that can effectively match buyers (drivers) and sellers (charger owners) while ensuring fairness and efficiency. Traditional approaches like First-Come-First-Served (FCFS) lack individual rationality and don't account for strategic behavior. While some market-based solutions exist, they often struggle with computational complexity, especially in two-sided markets where both buyers and sellers have private information and act in their self-interest. This paper addresses the challenge of designing a decentralized, efficient, and truthful mechanism for this two-sided charger sharing market.
Methods
The core contribution is a Price-Based Iterative Double Auction (P-IDA). This mechanism operates in rounds, where charger owners (sellers) submit "asks" (availability and price per unit time) and EV drivers (buyers) submit "bids" (desired charging times, duration, and willingness to pay).
Key aspects of the method include:
- Iterative Bidding: Unlike one-shot auctions, P-IDA allows participants to adjust their bids and asks over multiple rounds based on provisional schedules provided by an auctioneer. This iterative process helps reveal private information gradually and reduces the computational burden per round.
- Price-Based Clearing: The auctioneer uses a winner determination model to compute a provisional schedule that maximizes social welfare (total buyer value minus total seller cost). This model considers constraints like charging duration, time windows, and seller availability.
- Truthfulness Guarantees: The paper proves that P-IDA is individually rational (participants are no worse off than not participating) and budget-balanced. Crucially, it establishes that truthfully reporting charging time constraints (arrival/departure times, charging duration) is a weakly dominant strategy for both buyers and sellers, simplifying strategic behavior.
- Simulated Annealing for Scalability: To handle large-scale problems where optimal winner determination is computationally infeasible, the authors incorporate a Simulated Annealing (SA) meta-heuristic. This "P-IDA-SA" approach provides near-optimal solutions within reasonable timeframes.
- XOR-Bid Strategy: Buyers can employ an XOR-bid strategy, allowing them to submit multiple bids that are mutually exclusive, which can improve efficiency.
Datasets
The paper does not introduce a new dataset. Instead, it generates synthetic testing data for evaluation.
- Generated Testing Data: 15 groups of testing data were created, varying the number of sellers (4-20) and buyers (5-150), with 10 instances randomly generated for each group. This allows for testing the algorithm's performance across different market sizes and configurations.
Key Insights and Ideas
- Decentralization and Privacy: The P-IDA effectively handles the decentralized nature of charger sharing, where participants have private information. It avoids the need for agents to reveal their complete valuations upfront, unlike some other mechanisms.
- Iterative Bidding as a Computational Strategy: The iterative nature of the auction is not just for eliciting truthful bids but also as a practical strategy to break down a complex optimization problem into smaller, manageable sub-problems solved in each round.
- Truthfulness as a Weakly Dominant Strategy: Proving that truthful reporting is a weakly dominant strategy is a significant theoretical contribution. It means participants have no incentive to lie about their constraints, simplifying the mechanism's design and improving the reliability of allocations.
- Scalability through Meta-heuristics: The integration of Simulated Annealing demonstrates a practical approach to applying sophisticated auction mechanisms to real-world scenarios where computational resources are limited.
Key Results
- Efficiency: P-IDA with a single-bid strategy achieved an average of 94% efficiency compared to optimal solutions across tested groups, significantly outperforming the FCFS algorithm (around 88%). XOR-bid strategies further improved efficiency to 97-98%.
- Profit Ratio: The profit ratio, measuring seller gains, was positively correlated with the maximum bid price allowed (a_max). With a_max = 7, P-IDA achieved an average of 70% profit ratio.
- Scalability (P-IDA-SA): The P-IDA-SA approach demonstrated strong performance on larger problem instances (Groups 13-15), achieving social welfare that was, on average, 4% higher than a greedy allocation mechanism and 40% higher than FCFS.
- Running Time: The computation time for P-IDA decreased with larger values of the bid increment/decrement parameter (€), but this also led to slightly lower efficiency. XOR-bid-repeating strategies, while more efficient, incurred higher computation times.
Limitations and Future Work
- Restricted Reports: The theoretical guarantees of truthfulness are based on "restricted reports," meaning sellers cannot report earlier start times or later end times, and buyers cannot report earlier arrival or later departure times. This assumption simplifies the analysis but might not fully capture all real-world scenarios.
- Myopic Best-Response: Participants are assumed to follow myopic best-response strategies, reacting to current prices rather than anticipating future market dynamics. This is a common assumption in large markets but might not hold for sophisticated agents.
- Day-Ahead Scheduling: The current P-IDA is designed for a day-ahead charging setting. The authors suggest extending the framework to accommodate online, dynamic charger sharing scheduling as a future research direction.
- Further Exploration of Bidding Strategies: While XOR-bid-repeating showed high efficiency, its computational cost warrants further investigation and potential optimizations.
Summary updated