# Truthful Profit Maximization Mechanisms for Mobile Crowdsourcing

Authors: Yu Qiao; Jie Zhang; Qiangqiang He; Yi Gu; Jun Wu; Lei Zhang; Chongjun Wang
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

Crowdsourcing is an effective tool to allocate tasks among workers to obtain a cumulative outcome. Algorithmic game theory is widely used as a powerful tool to ensure the service quality of a crowdsourcing campaign. By this paper, we consider a more general optimization objective for the budget-free crowdsourcer, profit maximization, where profit is defined as the difference between the benefit obtained by crowdsourcer and payments to workers. Based on the framework of random sampling and profit extraction, we proposed a strategy-proof profit-oriented mechanism for our problem, which also satisfies computational tractability and individual rationality and has a performance guarantee. We also extend the profit extract algorithm to the online case through a two-stage sampling. Also, we study the setting in which workers are not trusted, and untrustworthy workers would infer others’ true type. For untrustworthy workers, we introduce a differentially private mechanism, which also has desired properties. Finally, we will conduct numerical simulations to show the effectiveness of our proposed profit maximization mechanisms. By this work, we enrich the class of competitive auctions by considering a more general optimization objective and a more general demand valuation function.


---

## Body

## 1. Introduction

With the rapid development of the Internet and communication technology in recent decades, the Internet has become an important market for labor hirings, such as Amazon MTurk and Meituan. Compared to traditional labor markets, such online platforms are known as crowdsourcing markets, in which the service subscriber could divide microtasks to the geographically distributed workers. There are various applications of crowdsourcing or crowdsensing in practice, such as healthcare [1], smart city [2], and localization [3].In order to incentivize workers’ participation, the platform needs to pay compensations to the worker for the completion of tasks. The strategic behavior of online workers is a reasonable assumption, since all workers are rational individuals, who will seek to increase their utility by misreporting. Thus, we must design mechanisms to tackle the strategic workers. Algorithmic mechanism design is a branch of economic theory and game theory, which allows the designer to achieve desired objectives with strategic participants. Algorithmic mechanism design is also known as reverse game theory, which has been widely applied in our daily life, such as markets, sponsored search auctions, and voting procedures.In reality, a data broker may hire online workers to label data and build through a crowdsourcing campaign. The data broker is aimed to reselling the dataset to earn profits. Instead of finishing a specific set of tasks, the service subscriber is budget-free, whose target is profit-oriented, where profit is defined as the difference between payments to workers and the revenue. In this paper, we introduce a mechanism for profit-oriented crowdsourcer. Without loss of generality, we assume the crowdsourcer’s revenue function is symmetric submodular, which means the marginal revenue will decrease, as more data are sold. We design a strategy-proof mechanism based on random sampling, which also satisfies all desirable properties. Meanwhile, we extend the mechanism to the online setting. For the untrustworthy worker, we design a differentially private mechanism, which also has desired properties. Finally, we conduct numerical experiments to demonstrate the effectiveness of our proposed profit maximization mechanisms.Remark 1.
Compared to our earlier version [4], we simplify the competitive ratio from α−1/4α to 1/4 with the same allocation and payment function and different method of analysis. Also, we get a new competitive ratio for the online auction. Furthermore, we propose a profit-maximized differentially private mechanism for privacy-aware workers. Simulations are based on a real-world dataset instead of following some distributions.The contributions of this work are summarized as follows:(i)
Compared to the existing work on profit-oriented auction design, we study mechanisms for the buyer with a more generalized utility function, which is symmetric submodular(ii)
Drawing from the idea behind the online learning, we introduce a novel multistage sampling framework for online profit maximized auctions(iii)
We also study the mechanism for untrustworthy sellers. The proposed differentially private mechanism has good properties of individual rationality and approximate truthfulness and has a performance guarantee.


## 2. Related Work

Algorithmic game theory has become a useful method to build incentive auctions in the crowdsourcing system due to the strategic behavior of workers. Yaron [5] is the first person who studied the budget-constraint mechanism design which then became the major category of auctions for crowdsourcing auction design, i.e., [6–17]. In particular, Yaron proposed a method for provable guarantee auctions in crowdsourcing markets with fixed budget [7]. Biswas et al. proposed a multiarmed bandit setting under a budget constraint, in which the background that every task is with an invariable duration and unknown user abilities and due to the fixed budget, cost, and quality should be balanced when assigning tasks to workers [8]. Eric and Jason studied the budget constraint crowdsourcing auction with a Bayesian environment, who also proposed a posted price mechanism for their problem [10].This paper involves the study of revenue maximization, which was broadly studied by the community of economists, and the satisfactory solution is known in the Bayesian condition with a single-dimensional type of sellers [18].In recent time, one branch of research for the area of mechanism design suggests that even in the worst condition, in which the buyer has nothing about the knowledge of seller’s valuation, it is likely to maximize the buyer’s profit with a performance lower bound. A representative example of this area is a competitive digital auction, which is by getting certain knowledge from the sellers through bootstrapping, proposing the method of set partition and profit-extract, where its utility is measured by omniscient cases [19–21]. Several researchers have improved on the framework of competitive auctions; for example, Carry et al. introduced an extended competitive auction, which is adapted to auctions with structured goods [22]; Ray et al. considered how to maximize the profit of prior-free procurement auction when the auctioneer wants to purchase multiple homogeneous goods [23]; Zoe et al. found that according to the competitive mechanism, the multiunit budget-constrained auction problem proposed by Christien et al. [24] can be solved, where the quantity of the identical commodity is limited and each bidder’s private type is her cost and her budget constraint to maximize the sale revenue. Christien et al. built conditions that characterizes lower bound for all monotonic measurements [24]. Meanwhile, the methods used in this paper are built by random sampling and profit-extract framework introduced and lack full stop [19]. The differences on our proposal are major three points as follows: (a) the buyer’s revenue function; (b) the final objective; and (c) the number of units that every worker could provide.


## 3. Preliminaries

