# Designing Incentive Mechanisms for Mobile Crowdsensing with Intermediaries

Authors: Yatong Chen; Huangxun Chen; Shuo Yang; Xiaofeng Gao; Yunhe Guo; Fan Wu
Journal: Wireless Communications and Mobile Computing
 (2019)

---

## Abstract

In the past decade, with the rapid development of wireless communication and sensor technology, ubiquitous smartphones equipped with increasingly rich sensors have more powerful computing and sensing abilities. Thus, mobile crowdsensing has received extensive attentions from both industry and academia. Recently, plenty of mobile crowdsensing applications come forth, such as indoor positioning, environment monitoring, and transportation. However, most existing mobile crowdsensing systems lack vast user bases and thus urgently need appropriate incentive mechanisms to attract mobile users to guarantee the service quality. In this paper, we propose to incorporate sensing platform and social network applications, which already have large user bases to build a three-layer network model. Thus, we can publicize the sensing platform promptly in large scale and provide long-term guarantee of data sources. Based on a three-layer network model, we design incentive mechanisms for both intermediaries and the crowdsensing platform and provide a solution to cope with the problem of user overlapping among intermediaries. We theoretically prove the properties of our proposed incentive mechanisms, including incentive compatibility, individual rationality, and efficiency. Furthermore, we evaluate our incentive mechanisms by extensive simulations. Evaluation results validate the effectiveness and efficiency of our proposed mechanisms.


---

## Body

## 1. Introduction

Nowadays smartphones have become indispensable elements for communication and entertainment in our daily lives. The power of smartphone owes greatly to the rapid development of sensor technology. More and more embedded sensors have been integrated into smartphone system, such as GPS, gyroscope, accelerometer, digital compass, microphone, and camera [1, 2]. These sensors provide rich possibilities of smartphone functionality and bring emerging sensing paradigms, which have attracted attentions from both industry and academia.In the past decade, many efforts on system works have been made to dig the potential of sensor-equipped smartphones. The concept of mobile crowdsensing has been applied to many domains. Taking environment monitoring and transportation, for example, there appeared noise monitoring system [3], air pollution monitoring system [4], traffic congestion monitoring [5, 6], parking lots locating [7], and dynamic driving planning [8, 9]. The system works mentioned above effectively tackle the technical matters. However, one of the realistic challenges encountered by the above systems is how to attract enough number of participants and maintain user stickiness in order to guarantee service quality. First, as human-involved applications, the reliability and accuracy of mobile crowdsensing systems are affected by human factors, such as dynamic joining and leaving, inaccurate or even corrupted sensing, and environment changing due to user mobility. Thus, mobile crowdsensing systems rely on a large and active user community to guarantee adequate level of service quality. Second, the large user community should be accessed quickly as soon as possible. Mass-oriented applications like mobile crowdsensing applications all face a difficult cold set-up period and need to gradually gather users and effectively turn them into loyal ones. Applications failing to go through this period would not prevail, even if they are of high quality.Unfortunately, according to [10], nowadays, mobile crowdsensing applications have rarely scaled up to more than 1000 participants. Thus, the key problem we face is (i) how to make mobile crowdsensing application prevalent and (ii) how to shorten the hard cold setup time.Sensing service would bring cost to the smartphone users, including battery power, computing power, and bandwidth. Counting merely on users’ voluntary contributions would impair the users’ loyalty and jeopardize the reliability and validity of the system in the long run. To the best of our knowledge, Lee et al. [11] made the first try to address the incentive mechanism for user participation. They designed an incentive mechanism named Reverse Auction based Dynamic Price (RADP) to minimize the cost, while stabilizing the participation level. Yang et al. [12] considered incentive mechanisms under two system models: the platform-centric model and the user-centric model. Luo et al. [13] proposed an all-pay auction to achieve profit maximization of sensing platform. In the above incentive mechanism, generally there are two roles in the system, including a sensing platform and a number of smartphone users. The sensing platform launches the sensing tasks and provides payments (monetary or nonmonetary) to incentivize smartphone users to perform sensing tasks.The above ubiquitous structure faces three obstacles for mobile crowdsensing applications to scale up. First, it takes a lot of time for the application developers to handle the heterogeneity of software platforms (e.g., Android, iOS, and Windows Phone), and even different versions of each platform. Second, there already appeared many mobile crowdsensing systems. To participate in one of them, a user should install and run the specific application and then directly transmit the sensed data to its central server(s). It is impossible for a smartphone to install all kinds of applications, and thus it can only be accessed by a few applications. Third, the increasing of network bandwidth demand hinders the scale of mobile crowdsensing systems.Our proposed strategy to overcome the defects mentioned above is to let the crowdsensing platform cooperate with existing applications with large user bases, such as Facebook, Instagram, and Flickr. It is quite common for the applications that may have their own APIs to access the devices’ sensor units. Thus, they could act as intermediaries between the mobile sensing platform and a great number of users. With the necessary information provided by the sensing platform, the intermediaries can process sensing data into the format required by some specific crowdsensing application and then send them to the platform.Intermediary applications’ participation changes the existing two-layer network model to a three-layer network model. In the two-layer model, interactions happen only between smartphone users and sensing platform directly. In our proposed model, interactions occur in two places. One is between the intermediary applications and the sensing platform. The other is between every intermediary application and its smartphone user community. For the altering of system model, we must rethink and redesign appropriate incentive mechanisms in mobile crowdsensing systems.Based on our survey of the state-of-the-art literature, this is the first work on designing incentive mechanism for mobile sensing system with intermediaries. The benefits brought by the participation of intermediaries are summarized as follows:(i)
Sensing platforms do not need to be in the face of the heterogeneity of software platforms directly. Dealing with the transmission interfaces under cooperation protocols is much easier than developing different versions for every software platform.(ii)
Intermediaries have established stable trust relationship with their own large and active user community. Their participation could effectively publicize their cooperating partners, i.e., mobile crowdsensing systems among their users, and more likely enlarge user community of mobile sensing systems in a short time as well as in the long run.(iii)
Intermediaries can incentivize “lazy” users as much as possible. “Lazy” user here means the one that has no time or no interest to download specific sensing applications or to learn how to perform the sensing task. There exists considerable quantity of them in practice. With the help of the intermediary applications, “lazy” users could authorize their intermediary to fetch proper sensing tasks, finish them automatically, and get paid. Thus, “lazy” users may have higher motivations to be involved in crowdsensing.However, the participation of intermediaries obviously complicates the system model and brings challenges for both mechanism design and analysis. Here, we summarize the main research challenges as follows.(i)
Both the intermediaries and smartphone users are rational and selfish. They may misreport their costs to improve their utilities. The incentive mechanism should prevent both the intermediaries and smartphone users from strategic misbehaviours, which has not been simultaneously considered in the existing work for mobile crowdsensing.(ii)
Intermediaries’ participation may enlarge the gap between possible solution results and theoretical optimal result, compared with the way of interacting with smartphone users directly. Limiting the gap within an acceptable level but not damaging the truthfulness of the whole mechanism is difficult, but necessary to avoid the situation, in which the costs exceed the benefits.(iii)
The auction between the platform and the intermediaries is a reverse multiunit auction with multisupply. The mathematical formalization of its allocation problem is a variation of knapsack problem, which is a well-known NP-complete problem. Furthermore, our mechanism should meanwhile eliminate the duplication effectively. The users of different popular intermediaries are much likely to overlap, but the platform does not want to receive duplicated data from the same users.The key contributions of our work are summarized as follows.(i)
We are the first to introduce intermediaries to mobile sensing system. We model the system as a three-layer network model and design incentive mechanisms for both intermediary and sensing platform.(ii)
We begin with considering the setting without user overlapping and then further improve our design to be applicable to the setting with user overlapping.(iii)
We theoretically prove the following properties of proposed mechanisms: individual rationality, incentive compatibility, and computational efficiency.(iv)
We evaluate the performance of our mechanisms by extensive simulations. Our evaluation results show that the gap between our mechanisms’ results and theoretical optimal results is small.The rest of the paper is organized as follows. In Section2, we introduce the system model. The detailed mechanism design is elaborated in Section 3. We give formal theoretical proof for the economic properties in Section 4. Section 5 shows the numerical results to verify our design. We summarize related work in Section 6 and conclude this paper in Section 7.


## 2. Technical Preliminaries

In this section, we would like to illustrate our system model and settings and introduce several important concepts from mechanism design domain.


### 2.1. System Model

