Budget-Feasible Online Incentive Mechanisms for Crowdsourcing Tasks Truthfully

Mobile crowd sensing (MCS) is a new paradigm that takes advantage of pervasive mobile devices to efficiently collect data, enabling numerous novel applications. To achieve good service quality for an MCS application, incentive mechanisms are necessary to attract more user participation. Most existing mechanisms apply only for the offline scenario where all users report their strategic types in advance. On the contrary, we focus on a more realistic scenario where users arrive one by one online in a random order. Based on the online auction model, we investigate the problem that users submit their private types to the crowdsourcer when arriving, and the crowdsourcer aims at selecting a subset of users before a specified deadline for maximizing the value of services (assumed to be a nonnegative monotone submodular function) provided by selected users under a budget constraint. We design two online mechanisms, OMZ and OMG, satisfying the computational efficiency, individual rationality, budget feasibility, truthfulness, consumer sovereignty, and constant competitiveness under the zero arrival-departure interval case and a more general case, respectively. Through extensive simulations, we evaluate the performance and validate the theoretical properties of our online mechanisms.