Aggregating Large-Scale Residential Users for Regulation Reserve Provision: Truthful Combinatorial Auction Based Approach

The proliferation of flexible loads has empowered residential users in contributing both upward and downward frequency regulation reserves to the power grid. Due to barriers like minimum bid size, residential users with relatively small power consumption must be aggregated before they can enter the reserve market. However, the large number of residential users renders the aggregation mechanism design problem a challenging task. In particular, the cost for reserve provision of each user is not only highly heterogeneous, but also coupled through both the temporal dimension and the up/down regulation direction. In order to allow the users to fully express their costs, in this paper, we propose a combinatorial reverse auction (CRA) framework as the market mechanism for user aggregation. In this auction, the aggregator is the auctioneer and procures reserves from residential users. The users submit package bids consisting of combinations of both upward and downward reserves over multiple time-slots, capturing the coupling in the user cost. Furthermore, to address the infamous computational challenges of large-scale combinatorial auctions, we develop a novel fast combinatorial auction (FCA) mechanism that can be solved in polynomial time. It includes an approximate winner determination algorithm and a critical payment scheme. Notably, our proposed mechanism is rigorously proved to possess desirable economic properties such as truthfulness and individual rationality. Extensive simulations have validated the theoretic properties of the proposed CRA mechanism and its advantages over existing methods. In particular, compared with the widely employed truthful Vickery-Clarke-Groves (VCG) mechanism, CRA can be <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$10^{4}$</tex-math></inline-formula> times faster than VCG when the user number is above 1000. Meanwhile, it is able to achieve near-optimal social cost, where the average optimality loss is 2.92%.