# Truthful Mechanism Design for Multiregion Mobile Crowdsensing

Authors: Yu Qiao; Jun Wu; Hao Cheng; Zilan Huang; Qiangqiang He; Chongjun Wang
Journal: Wireless Communications and Mobile Computing
 (2020)

---

## Abstract

In the age of the development of artificial intelligence, we face the challenge on how to obtain high-quality data set for learning systems effectively and efficiently. Crowdsensing is a new powerful tool which will divide tasks between the data contributors to achieve an outcome cumulatively. However, it arouses several new challenges, such as incentivization. Incentive mechanisms are significant to the crowdsensing applications, since a good incentive mechanism will attract more workers to participate. However, existing mechanisms failed to consider situations where the crowdsourcer has to hire capacitated workers or workers from multiregions. We design two objectives for the proposed multiregion scenario, namely, weighted mean and maximin. The proposed mechanisms maximize the utility of services provided by a selected data contributor under both constraints approximately. Also, extensive simulations are conducted to verify the effectiveness of our proposed methods.


---

## Body

## 1. Introduction

With the rapid development of the hand-held mobile devices, mobile crowdsensing [1] has becomes a new tool for problem-solving, and there has been lots of applications in real life, such as healthcare [2], smart city [3], and localization [4]. Due to the fact that workers’ participation will depreciate their devices, such as consumption of CPU and battery, they may take a toll on their participation. Incentive mechanisms are significant to the crowdsensing applications, since a good incentive mechanism will attract more workers to participate. Estimating workers’ personal cost is a hurdle. Workers’ private cost is subjective, which is associated with various factors. These factors are hard to observe, such as difficulties of tasks and abilities of workers. A reasonable method is to offer an estimated optimal bonus to compensate costs of workers.With the limited budget, workers may be reluctant to participate, if the offered price is too low. Offering a high price to workers may result in lower outcome. We will use a powerful tool from the algorithmic game to ensure both the efficiency and workers’ incentivization.The mechanism design is a tricky issue for the crowdsourcer with budget constraint, since designing a budget constraint allocating scheme needs understanding its payoff to workers, which is also related to the allocating scheme itself. Most existing works aim at maximizing the efficiency of crowdsensing by hiring workers in a single region. Nevertheless, with some geographical limitations, the crowdsourcer is necessary to procure service from workers in multiple regions to perform tasks and consider the interactions of different regions. Consider a crowdsourcer with a hard budget who wants to estimate the residential information in Eastern Asia which consisted of five countries, China, Japan, South Korea, North Korea, and Mongolia. Due to the geographical limitation, the crowdsourcer has to hire workers in each country to perform tasks separately. Furthermore, the populations or the area of the territories of five countries are different. Thus, the crowdsourcer has to design mechanisms to allocate proper budgets to each region and considers the incentives for workers from different regions.In this paper, we introduce and study a new scenario, where the crowdsourcer or buyer wants to buy service in a macroregion which is composed of several nonoverlapped microregions. The crowdsourcer will get a utility for each microregion, respectively, and aggregate results in each microregion to get a final result. We introduce and study two optimization goals when combining results of each microregion, namely, weighted mean and maximin. Under the first model, we define the crowdsourcer’s utility as the weighted mean of utility obtained in each microregion. Under the second model, the crowdsourcer’s utility is defined as the minimum utility obtained in all microregions. Compared with single region settings, our multiple region setting leads to more useful solutions in practice. By this work, we proposed an incentive mechanism for the weighted mean model firstly, which consists of a task allocation algorithm and a worker compensation algorithm. Then, we extend the proposed mechanism to the maximin model.The main of our paper can be summarized as follows:(i)
A major contribution of this work is introducing a new problem, multiregion crowdsensing. Two objectives are introduced to measure the utility of multiregion crowdsensing. Although we study our problem in the context of crowdsensing, the framework and solution proposed in this paper can be applied to a broad range of domains, such as procurement and resource allocation(ii)
For a multiunit budget-feasible mechanism, we propose a novel method via a proportional share allocation rule instead of the random sampling method applied in [5]. Also, our proposed mechanism can handle the multiregion procurement settings


## 2. Related Work

In recent years, the mobile crowdsensing system has a wide range of application in our daily life [1–3, 6–10]. At the same time, game theoretic models become an effective tool for incentive mechanism in mobile crowdsensing systems because of the strategic behavior of workers [11, 12]. Jin et al. considered integrating information quality into the design of the incentive mechanism for mobile systems [13]. Zhang et al. designed an incentive mechanism by which crowd workers were encouraged to label a set of binary tasks within strict budget constraints [14]. Another Zhang et al. studied three models of cooperation and competition among service providers [15]. Gao et al. devoted to providing a sufficient long-term participation incentive for crowd workers [16]. Feng et al. studied the key dimension of location information in smartphones which are assigned sensing tasks [17]. Qiao et al. studied the task crowdsensing under the background of the cross market [18]. Zhao et al. designed online incentive mechanisms for crowdsensing systems [19]. Liu et al. studied a two-phase group buying based on the auction mechanism for mobile crowdsensing [20]. Xu et al. improved online crowdsourcing auctions via a two-tiered framework [21]. Xu et al. [22] also proposed a mechanism with a strategy-proof discovery phase and a budget-constrained purchasing stage.Budget-feasible incentive mechanism design, which was initially studied by Singer [23] when he found a novel class of mechanism design problems where the outcomes are limited by payments, becomes a newly emerging branch of mechanism design. Chen et al. designed a stochastic budget-feasible mechanism with a polynomial time approximate ratio and a deterministic budget-feasible mechanism with an exponential time approximate ratio [24]. Bei et al. studied the budget-feasible mechanism through random sampling and designed a constant approximation mechanism for all subadditive functions in Bayesian environment [25]. Anari et al. investigated a model to solve the mechanism design problem in the context of large-scale crowdsensing markets such as Amazon’s Mechanical Turk [26]. Then, Singer applied this model to influence maximization in social networks [27] while Horel et al. applied this model to an experiment design problem [28]. Chan and Chen came up with multiunit budget-feasible mechanism design which has been a new setting in budget-feasible incentive mechanism design [5].In our setting, a crowdsourcer or buyer wants to procure service in a macroregion, which is composed ofr=1,⋯,r nonoverlapping microregions. A set of sellers or workers N=1,⋯,n is scattered in each microregion.Letr· be a function to specify the region. Let ci index the private cost of the worker i. Each worker i could provide mi units of homogeneous service, which is common knowledge. We use si to denote the set of service which could be provided by worker i. Let M=∪i∈Nsi denote the total service that can be provided by all workers in the macroregion, thus the number of total service in the macroregion M=∑i∈Nmi.This paper studies the service procurement with strategic players, and each worker will report his cost strategically in order to maximize his benefit. Letb=b1,b2,⋯,bn index bids of all workers. In our mechanism, there are two functions, a payment function and an allocation function. The payment scheme will decide the payoff pi to the worker i, and the quota of service xi procured from worker i is the outcome of the allocating scheme. The output of the designed mechanism is two vectors, payment vector p→=p1,p2,⋯,pn and allocating vector x→=x1,x2,⋯,xn. The benefit uib→ of service provider i is quasilinear. Formally, we have
(1)uib→=pib→−ci⋅xib→,ifxib→≤mi,−∞,otherwise.