In our setting, there is a crowdsourcerC and a group of n workers who participate in the crowdsourcing auction. The crowdsourcer is the buyer in the market, who hires workers to build datasets and aims to sell data to earn profit. Workers are sellers in the market, who provide service to the buyer and get a return for their participation. The crowdsourcer’s target is profit maximization, where the profit is defined as the difference between the revenue of data and compensations to workers.Since the crowdsourcer will allocate tasks to the worker through an auction, every worker will submit a bidbi=mi,ci to the buyer. The bids of workers are bidimensional, where mi∈ℕ means the maximum number of tasks that the worker i could finish and ci denotes his unit private cost. If the quantity of tasks that are assigned to worker i is larger than mi, it will make the cost of worker i to +∞. Let b=b1,b2,⋯,bn index the bidding profile of all workers. Based on the reported bidding profile of workers, the decision made by the buyer consists of two schemes:
(i)
Anallocation schemexi:b1×⋯×bn⟶ℕ(ii)
Apayment schemepi:b1×⋯×bn⟶ℝ+Herein,pib is the compensation to the worker i and xib denotes the task number which is needed to be performed by worker i.Meanwhile, letm and c index the capacity vector and cost vector, respectively. In the end, the winners in the auction will perform tasks, and the crowdsourcer will pay them compensations.We denoteS as the quota of purchased unit service, and all purchased service is homogeneous. The revenue of the crowdsourcer is a function of S, which is only related the cardinality of S, i.e., S. In each round i, the revenue of the crowdsourcer increases by an incremental valueri when adding a new item i. ri denotes the marginal contribution for i-th unit, when i−1 units have been added. Meanwhile, we have r1>r2>,rn. Formally, the revenue function of the crowdsourcer is a symmetric submodular function. The revenue function is as follows:
(1)vrj=∑i=1jri,S=jj∈ℕ,in which r=r1,⋯,rN is a list of sorted nonnegative numbers. N is an extremely large number. The assumption of the symmetric submodularity of the revenue function is reasonable, due to the demand curve in economic theory.For an auctionx,p, with a bidding profile b, the profit obtained by the crowdsourcer is calculated by the difference between revenue achieved and the compensation to workers:
(2)πb=vr∑j=1nxjb−∑j=1npjb=∑i=1∑j=1nxjbri−∑j=1npjb.Also, we indexπb as πb.Letuib index the utility got by worker i. Formally, uib is defined as
(3)uib=pib−ci·xib,ifxib≤mi,−∞,otherwise.Next, we will present several properties which are often desired by the designer.(i)
Truthful: given any worker i, his utility is never increased by lying.(ii)
Individual rationality: given any worker i, his utility is never negative by participating the auction.(iii)
Computational tractability: all outcomes of the mechanism are computed in a polynomial time.(iv)
Competitive profit: when compared with the omniscient mechanism OPT that could get a best result Pb, the auction could get an unchanged part of Pb. If ∀b:Eπb≥1/γPb, in which γ represents an unchanged number, we will regard this mechanism achieves γ-competitive to OPT.


## 4. Performance Benchmark

In the rest of the paper, the optimal omniscient auction would be used as the benchmark and compared with our designed auction. In the optimal omniscient auction, the buyer has the full knowledge of the real information of all workers. There will be a clear price or purchasing price in such auctions. Purchasing price for the whole workers is the same numbers; then, it is named the optimal single-price omniscient mechanism, or it is named the optimal multiple price omniscient mechanism.For omniscient auctions, the buyer has the knowledge of workers’ capacity and cost. With a revenue functionvr·, the crowdsourcer will procure the labor service with the price of worker’s cost greedily in the optimal multiple price omniscient mechanism, until the marginal revenue is lower than next worker’s cost. Thus, the profit achieved in such auctions is
(4)OPTmb=maxj∑i=1jri−qi=∑i=1kmri−qi.Next, we would like to introduce the optimalsingle-price omniscient mechanism OPTsb, in which only one clear price will be adopted for all winners. Note the threshold payment adopted by OPTsb is the highest cost of the whole winners in this auction. Such utility achieved through OPTsb could be written as
(5)OPTs=maxj∑i=1jri−qj=∑i=1ksri−qks.ForOPTmb and OPTsb, we have the result as follows:Theorem 1.
OPTsb≥1/lnkm+O1OPTmb.Proof.
SinceOPTsb is the optimal result, we obtain that
(6)∀j:∑i=1ksri−qks≥∑i=1jri−qj≥∑i=1jrj−qj=jrj−qj.
Also, we have(7)∀j:rj−qj≤1j∑i=1ksri−qks.☐In the end, we get(8)OPTmb≤∑i=1km1j∑i=1ksri−qks≤lnkm+O1·OPTsb.


## 5. A Mechanism with Competitive Profit

When workers are strategic, the information of workers is unknown. The challenge is whether we can and how to reliably obtain a profit that is competitive to the profit of omniscient auctions, despite the challenge posed by information incompleteness and rational behavior of the users. Without prior knowledge of workers, a profit competitive auction seems a natural fit. The main idea behind our designed auction is to measure the optimal result through a sampling set of workers, and a profit-extract algorithm extracts the expected profit. This method is based on the framework of random sampling and profit extractor [22].


### 5.1. The Profit Extractor

At first, the profit extraction algorithm for a buyer, who has the revenue functionvr and expected profit R, is presented in the following algorithm ProfitExtractr,R that will use workers’ reported bidding profile bm,bc as inputs and x,p as outputs.The workflow of the above algorithm is as follows and presented in Algorithm1: we make the workers into a sorted list according to one’s reported unit cost firstly. Then, let qi be the cost of i-th service in the sorted list. After this, we set a clear price in the interval rk+1,rk in k-th unit service to procure all units of 1,⋯,k. Then, the expected profit R is achieved. Obviously, k is the maximum number to purchase. After this, if R is liked to be achieved, we need to find the last unit service k∗, and his cost is used as the clear price. k∗ service is named as stopping unit, and the worker who provides k∗ is named stopping worker. If we find k∗, the purchasing quota will be X with the clear price P. Else, X and P will both be zero. In the end, P is the clear price to buy X units from workers. The worker interacts with the buyer in a random order, and the mechanism stops when P is larger than the reported cost.Through the above algorithm, every workeri provides xi units with the payment pi=P·xi, in which xi is random, due to the fact that the X units are chosen randomly from workers. The expected benefit of worker i could be calculated:
(9)Eui=P−ci·Exi,ifPrxi≤mi=1,−∞,otherwise.Every workeri will not provide more than his capacity; otherwise, he would get the −∞ benefit.Algorithm 1:ProfitExtractr,R.
1:Input: Reported capacity bm and reported cost bc;2: Sort the workers according to his cost, and initiate the vectorxi,pi to every worker i as 0,0;3: Find out the unitk so that∑i=1kri−rk<R and ∑i=1kri−rk+1≥R;4: Find out the ending itemsk∗∈1,⋯,k satisfying ∑i=1k∗ri−qk∗·k∗≥R;5:ifk∗ exists then6:X⟵k∗; P⟵∑i=1k∗ri−R/k∗;7:elseX⟵0,P⟵0;8:W⟵1,2,⋯,n;9:whileW≠∅ and X≠0do10:  Select a workeri from W randomly;11:W⟵W\i;12:ifbic≤Pthen13:xi,pi⟵minX,bim,P·xi; X⟵X−xi;14:end while15:Output: x,pLemma 1.
For the auctionProfitExtractr,R, there is no worker could increase his utility by misreporting his capacity.Proof.
Obviously, every worker reporting a lower amount would neither change the procurement number nor change the purchasing price; thus, misreporting would not increase his utility. When it came to higher bid, we useX as the current quota and P as the clear price. Given a worker j whose capacity is mj, if he reports his capacity mj′>mj, and his xj′ units will be provided and get a higher benefit Euj′. We use X′ and P′ to index the procured amount and the clear price separately. Then, we have that 1 of the below equations will be true: (1) P′>P and (2) Exj′>Exj. P′>P represents X′=∑i=1kbim>X and 1≤j≤k; i.e., the capacity bid of worker i will be the sum of X′, thus, X′>mj′>mj, and it implies Euj′=−∞, and we have a contradiction; Exj′>Exj implies X′>X or cj≤P′<P. We have already presented X′>X would reach a contradiction. Meanwhile, it is obviously that cj≤P′<P would not happen.☐Furthermore, we could show no worker could increase his utility by lying about his unit cost.Theorem 2.
Profit−Extractr,R is truthful.Proof.
According to Lemma1, it only needs to prove the whole workers would bid his unit cost truthfully. Given a worker i, there will be 2 cases to discuss:
1)i≤i∗. This seller i is the stopping worker or a seller in front of the stopping worker. It is easy to see that every worker would get a utility at least zero by reporting one’s true cost. If a worker increases his reported cost which is lower than the clear price, then the clear price and procuring quota will not change. Thus, worker i’s utility is invariable. If a worker increases his reported cost which is more than the purchasing price, there will be two cases: (1) a worker j (j<i∗) would be the new stopping worker; thus, the purchasing price and the procuring amount would decrease, and the worker would lose in the game, whose utility will be zero. (2) The mechanism is a failure, and no task is allocated to the workers, and all workers would achieve a zero benefit. For the aforementioned two possibilities, worker i’s benefit will decrease,i>i∗. Worker i is after the stopping worker. If worker i increases his bidding, PX, and his utility will be the same. If his bidding cost decreases, there will be two cases: (1) X and P would not change; and (2) the worker i will provide some service at a price which is lower than his true cost. Then, his utility will not be positive. In the above two cases, the worker’s benefit will not increase.☐Combining the above two cases, the lemma holds.Theorem 3.
ProfitExtractr,R is individually rational.Proof.
Given a workeri, he reports bim,bic. The purchasing price would satisfy P≤bic. Therefore, bim of his units would be sold with P. Based on Theorem 2, each worker’s benefit would report his true type; thus, each worker is larger than zero.☐Next, we will show that, for an arbitrary group of workers, the designed algorithm could achieve any target profitR.Lemma 2.
AlgorithmProfitExtractr,R achieves benefit RifOPTsb>R and gets 0 otherwise.Proof.
According to Lemma1, any worker’ biding information will be his true cost. OPTsb>R implies that ∑i=1ksri−qks>R through equation (4). It would be 2 possibilities:
(1)
ks≤k: if we assume that X=ks and set the clear price as P=∑i=1ksri−R/ks, we obtain P>qks. The cost of every first ks service is lower than P. Therefore, we could use the above P and X to achieve a predetermined profit R.(2)
ks>k: if we assume that X=k and set P=∑i=1kri−R/k, which implies P≥∑i=1kri−∑i=1kri−rk+1/k=rk+1≥rks. Meanwhile, because rks≥qks could be get by the concept of OPTsb, P≥rk+1≥rks, and qks>qk, which implies P>qk. Therefore, we could use the above P and X to achieve a predetermined profit R.☐Also, ifOPTsb<R, then nothing would be bought from workers and the profit is zero.


