Efficient Auction Games

Over the past decade, smart grid systems, which integrate communication, control, and sensing technologies, have been deployed as hot research topics due to the stress operations of the power grid, increasing power demand, high penetration of renewable energy, and environment requirements [1, 2]. The researches that aim at cost saving, environmental friendly and intelligent operation of future grids cover economic dispatch and energy management in power grids, power markets, coordination of electric vehicles (EVs), demand response, secure problems, etc.

We study how to efficiently allocate the infinitesimal divisible resource under auction mechanism. In this chapter, we mainly focus on allocating a fixed amount of a single-type resource. A VCG-type auction mechanism is proposed with a two-dimensional bid, which specifies a per unit price and a maximum of the demand. Due to the absence of enough information related to the infinite-dimensional valuations of individual players in a single-bid strategy, it is challenging to implement the efficient Nash equilibrium (NE) in a dynamic way. In this chapter, we introduce a pair of parameters related to players’ valuations, and design a decentralized dynamic process assisted with this pair of values, such that at each iteration, a single player updates its best bid under a constrained set of demand. Under the proposed auction mechanism, we show the incentive compatibility, efficiency, and uniqueness of the NE. Furthermore, our method is guaranteed to converge to the efficient NE, and it presents the enhanced convergence performance compared with those methods proposed in the literature. Case studies are given to demonstrate the results developed in this work.

With an effort to allocate divisible resources among suppliers and consumers, a double-sided auction model is designed to decide strategies for individual players in this chapter. Under the auction mechanism with the VCG-type payment, the incentive compatibility holds, and the efficient bid profile is a Nash equilibrium (NE). Different from the single-sided auction in the previous chapter, there exists an infinite number of NEs in the underlying double-sided auction game, which brings difficulties for players to implement the efficient solution. To overcome this challenge, we formulate the double-sided auction game as a pair of single-sided auction games which are coupled via a joint potential quantity of the resource. A decentralized iteration procedure is then designed to achieve efficient solution, where a single player, a buyer or a seller, implements his best strategy with respect to a given potential quantity and a constraint on his bid strategy. Accordingly, the potential quantity is updated with respect to iteration steps as well. It is verified that the system converges to the efficient NE within finite iteration steps in the order of \(\mathscr {O}(\ln (1/\varepsilon ))\) with \(\varepsilon \) representing the termination criterion of the algorithm.

This chapter studies a class of auction-based resource allocation games under a hierarchical structure, such that each supplier is assigned a certain amount of resource from a single provider and allocates it to its buyers with auction mechanisms. To implement the efficient allocations for the underlying hierarchical system, we first design an auction mechanism, for each local system composed of a supplier and its buyers, which inherits the advantages of the progressive second price (PSP) mechanism. By employing a dynamic algorithm, each local system converges to its own efficient Nash equilibrium (NE), at which the efficient resource allocation is achieved and the bidding prices of all the buyers in this local system are identical to each other. After the local systems reach their own equilibria, respectively, the resources assigned to suppliers are readjusted via a dynamic hierarchical algorithm with respect to the bidding prices associated with the implemented equilibria of local systems. By applying the proposed hierarchical process, the formulated hierarchical system can converge to the efficient allocation under certain mild conditions. The developed results in this work are demonstrated with simulations.

Auctions, e.g., market clearing price (MCP) auctions, have been widely adopted in electricity markets, and progressive second price (PSP) auctions are stated possessing promising properties of incentive compatibility and efficiency. In this work, we study the coordination of large-scale elastic loads in deregulated electricity markets under MCP and PSP auctions. To explore the performances of these auctions in the underlying problems, we focus on key issues of the payment comparison, incentive compatibility, and efficiency of Nash equilibrium (NE), and develop the following results: (i) The individual payment under MCP is always higher than that under PSP, and their difference vanishes asymptotically as the system scale increases; (ii) The incentive compatibility holds under PSP, and holds under MCP only with respect to others’ efficient bid profile; (iii) The efficient bid profile under PSP auctions is a NE, while that under MCP is an \(\varepsilon \)-NE which degenerates to a NE asymptotically as the system scale increases. With these analyses, we claim that it is pretty promising to apply both MCP and PSP auctions to the large-scale load coordination problems in deregulated electricity markets.