### 2.1. Problem Formulation

#### 2.1.1. Single-Region Utility Measurement

Since the utility in each microregion is calculated, respectively, we need to know the quota of procured service in each microregion. We usekj=∑i∈N,ri=jxi to present the quota of procured services in microregion j. Then, the utility obtained in microregion j is measured by a symmetrical submodular function Akj=∑i=1kjυi, where vi is the marginal incremental value by procuring the i-th unit service from the workers when the crowdsourcer has brought i−1 service. The symmetrical submodularity means vi will decrease as i grows, and v1≥v2≥⋯≥vn≥0.


#### 2.1.2. Multiregion Utility Measurement

The crowdsourcer will get a final result by combining the outcomes in each microregion. Two optimization objectives are introduced, namely,maximin and weighted mean. In the weighted mean scheme, each microregion i is related with a region weight wi0≤wi≤1,∑i∈rwi=1, which measures the relative significance of every microregion. The global utility is calculated by the weighted mean of utility obtained in each microregion. Formally, the weighted mean maximization model can be summarized as follows.Problem: weighted mean maximization.Objective: maximizeAwm=∑j=1rwjAkj,Subject to:(2)∑j=1rwj=1,0≤wj≤1,(3)∑i∈Npi⋅xi≤B.In the maximin model, the global benefit of the crowdsourcer is calculated by the minimum of the accuracy rate achieved in all microregions.Problem: minimum maximization.Objective: maximizeAmm=minj∈1,⋯,rAkj,Subject to:(4)∑i∈Npi⋅xi≤B.We useOPTwmB,M and OPTmmB,M to index the optimal results for weighted mean and maximin, respectively.Due to the fact that the workeri’s cost ci is private information, the problem in our paper belongs to the single parameter mechanism design problem. According to the well-known Myerson’s lemma [29], any truthful auctions must have a monotone allocating scheme and a payment scheme with a threshold payment. For the more complex multiunit setting in our paper, we have the following lemma.Lemma 1.
A single-parameter multiunit domain, a normalized auctionH=x,p is truthful, if and only if,
(1)
Monotone allocation: xici,c−i>0,∀i∈N, implied xici′,c−i>0, if ci′<ci(2)
Threshold payment to the selected workers: pici=∑j=1xiciqj, where qj=infci:xibi<jProof.
The first condition is trivial and could be obtained via Myerson’s lemma [29]. For the second condition, we use w to index xibi. Then, we obtain
(5)pibi=wbi+∫biqwwdz+∫qwqw−1w−1dz+⋯+∫q2q11dz=qw+qw−1+⋯+q1.
Thus, the lemma holds.We expect our designed auctions are(i)
Truthful: for any worker i, his benefit is maximized by reporting his true cost, regardless of the bidding of others:∀bi,b→−i:uibi,b→−i≥uibi′,b→−i(ii)
Individually rational: workers are not worse off by participating in the campaign. Formally, it requires ∀b→−i:uibi,b→−i≥0(iii)
Budget-feasible: the total payment to workers does not exceed the buyer’s budget(iv)
Computationally efficient and performance guaranteed: the results of function x and p could be found out in polynomial time, and constant approximations are expected for our proposed mechanisms


## 2.1. Problem Formulation

### 2.1.1. Single-Region Utility Measurement

Since the utility in each microregion is calculated, respectively, we need to know the quota of procured service in each microregion. We usekj=∑i∈N,ri=jxi to present the quota of procured services in microregion j. Then, the utility obtained in microregion j is measured by a symmetrical submodular function Akj=∑i=1kjυi, where vi is the marginal incremental value by procuring the i-th unit service from the workers when the crowdsourcer has brought i−1 service. The symmetrical submodularity means vi will decrease as i grows, and v1≥v2≥⋯≥vn≥0.


### 2.1.2. Multiregion Utility Measurement