### 5.2. The Profit Competitive Auction

Until now, a profit-extract algorithm has been introduced. Through this algorithm, we could obtain Algorithm2.Algorithm 2:Profit−PAr.
1:Input: capacity bid bm and unit cost bid bc;2: Partition bids,Σ=b u.a.r. into two sets ΣA=bA and ΣB=bB with equal probabilities;3:RA⟵OPTsbA;RB⟵OPTsbB;4: Choose a setΣx from ΣA,ΣB randomly;x,p⟵ProfitExtractr,Rx¯bxm,bxciffailx,pthenx,p⟵ProfitExtractr,Rxbx¯m,bx¯cThis algorithm is based on random sampling and presented in Algorithm2, where workers are partitioned into 2 groups. Next, OPTs of every group is calculated. In the end, the extractor algorithm will be applied to one of two groups to get the OPTs profit which is calculated by the other group. In our method, at least one of the two partitions will achieve profits.Theorem 4.
Profit−PAr finishes in polynomial time.Proof.
In the complexity ofOPTs, the profit extractor algorithm isOn. The algorithm contains a dividing process and two times of calculating OPTs and one time of profit-extractor algorithm. Thus, the mechanism could be calculated in polynomial time.☐Theorem 5.
Profit−PAr is truthful.Proof.
Given a set of workersΣA, whose bidding types are bAm,bAc, the allocation and compensation vectors are calculated via performing ProfitExtractr,RBbAm,bAc, in which r and RB have nothing related to bAm,bAc. Thus, based on Lemma 2, for every worker in ΣA, reporting his true type is the best strategy. Drawing from ΣA, we also have the conclusion in ΣB.☐As for the performance of our designed algorithm, we could have the result as follows.Lemma 3.
With an arbitrary bidding profileb, the algorithm Profit−PAr gets a profit minOPTsbA,OPTsbB.Proof.
AssumeRA>RB in the algorithm, and according to Lemma 2, RB will be achieved in line 3. Meanwhile, with RA<RB, the achieved value is RA. In the end, with RA=RB, the profit could also be achieved.☐Theorem 6.
Profit−PAr achieves 4-competitive to OPTs.Proof.
Letm^i index the i-th worker’s sold service for ks. We use Σs=a1,⋯,aj to index the j workers who sold services to OPTsb, Ps indexes the used purchasing price. We use ΣAs and ΣBs to denote the sellers from Σs, and be divided to subgroups A and B separately. Thus, ks=∑i=1jm^i. It implies kAs=∑i∈ΣAsm^i, kBs=∑i∈ΣBsm^i and kAs+kBs=ks. Meanwhile, we get
(10)OPTsbA≥∑i=1kAsri−Ps,
due to the fact that we could achieve a benefit by procuringkAs units with Ps. Also,
(11)OPTsbB≥∑i=1kBsri−Ps.☐Based on Lemma3, Profit−PAr achieves a benefit of
(12)πb=minOPTsbA,OPTsbB≥min∑i=1kAsri−Ps,∑i=1kBsri−Ps≥minkAs,kBsks·∑i=1ksri−Ps.BecauseA, B are two partitions of all workers,
(13)minkAs,kBsks=1ks∑i=1ks−1mini,ks−iksi2−ks=12−2−ksks−1ks2.The value of above equation reaches the minimum1/4 with ks=2,3. As ks increases, the value would approach 1/2.In the end, we have(14)Eπb≥EminkAs,kBsks·OPTsb≥14OPTsb.


## 5.1. The Profit Extractor