This chapter studies the economic operations of the microgrid in a distributed way such that the operational schedule of each of units, like generators, load units, storage units, etc., in a microgrid system is implemented by autonomous agents. In this problem, the divisible resource is electricity resource in the system and we apply the progressive second price (PSP) auction mechanism to efficiently allocate the resource. Considering the economic operation for the microgrid systems, the generators play as sellers to supply energy and the load units play as the buyers to consume energy, while a storage unit, like battery, supercapacitor, etc., may transit between buyer and seller, such that it is a buyer when it charges and becomes a seller when it discharges. This problem is different from the double-sided auction game specified in Chap. 3 due to the existence of the storage units. Furthermore, when the microgrid is in a connected mode, each individual unit competes against not only the other individual units in the microgrid but also the exogenous main grid possessing fixed electricity price and infinite trade capacity; that is to say, the auctioneer assigns the electricity among all individual units and the main grid with respect to the submitted bid strategies of all individual units in the microgrid in an economic way. Due to these distinct characteristics, the underlying auction games are distinct from those studied in the literature. We show that under mild conditions, the efficient economic operation strategy is a Nash equilibrium (NE) for the PSP auction games, and propose a distributed algorithm under which the system can converge to a NE. We also show that the performance of worst NE can be bounded with respect to the system parameters, say the energy trading price with the main grid, and based upon that, the implemented NE is unique and efficient under some conditions.

Emerging plug-in electric vehicles (PEVs), as distributed energy sources, are promising to provide vehicle-to-grid (V2G) services for the power grid, like frequency and voltage regulations, by coordinating their active and reactive power rates. However, due to the autonomy of PEVs, it is challenging how to efficiently schedule the coordination behaviors among these units in a distributed way. In this chapter we formulate the underlying coordination problems as a novel class of VCG-style auction games where players, power grid, and PEVs, do not report a full cost or valuation function but only a multi-dimensional bid signal: the maximum active and reactive power quantities that power grid wants and the maximum per unit prices it is willing to pay, the maximum active and reactive power quantities that a PEV can provide and the minimum per unit prices it asks. From this formulation, the underlying V2G problem is actually a two-type resource allocation problem featuring the active and reactive power as resources. We show the existence of an efficient Nash equilibrium (NE) for the underlying auction games, though there may exist other inefficient NEs. In order to deal with large-scale PEVs, we design games with aggregator players each of which submits bid profiles representing the overall utility for a collection of PEVs, and extend the so-called quantized-PSP mechanism to the underlying auction games to implement an efficient NE.

A novel class of auction games is formulated to study coordination problems arising from charging a population of electric vehicles (EVs) over a finite horizon. Different from those analyzed in the above chapters, the charging power of EVs at different time slots could be regarded as multi-type resources, and there exist coupling constraints among these resources, say the total charging power over the whole horizon should not exceed the battery size of EVs in this scenario. 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. The use of the progressive second price (PSP) auction mechanism ensures that incentive compatibility holds for the auction games. 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.

This book focuses on auction games to efficiently allocate resources. It is divided into two parts: theory part and applications in smart grids and electric vehicle charging. In the theory part, the book studies three classes of resource allocation problems, say single-sided, double-sided, and hierarchical, designing the corresponding auction games and algorithms to achieve an efficient equilibrium in a decentralized way. The followed part is the application of auction games in the problems of elastic loads management in electricity markets, economic operation of the microgrid, V2G service regulation, and EV charging coordination. Different from the general single-sided, double-sided, and hierarchical resource allocation problems considered in the theory part, all of those application problems have special characteristics, e.g., in the problem of economic operation of the microgrid, there exist three-side participants. In the following, we conclude this book in seven parts.