Mobile crowd sensing with smartphones [1–۴] has gradually bloomed into an appealing paradigm to collect various distributed sensing data for purposes [5]. The main application can be associated with the development and promotion of mobile crowd sensing systems such as the noise map calculation [6], real-time traffic delay prediction [7], citizen emergency monitoring [8] and so forth. Embedded with a variety of sensors, like GPS(Global Position System), microphone, camera, a smartphone can easily collect the essential data for various applications. Especially, smartphones gather ubiquitous data but only claim the little money, probably leading to enormous economic as well as the improvement of life quality [9]. A mobile crowd sensing system typically consists of a platform residing in the cloud, mobile smartphones and the platform users who consume sensing data. An example is illustrated in Fig. 1. The associated sensing tasks with diverse weights are released by the platform once it receives new arriving sensing requests from the platform users. Then the platform determines the appropriate set of smartphones to provide sensing services for new sensing tasks. Once receiving the hiring decision from the platform, the chosen smartphone starts to collect the required sensing data. Later, it submits the collected data to the platform, which aggregates the data to the platform user. Finally, the platform pays for the data. This demonstrates that a mobile crowd sensing system with geographically distributed smartphones can support a wide range of large-scale monitoring applications [8,10]. Motivation: Stimulating smartphone users to participate in mobile crowd sensing system is fairly significant to the success of mobile crowd sensing with smartphones. As we know, it incurs some nonnegligible cost (e.g., power consumption, bandwidth occupation) in consideration of limited resources when a smartphone provides sensing service for various applications [11,12]. Specifically, for our case, smartphones allocated to sensing tasks with higher weight are paid for more money, in consideration of more spent cost(e.g., time cost). Furthermore, smartphone users may suffer the risk of privacy breach when providing sensing service related to their current location. Thus, smartphone users are usually reluctant to join a mobile crowd sensing system without sufficient incentives as compensation.