Mobile crowd sensing (MCS) is a new paradigm for urban-scale monitoring. This paper concentrates on the Cost-Fair Task Allocation (CFA) problem for the MCS scenario where the collaboration of multiple probabilistic mobilephone users is needed to yield more reliable observation. CFA aims to allocate sensing tasks to users so that the sensing costs undertaken by all users are as balancing as possible, while the requirement of the requester for data reliability can be satisfied. CFA is greatly important to MCS campaigns in terms of reliability and sustainability. We design two algorithms to solve the CFA problem in the offline and online cases, respectively. Specifically, we propose a novel penalty-based model to reformulate the offline CFA problem, and based on this model, we design an offline algorithm, which can yield a computation-efficient ε-solution with any small ε > 0. For the online case, we design a polynomial-time approximation algorithm, which struggles to allocate each of the sequentially arriving tasks to users as fairly as possible, and can achieve an upper-bounded competitiveness relative to the optimal CFA solution. Finally, we conduct extensive numeric analyses to validate the performance of our algorithms under diverse experimental setups.

Sample average approximation method is one of the well-behaved methods in the stochastic optimization. This paper presents a sample average approximation method based on a D-gap function for stochastic variational inequality problems. An unconstrained optimization reformulation is proposed for the expected-value formulation of stochastic variational inequality problems based on the D-gap function. An implementable sample average approximation method for the reformulation is established and it is proven that the optimal values and the optimal solutions of the approximation problems converge to their true counterpart with probability one as the sample size increases under some moderate assumptions. Finally, the preliminary numerical results for some test examples are reported, which show that the proposed method is promising.