At first, the profit extraction algorithm for a buyer, who has the revenue functionvr and expected profit R, is presented in the following algorithm ProfitExtractr,R that will use workers’ reported bidding profile bm,bc as inputs and x,p as outputs.The workflow of the above algorithm is as follows and presented in Algorithm1: we make the workers into a sorted list according to one’s reported unit cost firstly. Then, let qi be the cost of i-th service in the sorted list. After this, we set a clear price in the interval rk+1,rk in k-th unit service to procure all units of 1,⋯,k. Then, the expected profit R is achieved. Obviously, k is the maximum number to purchase. After this, if R is liked to be achieved, we need to find the last unit service k∗, and his cost is used as the clear price. k∗ service is named as stopping unit, and the worker who provides k∗ is named stopping worker. If we find k∗, the purchasing quota will be X with the clear price P. Else, X and P will both be zero. In the end, P is the clear price to buy X units from workers. The worker interacts with the buyer in a random order, and the mechanism stops when P is larger than the reported cost.Through the above algorithm, every workeri provides xi units with the payment pi=P·xi, in which xi is random, due to the fact that the X units are chosen randomly from workers. The expected benefit of worker i could be calculated:
(9)Eui=P−ci·Exi,ifPrxi≤mi=1,−∞,otherwise.Every workeri will not provide more than his capacity; otherwise, he would get the −∞ benefit.Algorithm 1:ProfitExtractr,R.
1:Input: Reported capacity bm and reported cost bc;2: Sort the workers according to his cost, and initiate the vectorxi,pi to every worker i as 0,0;3: Find out the unitk so that∑i=1kri−rk<R and ∑i=1kri−rk+1≥R;4: Find out the ending itemsk∗∈1,⋯,k satisfying ∑i=1k∗ri−qk∗·k∗≥R;5:ifk∗ exists then6:X⟵k∗; P⟵∑i=1k∗ri−R/k∗;7:elseX⟵0,P⟵0;8:W⟵1,2,⋯,n;9:whileW≠∅ and X≠0do10:  Select a workeri from W randomly;11:W⟵W\i;12:ifbic≤Pthen13:xi,pi⟵minX,bim,P·xi; X⟵X−xi;14:end while15:Output: x,pLemma 1.
For the auctionProfitExtractr,R, there is no worker could increase his utility by misreporting his capacity.Proof.
Obviously, every worker reporting a lower amount would neither change the procurement number nor change the purchasing price; thus, misreporting would not increase his utility. When it came to higher bid, we useX as the current quota and P as the clear price. Given a worker j whose capacity is mj, if he reports his capacity mj′>mj, and his xj′ units will be provided and get a higher benefit Euj′. We use X′ and P′ to index the procured amount and the clear price separately. Then, we have that 1 of the below equations will be true: (1) P′>P and (2) Exj′>Exj. P′>P represents X′=∑i=1kbim>X and 1≤j≤k; i.e., the capacity bid of worker i will be the sum of X′, thus, X′>mj′>mj, and it implies Euj′=−∞, and we have a contradiction; Exj′>Exj implies X′>X or cj≤P′<P. We have already presented X′>X would reach a contradiction. Meanwhile, it is obviously that cj≤P′<P would not happen.☐Furthermore, we could show no worker could increase his utility by lying about his unit cost.Theorem 2.
Profit−Extractr,R is truthful.Proof.
According to Lemma1, it only needs to prove the whole workers would bid his unit cost truthfully. Given a worker i, there will be 2 cases to discuss:
1)i≤i∗. This seller i is the stopping worker or a seller in front of the stopping worker. It is easy to see that every worker would get a utility at least zero by reporting one’s true cost. If a worker increases his reported cost which is lower than the clear price, then the clear price and procuring quota will not change. Thus, worker i’s utility is invariable. If a worker increases his reported cost which is more than the purchasing price, there will be two cases: (1) a worker j (j<i∗) would be the new stopping worker; thus, the purchasing price and the procuring amount would decrease, and the worker would lose in the game, whose utility will be zero. (2) The mechanism is a failure, and no task is allocated to the workers, and all workers would achieve a zero benefit. For the aforementioned two possibilities, worker i’s benefit will decrease,i>i∗. Worker i is after the stopping worker. If worker i increases his bidding, PX, and his utility will be the same. If his bidding cost decreases, there will be two cases: (1) X and P would not change; and (2) the worker i will provide some service at a price which is lower than his true cost. Then, his utility will not be positive. In the above two cases, the worker’s benefit will not increase.☐Combining the above two cases, the lemma holds.Theorem 3.
ProfitExtractr,R is individually rational.Proof.
Given a workeri, he reports bim,bic. The purchasing price would satisfy P≤bic. Therefore, bim of his units would be sold with P. Based on Theorem 2, each worker’s benefit would report his true type; thus, each worker is larger than zero.☐Next, we will show that, for an arbitrary group of workers, the designed algorithm could achieve any target profitR.Lemma 2.
AlgorithmProfitExtractr,R achieves benefit RifOPTsb>R and gets 0 otherwise.Proof.
According to Lemma1, any worker’ biding information will be his true cost. OPTsb>R implies that ∑i=1ksri−qks>R through equation (4). It would be 2 possibilities:
(1)
ks≤k: if we assume that X=ks and set the clear price as P=∑i=1ksri−R/ks, we obtain P>qks. The cost of every first ks service is lower than P. Therefore, we could use the above P and X to achieve a predetermined profit R.(2)
ks>k: if we assume that X=k and set P=∑i=1kri−R/k, which implies P≥∑i=1kri−∑i=1kri−rk+1/k=rk+1≥rks. Meanwhile, because rks≥qks could be get by the concept of OPTsb, P≥rk+1≥rks, and qks>qk, which implies P>qk. Therefore, we could use the above P and X to achieve a predetermined profit R.☐Also, ifOPTsb<R, then nothing would be bought from workers and the profit is zero.


## 5.2. The Profit Competitive Auction

Until now, a profit-extract algorithm has been introduced. Through this algorithm, we could obtain Algorithm2.Algorithm 2:Profit−PAr.
1:Input: capacity bid bm and unit cost bid bc;2: Partition bids,Σ=b u.a.r. into two sets ΣA=bA and ΣB=bB with equal probabilities;3:RA⟵OPTsbA;RB⟵OPTsbB;4: Choose a setΣx from ΣA,ΣB randomly;x,p⟵ProfitExtractr,Rx¯bxm,bxciffailx,pthenx,p⟵ProfitExtractr,Rxbx¯m,bx¯cThis algorithm is based on random sampling and presented in Algorithm2, where workers are partitioned into 2 groups. Next, OPTs of every group is calculated. In the end, the extractor algorithm will be applied to one of two groups to get the OPTs profit which is calculated by the other group. In our method, at least one of the two partitions will achieve profits.Theorem 4.
Profit−PAr finishes in polynomial time.Proof.
In the complexity ofOPTs, the profit extractor algorithm isOn. The algorithm contains a dividing process and two times of calculating OPTs and one time of profit-extractor algorithm. Thus, the mechanism could be calculated in polynomial time.☐Theorem 5.
Profit−PAr is truthful.Proof.
Given a set of workersΣA, whose bidding types are bAm,bAc, the allocation and compensation vectors are calculated via performing ProfitExtractr,RBbAm,bAc, in which r and RB have nothing related to bAm,bAc. Thus, based on Lemma 2, for every worker in ΣA, reporting his true type is the best strategy. Drawing from ΣA, we also have the conclusion in ΣB.☐As for the performance of our designed algorithm, we could have the result as follows.Lemma 3.
With an arbitrary bidding profileb, the algorithm Profit−PAr gets a profit minOPTsbA,OPTsbB.Proof.
AssumeRA>RB in the algorithm, and according to Lemma 2, RB will be achieved in line 3. Meanwhile, with RA<RB, the achieved value is RA. In the end, with RA=RB, the profit could also be achieved.☐Theorem 6.
Profit−PAr achieves 4-competitive to OPTs.Proof.
Letm^i index the i-th worker’s sold service for ks. We use Σs=a1,⋯,aj to index the j workers who sold services to OPTsb, Ps indexes the used purchasing price. We use ΣAs and ΣBs to denote the sellers from Σs, and be divided to subgroups A and B separately. Thus, ks=∑i=1jm^i. It implies kAs=∑i∈ΣAsm^i, kBs=∑i∈ΣBsm^i and kAs+kBs=ks. Meanwhile, we get
(10)OPTsbA≥∑i=1kAsri−Ps,
due to the fact that we could achieve a benefit by procuringkAs units with Ps. Also,
(11)OPTsbB≥∑i=1kBsri−Ps.☐Based on Lemma3, Profit−PAr achieves a benefit of
(12)πb=minOPTsbA,OPTsbB≥min∑i=1kAsri−Ps,∑i=1kBsri−Ps≥minkAs,kBsks·∑i=1ksri−Ps.BecauseA, B are two partitions of all workers,
(13)minkAs,kBsks=1ks∑i=1ks−1mini,ks−iksi2−ks=12−2−ksks−1ks2.The value of above equation reaches the minimum1/4 with ks=2,3. As ks increases, the value would approach 1/2.In the end, we have(14)Eπb≥EminkAs,kBsks·OPTsb≥14OPTsb.