In this paper, we consider a crowdsensing system as shown in Figure1. There are three main roles in the system, includingsensing platform,intermediaries, andsmartphone users. We model it as a three-layer network.Figure 1
A three-layer network scenario.To be specific, our system consists of one sensing platform, a setI={1,2,…,N} of N intermediaries, and a number of smartphone users. For each intermediary i∈I, there are Ni smartphone users associated with it. Let uji denote the j-th user of intermediary i. We note that the users of different intermediaries can overlap, which is revealed in Figure 1.To address the problem of users’ overlapping, we assume that intermediaries could access the smartphones’ unique device ID. According to our survey, IMEI number is a very good and primary source to get the device ID. It is dependent on the device hardware; thus it is unique for every device. Besides, it is permanent till the lifetime of the device even if the device is rooted or factory reset. The applications require the permission to get the device IMEI. Also, there are some alternatives to device IMEI, such as the WLAN MAC address string and the Bluetooth Address string, each of which has its own advantages and disadvantages. However, the details of the choice of device identifier are not within the scope of this paper.When the sensing platform receives a task, denoted asT(D,M), from platform users, it can recruit a team of intermediaries, initialize an auction to collect needed data, and then send the analyzed result back to the platform users. M denotes the number of data items needed. D contains data specifications, including data location and sensing time. In this work, we have not taken the budget of the sensing platform into consideration yet. The characterization of the tradeoff between the budget and the percentage of completed tasks is one of our main future researches.The platform collects data from multiple intermediaries. Every intermediary may provide multiple available pieces of data. Thus, the auction between platform and intermediaries is areverse multiunit (the platform buys multiple copies of data from multiple intermediaries) auction withmultisupply (each intermediary can provide multiple pieces of data for the platform).When the platform conducts an auction and announces the mechanismM, each intermediary Ii would conduct acontingent downstream auction to calculate a bid strategy profile βi based on her Ni available users’ bids. Every smartphone user can only provide one piece of data, (i.e., it is meaningless for one smartphone user to provide duplicated data for the same task). Thus, the auction between an intermediary and her smartphone users is areverse multiunit (an intermediary collects multiple data from multiple smartphone users) auction withunit-supply (a smartphone user can only provide a piece of data)Besides the bidding strategyβi, every intermediary Ii∈I should also submit a list of user IDs li=(idji)j∈Wi. The content in the user ID list is decided according to thecontingent downstream auction’s outcome.For a given bidding profileB=(β1,…,βi,…,βN) from the intermediaries, the mechanism M(B) determines a participation level vector χ(B)=(x1,…,xi,…,xN) and payment vector ρ(B)=(p1,…,pi,…,pN), where xi means the number of pieces of data selected from intermediary Ii and pi means the payment to intermediary Ii. Next, the platform announces to each intermediary its participation level xi and payment pi. Based on the upstream auction’s outcome, intermediaries submit data collected from their users to the platform and accordingly get paid by the platform.Every smartphone useruji is characterized by a perceived cost cji>0 per piece of data contributed. The cost is private information of each user, as it depends on various factors inherent to the device and the user. In our mechanism, every user would submit a bid bji to its intermediary. The bid bji can be interpreted as user uji’s minimum requested compensation per piece of data contribution. Here, bji may not equal cji unless truthfulness can be achieved in the auction. The payment pji to user uji is determined by the intermediary Ii she belongs to.The utility of a smartphone user is defined as the difference between the payment from the corresponding intermediary and the cost induced by performing the sensing task. We can define the utility foruji as(1)Uji=pji-cji,ifujiisawinner;0,otherwise.The utilityUi of an intermediary is defined as the difference between the payment from the platform and the prices paid in downstream auction. (2)Ui=pi-∑j∈Mipji.The objective of this work is to design a truthful mechanism under the following constraints:(1)
The platform must collect at leastM pieces of data.(2)
The platform must solve the problem of user overlapping; i.e., every piece of collected data comes from a distinguished smartphone.(3)
Ex-post Budget Balance: the utility of each intermediaryUi≥0,(i=1,2,…,N).(4)
Individual rationality: the utility of each smartphone userUji≥0,(i=1,2,…,N;j=1,2,…,Ni).Here, we briefly review some important solution concepts and economic properties we would like to achieve in our mechanism.Definition 1 (dominant strategy [14]).
A dominant strategy of a player is one that maximizes her utility regardless of what strategies the other players choose. Specifically,ai is player i’s dominant strategy if, for any ai′≠ai and any strategy profile of the other players a-i, ui(ai,a-i)≥ui(ai′,a-i).Definition 2 (truthfulness/incentive compatibility [15]).
A mechanism(f,p) is truthful/incentive compatible if, for every player i with true valuation vi, vi(f(vi,v-i))-p(vi,v-i)≥vi(f(vi′,v-i))-p(vi′,v-i). Intuitively, player i would prefer to tell the true valuation vi rather than giving a cheating one vi′ to get a higher utility.Definition 3 (individual-rationality [16]).
An auction is individual rational if no buyer is charged more than her bid and no seller is paid less than her ask. It means that each player can always achieve at least as much expected utility from faithful participation as without participation, which guarantees the validness of the auction result.For readers’ convenience in later sections, we list key notations in Table1.Table 1
Key notations in this paper.
Sym Meaning Sym Meaning P The sensing platform I The set of all intermediaries I i Thei-th intermediary N The number of intermediaries N i Number ofIi’ smartphones uji j-th user of i-th intermediary T Task launched by platform M The number of data needed D The data specification M ( B ) Platform mechanism χ ( B ) platform allocation scheme x i I i’ participation level ρ ( B ) platform payment scheme p i payment toIi β i I i’ bidding strategy l i I i’ sorted smartphone ID list i d j i j-th id in li p j i payment touji c j i u j i’ true cost per data b j i u j i’ bid U i I i’ utility U j i u j i’ utility


## 2.1. System Model

In this paper, we consider a crowdsensing system as shown in Figure1. There are three main roles in the system, includingsensing platform,intermediaries, andsmartphone users. We model it as a three-layer network.Figure 1
A three-layer network scenario.To be specific, our system consists of one sensing platform, a setI={1,2,…,N} of N intermediaries, and a number of smartphone users. For each intermediary i∈I, there are Ni smartphone users associated with it. Let uji denote the j-th user of intermediary i. We note that the users of different intermediaries can overlap, which is revealed in Figure 1.To address the problem of users’ overlapping, we assume that intermediaries could access the smartphones’ unique device ID. According to our survey, IMEI number is a very good and primary source to get the device ID. It is dependent on the device hardware; thus it is unique for every device. Besides, it is permanent till the lifetime of the device even if the device is rooted or factory reset. The applications require the permission to get the device IMEI. Also, there are some alternatives to device IMEI, such as the WLAN MAC address string and the Bluetooth Address string, each of which has its own advantages and disadvantages. However, the details of the choice of device identifier are not within the scope of this paper.When the sensing platform receives a task, denoted asT(D,M), from platform users, it can recruit a team of intermediaries, initialize an auction to collect needed data, and then send the analyzed result back to the platform users. M denotes the number of data items needed. D contains data specifications, including data location and sensing time. In this work, we have not taken the budget of the sensing platform into consideration yet. The characterization of the tradeoff between the budget and the percentage of completed tasks is one of our main future researches.The platform collects data from multiple intermediaries. Every intermediary may provide multiple available pieces of data. Thus, the auction between platform and intermediaries is areverse multiunit (the platform buys multiple copies of data from multiple intermediaries) auction withmultisupply (each intermediary can provide multiple pieces of data for the platform).When the platform conducts an auction and announces the mechanismM, each intermediary Ii would conduct acontingent downstream auction to calculate a bid strategy profile βi based on her Ni available users’ bids. Every smartphone user can only provide one piece of data, (i.e., it is meaningless for one smartphone user to provide duplicated data for the same task). Thus, the auction between an intermediary and her smartphone users is areverse multiunit (an intermediary collects multiple data from multiple smartphone users) auction withunit-supply (a smartphone user can only provide a piece of data)Besides the bidding strategyβi, every intermediary Ii∈I should also submit a list of user IDs li=(idji)j∈Wi. The content in the user ID list is decided according to thecontingent downstream auction’s outcome.For a given bidding profileB=(β1,…,βi,…,βN) from the intermediaries, the mechanism M(B) determines a participation level vector χ(B)=(x1,…,xi,…,xN) and payment vector ρ(B)=(p1,…,pi,…,pN), where xi means the number of pieces of data selected from intermediary Ii and pi means the payment to intermediary Ii. Next, the platform announces to each intermediary its participation level xi and payment pi. Based on the upstream auction’s outcome, intermediaries submit data collected from their users to the platform and accordingly get paid by the platform.Every smartphone useruji is characterized by a perceived cost cji>0 per piece of data contributed. The cost is private information of each user, as it depends on various factors inherent to the device and the user. In our mechanism, every user would submit a bid bji to its intermediary. The bid bji can be interpreted as user uji’s minimum requested compensation per piece of data contribution. Here, bji may not equal cji unless truthfulness can be achieved in the auction. The payment pji to user uji is determined by the intermediary Ii she belongs to.The utility of a smartphone user is defined as the difference between the payment from the corresponding intermediary and the cost induced by performing the sensing task. We can define the utility foruji as(1)Uji=pji-cji,ifujiisawinner;0,otherwise.The utilityUi of an intermediary is defined as the difference between the payment from the platform and the prices paid in downstream auction. (2)Ui=pi-∑j∈Mipji.The objective of this work is to design a truthful mechanism under the following constraints:(1)
The platform must collect at leastM pieces of data.(2)
The platform must solve the problem of user overlapping; i.e., every piece of collected data comes from a distinguished smartphone.(3)
Ex-post Budget Balance: the utility of each intermediaryUi≥0,(i=1,2,…,N).(4)
Individual rationality: the utility of each smartphone userUji≥0,(i=1,2,…,N;j=1,2,…,Ni).Here, we briefly review some important solution concepts and economic properties we would like to achieve in our mechanism.Definition 1 (dominant strategy [14]).
A dominant strategy of a player is one that maximizes her utility regardless of what strategies the other players choose. Specifically,ai is player i’s dominant strategy if, for any ai′≠ai and any strategy profile of the other players a-i, ui(ai,a-i)≥ui(ai′,a-i).Definition 2 (truthfulness/incentive compatibility [15]).
A mechanism(f,p) is truthful/incentive compatible if, for every player i with true valuation vi, vi(f(vi,v-i))-p(vi,v-i)≥vi(f(vi′,v-i))-p(vi′,v-i). Intuitively, player i would prefer to tell the true valuation vi rather than giving a cheating one vi′ to get a higher utility.Definition 3 (individual-rationality [16]).
An auction is individual rational if no buyer is charged more than her bid and no seller is paid less than her ask. It means that each player can always achieve at least as much expected utility from faithful participation as without participation, which guarantees the validness of the auction result.For readers’ convenience in later sections, we list key notations in Table1.Table 1
Key notations in this paper.
Sym Meaning Sym Meaning P The sensing platform I The set of all intermediaries I i Thei-th intermediary N The number of intermediaries N i Number ofIi’ smartphones uji j-th user of i-th intermediary T Task launched by platform M The number of data needed D The data specification M ( B ) Platform mechanism χ ( B ) platform allocation scheme x i I i’ participation level ρ ( B ) platform payment scheme p i payment toIi β i I i’ bidding strategy l i I i’ sorted smartphone ID list i d j i j-th id in li p j i payment touji c j i u j i’ true cost per data b j i u j i’ bid U i I i’ utility U j i u j i’ utility


## 3. Auction-Based Incentive Mechanism Design

In this section, we present our auction-based incentive mechanism design in detail. To facilitate readers’ understanding, we would clarify the algorithms used and details of our design for intermediary (Section3.1) and platform (Sections 3.2 and 3.3) at first. Then we prove theoretically the properties our mechanism achieved in Section 4.


### 3.1. Design of Intermediary Mechanism