The crowdsourcer will get a final result by combining the outcomes in each microregion. Two optimization objectives are introduced, namely,maximin and weighted mean. In the weighted mean scheme, each microregion i is related with a region weight wi0≤wi≤1,∑i∈rwi=1, which measures the relative significance of every microregion. The global utility is calculated by the weighted mean of utility obtained in each microregion. Formally, the weighted mean maximization model can be summarized as follows.Problem: weighted mean maximization.Objective: maximizeAwm=∑j=1rwjAkj,Subject to:(2)∑j=1rwj=1,0≤wj≤1,(3)∑i∈Npi⋅xi≤B.In the maximin model, the global benefit of the crowdsourcer is calculated by the minimum of the accuracy rate achieved in all microregions.Problem: minimum maximization.Objective: maximizeAmm=minj∈1,⋯,rAkj,Subject to:(4)∑i∈Npi⋅xi≤B.We useOPTwmB,M and OPTmmB,M to index the optimal results for weighted mean and maximin, respectively.Due to the fact that the workeri’s cost ci is private information, the problem in our paper belongs to the single parameter mechanism design problem. According to the well-known Myerson’s lemma [29], any truthful auctions must have a monotone allocating scheme and a payment scheme with a threshold payment. For the more complex multiunit setting in our paper, we have the following lemma.Lemma 1.
A single-parameter multiunit domain, a normalized auctionH=x,p is truthful, if and only if,
(1)
Monotone allocation: xici,c−i>0,∀i∈N, implied xici′,c−i>0, if ci′<ci(2)
Threshold payment to the selected workers: pici=∑j=1xiciqj, where qj=infci:xibi<jProof.
The first condition is trivial and could be obtained via Myerson’s lemma [29]. For the second condition, we use w to index xibi. Then, we obtain
(5)pibi=wbi+∫biqwwdz+∫qwqw−1w−1dz+⋯+∫q2q11dz=qw+qw−1+⋯+q1.
Thus, the lemma holds.We expect our designed auctions are(i)
Truthful: for any worker i, his benefit is maximized by reporting his true cost, regardless of the bidding of others:∀bi,b→−i:uibi,b→−i≥uibi′,b→−i(ii)
Individually rational: workers are not worse off by participating in the campaign. Formally, it requires ∀b→−i:uibi,b→−i≥0(iii)
Budget-feasible: the total payment to workers does not exceed the buyer’s budget(iv)
Computationally efficient and performance guaranteed: the results of function x and p could be found out in polynomial time, and constant approximations are expected for our proposed mechanisms


## 2.1.1. Single-Region Utility Measurement

Since the utility in each microregion is calculated, respectively, we need to know the quota of procured service in each microregion. We usekj=∑i∈N,ri=jxi to present the quota of procured services in microregion j. Then, the utility obtained in microregion j is measured by a symmetrical submodular function Akj=∑i=1kjυi, where vi is the marginal incremental value by procuring the i-th unit service from the workers when the crowdsourcer has brought i−1 service. The symmetrical submodularity means vi will decrease as i grows, and v1≥v2≥⋯≥vn≥0.


## 2.1.2. Multiregion Utility Measurement

The crowdsourcer will get a final result by combining the outcomes in each microregion. Two optimization objectives are introduced, namely,maximin and weighted mean. In the weighted mean scheme, each microregion i is related with a region weight wi0≤wi≤1,∑i∈rwi=1, which measures the relative significance of every microregion. The global utility is calculated by the weighted mean of utility obtained in each microregion. Formally, the weighted mean maximization model can be summarized as follows.Problem: weighted mean maximization.Objective: maximizeAwm=∑j=1rwjAkj,Subject to:(2)∑j=1rwj=1,0≤wj≤1,(3)∑i∈Npi⋅xi≤B.In the maximin model, the global benefit of the crowdsourcer is calculated by the minimum of the accuracy rate achieved in all microregions.Problem: minimum maximization.Objective: maximizeAmm=minj∈1,⋯,rAkj,Subject to:(4)∑i∈Npi⋅xi≤B.We useOPTwmB,M and OPTmmB,M to index the optimal results for weighted mean and maximin, respectively.Due to the fact that the workeri’s cost ci is private information, the problem in our paper belongs to the single parameter mechanism design problem. According to the well-known Myerson’s lemma [29], any truthful auctions must have a monotone allocating scheme and a payment scheme with a threshold payment. For the more complex multiunit setting in our paper, we have the following lemma.Lemma 1.
A single-parameter multiunit domain, a normalized auctionH=x,p is truthful, if and only if,
(1)
Monotone allocation: xici,c−i>0,∀i∈N, implied xici′,c−i>0, if ci′<ci(2)
Threshold payment to the selected workers: pici=∑j=1xiciqj, where qj=infci:xibi<jProof.
The first condition is trivial and could be obtained via Myerson’s lemma [29]. For the second condition, we use w to index xibi. Then, we obtain
(5)pibi=wbi+∫biqwwdz+∫qwqw−1w−1dz+⋯+∫q2q11dz=qw+qw−1+⋯+q1.
Thus, the lemma holds.We expect our designed auctions are(i)
Truthful: for any worker i, his benefit is maximized by reporting his true cost, regardless of the bidding of others:∀bi,b→−i:uibi,b→−i≥uibi′,b→−i(ii)
Individually rational: workers are not worse off by participating in the campaign. Formally, it requires ∀b→−i:uibi,b→−i≥0(iii)
Budget-feasible: the total payment to workers does not exceed the buyer’s budget(iv)
Computationally efficient and performance guaranteed: the results of function x and p could be found out in polynomial time, and constant approximations are expected for our proposed mechanisms


## 3. Weighted Mean Maximization

