Differentially Private Mechanisms for Budget Limited Mobile Crowd sourcing
ABSTRACT
Recently, Mobile Crowd sourcing (MC) has aroused great interest on the part of both academic and industrial circles. One of the key problems in MC is designing the proper mechanisms to incentivize user participation, as users are typically self-interested and must consume a substantial amount of MC resources/costs. Although considerable research has been devoted to this problem, the majority of studies have neglected the privacy issue in mechanism design. In this study, we consider the scenario where a mobile crowd sourcing platform aims to maximize the crowd sourcing revenue under a budget constraint, and users are interested in maximizing their utility while keeping their cost private. We design differentially-private mechanisms for such a scenario under an offline setting where users bid their costs simultaneously and under an online setting where user bids are revealed one by one. We show that our mechanisms simultaneously achieve provable performance bounds with respect to several measures, including revenue, differential privacy, truthfulness and individual rationality. Finally, we also conduct extensive numerical experiments to demonstrate the effectiveness of our approach.
EXISTING SYSTEM:
In recent years, the spread of smart phones has led to the proliferation of Mobile Crowd sourcing (MC) applications, where collected information about interested events can be acquired by assigning MC tasks to individuals (users). Due to its wide applications, MC has already aroused great interest on the part of academic and industrial circles. One of the central problems in MC is incentivizing user participation, as users are typically self-interested and incur substantial costs to perform MC tasks. However, the users may not report their true costs, as they are selfish/rational and may engage in strategic behavior to maximize their utility. Based on these observations, many incentivization mechanisms for MC have appeared. these mechanisms usually encourage users to participate in MC and behave truthfully through carefully determining the monetary payments to them, while satisfying various constraints such as a predefined budget on total payments. Nevertheless, the majority of previous studies on incentivization mechanism design for MC have neglected another important issue–user privacy. In practice, the users’ costs for participating in MC can be important information; leaks of this information may expose users personal status and hence harm user utility. For example, in a spatial crowd sourcing application, the users’ costs for performing MC tasks could be determined by their traveling costs to the Point of Interests (PoIs), so having the cost information in hand would allow attackers to infer the location information about the users. As the current incentivization mechanisms for crowdsourcing determine the payments to the users based on the users’ costs1, the cost information of the users can be easily leaked to any third party (or adversary) who observes the payment profile calculated by the crowd sourcing mechanism. One possible way to address this problem is to use the traditional syntactic approaches such as k-anonymity and ℓ-diversity to protect the users’ privacy. Roughly speaking, these syntactic approaches try to generalize the data entries such that the ability of an adversary to link a “quasi-identifier” tuple to sensitive values is restricted. However, it has been proved that these approaches are vulnerable, especially when the adversary has strong background knowledge. Therefore, a more prevailing approach for data privacy adopted by the recent work is Differential Privacy (DP) . The basic idea of DP is to add noises to the answers of data queries such that it becomes harder for an adversary who observes the output of the algorithm to distinguish two neighboring input datasets of the algorithm (in a probabilistic sense) . Compared to the traditional syntactic approaches, DP has a more rigorous mathematical framework for defining and preserving privacy, and it also adopts a stronger model on adversary’s background knowledge
PROPOSED SYSTEM:
In this paper, we study the problem of maximizing crowdsourcing revenue under a budget constraint on payments to users and propose mechanisms that achieve budget-feasibility, truthfulness, differential privacy and high revenue simultaneously. We consider both the offline setting where all users show up simultaneously and the online setting where users arrive sequentially in an arbitrary order. More specifically, our contributions can be summarized as follows: 1) In the offline setting, we first propose a benchmark mechanism called PWDP with a 1 2 performance ratio on the revenue without considering DP, and then provide a mechanism achieving ǫ-differential privacy and a performance ratio close to that of PWDP. 2) In the online setting, we propose DPP-UCB, a dynamic pricing mechanism based on the multi-armed-bandit paradigm [19]. We prove that DPP-UCB achieves ǫ-differential privacy and an O(logW log logW) regret bound with respect to revenue, where W is the predefined budget limit. 3) In addition to DP, we prove that all our proposed mechanisms achieve other nice properties including truthfulness, budget-feasibility and individual rationality [11]. 4) We conduct extensive numerical experiments to compare our algorithms with related studies, and the experimental results demonstrate the effectiveness of our approach. 5) To the best of our knowledge, we are the first to propose differentially private and budget-limited mechanisms for mobile crowdsourcing with provable performance bounds, both under the offline setting and under the online setting. The rest of our paper is organized as follows. We first formally formulate our problem in Sec. 2, and then introduce our mechanisms as well as their performance analysis in Sec. 3 and Sec. 4. The experimental results are shown in Sec. 5 The incentivization problem in mobile crowdsourcing has been extensively studied, and the related studies in this area can be found in two excellent surveys [39], [40]. In particular, the insightful survey in [39] has presented a novel and comprehensive taxonomy of existing incentive mechanisms for mobile crowdsourcing systems, and it has also discussed about the related approaches in depth. The more recent survey in [40] has proposed the first framework in the literature for defining and enforcing Quality of Information (QoI) in mobile crowdsourcing, and has also proposed some novel research challenges and possible research directions in this area.
CONCLUSION
We have studied the problem of designing differentially private incentivization mechanisms for mobile crowdsourcing, where the total payment to users should not exceed a predefined budget. We have proposed novel algorithms for our problem both in an offline setting and an online setting. We have shown that our mechanisms achieve provable theoretical performance bounds on revenue, truthfulness and differential privacy simultaneously, and the effectiveness of our approach has also been corroborated by the results of numerical experiments. To the best of our knowledge, we are the first to propose privacy-preserving mechanisms with provable performance bounds for budget limited mobile crowdsourcing. Although the effectiveness of our algorithms has been proved by both theoretical analysis and experimental evaluations, there are still several improvements that could be done. First, as our model only assumes homogeneous crowdsourcing tasks (and hence homogeneous task values), extending the current model to the case of heterogeneous tasks would be an interesting problem. Second, it would be interesting to design more efficient algorithms for our problem under the continuouspricing scenario, as the running time of the current algorithms could be high in this case. Third, although we have followed some related work (e.g., [20], [28], [33], [34]) to assume that there are some prior knowledge on the number of users under the online setting, designing algorithms for our problem without this assumption could make our approach more general. We plan to investigate all these issues in the future
REFERENCES:
[1] B. Guo, Z. Wang, Z. Yu, Y. Wang, N. Y. Yen, R. Huang, and X. Zhou, “Mobile crowd sensing and computing: The review of an emerging human-powered sensing paradigm,” ACM C
omputing Surveys, vol. 48, no. 1, pp. 7:1–7:31, 2015.
[2] Y. Singer, “Budget feasible mechanisms,” in FOCS, 2010, pp. 765– 774.
[3] N. Chen, N. Gravin, and P. Lu, “On the Approximability of Budget Feasible Mechanisms,” in SODA, 2011, pp. 685–699.
[4] X. Bei, N. Chen, N. Gravin, and P. Lu, “Budget feasible mechanism design: from prior-free to bayesian,” in STOC, 2012, pp. 449–458.
[5] T. Luo, S. S. Kanhere, H. P. Tan, F. Wu, and H. Wu, “Crowdsourcing with tullock contests: A new perspective,” in INFOCOM, 2015, pp. 2515–2523.
[6] D. Zhao, X. Y. Li, and H. Ma, “Budget-feasible online incentive mechanisms for crowdsourcing tasks truthfully,” IEEE/ACM Transactions on Networking, vol. 24, no. 2, pp. 647–661, 2016.
[7] D. Yang, G. Xue, X. Fang, and J. Tang, “Crowdsourcing to Smartphones: Incentive Mechanism Design for Mobile Phone Sensing,” in MobiCom, 2012, pp. 173–184.
[8] H. Jin, L. Su, B. Ding, K. Nahrstedt, and N. Borisov, “Enabling privacy-preserving incentives for mobile crowd sensing systems,” in ICDCS, 2016, pp. 344–353.
[9] P. Cheng, X. Lian, Z. Chen, R. Fu, L. Chen, J. Han, and J. Zhao, “Reliable diversity-based spatial crowdsourcing by moving workers,” in VLDB, 2015, pp. 1022–1033.
[10] R. Shokri, G. Theodorakopoulos, C. Troncoso, J.-P. Hubaux, and J.-Y. Le Boudec, “Protecting location privacy: optimal strategy against localization attacks,” in CCS, 2012, pp. 617–627.