331
Mechanism Design for Mobile Crowdsensing with Execution Uncertainty
Zhenzhe Zheng, Zhaoxiong Yang, Fan Wu and Guihai Chen
Shanghai Jiao Tong University, Shanghai Jiao Tong University, Shanghai Jiao Tong University, Shanghai Jiao Tong University

Mobile crowdsensing has emerged as a promising paradigm for data collection due to increasingly pervasive and powerful mobile devices. There have been extensive research works that propose incentive mechanisms for crowdsensing, but they all make the assumption that the mobile user will positively complete the allocated sensing task. In this paper, we consider a new scenario of crowdsensing where a user may fail to complete the task. For example, we suppose the user continuously collect data with his device in the background, and he completes the sensing task only if he passes through the location of interest. Due to the users mobility pattern, he may succeed or fail in the task. It is an important issue for the incentive mechanism to ensure fault tolerance for each sensing task. We design reverse auctions to model the interaction between the platform and mobile users, in which users probability of success and cost to perform the tasks are private information, and we aim to guarantee the tasks to be completed with high probability, while minimizing the social cost. We prove that minimizing the social cost is an NP-hard problem, and present mechanisms that achieve truthfulness and guaranteed approximation ratio. We perform extensive simulations to validate the desirable properties of our mechanisms.