## 6. Online Profit-Maximizing Mechanism

Until now, we have introduced an offline mechanism; the buyer and worker will interact through a sealed bid auction. But it is hard to gather all workers in a time in practice; it motivates us to design an online profit-oriented auction. The parameters and settings of online auctions are similar to the one of offline auction, but there will be a time durationT between the starting time and ending time. All workers will arrive and participate in the auction. The arrival time of each worker is i.i.d. and followed some unknown distributions.When we design the auction of the online setting, it is necessary to consider the following challenges: (1) the auction needs to incentivize the seller to report his true type; (2) the auction needs to decide the purchasing quota before all workers’ arrival; and (3) the auction needs to handle the online arrival of workers. To handle the hurdle, we proposed a two-stage sampling, enlightened by the online learning. The auction will partition the time into two substages. The first stage will be used for learning, and the other is for earning profit. The first substage will be terminated byT/2; the next substage will start at T/2 and end at T. The workers in the first substage will be rejected automatically, which will be used to learn the information for making decision in the substage. While the first substage is terminated, we will use workers, who arrived in this substage, to build a sample S′ to calculate P and R. With P and R, we could extract profit from workers in the second substage.Algorithm 3: Online profit-oriented auction.
1: Sett,T′,S′,P,W⟵1,T,∅,0,∅;2:whilet<T′/2do3:if there is a worker i arriving at tthen4:S′⟵S′∪i;5:end while6:R⟵OPTsbS′ and P⟵Ps′;7:whileT′/2<t<T′do8:if there is a worker i arriving at tthen9:ifci≤P and OPTsbW<Rthen10:pi⟵P and W⟵W∪i;11:elsepi⟵0;12:end while13:Output:W and p;The auction does not terminate untilR is obtained. Intuitively, the stop criterion is to guarantee that our obtained profit is not a negative value number, because the utility function of the crowdsourcer is monotone decreasing with r. The crowdsourcer procures too many units from workers, which might result in a loss. Since the online profit-oriented auction is extended by the offline profit-extract, it will share some properties.Lemma 4.
The online profit-oriented auction is computed in polynomial time computationally tractableProof.
The mechanism has an online decision operation, one time of calculating optimal profitOn, and single time of running Profit extracts On in Algorithm 3, which all will be finished in a polynomial time, since Algorithm 3 will run few times of profit extraction algorithms.☐Lemma 5.
The online profit oriented auction is individually rational.Proof.
It is trivial, since our proposed mechanism is a posted-price mechanism. Therefore, we have the lemma.☐Lemma 6.
The online profit oriented auction is truthful.Proof.
It is trivial, since our proposed mechanism is a posted-price mechanism. Thus, the lemma holds.☐LetN1 and N2 index the subsets of N that appears in the first and second halves of the input workers, separately. Because the types of all workers are i.i.d., they could be chosen in the set N under the same probability. The sampling set S′ is a randomized subset of N since all users arrives in a random order. Thus, the number of workers inNinS′would follow a hypergeometric distributionHn/2,∣N∣,n. We index the total services of the workers whose cost is lower than P′ as kP′Z1 in the subset Z1 and kP′Z2 in the subset Z2, in which Z1 and Z2 are two random partitions. Because the types of all workers are i.i.d. and the two subsets are generated from a hypergeometric distribution, let us assume kP′Z1 has an invariant ratio to kP′Z2, which bounded by 1−δ for any given clear price P′, in which δ is a small invariant value between (0,1) if kP′Z1≥kP′Z2. Then, we could obtain kP′N2/kP′N1≥1−δ. Then, we get the lemma as follows.Lemma 7.
The online profit oriented auction is1−δ4-competitive to OPTs.Proof.
We index the profit for the optimal omniscient auctions for the first sub-stage asOPTS′. According to Theorem 10, it implies that OPTS′≥1/4-competitive to OPTs. Thus, we only need to prove the ratio of OPTN2 to OPTS′. There will be 2 possibilities:
(i)
The auction gets the target profitR by the second substage. Therefore, it implies R≥1/4OPTs≥1−δ1/4OPTs(ii)
The auction is failed to getR while the mechanism ends. It is easy to see kPS′≥kPN2. The obtained R′ is formulated by(15)R′=R−R−πbW=R−R−∑i=1kPN2ri−kPN2×P=R−∑i=1kPN1ri−kPN1×P−∑i=1kPN2ri−kPN2×P=R−∑i=1kPN1ri−∑i=1kPN2ri−kPN1−kPN2×P≥R−∑i=1kPN1−kPN2ri−kPN1−kPN2×P≥R−∑i=1kPN1−1−δkPN1ri−kPN1−1−δkPN1×P=R−δ∑i=1kPN1ri−kPN1×P=1−δR≥1−δ14OPTs☐Thus, combining two possibilities, the lemma holds.By the aforementioned lemmas, we can get the theorem as follows.Theorem 7.
The online profit oriented auction is the computational efficiency, individual rationality, and truthfulness and has1−δ4-competitive to OPTs.


## 7. Differentially Private Mechanism

In this part, we will study privacy-preserving mechanisms for the profit-oriented crowdsourcing, in which there will be workers acting as attackers who snoop on other workers’ private information [25]. The differentially private algorithm ensures the distribution of results does not change significantly while one item changes her input. Formally, the definition of the differentially private algorithm isDefinition 1 (differential privacy).
A randomized algorithmA is ϵ-differentially private if for an arbitrary input vector D1 and D2, whose difference is only one worker, and the following formula holds for any payment vector x:
(16)PrAD1∈x≤expϵPrAD2∈x.The above definition ensures that any alternation in an arbitrary worker’s reported information will not result in a significant change in the outcome of the payment profile, which makes it hard for an attacker to obtain the private types of other workers in the mechanism. Note, unlike the trustworthy case, we wish our mechanism satisfies the following property.Definition 2 (approximate truthfulness).
We say a mechanism approximate truthful, if it satisfies the following equation:(17)∀bi′Euibi,b−i≥Euibi′,b−i−γ,in which γ is a small positive number.Next, we will design a profit-oriented differentially private auction through the exponential mechanism. The exponential mechanism computes the result over arbitrary domains and ranges instead of a specific value [26]. The definition of the exponential mechanism is as follows:Definition 3 (exponential mechanism).
The exponential mechanismsM randomly assign the input set D to the outcome r∈R. In particular, the exponential mechanism decides the outcome r based on the equation as follows:
(18)PrMD=r∝expϵqD,r,
in whichqD,r is a query function mapping a pair of input data set D and the candidate result r to a real value.Algorithm4 is our proposed exponential mechanism for a profit-oriented auction. We denote P as all possible clearing price, which can be get from the cost profile of sellers. Firstly, for each possible purchasing price P, sifts out the sellers whose private cost is not higher than P and make them a new group ΦP. Then, we can compute the maximum amount of service that can be purchased, denoted as ΨP, Finally, work out the profit obtained through the workers in ΦP, which is indexed by Ub,P. We will choose the clearing price according to the probability which is proportional to the expϵUb,x/2U∗b,P∗, where U∗b,P∗ is the optimal outcome of the auction.


### 7.1. Mechanism Analysis

