Demand response (DR) is not only a crucial solution to the demand side management but also a vital means of electricity market in maintaining power grid reliability, sustainability and stability. DR can enable consumers (e.g. data centers) to reduce their electricity consumption when the supply of electricity is a shortage. The consumers will be rewarded in the case of DR if they reduce or shift some of their energy usage during peak hours. Aiming at solving the efficiency of DR, in this paper, we present MEDR, a mechanism on emergency DR in colocation data center. First, we formalize the MEDR problem and propose a dynamic programming to solve the optimization version of the problem. We then design a deterministic mechanism as a solution to solve the MEDR problem. We show that our proposed mechanism is truthful. Next, we prove that our mechanism is an FPTAS, i.e., it can be approximated within @math for any given @math , while the running time of our mechanism is polynomial in @math and @math , where @math is the number of tenants in the datacenter. Furthermore, we also give an auction system covering the efficient FPTAS algorithm as bidding decision program for DR in colocation datacenter. Finally, we choose a practical smart grid dataset to build a large number of datasets for simulation in performance evaluation. By evaluating metrics of the approximation ratio of our mechanism, the non-negative utility of tenants and social cost of colocation datacenter, the results demonstrate the effectiveness of our work.
@cite_24: We give the first black-box reduction from approximation algorithms to truthful approximation mechanisms for a non-trivial class of multi-parameter problems. Specifically, we prove that every welfare-maximization problem that admits a fully polynomial-time approximation scheme (FPTAS) and can be encoded as a packing problem also admits a truthful-in-expectation randomized mechanism that is an FPTAS. Our reduction makes novel use of smoothed analysis by employing small perturbations as a tool in algorithmic mechanism design. We develop a “duality” between linear perturbations of the objective function of an optimization problem and of its feasible set, and we use the “primal” and “dual” viewpoints to prove the running time bound and the truthfulness guarantee, respectively, for our mechanism.
@cite_4: The smart grid is a modern power grid that achieves high efficiency and robustness through sophisticated information and communications technology. Demand response has great potential in helping balance demand and supply in a smart grid, cutting generation cost and carbon footprint, and improving system stability. Auctions represent a natural and efficient approach for carrying out demand response between the power grid and large electricity users, microgrids, and electricity storage devices. This work explores the modeling and design space of demand response auctions, targeting expressive power, truthful information revelation, computational efficiency, and economic efficiency. We present a randomized auction that explores the underlying problem structure of demand response, and prove that it is truthful, runs in polynomial time, and achieves @math -optimal social cost for an arbitrarily small constant @math . The key technique lies in the marriage of smoothed analysis and randomized reduction, which makes its debut in this work among literature on mechanism design, and can be applied to problems where social welfare optimization is NP-hard but admits a smoothed polynomial-time algorithm.
A closely related work is DR in smart grids. @cite_4 studied the mechanism design on DR in smart grids. Let @math , and there is an upper bound on the BES, i.e. @math . A randomized FPTAS mechanism was given in @cite_4 . Their idea is to combine with smooth analysis and randomize auction. Actually, Dough and Roughgarden @cite_24 showed that if there exists an FPTAS approximation, then this algorithm can be transformed into a truthful in expectation mechanism that retains the FPTAS property. The work in @cite_24 does not require the existence of FPTAS. However, it still remains open whether there exists a deterministic FPTAS.