As mentioned above, the auction between every intermediaryIi∈I and its smartphone users uji∈Wi is areverse multiunit auction withunit-supply.Upon the platform’s announcing of the taskT(D,M) and mechanism M, each intermediary Ii first finds out the smartphones who can provide the qualified data according to the data specification D and then conduct acontingent downstream auction to calculate her bid strategy βi(k)(k=1,2,…,min⁡(Ni,M)), in which βi(k) represents the average bid for k pieces of data. Every contingent downstream auction follows the same principle; i.e., to select k winners, the intermediary Ii sorts bji(j=1,2,…,Ni) in increasing order, and the selected first k users are winners, with a payment to each equalling to the (k+1)-th bid, which is calledGeneralized Secondary Price Auction. Thus, the kth item in the strategy profile is βi(k)=bk+1i,i.e., the (k+1)-th smallest bid.Generally, the intermediaries always operate to maintain their own services and could also leverage existing optimization algorithms to reduce the overhead of data collection and transmission. Thus, we here consider that the main cost for an intermediary to complete sensing tasks comes from the payment to the smartphones users.


### 3.2. Platform Mechanism Design without User Overlapping

In this section, we first consider a simple setting without the problem of user overlapping and then improve our mechanism to deal with it.


#### 3.2.1. Overview

Upon receiving a sensing taskT(D,M) from platform users, the platform conducts an auction to complete the task. As mentioned before, the auction between platform and intermediaries is amultiunit reverse auction withmulti-unit supply. Given a bidding profile of intermediaries B=(β1,…,βi,⋯βN), the mechanism M(B) consists of computing a participation level vector χ(B)=(x1,…,xi,…,xN), and payment vector ρ(B)=(p1,…,pi,…,pN) for each intermediary.


#### 3.2.2. Allocation Scheme

GivenB=(β1,…,βi,…,βN) without user overlapping, the allocation problem of multiunit reverse auction between the platform and the intermediaries could be characterized as the following optimization problem. Here, Xk,i=1 iff Ii’s participation level xi=k; otherwise, Xk,i=0.(3)Obiectivemin∑i∈I∑k=1minM,NiβikXk,i(4)Subjectto∑i∈I∑k=1minM,NikXk,i≥M(5)∑k=1minM,NiXk,i≤1,∀i∈I(6)Xk,i∈0,1,∀i∈I,1≤k≤min⁡M,NiWithout user overlapping, data items offered from different intermediaries would come from different data sources. According to the intermediary mechanism above, different data item options provided by the same intermediary have part of the same data sources. Data item options from the same intermediary could be regarded as a group, and thus at most one option in each group could be chosen. We note that the problem formulated above can be reduced to the grouping knapsack problem, which is a well-known NP complete problem.Efficient solutions ask for more insights into bidding strategies’ structure. Thus, before conducting allocation, we would process raw bids to satisfy a tailored supermodular property. The traditional definition of supermodular is as follows:V:R+→R+ is supermodular if V(x+1)-V(x)≤V(y+1)-V(y)∀x≤y. The profiles of bidding strategies computed by the above Generalized Secondary Price Auction do not guarantee satisfying the supermodular property. Therefore, we give a tailored supermodular definition for our proposed mechanism.Definition 4 (tailored supermodular).
V ( k ) satisfies tailored supermodular if ∃a monotone increasing nature number sequence (x1,x2,…,xn), assume x0=0 and V(0)=0, and then (Vxi+1-Vxi)/(xi+1-xi)≤(Vxk+1-Vxk)/(xk+1-xk) for ∀i≤k (k=1,2,…,N).We now give the way (Algorithm1) for processing the bidding strategy βi(i∈I) to match the tailored supermodular fashion.Algorithm 1:Intermediary Ii’ bidding preprocessing.
Input: The raw bidding strategy of Ii: β i ( k ) ( k = 1,2 , . . , min ⁡ ( M , N i ) ), Sorted ID list li={idi1,⋯,idimin⁡(M,Ni)}; Output: The processed bidding strategy of Ii: β i = { P i j = ( p j , q j , S j ) } , j = 1,2 , ⋯ , min ⁡ ( M , N i ) 1 Calculate the k-th data’s marginal cost: M C i k = β i ( k ) × k - β i ( k - 1 ) × ( k - 1 ); 2 Initialize the output: Pij=pj,qj,Sj= ( M C i j , 1 , { i d i j } ) , j = 1,2 , ⋯ , min ⁡ ( M , N i ); 3 x←1,y←2,flag←false; 4 while!flagdo 5flag←true; 6 whiley≤length(βi)do 7 ifpx>pythen 8 merge Piy into Pix: p x × q x + p y × q y q x + q y , q x + q y , S x ∪ S y; 9 flag←false; 10else 11x←y,y←y+1; 12return β i = { P i j = ( p j , q j , S j ) } , j = 1,2 , ⋯ , min ⁡ ( M , N i );Here, we give a toy example to illustrate the key idea of Algorithm1.Figure2 shows five smartphone users denoted by different colored circles belonging to one intermediary along with their own bids. In the first pass, we execute Generalized Secondary Price Auction to get the raw bidding strategy βi (1×2=2, 2×7=14, 3×8=24, 4×9=36). In the second pass, we calculate the marginal cost of every data according to formula in Line 1 in Algorithm 1 (2-0=2,14-2=12,24-14=10,36-24=12). In Algorithm 1, Pij=(pj,qj,Sj) means the average marginal cost for the next qj data is pj with their IDs in set Sj. In the final pass, we scan the marginal cost list one by one (Line 4 to Line 11). We find that the second item “12” is larger than the third item “10”; thus we merge them together (Line 8) ((12+10)/(1+1)=11,1+1=2). After the above procedure, the final bidding strategy βi is monotone increasing by the value of the item’s first component (2≤11≤12). The nice marginal increasing property of processed bidding strategies greatly facilitates the platform mechanism design which we would expatiate on later.Figure 2
A toy example of bidding preprocessing.Given the tailored supermodular property held by processed intermediaries’ bidding strategy, the winner determinationχ(B) is shown in Algorithm 2.Algorithm 2:Allocation scheme χ(B).
Input: Task T(D,M); Intermediaries’ biddings B={βi},i=1,2,⋯,N: P i j = ( p j , q j , S j ) denotes the j-th bidding in βi Output: Intermediaries’ participation level vector χ ( B ) = { x i } , i = 1,2 , ⋯ , N 1 Scandi←∅,Sfinal←∅,num←0; 2 xi←0,∀i=1,2,⋯,N; 3 Add the first item of every intermediary’s bidding into Scandi; 4 whilenum<Mdo 5 Choose the item P= (p, q, S) with the smallest p in S c a n d i, assume denoted as Pst=(pt,qt,St); 6Sfinal←Sfinal∪{St}; 7xs←xs+qt; 8 num←num+qt; 9 add the next item in bidding βs to the Scandi; 10return  Intermediaries’ participation level vector χ ( B ) = { x i } , i = 1,2 , ⋯ , NThe idea behind Algorithm2 is as follows. In each step, the first unchosen item in every intermediary would form the candidate set (Line 3 and Line 9). The platform keeps choosing the bid item with the smallest p component in candidate set until the number of effective data units in chosen set exceeds M (Lines 4 to 9).To help illustrate the main idea of Algorithm2 intuitively, we give the following toy example (see Figure 3). In this specific setting, there are two intermediaries, I1 and I2. Their smartphone users are denoted by different colored circles in Figure 3. Each item of their biddings has three components: bid per data, data quantity, and effective data provider set (Pkji=(p,q,S)). The candidate set (Scandi) contains data packages that are likely to be chosen in the next step while the chosen set (Sfinal) consists of data packages that have already been chosen. M indicates the number of data units needed at least. Initially, we group the first item of every intermediary’s bidding into the candidate set (Line 3). When the number of effective data units in chosen set has not exceeded M, we should keep choosing operation among the candidate set. In every step, the item which has the smallest p component would leave the candidate set for the chosen set (Line 6). Meanwhile, the chosen item’s corresponding intermediary would contribute the next item to the candidate set (Line 9) and its participation level would be updated (Line 7).Figure 3
A toy example of winner determination.


#### 3.2.3. Partial Uniform Payment Scheme

The platform’s payment schemeρ(B) is shown in Algorithm 3. In partial uniform payment scheme, a winning intermediary would be paid the same amount of money for each data contribution. Its unit reward is determined by the other’s lowest losing bid. Different intermediaries can have different unit rewards. Taking the scenario in Figure 3, for example, intermediary I1 would be paid the lowest losing bid of intermediary I2 per unit of data (p1=12×3=36), while intermediary I2 would be paid the lowest losing bid of the intermediary I1 per unit of data (p2=12×1=12).Algorithm 3:Payment scheme ρ(B).
Input: Intermediaries’ biddings: B={βi},i=1,2,⋯,N; Participation vector χ(B)={xi},i=1,2,...,N Output: Intermediaries’ payment: ρ ( B ) = { p i } , i = 1,2 , ⋯ , N // Find the smallest losing bids of each intermediary and stores in an array minLoserBid; 1fori=1:Ndo 2minLoserBid(i) = the smallest losing bid of intermediary i; 3 Find the two smallest ones from minLoserBid, denoted as s1,s2(s1≤s2); 4fori=1:Ndo 5ifminLoserBid(i)==s1then 6pi←s2×xi; 7else 8pi←s1×xi; 9return payment vector ρ(B)={pi},i=1,2,⋯,N;


### 3.3. Duplication Elimination