Based on Myerson’s well-known lemma [29], strategy-proof auctions must have a monotone allocating scheme and a payment scheme with a threshold payment. For the mechanism design under budget constraint, selecting items for the candidate set according to the benefit-to-cost ratio is a natural fit. The basic idea of our proposed mechanism is to select workers greedily based the marginal of each worker and terminate with an appropriate threshold payment.First, we would like to introduce a greedy but nonmonotone selecting rule. Then, we modify this rule to make it monotone. Given a set of procured serviceM, we define the marginal value of a unit service si∈M\M for the weighted mean model as
(6)Ui∣M=AwmM∪si−AwmM.Our greedy algorithm selects a group of services one by one. In each stagei, it adds a service si∗ that maximizes the benefit-to-cost ratio Ui∣Mi−1/ci, in which we use Mi−1 to denote first i−1 services selected by our algorithm; without loss of generality, we assume M0=∅. Since the utility is computed separately, the contribution of service si to the global utility equals the incremental value of si in its own microregion. We use ui∣Mi−1 to denote the utility increment in region rsi with service si and the given set Mi−1. Formally, we have
(7)si∗=argmaxsi∈M\Mi−1Ui∣Mi−1ci=argmaxsi∈M\Mi−1Ui∣Mi−1⋅wrici.If there are multiple candidate workers, we sort them lexicographically. For eachsi∗, selected in stage i, we use ui∗, wi∗, and ci∗ as abbreviations for ui∣Mi−1, wr(i∗), and ci∗, respectively. Through the greedy selecting principle, we have a sorted list L:
(8)L:u1∗w1∗c1∗≥u2∗w2∗c2∗≥⋯≥uM∗wM∗cM∗.We choose workers as candidates iteratively until the budget constraint is exceeded. Formally, we have(9)ci∗≤B1+1nM⋅wi∗ui∗AwmMi.This allocation rule is a variation of the proportional share rule which is the basis for mechanisms under a budget. Observing that ifk services are selected according to this rule and each selected worker is paid according to their proportional contribution, the one nice feature about this allocation rule is that for any submodular function, it can be proven that the incentive compatible payments do not exceed the workers’ proportional contributions. We will further discuss payments after describing the entire mechanism below. Importantly, this allocation rule achieves a bounded approximation ratio.
(10)∑i=1kB⋅AwmMi−AwmMi−1AwmMk≤BAwmMk∑i=1kAwmMi−AwmMi−1=BAwmMk⋅AwmMk=B.Lemma 2.
Given a sorted listL and a service si∈L, we use Lsi to denote the position of si in L. For any two services from the same region,
(i)
ifci<cj, then Lsi≺Lsj(ii)
ifci=cj, then Lsi≺Lsj, iff i<jProof.
(1)
Withci<cj, we assume Lsj≺Lsi. Thus, we have(11)uj∣Μj−1⋅wrjcj≥ui∣Μi−1⋅wrici.
Sincerj=ri, we have u{jMj−1}=u{iMi−1}, then ci≥cj. Thus, we have a contradiction!
(2)
Withci=cj, service si and sj are sorted according to the lexicographical orderNo two services from the same region intersect with each other inL if they are provided by two different workers. For each region, each agent’s units are placed in L as nonoverlapping clusters and ordered according to increasing bid. An illustration of the services’ position is in Figure 1.Lemma 3.
The greedy selection principle is monotone.Proof.
For each servicesl chosen as the candidate, the rest of the service in M can be classified into 4 classes:
(i)
T+: all services ranked higher than sl in region rl(ii)
T−: all services ranked lower than sl in region rl(iii)
F+: all services not in region rl whose rank is higher than sl(iv)
F−: all services not in region rl whose rank is lower than slFigure 1
For each microregion, each worker’s units are placed inL as nonoverlapping clusters and ordered according to increasing bid. Total payments do not exceed the budget.Assume that workerl declares a cost c′≤cl and achieves a utility u′. Let T^+,T^−,F^+, and T^ denote the four updated classes. We can easily obtain that no service sd can be moved forward to the front of sl. If l=d, they are owned by the same worker, and we still have Lsl≺Lsd. If l=d, we have cd≥cl>c′, and we obtain Lsl≺LSd. Thus, we obtain T^+⊂T+ and u′≤u∗. Services in F+∪F− are unchanged. No service sd in F− could be moved before sl; this is because the cost-to-benefit ratio of sd is unchanged, and
(12)wd∗ud∗cd∗≤wl∗ul∗cl∗≤wl∗u′c′.Therefore, we obtainF^+⊂F+. Furthermore,
(13)c′wl∗ul∗<cs∗wl∗ul∗≤B1+1nM∑i<lwi∗ui∗=B1+1nM∑si∈T+∪F+∪slui∗wi∗=B1+lnMwl∗AwmF++1+∑si∈F+ui∗wi∗≤B1+1nMwl∗AwmF^++1+∑si∈F^+ui∗wi∗.Thus, each service will be allocated with a lower cost declaration, and the monotonicity achieved.Through the greedy selecting principle, we get a candidate set, denoted byMk. Unfortunately, Mk could not provide any lower bound guarantee, if we regard Mk as the winners. We consider another feasible candidate solution. s∗ which is the single service with the highest marginal utility, i.e., s∗=argmaxsi∈Mwiui/ci⋅s∗, is a possible solution. In order to get a bounded approximation ratio, we will compare these two sets, Mk and s∗, and select the one with higher utility. We have the following theorem.Theorem 4.
LetOPTwmB,M denote the optimal solution for the weighted mean model, i.e., OPTwmB,M≤3+21nM×maxAwms∗,AwmMk.Sort workers likeL. We use l to present the largest index such that ∑i=1lci<B. For analysis convenience, we add a new virtual worker v with a single service sv, who reports his cost cv=B−∑i=1lci and his utility is u′=Awmsv=B−∑i=1lci/cl+1AwmMl+1−AwmMl. Obviously, the optimal result over all workers in M+=M∪sv is higher than the optimal result from all workers in M. Through greedy selection principle, the first l workers will be chosen in both M+ and M. In the rest of the proof, we will index service sv as sl+1.Due to the optimality, we have(14)AwmMl+1=∑i=1lwi∗ui∗+wl+1∗u′≥OPTwmB,M.Next,AwmMl+1 will be regarded as the benchmark for analysis. Since all workers are sorted in decreasing order of their benefit-to-cost ratio, for each i∈k+1,⋯,l+1, we get
(15)wi∗ui∗ci∗≤wk+1∗uk+1∗ck+1∗.Combining the above inequalities, which imply(16)ck+1∗wk+1∗uk+1∗∑i=k+1l+1wi∗ui∗=ck+1∗wk+1∗uk+1∗AwmMl+1−AwmMk≤∑i=k+1l+1ci∗≤B.Then, we obtain(17)ck+1∗≤B⋅wk+1∗uk+1∗AwmMl+1−AwmMk.Based on the concept of notationk, we obtain
(18)ck+1∗>B1+1nM⋅wk+1∗uk+1∗AwmMk+1.From inequalities (17) and (18), we know
(19)AwmMl+1−AwmMk<1+1nMAwmMk+1.Thus, we have(20)AwmMl+1=AwmMl+1−AwmMk+AwmMk<1+1nMAwmMk+1+AwmMk≤1+1nMAwms∗+2+1nMAwmMk.Finally, we get(21)OPTwmB,M≤OPTwmB,M+≤AwmMl+1≤3+21nMmaxAwms∗,AwmMk.However, one can show that simply selecting maxmaxAwms∗,AwmMk would violate incentive compatibility. To address this issue, we further design Algorithm 1 to ensure the monotonicity, in which the total cost is bounded by B/1+1nM. Therefore, we remove the services with costs larger than B/1+1nM, indexed by MB/1+1nM. Different from the previous greedy algorithm, we compare Awms∗ with the optimal solution for the set M− with budget B/1+1nM, whereM_=M\s∗∪MB/1+1nM. Algorithm 1 will compare OPTB/1+1nM,M_ with 3Awms∗ to determine the final outcome.Algorithm 1: Task allocation algorithm (TAB,M).
1: Input: a set of workersN from r microregions with total M service available, a budget B and a biding profile b;2: Output: a set of winning workerM∗3:Mk←0;4:s∗←argmaxsi∈Mwiui/ci;5:whileM\Mkandci∗≤B/1+1nM×wi∗ui∗/Awmsi∗∪Mkdo6:Mk←Mk∪si∗;7:si∗←argmaxM\Mki∗wi∗ui∗/ci∗8:end while9:M−←M\s∗∪MB/1+1nM;10:OPTB/1+1nM,M_← optimal solution for the set M_ with budget B/1+1nM;11:ifOPTB/1+1nM,M_≥3Awmsi∗then12:M∗←Mk13:else14:M∗←s∗15:end ifLemma 5.
Algorithm1 is monotone.Proof.
We prove this lemma through contradiction. With a cost vectorc→, we assume there exists a winner i∈M with a single service such that he is not allocated when declaring ci′≤ci. The lemma will be analyzed from two conditions:
(1)
IfM∗=s∗, then we have OPTB/1+1nM,M_≤3Awms∗. Due to the fact that the cost of the owner of s∗ will not change OPTB/1+1nM,M_andAwms∗, s∗ will still be allocated if s∗’s owners reported cost changes(2)
IfM∗=Mk, then it implies that OPTB/1+lnM,M_>3Awmsi∗. OPTB/1+lnM,M_ increases as i’s reported cost decreases. Furthermore, i ranks higher in L, since ci′<ci. Assume the update index in new L, j≤i. According to the symmetrical submodularity of Awm⋅, the incremental value of service at i is lower than that at j, i.e., wj∗uj∗≥wi∗ui∗. We obtain AwmMi−1∪i≥AwmMj−1∪j. Then, we have(22)ci′<ci≤B1+lnM×wi∗ui∗AwmMi−1∪i≤B1+lnM×wj∗uj∗AwmMi−1∪i.Thus, it does not violate the budget constraint, and the workeri will still be in the solution set. The above conclusion implies that the worker i will still be selected as a winner when he decreases his bid. Thus, the allocating scheme is monotone.Now, we move to our payment scheme which is presented in Algorithm2. The basic idea of the payment scheme can be summarized as follows. If M∗=s∗, we pay s∗’s owner B. If M∗=Mk, we sort workers in region ri in nondecreasing order of their bids. Let y denote the position of worker i. Then, remove all service from worker i and sort the remaining units to the sequence L′ according to the benefit-to-cost ratio. Then, for each worker j in the region ri, we index the first and the last of its service in L′ as fj and lj. According to Lemma 2, we obtain
(23)L′=f1<l1<f2<l2<⋯<fy−1<ly−1<fy+1<ly+1<⋯<fh<lh,where ∣h∣ denotes the number of workers in region h. Thus, the threshold could be found between these intervals
(24)fy−1,⋯,ly+1,fy+1,⋯,ly+2,fy+2,⋯,ly+3,⋯,and the search for the largest value worker i could be reported, which could make si be positioned next to one of the unit intervals and be selected. Based on worker i’s current reported cost information, we will insert unit si to the interval fy−1,⋯,ly+1 and be selected. Worker i must report the cost lower in order to move si to some earlier intervals. So the search could begin at the interval fy−1,⋯,ly+1.We can show that the payment for the selected workers can be bounded.Lemma 6.
Ifsi is selected, ci≤B/1+lnMLsi.Proof.
We assume that the mechanism will select firstk services, i.e., s1,⋯,sk, in L. We then resort these k services in nonincreasing order of their benefit-to-cost ratio, as s1+,⋯,sk+. Let sj+’s incremental contribution as uj+. We use csj+ and wrsj+, as cj+ and wj+ for short.
We assume that∃1≤e≤k satisfying ce+>B/1+lnMe, then
(25)ck∗uk∗wk∗≤B1+lnM∑j≤kwj∗uj∗=B1+lnM∑j≤kwj+uj+≤B1+lnM∑i≤ewj+uj+≤B1+lnMe⋅we+ue+.Algorithm 2: Payment algorithm (PB,M).
1: Input: a set of workersN from r microregions with total M service available, a budget B and a biding profile b, and a set of winning worker M∗;2: Output: a payment profile of workersp→;3:p→←0;4:ifM∗=s∗then5:p∗←B6:  returnp→;7:else8:whilei∈M∗do9:   1. Order the workers in regionh as n1,n2,⋯,n∣h∣ according to increasing cost bid, let y satisfy ny=i;10:   2. Order all services except from workeri, according to decreasing benefit-to-cost ratio, as L′=s1,⋯,s∣M\Φi∣;11:   3. For eachj∈∣h∣\y, get the first unit fj and last unit lj;12:   4. Get the last positionk′s.t.ck′′/wk′′uk′′≤B/1+lnM∑y≤k′wy′uy′;13:l0=0; k=ly−1+1; z=1; S=∅;14:whilek≤k′+1do15:ifk=fy+z+1then16:k=ll+z; z++;17:else18:Γ=∑j=1y−1sj+∑j=2zsy+j−1+j;19:δ=AwmΓ−AwmΓ−120:t=minδck′′/uk′′,Bδ/1+lnM1/∑i≤k−1uk′+lΓ−j+1+⋯+lΓ21:S=S∪t; k++;22:end if23:end while24:   5.pi ← the max value in S25:end while26:  returnp→;27:end ifFurthermore, we haveB<1+lnMe⋅ce+ and so
(26)B1+lnMe⋅we+ue+<ce+we+ue+.Combining these two inequalities, we have(27)ck∗wk∗uk∗<ce+we+ue+.It is a contradiction, becauseLsk≺Lse in L, and therefore, sk cannot be selected.With the previous lemma, we still do not know whether workeri could report c′>B/1+lnMLsi and get a new position index L′si, and make si win.Lemma 7.
The threshold reported costϵi for a single service si is bounded by B/1+lnMLsi.Proof.
Suppose∃se+, e≤k, and ϵe>B/1+lnMe. So, worker ie+ could report a higher cost c′ to satisfy B/1+lnMe<c′<ϵe and make se+ be selected. Now, assume worker ie+ bid c′ and let u′ be the incremental value of unit se+ in such a case. Obviously, we have u′≤ue+, and
(28)c′we+u′≥c′we+ue+>B1+lnMe⋅we+ue+≥ck∗wk∗uk∗.For anysj+ where j<e (the unit used to rank ahead unit se+ in the greedily sorted list), Let uj′ index its new incremental contribution as uj′ and new reported cost as cj′. There could be 3 cases for the relations of the items of sj+ and se+, which are as follows:Case 1 (belong to the same worker).
By the lexicographical rule,Lsj+≺Lse+ still holds in L, and thus, uj′>u′.Case 2 (belong to different workers in the same region).
Sinceuj+≥ue+, cj+≤ce+, and therefore,
(29)cj′=cj+≤ce+≤c′.Case 3 (belong to different regions).
It is trivial to haveuj′=uj+ and cj′=cj+, and thus,
(30)cj′uj′wj+=cj+uj+wj+≤ck∗uk∗wk∗<c′u′we+.Moreover, we haveuj′=uj+≥ue+≥u′.It is obvious to know in all 3 cases, servicesj+ will be selected and be ranked before se+ in L. We denote e′ as the unit se+’s new position index. We have e′≥e, and thus,
(31)c′>B1+lnMe≥B1+lnMe′.According to Lemma6, se+ could not be selected, and we have a contradiction. Based on the previous lemma, we can get the upper bound for total threshold payment of all the selected units directly.Lemma 8.
The payment to all workers in worker compensation algorithm is upper bounded byB.Proof.
By Lemma7, the threshold payment is
(32)∑e=1kϵi≤∑e=1kB1+lnMe≤∑e=1M1eB1+lnM≤1+lnM11+lnMB.That is, it is upper bounded byB.Now, we have the following theorem.Theorem 9.
The weighted mean mechanism is truthful, budget feasible, individual rational and tractable.Proof.
Truthful: based on Lemma 1, 5, and 6, we conclude that reporting truthful cost is a dominant strategy for each worker.
Individual rational: the worker whose cost is larger than B will be removed directly. Therefore, if M∗=s∗, the individual rational is obvious. For the case of M∗=Mk, the payment to each worker is the sum of the threshold bid of his procured services, which is larger than his bid unit cost. Budget feasible: from Lemma 8, we can assure the property of being budget feasible. Computationally efficient: it is obvious that the task allocation algorithm and payment algorithm can be computed in a polynomial time.Theorem 10.
Weighted mean multiunit multiregion budget-feasible mechanism achieves a constant ratio approximation:4+3ln∣M∣.Proof.
Drawing from the proof of Theorem4, we obtain OPTB/1+lnM,M_≤3×maxAwms∗,AwmMk. There are two cases. If OPTB/1+lnM,M_≥3×Awms∗, from above inequality, we have AwmMk≥Awms∗. Based on Theorem 4, we have OPTwmB,M≤3+2ln∣M∣×AwmMk. Then, we have the expected approximation ratio. Otherwise, if OPTB/1+lnM,M_<3×maxAwms∗; in this case, we get
(33)OPTwmB,M=OPTwmB,M−+Awms∗≤1+lnM×OPTwmB1+lnM,M−+Awms∗≤31+lnMAwms∗+Awms∗=4+3lnM×Awms∗.