Theorem 8.
Differential privacy mechanism is individually rational.Proof.
When the unit service cost of sellersi is more than the clearing price P, i.e., ciP, the auctioneer will not purchase services from them; in this case, the utility of sellersiis to equal 0. In contrast, when the unit service cost of sellers i is no greater than the clearing price P, i.e., ci≤P, the auction possibly purchases services from them; in this case, the utility of sellers i is ci−Pxi≥0.☐In summary, the utility of sellersi is no lesser than 0.Algorithm 4: Differential privacy mechanism.
1:forP∈Pdo2:ΦP⟵i∈Jm:ci≤P3:ΨP⟵∑i∈ΦPmi4:Ub,P⟵maxj≤ΨP∑i=1jri−P5:U∗b,P∗=maxPUb,P6:end for7: choose a clearing priceP with the probability distributions:8:PrP=x=expϵUb,x/2U∗b,P∗/∑y∈PexpϵUb,y/2U∗b,P∗,∀x∈P9:k⟵argmaxj≤ΨP∑i=1jri−P10:whileΦP≠∅ and k≠0do11:  Randomly select a bidderi from ΦP12:ΦP⟵ΦP\i13:xi,pi⟵mink,mi,P·xi14:k⟵k−xi15:end while16:Output: the combined allocation and payment x,pTheorem 9.
Differential privacy mechanism satisfiesε-differentially private.Proof.
We denoteb and b′ as two input sets with only one different element. With a fixed price P, the maximum difference of profit obtained from the two bidding sets is
(19)ΔUP=maxb,b′Ub,P−Ub′,P.☐We useΔU to denote the maximum ΔUP over all clear prices P. Obviously we know that
(20)ΔU=maxP∈PΔUP≤U∗b,P.∀x∈P, we have
(21)PrMb=xPrMb′=x=expϵUb,x/2U∗b,P∗∑y∈PexpϵUb,y/2U∗b,P∗∑y∈PexpϵUb′,y/2U∗b,P∗expϵUb′,x/2U∗b,P∗≤expϵΔUx2U∗b,P∗∑y∈PexpϵUb,y+ΔUy/2U∗b,P∗∑y∈PexpϵUb,y/2U∗b,P∗≤expϵΔU2U∗b,P∗expϵΔU2U∗b,P∗≤expϵ2expϵ2=expϵ.Thus, we have(22)PrMb=x≤expϵPrMb′=x,∀x∈P.Therefore, the theorem holds.Theorem 10.
Differential privacy mechanism is approximately truthful.Proof.
With the bid vectorb, the expected utility of seller i is as follows:
(23)EP~Mbuibi,b−i,P=∑P∈PEuibi,b−i,PPrMb=P.
According to Theorem8, we know
(24)PrMb′=x≤expϵPrMb=x,∀x∈P,so
(25)∑P∈PEuibi,b−i,PPrMb=P≥∑P∈PEuibi,b−i,Pexp−ϵPrMb′=P.
We can prove that the expected utility will not increase when the selleri lies about his type.
(1)
Whenci′<ci, if ci>P, this is discussed in two cases. If ci′>P, then the auctioneer will not purchase services from the mobile user i; if ci′≤P, then the auctioneer may purchase the service from the data contributor i And then his utility is P−cixi, which has a negative value. If ci≤P, then the expected utility is unchanged(2)
Whenci′>ci, if ci>P, the expected utility is unchanged. If ci≤P, this is discussed in two cases. If ci′>P, the auctioneer will not purchase from the seller i, so the utility is reduced; if ci′≤P, obviously, the expected utility is unchanged(3)
Whenmi′>mi, because the cost of the service beyond the capacity of sellers, so his utility is +∞, when mi′<mi, it is easy to know that the expected utility will not increase☐In summary, there isEuibi,b−i,P≥Euibj′,b−i,P; thus, we have
(26)∑P∈PEuibi,b−i,PPrMb=P≥∑P∈PEuibi,b−i,Pexp−ϵPrMb′=P≥∑P∈PEuibi′,b−i,Pexp−ϵPrMb′=P=exp−ϵEP~Mb′uibi′,b−i,P≥1−ϵEP~Mb′uibi′,b−i,P=EP~Mb′uibi′,b−i,P−ϵEP~Mb′uibi′,b−i,P.We usesmmax to index the maximum amount of services that the sellers can provide, so we get
(27)EP~Mb′uibi′,b−i,P≤maxP∈Puibi′,b−i,P≤Pmax−ci·mi≤Pmaxmmax.Combined with the previous formula, we can get(28)EP~Mbuibi,b−i,P≥EP~Mb′uibi′,b−i,P−ϵPmaxmmax.According to Definition2, the theorem is proved.Theorem 11.
Differential privacy mechanism to obtain a profit of not less thanmaxPUb,P−Olnn with a probability of at least 1−1/nO1.Proof.
From [27], we have the following formula:
(29)PrUb,Mb<maxPUb,P−lnP/POPTϵ−κϵ≤exp−κ.☐Due to the fact thatP and POPT are constants, if we set κ=Olnn in the above equation, then, we obtain
(30)PrUb,Mb≥maxPUb,P−Olnn≥1−1nO1.So, the theorem is proved.


## 7.1. Mechanism Analysis