In this section, we deal with the problem of user overlapping mentioned in Section2.1 in order to improve the mechanism design in Section 3.2.Given the bidding profile of intermediariesB=(β1,…,βi,…,βN), our duplication elimination would be conducted before bidding preprocessing (Algorithm 1) and contains two steps: duplication identification and bid adjustment.We design Algorithm4 for duplication identification. The main idea of Algorithm 4 is as follows. First, according to all intermediaries’ bidding profile, we construct 3-tuples for every item in every intermediary’s sorted ID list, composed of an ID number, the corresponding intermediary, and the ID location in the intermediary (Line 1). We assume ID numbers here are all integer and sort all tuples by the ID value in increasing order (Line 2). Here, tuples with the same ID number are adjacent in tuple array (Arr). Then with the help of two scanning cursors (x and y) in tandem, we find out all duplication ID numbers including the intermediary and corresponding location they appear (Dup) (Line 3 to Line 11).Algorithm 4:Duplication identification.
Input: All intermediaries’ sorted ID lists {li},i=1,2,⋯,N; Output: Duplication ID Set D u p : { ( i d , { ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯ } ) , ⋯ }; 1 Build 3-tuple (id,i,j) for every item in l i   i = 1,2 , ⋯ , N: (id, i, j) denotes the number id user is j-th user in intermediary i; 2 Put all 3-tuple (id, i, j) in one array Arr and sort it by the id field in increasing order; 3 x←0,y←1,Dup←∅; 4 whiley<len(Arr)do 5 ifArr[x].id==Arr[y].idthen 6 if!Dup.contain(id)) then 7Dup.Add((id,{(Arr[x].i,Arr[x].j), ( A r r [ y ] . i , A r r [ y ] . j ) } ) ); 8else 9 Dup[id].append((Arr[y].i,Arr[y].j)); 10y←y+1; 11else 12x←y,y←y+1; 13return Duplication ID Set Dup;After finding out the set of duplicated user IDs, we propose two policies to eliminate duplication.(i) KickOut: in the platform view, overlap behaviours are discouraged because they would bring about computation overhead to eliminate their effect. Thus, kicking out the repeated users directly and notifying the intermediaries of repetition message along with trading result could be a reasonable punishment to restrain overlap behaviours and reduce possible user overlap in the long term.(ii) Assign: considering some overlap behaviours are unintentional and KickOut policy may waste valuable data sources, another alternative is to delay the punishment and assign each repeated user to an intermediary. The assignment rules are as follows: if we could infer that the user submits different bids in different intermediaries, assign it to the intermediary with the smallest bid; otherwise, assign it randomly to an intermediary. The way of inferring the users’ bid could be regarded as the reverse process of Generalized Secondary Price Auction. If there is a tuple (id, i, j), the user id bid in intermediary i is βi(j-1) (average bid for j-1 pieces of winning data task of Ii).Following KickOut policy or Assign policy, the previous intermediary biddingB=(β1,…,βi,…,βN) needs adjustment. Assuming tuple (id, i, j) denotes that the i-th intermediary does not get the user id, the bidding strategy βi should be adjusted in the following way: βi(j-1)←βi(j),βi(j)←βi(j+1),⋯ until the end of bidding.After duplication identification and bidding adjustment, we could continue conducting mechanism design in Section3.2 including bidding preprocess, allocation, and payment.


## 3.1. Design of Intermediary Mechanism

As mentioned above, the auction between every intermediaryIi∈I and its smartphone users uji∈Wi is areverse multiunit auction withunit-supply.Upon the platform’s announcing of the taskT(D,M) and mechanism M, each intermediary Ii first finds out the smartphones who can provide the qualified data according to the data specification D and then conduct acontingent downstream auction to calculate her bid strategy βi(k)(k=1,2,…,min⁡(Ni,M)), in which βi(k) represents the average bid for k pieces of data. Every contingent downstream auction follows the same principle; i.e., to select k winners, the intermediary Ii sorts bji(j=1,2,…,Ni) in increasing order, and the selected first k users are winners, with a payment to each equalling to the (k+1)-th bid, which is calledGeneralized Secondary Price Auction. Thus, the kth item in the strategy profile is βi(k)=bk+1i,i.e., the (k+1)-th smallest bid.Generally, the intermediaries always operate to maintain their own services and could also leverage existing optimization algorithms to reduce the overhead of data collection and transmission. Thus, we here consider that the main cost for an intermediary to complete sensing tasks comes from the payment to the smartphones users.


## 3.2. Platform Mechanism Design without User Overlapping

In this section, we first consider a simple setting without the problem of user overlapping and then improve our mechanism to deal with it.


### 3.2.1. Overview

Upon receiving a sensing taskT(D,M) from platform users, the platform conducts an auction to complete the task. As mentioned before, the auction between platform and intermediaries is amultiunit reverse auction withmulti-unit supply. Given a bidding profile of intermediaries B=(β1,…,βi,⋯βN), the mechanism M(B) consists of computing a participation level vector χ(B)=(x1,…,xi,…,xN), and payment vector ρ(B)=(p1,…,pi,…,pN) for each intermediary.


### 3.2.2. Allocation Scheme

GivenB=(β1,…,βi,…,βN) without user overlapping, the allocation problem of multiunit reverse auction between the platform and the intermediaries could be characterized as the following optimization problem. Here, Xk,i=1 iff Ii’s participation level xi=k; otherwise, Xk,i=0.(3)Obiectivemin∑i∈I∑k=1minM,NiβikXk,i(4)Subjectto∑i∈I∑k=1minM,NikXk,i≥M(5)∑k=1minM,NiXk,i≤1,∀i∈I(6)Xk,i∈0,1,∀i∈I,1≤k≤min⁡M,NiWithout user overlapping, data items offered from different intermediaries would come from different data sources. According to the intermediary mechanism above, different data item options provided by the same intermediary have part of the same data sources. Data item options from the same intermediary could be regarded as a group, and thus at most one option in each group could be chosen. We note that the problem formulated above can be reduced to the grouping knapsack problem, which is a well-known NP complete problem.Efficient solutions ask for more insights into bidding strategies’ structure. Thus, before conducting allocation, we would process raw bids to satisfy a tailored supermodular property. The traditional definition of supermodular is as follows:V:R+→R+ is supermodular if V(x+1)-V(x)≤V(y+1)-V(y)∀x≤y. The profiles of bidding strategies computed by the above Generalized Secondary Price Auction do not guarantee satisfying the supermodular property. Therefore, we give a tailored supermodular definition for our proposed mechanism.Definition 4 (tailored supermodular).
V ( k ) satisfies tailored supermodular if ∃a monotone increasing nature number sequence (x1,x2,…,xn), assume x0=0 and V(0)=0, and then (Vxi+1-Vxi)/(xi+1-xi)≤(Vxk+1-Vxk)/(xk+1-xk) for ∀i≤k (k=1,2,…,N).We now give the way (Algorithm1) for processing the bidding strategy βi(i∈I) to match the tailored supermodular fashion.Algorithm 1:Intermediary Ii’ bidding preprocessing.
Input: The raw bidding strategy of Ii: β i ( k ) ( k = 1,2 , . . , min ⁡ ( M , N i ) ), Sorted ID list li={idi1,⋯,idimin⁡(M,Ni)}; Output: The processed bidding strategy of Ii: β i = { P i j = ( p j , q j , S j ) } , j = 1,2 , ⋯ , min ⁡ ( M , N i ) 1 Calculate the k-th data’s marginal cost: M C i k = β i ( k ) × k - β i ( k - 1 ) × ( k - 1 ); 2 Initialize the output: Pij=pj,qj,Sj= ( M C i j , 1 , { i d i j } ) , j = 1,2 , ⋯ , min ⁡ ( M , N i ); 3 x←1,y←2,flag←false; 4 while!flagdo 5flag←true; 6 whiley≤length(βi)do 7 ifpx>pythen 8 merge Piy into Pix: p x × q x + p y × q y q x + q y , q x + q y , S x ∪ S y; 9 flag←false; 10else 11x←y,y←y+1; 12return β i = { P i j = ( p j , q j , S j ) } , j = 1,2 , ⋯ , min ⁡ ( M , N i );Here, we give a toy example to illustrate the key idea of Algorithm1.Figure2 shows five smartphone users denoted by different colored circles belonging to one intermediary along with their own bids. In the first pass, we execute Generalized Secondary Price Auction to get the raw bidding strategy βi (1×2=2, 2×7=14, 3×8=24, 4×9=36). In the second pass, we calculate the marginal cost of every data according to formula in Line 1 in Algorithm 1 (2-0=2,14-2=12,24-14=10,36-24=12). In Algorithm 1, Pij=(pj,qj,Sj) means the average marginal cost for the next qj data is pj with their IDs in set Sj. In the final pass, we scan the marginal cost list one by one (Line 4 to Line 11). We find that the second item “12” is larger than the third item “10”; thus we merge them together (Line 8) ((12+10)/(1+1)=11,1+1=2). After the above procedure, the final bidding strategy βi is monotone increasing by the value of the item’s first component (2≤11≤12). The nice marginal increasing property of processed bidding strategies greatly facilitates the platform mechanism design which we would expatiate on later.Figure 2
A toy example of bidding preprocessing.Given the tailored supermodular property held by processed intermediaries’ bidding strategy, the winner determinationχ(B) is shown in Algorithm 2.Algorithm 2:Allocation scheme χ(B).
Input: Task T(D,M); Intermediaries’ biddings B={βi},i=1,2,⋯,N: P i j = ( p j , q j , S j ) denotes the j-th bidding in βi Output: Intermediaries’ participation level vector χ ( B ) = { x i } , i = 1,2 , ⋯ , N 1 Scandi←∅,Sfinal←∅,num←0; 2 xi←0,∀i=1,2,⋯,N; 3 Add the first item of every intermediary’s bidding into Scandi; 4 whilenum<Mdo 5 Choose the item P= (p, q, S) with the smallest p in S c a n d i, assume denoted as Pst=(pt,qt,St); 6Sfinal←Sfinal∪{St}; 7xs←xs+qt; 8 num←num+qt; 9 add the next item in bidding βs to the Scandi; 10return  Intermediaries’ participation level vector χ ( B ) = { x i } , i = 1,2 , ⋯ , NThe idea behind Algorithm2 is as follows. In each step, the first unchosen item in every intermediary would form the candidate set (Line 3 and Line 9). The platform keeps choosing the bid item with the smallest p component in candidate set until the number of effective data units in chosen set exceeds M (Lines 4 to 9).To help illustrate the main idea of Algorithm2 intuitively, we give the following toy example (see Figure 3). In this specific setting, there are two intermediaries, I1 and I2. Their smartphone users are denoted by different colored circles in Figure 3. Each item of their biddings has three components: bid per data, data quantity, and effective data provider set (Pkji=(p,q,S)). The candidate set (Scandi) contains data packages that are likely to be chosen in the next step while the chosen set (Sfinal) consists of data packages that have already been chosen. M indicates the number of data units needed at least. Initially, we group the first item of every intermediary’s bidding into the candidate set (Line 3). When the number of effective data units in chosen set has not exceeded M, we should keep choosing operation among the candidate set. In every step, the item which has the smallest p component would leave the candidate set for the chosen set (Line 6). Meanwhile, the chosen item’s corresponding intermediary would contribute the next item to the candidate set (Line 9) and its participation level would be updated (Line 7).Figure 3
A toy example of winner determination.


