Linear Online Incentive Mechanism Design: Case Study of Crowdsensing with Random Task Arrivals

In this chapter, we use crowdsensing as the case study to show how we can design a linear online incentive mechanism design to address the potential random task arrivals. We focus on jointly considering cost budget and quality of sensed data at each participant. Specifically, following task arrivals, the platform must make decisions in a sequence to select a specific number of participants to obtain a sound competitive ratio. To address this issue, an online strategy proof incentive mechanism is designed to minimize the social cost of the whole system and achieve truthfulness by applying the auction framework. Moreover, in order to further improve the competitive ratio of the online algorithm, a more efficient online scheme is introduced when extra information on participants is available at the platform.