Title: Differentially Private Resource Auction in Distributed Spatial Crowdsourcing
Authors: Yin Xu, Mingjun Xiao, Xiang Zou and An Liu
Abstract: In this paper, we study a new type of Spatial Crowdsourcing (SC), namely Distributed SC (DSC), which can support a variety of location-relative services demanded by different requesters with low latency and bandwidth costs. In DSC, requesters need to compete for limited resources so as to deploy their desired SC services, and the requested resources must be allocated together to meet the demand of the service. We model this competitive resource allocation problem as a combinatorial auction process. Since this problem is NP-hard, we design an approximation algorithm to solve it. Besides, the leakage of sensitive information such as bids may incur severe economic damage, and there is a lack of works that can provide efficient protection without a trustworthy third-party. Based on this, we propose a novel Differentially private Resource Auction (DRA) mechanism. A bid confusion strategy based on differential privacy is designed against the untrusted third-party. Moreover, we prove that DRA offers ¥å-differential privacy, ¥ã-truthfulness, individual rationality and computational efficiency. Finally, extensive simulations on a real trace confirm the efficacy of DRA and indicate good performance in accordance with the design expectations.