### 3.2.3. Partial Uniform Payment Scheme

The platform’s payment schemeρ(B) is shown in Algorithm 3. In partial uniform payment scheme, a winning intermediary would be paid the same amount of money for each data contribution. Its unit reward is determined by the other’s lowest losing bid. Different intermediaries can have different unit rewards. Taking the scenario in Figure 3, for example, intermediary I1 would be paid the lowest losing bid of intermediary I2 per unit of data (p1=12×3=36), while intermediary I2 would be paid the lowest losing bid of the intermediary I1 per unit of data (p2=12×1=12).Algorithm 3:Payment scheme ρ(B).
Input: Intermediaries’ biddings: B={βi},i=1,2,⋯,N; Participation vector χ(B)={xi},i=1,2,...,N Output: Intermediaries’ payment: ρ ( B ) = { p i } , i = 1,2 , ⋯ , N // Find the smallest losing bids of each intermediary and stores in an array minLoserBid; 1fori=1:Ndo 2minLoserBid(i) = the smallest losing bid of intermediary i; 3 Find the two smallest ones from minLoserBid, denoted as s1,s2(s1≤s2); 4fori=1:Ndo 5ifminLoserBid(i)==s1then 6pi←s2×xi; 7else 8pi←s1×xi; 9return payment vector ρ(B)={pi},i=1,2,⋯,N;


## 3.2.1. Overview

Upon receiving a sensing taskT(D,M) from platform users, the platform conducts an auction to complete the task. As mentioned before, the auction between platform and intermediaries is amultiunit reverse auction withmulti-unit supply. Given a bidding profile of intermediaries B=(β1,…,βi,⋯βN), the mechanism M(B) consists of computing a participation level vector χ(B)=(x1,…,xi,…,xN), and payment vector ρ(B)=(p1,…,pi,…,pN) for each intermediary.


## 3.2.2. Allocation Scheme

GivenB=(β1,…,βi,…,βN) without user overlapping, the allocation problem of multiunit reverse auction between the platform and the intermediaries could be characterized as the following optimization problem. Here, Xk,i=1 iff Ii’s participation level xi=k; otherwise, Xk,i=0.(3)Obiectivemin∑i∈I∑k=1minM,NiβikXk,i(4)Subjectto∑i∈I∑k=1minM,NikXk,i≥M(5)∑k=1minM,NiXk,i≤1,∀i∈I(6)Xk,i∈0,1,∀i∈I,1≤k≤min⁡M,NiWithout user overlapping, data items offered from different intermediaries would come from different data sources. According to the intermediary mechanism above, different data item options provided by the same intermediary have part of the same data sources. Data item options from the same intermediary could be regarded as a group, and thus at most one option in each group could be chosen. We note that the problem formulated above can be reduced to the grouping knapsack problem, which is a well-known NP complete problem.Efficient solutions ask for more insights into bidding strategies’ structure. Thus, before conducting allocation, we would process raw bids to satisfy a tailored supermodular property. The traditional definition of supermodular is as follows:V:R+→R+ is supermodular if V(x+1)-V(x)≤V(y+1)-V(y)∀x≤y. The profiles of bidding strategies computed by the above Generalized Secondary Price Auction do not guarantee satisfying the supermodular property. Therefore, we give a tailored supermodular definition for our proposed mechanism.Definition 4 (tailored supermodular).
V ( k ) satisfies tailored supermodular if ∃a monotone increasing nature number sequence (x1,x2,…,xn), assume x0=0 and V(0)=0, and then (Vxi+1-Vxi)/(xi+1-xi)≤(Vxk+1-Vxk)/(xk+1-xk) for ∀i≤k (k=1,2,…,N).We now give the way (Algorithm1) for processing the bidding strategy βi(i∈I) to match the tailored supermodular fashion.Algorithm 1:Intermediary Ii’ bidding preprocessing.
Input: The raw bidding strategy of Ii: β i ( k ) ( k = 1,2 , . . , min ⁡ ( M , N i ) ), Sorted ID list li={idi1,⋯,idimin⁡(M,Ni)}; Output: The processed bidding strategy of Ii: β i = { P i j = ( p j , q j , S j ) } , j = 1,2 , ⋯ , min ⁡ ( M , N i ) 1 Calculate the k-th data’s marginal cost: M C i k = β i ( k ) × k - β i ( k - 1 ) × ( k - 1 ); 2 Initialize the output: Pij=pj,qj,Sj= ( M C i j , 1 , { i d i j } ) , j = 1,2 , ⋯ , min ⁡ ( M , N i ); 3 x←1,y←2,flag←false; 4 while!flagdo 5flag←true; 6 whiley≤length(βi)do 7 ifpx>pythen 8 merge Piy into Pix: p x × q x + p y × q y q x + q y , q x + q y , S x ∪ S y; 9 flag←false; 10else 11x←y,y←y+1; 12return β i = { P i j = ( p j , q j , S j ) } , j = 1,2 , ⋯ , min ⁡ ( M , N i );Here, we give a toy example to illustrate the key idea of Algorithm1.Figure2 shows five smartphone users denoted by different colored circles belonging to one intermediary along with their own bids. In the first pass, we execute Generalized Secondary Price Auction to get the raw bidding strategy βi (1×2=2, 2×7=14, 3×8=24, 4×9=36). In the second pass, we calculate the marginal cost of every data according to formula in Line 1 in Algorithm 1 (2-0=2,14-2=12,24-14=10,36-24=12). In Algorithm 1, Pij=(pj,qj,Sj) means the average marginal cost for the next qj data is pj with their IDs in set Sj. In the final pass, we scan the marginal cost list one by one (Line 4 to Line 11). We find that the second item “12” is larger than the third item “10”; thus we merge them together (Line 8) ((12+10)/(1+1)=11,1+1=2). After the above procedure, the final bidding strategy βi is monotone increasing by the value of the item’s first component (2≤11≤12). The nice marginal increasing property of processed bidding strategies greatly facilitates the platform mechanism design which we would expatiate on later.Figure 2
A toy example of bidding preprocessing.Given the tailored supermodular property held by processed intermediaries’ bidding strategy, the winner determinationχ(B) is shown in Algorithm 2.Algorithm 2:Allocation scheme χ(B).
Input: Task T(D,M); Intermediaries’ biddings B={βi},i=1,2,⋯,N: P i j = ( p j , q j , S j ) denotes the j-th bidding in βi Output: Intermediaries’ participation level vector χ ( B ) = { x i } , i = 1,2 , ⋯ , N 1 Scandi←∅,Sfinal←∅,num←0; 2 xi←0,∀i=1,2,⋯,N; 3 Add the first item of every intermediary’s bidding into Scandi; 4 whilenum<Mdo 5 Choose the item P= (p, q, S) with the smallest p in S c a n d i, assume denoted as Pst=(pt,qt,St); 6Sfinal←Sfinal∪{St}; 7xs←xs+qt; 8 num←num+qt; 9 add the next item in bidding βs to the Scandi; 10return  Intermediaries’ participation level vector χ ( B ) = { x i } , i = 1,2 , ⋯ , NThe idea behind Algorithm2 is as follows. In each step, the first unchosen item in every intermediary would form the candidate set (Line 3 and Line 9). The platform keeps choosing the bid item with the smallest p component in candidate set until the number of effective data units in chosen set exceeds M (Lines 4 to 9).To help illustrate the main idea of Algorithm2 intuitively, we give the following toy example (see Figure 3). In this specific setting, there are two intermediaries, I1 and I2. Their smartphone users are denoted by different colored circles in Figure 3. Each item of their biddings has three components: bid per data, data quantity, and effective data provider set (Pkji=(p,q,S)). The candidate set (Scandi) contains data packages that are likely to be chosen in the next step while the chosen set (Sfinal) consists of data packages that have already been chosen. M indicates the number of data units needed at least. Initially, we group the first item of every intermediary’s bidding into the candidate set (Line 3). When the number of effective data units in chosen set has not exceeded M, we should keep choosing operation among the candidate set. In every step, the item which has the smallest p component would leave the candidate set for the chosen set (Line 6). Meanwhile, the chosen item’s corresponding intermediary would contribute the next item to the candidate set (Line 9) and its participation level would be updated (Line 7).Figure 3
A toy example of winner determination.


## 3.2.3. Partial Uniform Payment Scheme

The platform’s payment schemeρ(B) is shown in Algorithm 3. In partial uniform payment scheme, a winning intermediary would be paid the same amount of money for each data contribution. Its unit reward is determined by the other’s lowest losing bid. Different intermediaries can have different unit rewards. Taking the scenario in Figure 3, for example, intermediary I1 would be paid the lowest losing bid of intermediary I2 per unit of data (p1=12×3=36), while intermediary I2 would be paid the lowest losing bid of the intermediary I1 per unit of data (p2=12×1=12).Algorithm 3:Payment scheme ρ(B).
Input: Intermediaries’ biddings: B={βi},i=1,2,⋯,N; Participation vector χ(B)={xi},i=1,2,...,N Output: Intermediaries’ payment: ρ ( B ) = { p i } , i = 1,2 , ⋯ , N // Find the smallest losing bids of each intermediary and stores in an array minLoserBid; 1fori=1:Ndo 2minLoserBid(i) = the smallest losing bid of intermediary i; 3 Find the two smallest ones from minLoserBid, denoted as s1,s2(s1≤s2); 4fori=1:Ndo 5ifminLoserBid(i)==s1then 6pi←s2×xi; 7else 8pi←s1×xi; 9return payment vector ρ(B)={pi},i=1,2,⋯,N;


## 3.3. Duplication Elimination