## 4. Minimum Maximization

In the weighted mean model, the buyer will perform a single auction to allocate tasks and compensate workers from all micro-regions. However, in the maximin, the buyer will allocate budgetB/r to each microregion and perform mechanism in each microregion in parallel. Let Mj=∪i∈N,ri=jΦi index services could be provided in microregion j. The maximin mechanism is referred to Algorithm 3.Algorithm 3: Maximin mechanism.
1:for each microregion jdo2:  Run task allocationTAB/r,Mj under budget B/s and Mj;3:  Run worker compensationPB/r,Mj under budget B/s.4:end for5: Aggregate the outcome from each microregion.Theorem 11.
Maximin mechanism is truthful, budget feasible, individual rational, and computationally efficient.Since mechanisms performed in each microregion are truthful, budget feasible, individual rational, computationally efficient, and independent from each other, multiregion maximin mechanism is also truthful, budget feasible, individual rational, and computationally efficient.Corollary 12.
With payment algorithmPB/r,Mj and task allocation algorithm TAB/r,Mj, the mechanism will achieve a constant approximation ratio 4+3lnMj, in a single microregion j.Proof.
Trivial: the setting in a microregion j can be regarded as a special case of weighted multiregion setting with r=1 and wj=1, j∈r.UseOPTjB,Mj to index the optimal result for the Mj with budget B in a single microregion j. Let us make these following observations on the optimal solutions in microregion j.Lemma 13.
OPTjB,Mj is nondecreasing with B.Lemma 14.
OPTjB,Mj/B is nonincreasing with B between 0,+∞.Lemma 15.
For anyB,Mj,ϵ∈0,1,OPTjϵB,Mj≥ϵOPTjB,Mj.Proof.
For the setMj, if B increases, more service will be procured. However, the incremental value is nonincreasing under B. So the payment for unit service will be higher, as B increases. It implies that OPTjB,Mj/B is nonincreasing with B, and we get
(34)OPTjB,MjB≤OPTjϵB,MjϵB⇒ϵOPTjB,Mj≤OPTjϵB,Mj.
LetBmax be the largest amount of the budget that the buyer used in a microregion in OPTmmB,M. Let β index the B/Bmax. The 1/β denotes the largest fraction of total budget allocated for a microregion in OPTmmB,M, intuitively. We use kj∗ to denote the total service procured in microregion j in the optimal result OPTmmB,M.Theorem 16.
In the maximin model, the mechanism achieves a constant approximation ratio:r4+3lnM/βProof.
Based on the definition of the maximin problem, we get(35)AmmB,M=minAk1,⋯,Akr,(36)OPTmmB,M=minAk1∗,⋯,Akr∗.Since the single-region performance is guaranteed in Corollary12, we obtain
(37)Akj≥14+3lnMjOPTjBr,Mj≥14+3lnMOPTjBr,Mj.Since we have known(38)Bj≤Bβ,and the conclusions of Lemma 13, 14, and 15, we obtain
(39)OPTjBr,Mj≥βOPTjB/β,Mjr≥βOPTjBj,Mjr.Thus, we have(40)EAkj≥14+3lnMβOPTjBj,Mjr.Then, we have(41)AmmB,M≥minj14+3lnMβOPTjBJ,Mjr≥β4+3lnMrminjOPTjBj,Mj≥β4+3lnMrOPTmmB,M.