Theorem 8.
Differential privacy mechanism is individually rational.Proof.
When the unit service cost of sellersi is more than the clearing price P, i.e., ciP, the auctioneer will not purchase services from them; in this case, the utility of sellersiis to equal 0. In contrast, when the unit service cost of sellers i is no greater than the clearing price P, i.e., ci≤P, the auction possibly purchases services from them; in this case, the utility of sellers i is ci−Pxi≥0.☐In summary, the utility of sellersi is no lesser than 0.Algorithm 4: Differential privacy mechanism.
1:forP∈Pdo2:ΦP⟵i∈Jm:ci≤P3:ΨP⟵∑i∈ΦPmi4:Ub,P⟵maxj≤ΨP∑i=1jri−P5:U∗b,P∗=maxPUb,P6:end for7: choose a clearing priceP with the probability distributions:8:PrP=x=expϵUb,x/2U∗b,P∗/∑y∈PexpϵUb,y/2U∗b,P∗,∀x∈P9:k⟵argmaxj≤ΨP∑i=1jri−P10:whileΦP≠∅ and k≠0do11:  Randomly select a bidderi from ΦP12:ΦP⟵ΦP\i13:xi,pi⟵mink,mi,P·xi14:k⟵k−xi15:end while16:Output: the combined allocation and payment x,pTheorem 9.
Differential privacy mechanism satisfiesε-differentially private.Proof.
We denoteb and b′ as two input sets with only one different element. With a fixed price P, the maximum difference of profit obtained from the two bidding sets is
(19)ΔUP=maxb,b′Ub,P−Ub′,P.☐We useΔU to denote the maximum ΔUP over all clear prices P. Obviously we know that
(20)ΔU=maxP∈PΔUP≤U∗b,P.∀x∈P, we have
(21)PrMb=xPrMb′=x=expϵUb,x/2U∗b,P∗∑y∈PexpϵUb,y/2U∗b,P∗∑y∈PexpϵUb′,y/2U∗b,P∗expϵUb′,x/2U∗b,P∗≤expϵΔUx2U∗b,P∗∑y∈PexpϵUb,y+ΔUy/2U∗b,P∗∑y∈PexpϵUb,y/2U∗b,P∗≤expϵΔU2U∗b,P∗expϵΔU2U∗b,P∗≤expϵ2expϵ2=expϵ.Thus, we have(22)PrMb=x≤expϵPrMb′=x,∀x∈P.Therefore, the theorem holds.Theorem 10.
Differential privacy mechanism is approximately truthful.Proof.
With the bid vectorb, the expected utility of seller i is as follows:
(23)EP~Mbuibi,b−i,P=∑P∈PEuibi,b−i,PPrMb=P.
According to Theorem8, we know
(24)PrMb′=x≤expϵPrMb=x,∀x∈P,so
(25)∑P∈PEuibi,b−i,PPrMb=P≥∑P∈PEuibi,b−i,Pexp−ϵPrMb′=P.
We can prove that the expected utility will not increase when the selleri lies about his type.
(1)
Whenci′<ci, if ci>P, this is discussed in two cases. If ci′>P, then the auctioneer will not purchase services from the mobile user i; if ci′≤P, then the auctioneer may purchase the service from the data contributor i And then his utility is P−cixi, which has a negative value. If ci≤P, then the expected utility is unchanged(2)
Whenci′>ci, if ci>P, the expected utility is unchanged. If ci≤P, this is discussed in two cases. If ci′>P, the auctioneer will not purchase from the seller i, so the utility is reduced; if ci′≤P, obviously, the expected utility is unchanged(3)
Whenmi′>mi, because the cost of the service beyond the capacity of sellers, so his utility is +∞, when mi′<mi, it is easy to know that the expected utility will not increase☐In summary, there isEuibi,b−i,P≥Euibj′,b−i,P; thus, we have
(26)∑P∈PEuibi,b−i,PPrMb=P≥∑P∈PEuibi,b−i,Pexp−ϵPrMb′=P≥∑P∈PEuibi′,b−i,Pexp−ϵPrMb′=P=exp−ϵEP~Mb′uibi′,b−i,P≥1−ϵEP~Mb′uibi′,b−i,P=EP~Mb′uibi′,b−i,P−ϵEP~Mb′uibi′,b−i,P.We usesmmax to index the maximum amount of services that the sellers can provide, so we get
(27)EP~Mb′uibi′,b−i,P≤maxP∈Puibi′,b−i,P≤Pmax−ci·mi≤Pmaxmmax.Combined with the previous formula, we can get(28)EP~Mbuibi,b−i,P≥EP~Mb′uibi′,b−i,P−ϵPmaxmmax.According to Definition2, the theorem is proved.Theorem 11.
Differential privacy mechanism to obtain a profit of not less thanmaxPUb,P−Olnn with a probability of at least 1−1/nO1.Proof.
From [27], we have the following formula:
(29)PrUb,Mb<maxPUb,P−lnP/POPTϵ−κϵ≤exp−κ.☐Due to the fact thatP and POPT are constants, if we set κ=Olnn in the above equation, then, we obtain
(30)PrUb,Mb≥maxPUb,P−Olnn≥1−1nO1.So, the theorem is proved.


## 8. Simulation Study

### 8.1. Experiment Settings

We conducted two sets of experiments as follows:(1)
Firstly, we mainly verify the performance of theProfit−PAr algorithm, i.e., the competitive ratio to the single-price omniscient optimal auction(2)
Secondly, we demonstrate the performance of the proposed differential privacy mechanism. Also, we also study the sensitivity of parameters and settings to the performance of the mechanism. In addition, the performances of privacy protection are illustrated by analyzing the probability distribution of the results


#### 8.1.1. Profit-PA

Numerical experiments are conducted to illustrate the effectiveness of our designed profit-oriented mechanism. Cost information is hard to obtain from the worker directly; thus, we estimated the cost information according to the historical bidding data. In Weiboyi, a user will provide bidding for recommending a product to her friends and a number of friends that the user has. In Weiboyi, bidding contains both price and the number of friends. Thus, we use them to approximately estimate the cost information and capacity of a worker. We obtained over 10000 bidders in Weiboyi. The information of a selected user is shown in Figure1. The cost of a seller is from 0 to 5∗104 and the number of friends is from 0 to 2∗106. We normalize the cost into 0,5 and the number of friends into 0,2. When we select a seller from Weiboyi dataset, we will use the cost and the friends’ number of the seller in Weiboyi to simulate the cost and the friends’ number of a worker in our crowdsourcing platform. We use the following submodular function to measure the buyer’s revenue:
(31)πx=∑i=1x4000−i1000.Figure 1
Costs versus numbers of friends.


#### 8.1.2. Differential Privacy Mechanism

The private information of service providers is generated by a uniform distribution with intervals of [1, 10] and [0.2, 2]. Here, the minimum cost per unit of service is 0.2, which is a fixed overhead that is inevitably consumed by providing unit services. For the settings of competitive auctions, the cost is from uniform distribution that is known in advance.In the differential privacy mechanism,ϵ is an adjustable variable. The scope of ε is limited to [0, 1], and experiments are running with values of 0.05, 0.5, and 1, respectively. We will use the method of analyzing the quantity of disclosed privacy proposed in [28].Definition 4 (privacy leakage).
For an arbitrary mechanismM, let R index the result of M. b and b′ have only one different input data. π and π′ are the outcome of probability distributions of Mb and Mb′, separately. The privacy leakage of M is the maximum of absolute differences between logarithmic probabilities of the π and π′ for any b and b′:
(32)maxr∈Rlnπr−lnπr′.Theoretically, the parameter of differential privacy mechanismε is the upper bound of the privacy leakage.


### 8.2. Experiment Results and Analysis

In Experiment 1, we verify the performance of competitive auctions. For this case, we assume that the cost of the service is from Weiboyi dataset. As can be seen from Figure2(a), as the number of sellers increases, the profit of both optimal omniscient auction and competitive auction will show an upward trend. In other words, as the market competition increases, the buyer can achieve greater profits.Figure 2
Profit−PAr. (a) Competitive auction profit. (b) Winner ratio.
(a)(b)Similarly, as can be seen from Figure2(b), the change in the number of sellers has an impact on the winner ratio. This shows that the competitive auction mechanism is robust. As can be seen from Figure 2(b), as the number of workers increases, the winner ratio of both optimal omniscient auction and competitive auction will show a downward trend. In other words, as the number of sellers increases, the winner ratio will be less.In the second experiment, we mainly verified the performance of the proposed differential privacy mechanism. The costs of the worker are followed by a discrete distribution over the interval [0.2, 2]. From Figure3(a) as the number of workers increases, the profits show an upward trend, but it is slowly compared with Experiment 1, since the cost of workers is discrete. It can also be seen from Figure 3(a) that the profit of differential privacy mechanism is much lower than the competitive auction, since it is the cost of the privacy protection.Figure 3
Differential privacy mechanism. (a) Differential privacy mechanism profit, (b) impact of differentϵ on profit, and (c) impact of different ϵ on privacy leakage.
(a)(b)(c)In Figure3(b), as the parameter ϵ changes, the profit of differential privacy mechanism also changes. Although the number of sellers is fixed, this change is not obvious due to the randomness of the differential privacy mechanism. However, when the number of sellers increases and the value of ϵ is larger, the profit increases. This is because, with ϵ increases, the differential privacy can choose the higher clearing price with a greater probability; that is, it can achieve greater profit.As we can be seen from Figure3(c), when the parameter ϵ is larger, the privacy leakage will be larger, regardless of the number of sellers. From Figure 3(b), as the value of ϵ increases, the profit of differential privacy mechanism will increase; also the privacy leakage will increase. Therefore, the mechanism designer must make trade-offs between profit and privacy leakage.