In this section, we deal with the problem of user overlapping mentioned in Section2.1 in order to improve the mechanism design in Section 3.2.Given the bidding profile of intermediariesB=(β1,…,βi,…,βN), our duplication elimination would be conducted before bidding preprocessing (Algorithm 1) and contains two steps: duplication identification and bid adjustment.We design Algorithm4 for duplication identification. The main idea of Algorithm 4 is as follows. First, according to all intermediaries’ bidding profile, we construct 3-tuples for every item in every intermediary’s sorted ID list, composed of an ID number, the corresponding intermediary, and the ID location in the intermediary (Line 1). We assume ID numbers here are all integer and sort all tuples by the ID value in increasing order (Line 2). Here, tuples with the same ID number are adjacent in tuple array (Arr). Then with the help of two scanning cursors (x and y) in tandem, we find out all duplication ID numbers including the intermediary and corresponding location they appear (Dup) (Line 3 to Line 11).Algorithm 4:Duplication identification.
Input: All intermediaries’ sorted ID lists {li},i=1,2,⋯,N; Output: Duplication ID Set D u p : { ( i d , { ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯ } ) , ⋯ }; 1 Build 3-tuple (id,i,j) for every item in l i   i = 1,2 , ⋯ , N: (id, i, j) denotes the number id user is j-th user in intermediary i; 2 Put all 3-tuple (id, i, j) in one array Arr and sort it by the id field in increasing order; 3 x←0,y←1,Dup←∅; 4 whiley<len(Arr)do 5 ifArr[x].id==Arr[y].idthen 6 if!Dup.contain(id)) then 7Dup.Add((id,{(Arr[x].i,Arr[x].j), ( A r r [ y ] . i , A r r [ y ] . j ) } ) ); 8else 9 Dup[id].append((Arr[y].i,Arr[y].j)); 10y←y+1; 11else 12x←y,y←y+1; 13return Duplication ID Set Dup;After finding out the set of duplicated user IDs, we propose two policies to eliminate duplication.(i) KickOut: in the platform view, overlap behaviours are discouraged because they would bring about computation overhead to eliminate their effect. Thus, kicking out the repeated users directly and notifying the intermediaries of repetition message along with trading result could be a reasonable punishment to restrain overlap behaviours and reduce possible user overlap in the long term.(ii) Assign: considering some overlap behaviours are unintentional and KickOut policy may waste valuable data sources, another alternative is to delay the punishment and assign each repeated user to an intermediary. The assignment rules are as follows: if we could infer that the user submits different bids in different intermediaries, assign it to the intermediary with the smallest bid; otherwise, assign it randomly to an intermediary. The way of inferring the users’ bid could be regarded as the reverse process of Generalized Secondary Price Auction. If there is a tuple (id, i, j), the user id bid in intermediary i is βi(j-1) (average bid for j-1 pieces of winning data task of Ii).Following KickOut policy or Assign policy, the previous intermediary biddingB=(β1,…,βi,…,βN) needs adjustment. Assuming tuple (id, i, j) denotes that the i-th intermediary does not get the user id, the bidding strategy βi should be adjusted in the following way: βi(j-1)←βi(j),βi(j)←βi(j+1),⋯ until the end of bidding.After duplication identification and bidding adjustment, we could continue conducting mechanism design in Section3.2 including bidding preprocess, allocation, and payment.


## 4. Theoretical Analysis

In this section, we give formal theoretical proofs for the economic properties of our proposed mechanisms, including incentive compatibility, individual rationality, and computing efficiency.


### 4.1. Properties of Intermediary Mechanism

In intermediary mechanism, the smartphone users have strong motive to misreport their cost, i.e., declare a higher cost than the actual one to obtain higher utility. Thus intermediaries need incentive mechanism which isindividually rational (i.e., it motivates users to participate) andincentive compatible (i.e., it motivates truthful cost reporting by users).This is a single parameter mechanism design, in which each bidder has only one private value. Single-parameter mechanism design relies on Myerson’s well-known characterization. For the original version being a forward-auction version, we here modify it to be compatible with reverse auction scenario.Theorem 5.
In single parameter domains, an auction mechanism is truthful iff
(i) The selection rule is monotone: if user i wins the auction by bidding bi, it also wins by bidding bi′≤bi;
(ii) Winners are paid threshold payments: User i would not win the auction if it bids higher than this value.It is obvious to see aboveGeneralized Secondary Price Auction is truthful (i.e., bji=cji) by checking Theorem 5. Verification of smartphones’ individual-rationality is obvious in intermediary mechanism; thus here we omit it.


### 4.2. Properties of Platform Mechanism

In this section, we prove the properties of the platform mechanism, including incentive compatibility, individual rationality, and efficiency and analyze the task completion situation.Theorem 6.
The incentive mechanism conducted by the platform is incentive compatible such that each intermediary’s best bidding strategy is true result computed by Generalized Secondary Price Auction.Proof.
Generally, an intermediary has no idea about which group of other intermediaries’ users shows in the same trading. Since intermediaries could do nothing to identify user overlapping. The possible intermediaries’ manipulation only refers to misreporting bidding strategy{βi}(i=1,2,…,N). After duplication elimination and bidding preprocessing (Algorithm 1), every bidding strategy βi(i=1,2,…,N) would be transformed into the following style: (bki,qki), denoting that the unit marginal cost of qki more data is bki (here we omit the corresponding user ID set for there does not exist user overlapping yet).
The cheating on the bidding strategyβi(i=1,2,…,N) has two outcomes. If the cheating bid that happens belongs to the overlap user kicked out in duplication elimination process, the cheating actually has no effect on the final trading results. Otherwise, the cheating bid would be reflected on the first field bki of the transformed bid (bki,qki). In the following analysis, we would assume the possible cheating happens directly on the first field bki of the transformed bid.
To prove the incentive compatibility, we need to show, for anyi=1,2,…,N, true valuation {(b~1i,qki),…,(b~ki,qki),…} weakly dominates any other {(b1i,qki),…,(bki,qki),…}.
First, we only replacebki with b~ki(bk-1i≤b~ki≤b~k+1i) and prove the new strategy {b1i,…b~ki,…} weakly dominates the previous strategy {b1i,…bki,…}. Assuming by previous strategy Ii wins xi data tasks and by new strategy, Ii wins xi∗, we discuss three possible cases.
( 1 ) Case 1: xi=xi∗. Intermediary Ii wins the same data tasks on both strategies. By the Partial Uniform Payment Scheme (Algorithm 3), its payment is determined by other intermediaries’ bids. Thus, Intermediary Ii utilities are the same for both strategies.
( 2 ) Case 2: xi<xi∗. Intermediary Ii wins more data tasks by new strategy. Based on payment scheme above, its added reward would be more than its marginal cost of additional tasks collection. Therefore, Ii could improve or at least keep the same utility by adopting the new strategy.
( 3 ) Case 3: xi>xi∗. It means adopting new strategy would make Ii win less data tasks. bki is winning bid but b~ki is not. Both bki and b~ki are larger than bji(j=k+1,k+2,…); thus bji(j=k+1,k+2,…) are not winning bids. Therefore, xi=xi∗+qki. According to Partial Uniform Payment Scheme, in original strategy, the added reward paid to Ii is less than the marginal cost of additional qki data tasks (b~ki×qki).
Second, we show that for any strategy{b1i,…bki,…} could be adjusted step by step to the true evaluation {(b~1i,qki),…,(b~ki,qki),…} in the following way: {b1i,…bki,…bKi}→{b1i,…bki,…max⁡(b~Ki,bKi)}→⋯→{b1i,…max⁡(b~ki,bki),…}→⋯→{b~1i, …}→⋯→{b~1i,b~2i,…}→⋯{b~1i,…,b~Ki}. In every step, the new strategies dominate the previous ones. Thus {(b~1i,qki),…,(b~ki,qki),…} dominates {(b1i,qki),…,(bki,qki),…}.Theorem 7.
The incentive mechanism conducted by platform is individual rational; in other words, any intermediary will be paid more reward than its true cost.Proof.
Supposeb~ji is a winning bid from Ii and b~mi is the highest winning bid of Ii; we have b~ji≤b~mi. If b~∗ is the lowest losing bid among all intermediaries, b~mi<b~∗ holds. If pi is the corresponding unit reward, we have b~∗≤pi based on winner determination and payment mechanism. To sum up, b~ji<pi holds.Theorem 8.
Given taskT(D,M), the number of data units collected by the platform incentive mechanism would be in the range of [M,2M).Proof.
The lower bound is guaranteed by the winner determination algorithm (Line 4 in Algorithm2). In terms of upper bound, in intermediary mechanism, every intermediary would be restricted to contribute at most M units of data. In bidding preprocessing algorithm (Algorithm 1), some bids would be packaged but one package still does not exceed M units of data. Thus, during winner determination, the worst case is that we have chosen M-1 units of data; however the next candidate is a package with M units of data so that the final winner set contains 2M-1 units of data.In terms of social cost, our mechanism does not achieve social efficiency in theory, but still keeps social cost low enough. On the platform, we assign the overlapping user to the intermediary with that user’s lowest bid, i.e, minimize the true cost as much as possible. After duplication elimination, the platform assigns the data tasks to those who could complete them at the least cost. By motivating intermediaries to bid truthfully and selecting at leastM lowest biddings, the platform mechanism indeed minimizes social cost as much as possible in reverse auction scenario.


### 4.3. Time Complexity

In this section, we analyze the running time of the platform mechanism. In duplication identification (Algorithm4), constructing array Arr takes O(∑i=1NNi); sorting array Arr takes O(log⁡(∑i=1NNi)); scanning array Arr and building duplication set takes O(∑i=1NNi). Computation overhead for bidding adjustment based on duplication set depends on the number of intermediaries affected. For every effected intermediary, the corresponding bidding adjustment takes O(Ni). For intermediary Ii’s bidding preprocessing (Algorithm 1), marginal cost calculation takes O(Ni), and bidding adjustment also takes O(Ni). Thus, the whole bidding preprocessing takes O(Nmax⁡(Ni)(i=1,2,..,N)). To speed up the computing, we could assign one intermediary’s bidding preprocessing to one child process and let all processes execute concurrently. The complexity of winner determination (Algorithm 2) is O(Mlog⁡N). Partial uniform payment scheme (Algorithm 3) takes O(N) time.


## 4.1. Properties of Intermediary Mechanism

In intermediary mechanism, the smartphone users have strong motive to misreport their cost, i.e., declare a higher cost than the actual one to obtain higher utility. Thus intermediaries need incentive mechanism which isindividually rational (i.e., it motivates users to participate) andincentive compatible (i.e., it motivates truthful cost reporting by users).This is a single parameter mechanism design, in which each bidder has only one private value. Single-parameter mechanism design relies on Myerson’s well-known characterization. For the original version being a forward-auction version, we here modify it to be compatible with reverse auction scenario.Theorem 5.
In single parameter domains, an auction mechanism is truthful iff
(i) The selection rule is monotone: if user i wins the auction by bidding bi, it also wins by bidding bi′≤bi;
(ii) Winners are paid threshold payments: User i would not win the auction if it bids higher than this value.It is obvious to see aboveGeneralized Secondary Price Auction is truthful (i.e., bji=cji) by checking Theorem 5. Verification of smartphones’ individual-rationality is obvious in intermediary mechanism; thus here we omit it.


