Dynamic Resource Allocation and Pricing: A Randomized Auction Perspective

Date
2017
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Auctions are widely employed to allocate scarce resources among strategic users. Truthfulness is a desired property of auctions, for eliminating falsified bids. The celebrated VCG auction is truthful, yet it becomes computationally infeasible when the underlying winner determination problem is NP-hard. Simply substituting the optimal solutions with approximate solutions makes a VCG auction lose its truthfulness property. In this thesis, we aim to address this challenge by employing a randomized auction framework, which translates a cooperative approximation algorithm into a truthful auction. Four resource allocation problems are carefully studied. We first discuss dynamic resource provisioning in clouds through the auction of virtual machines (VMs). It generalizes the existing literature by introducing combinatorial auctions of heterogeneous VMs, and models dynamic VM provisioning. We then study electricity markets between power grids and microgrids, an emerging paradigm of electric power generation and supply. We address the economic challenges arising from such grid integration, and design a power auction that explicitly handles the Unit Commitment Problem, a key challenge in power grids. Both power markets with grid-to-microgrid and microgrid-to-grid energy sales are studied, with an auction designed for each, under the same randomized auction framework. We next study emergency demand response (EDR) in multi-tenant colocation data centers. EDR in colocation data centers is challenging, due to lack of incentives to reduce energy consumption by tenants who control their servers and are typically on fixed power contracts with the colocation. We propose a new auction mechanism using the framework to enable colocation EDR, which leverages a reverse auction to provide monetary remuneration to tenants according to their energy reduction. We further study the online electricity cost minimization problem at a colocation data center. Electricity billing faced by a data center is nowadays based on both the total volume consumed, and the peak consumption rate. This leads to an interesting new combinatorial optimization structure on the electricity cost optimization problem. Applying the randomized framework, we model and solve the problem through two approaches: the pricing approach and the auction approach.
Description
Keywords
Computer Science
Citation
Zhang, L. (2017). Dynamic Resource Allocation and Pricing: A Randomized Auction Perspective (Doctoral thesis, University of Calgary, Calgary, Canada). Retrieved from https://prism.ucalgary.ca. doi:10.11575/PRISM/25760