1. Differentially Private Combinatorial Cloud Auction
- Author
-
Yan Xu, Zhili Chen, Tianjiao Ni, Hong Zhong, Lin Chen, and Shun Zhang
- Subjects
FOS: Computer and information sciences ,TheoryofComputation_MISCELLANEOUS ,Mathematical optimization ,Computer Science - Cryptography and Security ,Computer Networks and Communications ,Unit price ,business.industry ,Computer science ,Cloud computing ,computer.software_genre ,Computer Science Applications ,Hardware and Architecture ,Virtual machine ,Clearing ,Revenue ,Differential privacy ,Resource allocation ,business ,Cryptography and Security (cs.CR) ,Time complexity ,computer ,Software ,Information Systems - Abstract
Cloud service providers typically provide different types of virtual machines (VMs) to cloud users with various requirements. Thanks to its effectiveness and fairness, auction has been widely applied in this heterogeneous resource allocation. Recently, several strategy-proof combinatorial cloud auction mechanisms have been proposed. However, they fail to protect the bid privacy of users from being inferred from the auction results. In this paper, we design a differentially private combinatorial cloud auction mechanism (DPCA) to address this privacy issue. Technically, we employ the exponential mechanism to compute a clearing unit price vector with a probability proportional to the corresponding revenue. We further improve the mechanism to reduce the running time while maintaining high revenues, by computing a single clearing unit price, or a subgroup of clearing unit prices at a time, resulting in the improved mechanisms DPCA-S and its generalized version DPCA-M, respectively. We theoretically prove that our mechanisms can guarantee differential privacy, approximate truthfulness and high revenue. Extensive experimental results demonstrate that DPCA can generate near-optimal revenues at the price of relatively high time complexity, while the improved mechanisms achieve a tunable trade-off between auction revenue and running time., 12 pages, 6 figures
- Published
- 2023