Leveraging on the pervasiveness of mobile phones and their rich built-in sensors, participatory sensing recently emerged as a promising approach to large-scale data collection. Whilst some contributors may be altruistic, many contributors are motivated by receiving something in return for their contributions, proportional to their level of contributions. In this paper, we adopt a service allocation approach that motivates users by allocating a determined amount of compelling services to contributors, as an alternative to other credit or reputation based incentive approaches. To address two major concerns that would arise from this approach, namely fairness and social welfare, we propose two service allocation schemes called Allocation with Demand Fairness (ADF) and Iterative Tank Filling (ITF), which is an optimization-based approach. We show that: (i) ADF is max–min fair and scores close to 1 on the Jain’s fairness index, and (ii) ITF maximizes social welfare and achieves the unique Nash equilibrium, which is also Pareto and globally optimal. In addition, we use stochastic programming to extend ITF to handle uncertainty in service demands that is often encountered in real-life situations.