## 8.1. Experiment Settings

We conducted two sets of experiments as follows:(1)
Firstly, we mainly verify the performance of theProfit−PAr algorithm, i.e., the competitive ratio to the single-price omniscient optimal auction(2)
Secondly, we demonstrate the performance of the proposed differential privacy mechanism. Also, we also study the sensitivity of parameters and settings to the performance of the mechanism. In addition, the performances of privacy protection are illustrated by analyzing the probability distribution of the results


### 8.1.1. Profit-PA

Numerical experiments are conducted to illustrate the effectiveness of our designed profit-oriented mechanism. Cost information is hard to obtain from the worker directly; thus, we estimated the cost information according to the historical bidding data. In Weiboyi, a user will provide bidding for recommending a product to her friends and a number of friends that the user has. In Weiboyi, bidding contains both price and the number of friends. Thus, we use them to approximately estimate the cost information and capacity of a worker. We obtained over 10000 bidders in Weiboyi. The information of a selected user is shown in Figure1. The cost of a seller is from 0 to 5∗104 and the number of friends is from 0 to 2∗106. We normalize the cost into 0,5 and the number of friends into 0,2. When we select a seller from Weiboyi dataset, we will use the cost and the friends’ number of the seller in Weiboyi to simulate the cost and the friends’ number of a worker in our crowdsourcing platform. We use the following submodular function to measure the buyer’s revenue:
(31)πx=∑i=1x4000−i1000.Figure 1
Costs versus numbers of friends.


### 8.1.2. Differential Privacy Mechanism

The private information of service providers is generated by a uniform distribution with intervals of [1, 10] and [0.2, 2]. Here, the minimum cost per unit of service is 0.2, which is a fixed overhead that is inevitably consumed by providing unit services. For the settings of competitive auctions, the cost is from uniform distribution that is known in advance.In the differential privacy mechanism,ϵ is an adjustable variable. The scope of ε is limited to [0, 1], and experiments are running with values of 0.05, 0.5, and 1, respectively. We will use the method of analyzing the quantity of disclosed privacy proposed in [28].Definition 4 (privacy leakage).
For an arbitrary mechanismM, let R index the result of M. b and b′ have only one different input data. π and π′ are the outcome of probability distributions of Mb and Mb′, separately. The privacy leakage of M is the maximum of absolute differences between logarithmic probabilities of the π and π′ for any b and b′:
(32)maxr∈Rlnπr−lnπr′.Theoretically, the parameter of differential privacy mechanismε is the upper bound of the privacy leakage.


## 8.1.1. Profit-PA

Numerical experiments are conducted to illustrate the effectiveness of our designed profit-oriented mechanism. Cost information is hard to obtain from the worker directly; thus, we estimated the cost information according to the historical bidding data. In Weiboyi, a user will provide bidding for recommending a product to her friends and a number of friends that the user has. In Weiboyi, bidding contains both price and the number of friends. Thus, we use them to approximately estimate the cost information and capacity of a worker. We obtained over 10000 bidders in Weiboyi. The information of a selected user is shown in Figure1. The cost of a seller is from 0 to 5∗104 and the number of friends is from 0 to 2∗106. We normalize the cost into 0,5 and the number of friends into 0,2. When we select a seller from Weiboyi dataset, we will use the cost and the friends’ number of the seller in Weiboyi to simulate the cost and the friends’ number of a worker in our crowdsourcing platform. We use the following submodular function to measure the buyer’s revenue:
(31)πx=∑i=1x4000−i1000.Figure 1
Costs versus numbers of friends.


## 8.1.2. Differential Privacy Mechanism

The private information of service providers is generated by a uniform distribution with intervals of [1, 10] and [0.2, 2]. Here, the minimum cost per unit of service is 0.2, which is a fixed overhead that is inevitably consumed by providing unit services. For the settings of competitive auctions, the cost is from uniform distribution that is known in advance.In the differential privacy mechanism,ϵ is an adjustable variable. The scope of ε is limited to [0, 1], and experiments are running with values of 0.05, 0.5, and 1, respectively. We will use the method of analyzing the quantity of disclosed privacy proposed in [28].Definition 4 (privacy leakage).
For an arbitrary mechanismM, let R index the result of M. b and b′ have only one different input data. π and π′ are the outcome of probability distributions of Mb and Mb′, separately. The privacy leakage of M is the maximum of absolute differences between logarithmic probabilities of the π and π′ for any b and b′:
(32)maxr∈Rlnπr−lnπr′.Theoretically, the parameter of differential privacy mechanismε is the upper bound of the privacy leakage.


## 8.2. Experiment Results and Analysis

In Experiment 1, we verify the performance of competitive auctions. For this case, we assume that the cost of the service is from Weiboyi dataset. As can be seen from Figure2(a), as the number of sellers increases, the profit of both optimal omniscient auction and competitive auction will show an upward trend. In other words, as the market competition increases, the buyer can achieve greater profits.Figure 2
Profit−PAr. (a) Competitive auction profit. (b) Winner ratio.
(a)(b)Similarly, as can be seen from Figure2(b), the change in the number of sellers has an impact on the winner ratio. This shows that the competitive auction mechanism is robust. As can be seen from Figure 2(b), as the number of workers increases, the winner ratio of both optimal omniscient auction and competitive auction will show a downward trend. In other words, as the number of sellers increases, the winner ratio will be less.In the second experiment, we mainly verified the performance of the proposed differential privacy mechanism. The costs of the worker are followed by a discrete distribution over the interval [0.2, 2]. From Figure3(a) as the number of workers increases, the profits show an upward trend, but it is slowly compared with Experiment 1, since the cost of workers is discrete. It can also be seen from Figure 3(a) that the profit of differential privacy mechanism is much lower than the competitive auction, since it is the cost of the privacy protection.Figure 3
Differential privacy mechanism. (a) Differential privacy mechanism profit, (b) impact of differentϵ on profit, and (c) impact of different ϵ on privacy leakage.
(a)(b)(c)In Figure3(b), as the parameter ϵ changes, the profit of differential privacy mechanism also changes. Although the number of sellers is fixed, this change is not obvious due to the randomness of the differential privacy mechanism. However, when the number of sellers increases and the value of ϵ is larger, the profit increases. This is because, with ϵ increases, the differential privacy can choose the higher clearing price with a greater probability; that is, it can achieve greater profit.As we can be seen from Figure3(c), when the parameter ϵ is larger, the privacy leakage will be larger, regardless of the number of sellers. From Figure 3(b), as the value of ϵ increases, the profit of differential privacy mechanism will increase; also the privacy leakage will increase. Therefore, the mechanism designer must make trade-offs between profit and privacy leakage.


## 9. Conclusion

We introduce a profit-oriented mechanism for the crowdsourcing, which is prior-free. Our designed mechanism adopts the framework of profit-extract and random sampling. We show the designed profit-oriented mechanism satisfies the properties of truthfulness, individual rationality, and computation tractability and has a performance lower bound. Through a two-substage sampling, we extended the offline algorithm to the online setting. And we also study the mechanism for our setting with privacy-aware sellers. Simulations are conducted to illustrate the effectiveness of the proposed profit-oriented algorithm.



---

*Source: 8859905-2022-01-22.xml*