## 4.2. Properties of Platform Mechanism

In this section, we prove the properties of the platform mechanism, including incentive compatibility, individual rationality, and efficiency and analyze the task completion situation.Theorem 6.
The incentive mechanism conducted by the platform is incentive compatible such that each intermediary’s best bidding strategy is true result computed by Generalized Secondary Price Auction.Proof.
Generally, an intermediary has no idea about which group of other intermediaries’ users shows in the same trading. Since intermediaries could do nothing to identify user overlapping. The possible intermediaries’ manipulation only refers to misreporting bidding strategy{βi}(i=1,2,…,N). After duplication elimination and bidding preprocessing (Algorithm 1), every bidding strategy βi(i=1,2,…,N) would be transformed into the following style: (bki,qki), denoting that the unit marginal cost of qki more data is bki (here we omit the corresponding user ID set for there does not exist user overlapping yet).
The cheating on the bidding strategyβi(i=1,2,…,N) has two outcomes. If the cheating bid that happens belongs to the overlap user kicked out in duplication elimination process, the cheating actually has no effect on the final trading results. Otherwise, the cheating bid would be reflected on the first field bki of the transformed bid (bki,qki). In the following analysis, we would assume the possible cheating happens directly on the first field bki of the transformed bid.
To prove the incentive compatibility, we need to show, for anyi=1,2,…,N, true valuation {(b~1i,qki),…,(b~ki,qki),…} weakly dominates any other {(b1i,qki),…,(bki,qki),…}.
First, we only replacebki with b~ki(bk-1i≤b~ki≤b~k+1i) and prove the new strategy {b1i,…b~ki,…} weakly dominates the previous strategy {b1i,…bki,…}. Assuming by previous strategy Ii wins xi data tasks and by new strategy, Ii wins xi∗, we discuss three possible cases.
( 1 ) Case 1: xi=xi∗. Intermediary Ii wins the same data tasks on both strategies. By the Partial Uniform Payment Scheme (Algorithm 3), its payment is determined by other intermediaries’ bids. Thus, Intermediary Ii utilities are the same for both strategies.
( 2 ) Case 2: xi<xi∗. Intermediary Ii wins more data tasks by new strategy. Based on payment scheme above, its added reward would be more than its marginal cost of additional tasks collection. Therefore, Ii could improve or at least keep the same utility by adopting the new strategy.
( 3 ) Case 3: xi>xi∗. It means adopting new strategy would make Ii win less data tasks. bki is winning bid but b~ki is not. Both bki and b~ki are larger than bji(j=k+1,k+2,…); thus bji(j=k+1,k+2,…) are not winning bids. Therefore, xi=xi∗+qki. According to Partial Uniform Payment Scheme, in original strategy, the added reward paid to Ii is less than the marginal cost of additional qki data tasks (b~ki×qki).
Second, we show that for any strategy{b1i,…bki,…} could be adjusted step by step to the true evaluation {(b~1i,qki),…,(b~ki,qki),…} in the following way: {b1i,…bki,…bKi}→{b1i,…bki,…max⁡(b~Ki,bKi)}→⋯→{b1i,…max⁡(b~ki,bki),…}→⋯→{b~1i, …}→⋯→{b~1i,b~2i,…}→⋯{b~1i,…,b~Ki}. In every step, the new strategies dominate the previous ones. Thus {(b~1i,qki),…,(b~ki,qki),…} dominates {(b1i,qki),…,(bki,qki),…}.Theorem 7.
The incentive mechanism conducted by platform is individual rational; in other words, any intermediary will be paid more reward than its true cost.Proof.
Supposeb~ji is a winning bid from Ii and b~mi is the highest winning bid of Ii; we have b~ji≤b~mi. If b~∗ is the lowest losing bid among all intermediaries, b~mi<b~∗ holds. If pi is the corresponding unit reward, we have b~∗≤pi based on winner determination and payment mechanism. To sum up, b~ji<pi holds.Theorem 8.
Given taskT(D,M), the number of data units collected by the platform incentive mechanism would be in the range of [M,2M).Proof.
The lower bound is guaranteed by the winner determination algorithm (Line 4 in Algorithm2). In terms of upper bound, in intermediary mechanism, every intermediary would be restricted to contribute at most M units of data. In bidding preprocessing algorithm (Algorithm 1), some bids would be packaged but one package still does not exceed M units of data. Thus, during winner determination, the worst case is that we have chosen M-1 units of data; however the next candidate is a package with M units of data so that the final winner set contains 2M-1 units of data.In terms of social cost, our mechanism does not achieve social efficiency in theory, but still keeps social cost low enough. On the platform, we assign the overlapping user to the intermediary with that user’s lowest bid, i.e, minimize the true cost as much as possible. After duplication elimination, the platform assigns the data tasks to those who could complete them at the least cost. By motivating intermediaries to bid truthfully and selecting at leastM lowest biddings, the platform mechanism indeed minimizes social cost as much as possible in reverse auction scenario.


## 4.3. Time Complexity

In this section, we analyze the running time of the platform mechanism. In duplication identification (Algorithm4), constructing array Arr takes O(∑i=1NNi); sorting array Arr takes O(log⁡(∑i=1NNi)); scanning array Arr and building duplication set takes O(∑i=1NNi). Computation overhead for bidding adjustment based on duplication set depends on the number of intermediaries affected. For every effected intermediary, the corresponding bidding adjustment takes O(Ni). For intermediary Ii’s bidding preprocessing (Algorithm 1), marginal cost calculation takes O(Ni), and bidding adjustment also takes O(Ni). Thus, the whole bidding preprocessing takes O(Nmax⁡(Ni)(i=1,2,..,N)). To speed up the computing, we could assign one intermediary’s bidding preprocessing to one child process and let all processes execute concurrently. The complexity of winner determination (Algorithm 2) is O(Mlog⁡N). Partial uniform payment scheme (Algorithm 3) takes O(N) time.


## 5. Evaluation

In this section, we evaluate the performance of our proposed mechanism. Our evaluation consists of the following aspects: task completion and its distribution, platform total payment, intermediary revenue and its distribution, and social cost.


### 5.1. Setting

In our evaluation, the proposed mechanism has four parameters: intermediary number, task number, user overlapping rate, and total user number. All intermediaries’ user numbers follow the Zipf distrubution. All user bids are randomly generated following the normal distribution in the range of (0,2). All user identification numbers (ID) are positive integer. As mentioned in our model, intermediaries have large user base; thus in our evaluation, every intermediary’s user number is larger than task number.For user duplication, to simplify but not harm generality, a user belongs to at most two intermediaries. User overlap rate here means the ratio of the overlap user number to the total user number. For example, considering 2 intermediaries each with 20 users, if without user overlapping, we have2∗20=40 valid users. However, if the user overlap rate is 0.1, then we only have 40∗(1-0.1)=36 valid users. In other words, the number of users who have two intermediaries is 4 and that of users who have one intermediary is 32 (32+4∗2=40). Thus, the user overlapping rate ranges from 0 to 0.5.Every data point in the following figures is the average result of 100 executions.


### 5.2. Task Completion

Theorem8 shows the proposed mechanism is not exact: given task T(D,M), the number of data units collected by the platform incentive mechanism would be in the range of [M,2M). In our experiments, we execute the proposed mechanism with different task number settings (all other parameters remain unchanged) and compare the final collected task number with the required task number. As shown in Figure 4, the deviation between the number of collected tasks and required ones is quite small. Thus, although the theoretical upper bound of proposed mechanism is double required task, the collected task numbers are very close to the lower bound at most time in practice.Figure 4
Task required vs. Task completed.


### 5.3. Intermediary Participation and Revenue Distribution

In this part, we choose a setting with 0.1 overlap rate, 2000 tasks, and 100 intermediaries with fixed smartphone users following Zipf distribution. Then we simulated the proposed mechanism 100 times, where each time we generate bids randomly following normal distribution in range of (0, 2). We calculate every intermediary’s average number of winning task and revenue. Figures5 and 6 show that intermediaries with more users win more tasks and gain more revenue. Besides, it is noticed that the tasks are distributed quite equally, which reveals that the proposed mechanism achieves some degree of fairness to attract and keep more participants.Figure 5
Winner distribution among intermediaries.Figure 6
Revenue distribution among intermediaries.


### 5.4. Platform Payment

The most significant difference between our mechanism and the previous works is the intermediaries’ participation. Compared with the way of interacting with smartphone users directly, intermediaries’ participation would increase the platform total payment because we would pay price to guarantee trufulness of both smartphones and intermediaries. Besides the proposed mechanism, we also simulate the mechanism where the platform accesses directly all valid users and carries out Generalized Secondary Price Auction mentioned in Section3.1. Figures 7 and 8 show the following:(1)
Both the platform payment and the payment gap between two models grow with the increase of task number and overlap rate and the decrease of intermediary number; i.e., a greatly competitive market with large gap between supply and demand helps lower the payment and payment gap.(2)
The payment gap is quite close to the intermediaries’ total revenue in all settings; i.e, the intermediaries gain profit from the platform overpayment.(3)
With the increment of intermediary number, intermediary total revenue is smaller than payment gap at first but becomes larger than that later. The turning point is around 20 intermediaries.Figure 7
Influential factors of platform payment under two models.Figure 8
Influential factors of platform payment gap and intermediaries’ total revenue.


### 5.5. Social Cost

Besides platform payment, intermediaries’ participation also increases social cost, i.e., the aggregation of all smartphone winners’ sensing cost equal to the sum of their bids in the proposed mechanism. Experimental settings are similar to those above. As shown in Figure9, the social cost grows with the increase of task number and overlap rate and the decrease of intermediary number. Similarly, a greatly competitive market with large gap between supply and demand helps lower the social cost. Furthermore, the social cost gap is relatively small which reveals that the proposed mechanism achieves social efficiency to a certain extent.Figure 9
Influential factors of social cost and social cost gap under two models.


## 5.1. Setting