## 5. Simulations

### 5.1. Simulation Setup

It is hard to get the bidding data of workers directly; thus, it is necessary for us to infer the cost profile via historical cost information. Drawing from [30], we will estimate workers’ cost information on a website, called weiboyi (http://www.weiboyi.com), which is for social advertising. In the website, advertisers are required to post their desired compensation to advertise to fans in the Weibo. From Figure 2, we show the cost information of 15012 advertisers. The range of their reported cost is from 0 to 5∗104, and the range of the number of their friends is from 0 to 2∗106. We use advertisers’ number of friends to simulate workers’ capacity. The cost information of advertisers will be normalized to (0,5) and the number of friends to [0,2]. The data set generation process is to select an instance in weiboyi data set and use the ca/mf for the worker’s cost and the normalized number of friends for workers’ capacity iteratively, in which ca denotes the advertiser’s normalized cost and mf indexes the advertiser’s normalized number of friends. We set crowdsourcer’s utility Ak (in a single region) with three symmetrical submodular functions, where Ak=k0.9, Ak=k, and Ak=∑i=1k100/100+k. We consider the a service subscriber wants to hire workers from 6 microregions. To obtain statistically 330 sound results, we run the simulation 1000 rounds for each parameter setting, and the microregion weight will be randomized in each round of experiments.Figure 2
Cost information with numbers of friends.


### 5.2. Benchmarks

We compare our designed auctions (MUMRwm and MUMRmm for two models) with 3 baselines. The first benchmark is the greedy algorithm, which will return the optimal solution. The greedy algorithm is not truthful and has full information of workers’ costs. The second benchmark is a uniform-price mechanism which is near-optimal, which is introduced in [31]. The last one is a random selecting algorithm. The mechanism chooses workers randomly and payoffs to workers are their declared cost, which are the lower bound performance of our designed problem. For maximin, the above three algorithms will be performed in each microregion in parallel with the same budget. We evaluate two performances of our proposed mechanism, crowdsourcer’s valuation and winner ratio. The first one means the utility achieved in the entire region. The second one represents the percentage of selected workers over all workers.


### 5.3. Results

We will present the results of the winner ratio, firstly. Since the simulation results of the three crowdsourcer’s valuations are similar, we just present the results ofAk=k0.9 here. We set the budget at 1000 and the number of workers from 100 to 1000. The results are shown in Figures 3(a) and 4(a) for both two models. We observe that the winner ratio decreases as the number of workers increases. The reason is that the auctions are more competitive with more workers. For the uniform pricing mechanism, the ratio will be stable, since the uniform pricing mechanism will choose a set of workers as the candidates when the scale of workers is relatively small.According Figures 3(b) and 4(b), we can know that the valuation of the buyer when the budget is 500 and the scale of workers is from 100 to 1000. The buyer’s utility grows with the increase of workers in all algorithms in both models. With a larger scale of workers, the buyer will utilize the budget more effectively. Our proposed mechanism outperforms random and uniform pricing mechanisms in the weighted mean model. MUMR’s performance approaches the performance of the greedy algorithm and uniform pricing mechanism in the maximin model. Figures 3(c) and 4(c) show the service subscriber’s valuation when the number of workers is 500 with the budget from 200 to 2000. From the figure, we know that the utility of the buyer increases simultaneously in algorithms MUMRwm and MUMRmm and greedy algorithm as the budget increases. The reason is that when the budget becomes larger, more workers can be hired. The greedy-based method performs well in the simulation; however, it is not strategy-proof. The performance of the uniform price mechanism approaches the one of MUMRwm and MUMRmm with the small budget. For the uniform price mechanism, the buyer’s valuation decreases as the budget increases. Since the mechanism will infer a threshold payoff based on the workers’ cost information, the one selected by the mechanism with larger budget may not be the optimal one.Figure 3
Results on weighted mean model.
(a)
Winner ratio(b)
Utility(c)
UtilityFigure 4
Results on maximin model.
(a)
Winner ratio(b)
Utility(c)
Utility


## 5.1. Simulation Setup

It is hard to get the bidding data of workers directly; thus, it is necessary for us to infer the cost profile via historical cost information. Drawing from [30], we will estimate workers’ cost information on a website, called weiboyi (http://www.weiboyi.com), which is for social advertising. In the website, advertisers are required to post their desired compensation to advertise to fans in the Weibo. From Figure 2, we show the cost information of 15012 advertisers. The range of their reported cost is from 0 to 5∗104, and the range of the number of their friends is from 0 to 2∗106. We use advertisers’ number of friends to simulate workers’ capacity. The cost information of advertisers will be normalized to (0,5) and the number of friends to [0,2]. The data set generation process is to select an instance in weiboyi data set and use the ca/mf for the worker’s cost and the normalized number of friends for workers’ capacity iteratively, in which ca denotes the advertiser’s normalized cost and mf indexes the advertiser’s normalized number of friends. We set crowdsourcer’s utility Ak (in a single region) with three symmetrical submodular functions, where Ak=k0.9, Ak=k, and Ak=∑i=1k100/100+k. We consider the a service subscriber wants to hire workers from 6 microregions. To obtain statistically 330 sound results, we run the simulation 1000 rounds for each parameter setting, and the microregion weight will be randomized in each round of experiments.Figure 2
Cost information with numbers of friends.


## 5.2. Benchmarks

We compare our designed auctions (MUMRwm and MUMRmm for two models) with 3 baselines. The first benchmark is the greedy algorithm, which will return the optimal solution. The greedy algorithm is not truthful and has full information of workers’ costs. The second benchmark is a uniform-price mechanism which is near-optimal, which is introduced in [31]. The last one is a random selecting algorithm. The mechanism chooses workers randomly and payoffs to workers are their declared cost, which are the lower bound performance of our designed problem. For maximin, the above three algorithms will be performed in each microregion in parallel with the same budget. We evaluate two performances of our proposed mechanism, crowdsourcer’s valuation and winner ratio. The first one means the utility achieved in the entire region. The second one represents the percentage of selected workers over all workers.


## 5.3. Results

We will present the results of the winner ratio, firstly. Since the simulation results of the three crowdsourcer’s valuations are similar, we just present the results ofAk=k0.9 here. We set the budget at 1000 and the number of workers from 100 to 1000. The results are shown in Figures 3(a) and 4(a) for both two models. We observe that the winner ratio decreases as the number of workers increases. The reason is that the auctions are more competitive with more workers. For the uniform pricing mechanism, the ratio will be stable, since the uniform pricing mechanism will choose a set of workers as the candidates when the scale of workers is relatively small.According Figures 3(b) and 4(b), we can know that the valuation of the buyer when the budget is 500 and the scale of workers is from 100 to 1000. The buyer’s utility grows with the increase of workers in all algorithms in both models. With a larger scale of workers, the buyer will utilize the budget more effectively. Our proposed mechanism outperforms random and uniform pricing mechanisms in the weighted mean model. MUMR’s performance approaches the performance of the greedy algorithm and uniform pricing mechanism in the maximin model. Figures 3(c) and 4(c) show the service subscriber’s valuation when the number of workers is 500 with the budget from 200 to 2000. From the figure, we know that the utility of the buyer increases simultaneously in algorithms MUMRwm and MUMRmm and greedy algorithm as the budget increases. The reason is that when the budget becomes larger, more workers can be hired. The greedy-based method performs well in the simulation; however, it is not strategy-proof. The performance of the uniform price mechanism approaches the one of MUMRwm and MUMRmm with the small budget. For the uniform price mechanism, the buyer’s valuation decreases as the budget increases. Since the mechanism will infer a threshold payoff based on the workers’ cost information, the one selected by the mechanism with larger budget may not be the optimal one.Figure 3
Results on weighted mean model.
(a)
Winner ratio(b)
Utility(c)
UtilityFigure 4
Results on maximin model.
(a)
Winner ratio(b)
Utility(c)
Utility


## 6. Conclusion

In this work, we introduce and study the multiregion crowdsensing problem and design two models for the multiregion crowdsensing. We propose a novel multiunit budget-feasible mechanism to solve problems. Our designed mechanisms are budget feasible, truthful, and individual rational and have a constant approximation ratio. Extensive simulations demonstrate the effectiveness of our solution.



---

*Source: 8834983-2020-08-19.xml*