In our evaluation, the proposed mechanism has four parameters: intermediary number, task number, user overlapping rate, and total user number. All intermediaries’ user numbers follow the Zipf distrubution. All user bids are randomly generated following the normal distribution in the range of (0,2). All user identification numbers (ID) are positive integer. As mentioned in our model, intermediaries have large user base; thus in our evaluation, every intermediary’s user number is larger than task number.For user duplication, to simplify but not harm generality, a user belongs to at most two intermediaries. User overlap rate here means the ratio of the overlap user number to the total user number. For example, considering 2 intermediaries each with 20 users, if without user overlapping, we have2∗20=40 valid users. However, if the user overlap rate is 0.1, then we only have 40∗(1-0.1)=36 valid users. In other words, the number of users who have two intermediaries is 4 and that of users who have one intermediary is 32 (32+4∗2=40). Thus, the user overlapping rate ranges from 0 to 0.5.Every data point in the following figures is the average result of 100 executions.


## 5.2. Task Completion

Theorem8 shows the proposed mechanism is not exact: given task T(D,M), the number of data units collected by the platform incentive mechanism would be in the range of [M,2M). In our experiments, we execute the proposed mechanism with different task number settings (all other parameters remain unchanged) and compare the final collected task number with the required task number. As shown in Figure 4, the deviation between the number of collected tasks and required ones is quite small. Thus, although the theoretical upper bound of proposed mechanism is double required task, the collected task numbers are very close to the lower bound at most time in practice.Figure 4
Task required vs. Task completed.


## 5.3. Intermediary Participation and Revenue Distribution

In this part, we choose a setting with 0.1 overlap rate, 2000 tasks, and 100 intermediaries with fixed smartphone users following Zipf distribution. Then we simulated the proposed mechanism 100 times, where each time we generate bids randomly following normal distribution in range of (0, 2). We calculate every intermediary’s average number of winning task and revenue. Figures5 and 6 show that intermediaries with more users win more tasks and gain more revenue. Besides, it is noticed that the tasks are distributed quite equally, which reveals that the proposed mechanism achieves some degree of fairness to attract and keep more participants.Figure 5
Winner distribution among intermediaries.Figure 6
Revenue distribution among intermediaries.


## 5.4. Platform Payment

The most significant difference between our mechanism and the previous works is the intermediaries’ participation. Compared with the way of interacting with smartphone users directly, intermediaries’ participation would increase the platform total payment because we would pay price to guarantee trufulness of both smartphones and intermediaries. Besides the proposed mechanism, we also simulate the mechanism where the platform accesses directly all valid users and carries out Generalized Secondary Price Auction mentioned in Section3.1. Figures 7 and 8 show the following:(1)
Both the platform payment and the payment gap between two models grow with the increase of task number and overlap rate and the decrease of intermediary number; i.e., a greatly competitive market with large gap between supply and demand helps lower the payment and payment gap.(2)
The payment gap is quite close to the intermediaries’ total revenue in all settings; i.e, the intermediaries gain profit from the platform overpayment.(3)
With the increment of intermediary number, intermediary total revenue is smaller than payment gap at first but becomes larger than that later. The turning point is around 20 intermediaries.Figure 7
Influential factors of platform payment under two models.Figure 8
Influential factors of platform payment gap and intermediaries’ total revenue.


## 5.5. Social Cost

Besides platform payment, intermediaries’ participation also increases social cost, i.e., the aggregation of all smartphone winners’ sensing cost equal to the sum of their bids in the proposed mechanism. Experimental settings are similar to those above. As shown in Figure9, the social cost grows with the increase of task number and overlap rate and the decrease of intermediary number. Similarly, a greatly competitive market with large gap between supply and demand helps lower the social cost. Furthermore, the social cost gap is relatively small which reveals that the proposed mechanism achieves social efficiency to a certain extent.Figure 9
Influential factors of social cost and social cost gap under two models.


## 6. Related Works

In recent years, the concept of mobile crowdsensing has been widely applied into various application domains. Rana et al. [3] and Dutta et al. [4] adopted mobile devices to monitor urban air pollution. PEIR [17] is a crowdsensing application that generates personal environmental impact report. TrafficSense [5] is a piggyback crowdsenisng system that utilizes smartphone sensors to monitor road and traffic conditions. ParkNet [7] and ParkSense [8] are two different mobile systems that can help drivers to find on-street parking space. GreenGPS is a crowdsensing-based navigation service that utilizes crowdsensing data to construct fuel efficient maps. Zhou et al. [18] relied on the collaborative effort of crowdsensing users to predict the bus arrival time. Azizyan et al. [19] proposed a logical localization system based on ambient fingerprintings. The problem of indoor physical localization has also been widely studied,e.g., [20–23]. Jigsam [24] leverages smartphone sensors to automatically construct indoor floorplans. Moazzami et al. [25] presented ORBIT, a smartphone-based platform for data-intensive embedded sensing applications. Jayarajah et al. [26] proposed LiveLabs deployed across small areas to collect real-time attributes which can be used to test new mobile sensing experiments. Song et al. [27] proposed a real-time projector-camera fnger system based on the crowdsensing, in which user can interact with a computer by bare hand touching on arbitrary surfaces. Yang et al. [28] considered designing incentive mechanisms for motivating private cars in a local region to collect data for HD map producers. However, most of these systems only work on a small scale of participants. To enable the accessibility of mobile crowdsensing systems in a larger participant scale motivates this work.Many researchers have adopted market economy or game theory in order to attract more users to engage in the emerging sensing paradigms. Lee and Hoh [11] studied the user participation problem and proposed an incentive mechanism to maintain a large number of participants. Yang et al. [12] considered designing incentive mechanisms for both platform-centric and user-centric models. Koutsopoulos [29] studied the design of optimal frugal mechanism for crowdsensing. Zhao et al. [30] studied the online incentive mechanism design with budget constraint. Gao et al. [31] considered incentivizing users’ long-term participation and proposed a Lyapunov-based VCG mechanism. Zhang et al. [32] studied three different models of crowdsensing and designed incentive mechanisms for them, respectively. Wei et al. [33] proposed truthful online double auctions for dynamic mobile crowdsensing. Zhang et al. [34] proposed a multimarket dynamic double auction mechanism for proximity-based mobile crowdsensing. Chen et al. [35] took the concept of network effects into consideration of designing incentive mechanisms. Li et al. [36] studied a new MCS architecture which leverages the cached sensing data to fulfill partial sensing tasks in order to reduce the size of selected participant set. Hu et al. [37] proposed a truthful incentive mechanism based on reverse auction to stimulate enough vehicles to participate in crowdsensing. Yang et al. [38] integrated quality estimation and monetary incentive and proposed a quality-based truth estimation and surplus sharing method for crowdsensing. Zheng et al. [39] studied a budget feasible and strategy-proof incentive mechanism for weighted coverage maximization in mobile crowdsensing. Zhu et al. [40] proposed a greedy discrete particle swarm optimization with genetic algorithm operation to solve the multitask allocation problem. Peng et al. [41] incorporated the consideration of data quality into the design of incentive mechanism for crowdsensing by offering each participant a reward based on her effective contribution. Some researchers also proposed preserving privacy in mobile crowdsensing. Lin et al. [42] designed two frameworks for privacy-preserving auction-based incentive mechanisms that also achieve approximate social cost minimization. Chen et al. [43] proposed an approach called P3 to preserve the privacy of the mobile nodes in a mobile crowd sensing system, leveraging node mobility. Xiong et al. [44] proposed a privacy preserving data aggregation scheme, where the mediator and sensing users may not be fully trusted. Lv et al. [45] investigated the possibilities and limitations of incentive trees via an axiomatic approach by defining a set of desirable properties. Zhang et al. [46] aimed to design an auction-based incentive tree to offer rewards to users for both participation and solicitation. Zhang et al. [47] designed a reward mechanism based on the incentive tree and proved that this mechanism satisfies several economic properties. However, these existing works only considered a two-layer crowdsensing architecture, consisting of a sensing platform and many smartphone users, which has critical drawbacks that prevent the sensing systems from scaling up. In contrast to these works, we consider a three-layer architecture by cooperating the sensing platform with certain popular applications that have large user bases. This work is based on the preliminary version [48] which appeared in IEEE IWQoS 2017.


## 7. Conclusion and Future Work

With the development of emerging mobile crowdsensing paradigm, data source shortage has become the bottleneck of most state-of-the-art mobile crowdsensing systems. Thus, we had proposed to cooperate with applications with large user base (act as intermediaries) to help to incentivize more users to be involved in crowdsensing. Our incentive mechanisms are based on a three-layer network model. We had designed auction-based mechanisms and identified the unique the problem of user overlapping, which had not been considered in existing incentive models, and had provided an effective solution to deal with it. Our incentive mechanisms are individual rational, incentive compatible, and computationally efficient and achieve quite low social cost. We have evaluated our mechanisms with extensive evaluations. Evaluation results have validated the effectiveness and efficiency of our proposed mechanisms.Mobile crowdsensing has become a promising paradigm in collecting and using sensing data. However, how to ensure the data quality has become a tricky problem for us to discuss. This will be the essential direction for us to explore in the future.( 1 ) In our evaluation, we pay the participants for their consumptions of physical resources based on their bids and default that the participants would provide the data of high quality. If we consider that the participants cannot guarantee the quality of the sensing data they promised, continuous low-quality data could be harmful to the availability and accuracy of crowdsensing platform, and thus the quality of service cannot be guaranteed. To solve the issue of data quality, we consider two possible approaches to penetrate into in the future. First, it is a feasible and effective method to incorporate the level of data quality as an index into our mechanism. We can pay the participants as how much they contribute to motivate the participants to submit sensory data. Thus, it is a key issue to estimate the quality of sensory data and to reward each participant based on the estimated value. Second, we can also integrate quality estimation and monetary incentives together, by using a learning-based method to quantify the data quality and long-term credits of users, and by sharing the surplus earned by the sensing platform with users depending on each user’s contribution. We can also reject low-credit users sensory data to improve data quality.( 2 ) We can also assume the possibility that a participant may fail to complete the task for some reason with a certain probability into consideration. We must make sure that our mechanism has fault tolerance capability for each sensing task under unreliable circumstances. To solve this problem, we can design a reverse auction mechanism to simulate the strategic interaction between the platform and the participants. The new auction mechanism aims to decrease the social cost and to guarantee the tasks to be completed as much as possible.We aim to solve the problems and continue to optimize our mechanism in the future.



---

*Source: 8603526-2019-01-01.xml*