Quality-aware and Fine-grained Incentive

Mechanisms for Mobile Crowdsensing

Jing Wang, Jian Tang, Dejun Yang, Erica Wang and Guoliang Xue

Abstract—Limited research efforts have been made for Mobile Cloud Operator (Buyer) Web Portal
CrowdSensing (MCS) to address quality of the recruited crowd, Sensor Data
i.e., quality of services/data each individual mobile user and the
whole crowd are potentially capable of providing, which is the Sensing Task
main focus of the paper. Moreover, to improve flexibility and
effectiveness, we consider fine-grained MCS, in which each sens- Sensor Sensing
ing task is divided into multiple subtasks and a mobile user may Data Task
Sensing Sensor
make contributions to multiple subtasks. In this paper, we first Task Data
introduce mathematical models for characterizing the quality of a
recruited crowd for different sensing applications. Based on these
models, we present a novel auction formulation for quality-aware
and fine-grained MCS, which minimizes the expected expenditure Mobile Users Service Users
subject to the quality requirement of each subtask. Then we (Bidders and Sellers)
discuss how to achieve the optimal expected expenditure, and
present a practical incentive mechanism to solve the auction Fig. 1. An MCS System
problem, which is shown to have the desirable properties of
truthfulness, individual rationality and computational efficiency.
We conducted trace-driven simulation using the mobility dataset
of San Francisco taxies. Extensive simulation results show the Recently, Mobile CrowdSensing (MCS) have been gaining
proposed incentive mechanism achieves noticeable expenditure increasing popularity. As shown in Fig. 1, we consider a
savings compared to two well-designed baseline methods, and
general-purpose MCS system [21], such as PRISM [1] and
moreover, it produces close-to-optimal solutions.
Index Terms—Mobile Crowdsensing, Smartphones, Incentive Medusa [19]. A service user can make a sensing service
Mechanism, Auction, Quality of Crowd request via a web portal. The request is then analyzed by
the cloud operator, which will use an incentive mechanism to
recruit a sensing crowd (a set of mobile users) and distribute
I. I NTRODUCTION
the request to them. Then their smartphones will perform the
Beyond communications, mobile phones have been playing corresponding sensing activities and report sensor data to the
a key role in many aspects of people’s daily life, including cloud operator. The cloud operator will aggregate and analyze
computing, entertainment, etc. However, some mobile users sensor data, and then send results back to the service user
may not fully realize that most smartphones (such as iPhone through the web portal.
6, Nexus 6, Lumia series, etc) are equipped with a rich While participating in MCS, there is usually a cost occurring
set of powerful embedded sensors, such as camera, GPS, to a mobile user. For example, performing sensing activities
WiFi/3G/4G interface, accelerometer, digital compass, gyro- consumes energy from a smartphone. So the mobile user may
scope, microphone, etc. Additionally, the emergence of wear- want to earn certain credits (e.g., money) to compensate for
able devices (such as smart watch, Fitbit, Sensordrone [20], his/her energy loss. Most sensing tasks are location-dependent,
etc) significantly extends the sensing capabilities of smart- which may require mobile users to travel to or around cer-
phones. Most wearable devices can be connected to a smart- tain areas, leading to certain costs such as transportation.
phone via a network interface (such as Bluetooth) for data Furthermore, mobile users usually won’t be willing to share
exchange. Ubiquitous mobile sensors have led to many at- their privacy while undertaking sensing tasks if there are no
tractive sensing applications in various domains [13], includ- satisfactory rewards. Based on the above observations, we
ing environmental monitoring, social networking, healthcare, are motivated to consider a reverse auction based incentive
transportation, safety, etc. mechanism to enable fair pricing between the cloud operator
and mobile users in MCS. As illustrated in Fig. 1, after
Jing Wang and Jian Tang are with Department of Electrical Engineering receiving a sensing task from a service user, the cloud operator
and Computer Science, Syracuse University, Syracuse, NY 13244. Email: (the buyer of sensor data) announces it to mobile users. Mobile
{jwang93, jtang02}@syr.edu. Dejun Yang is with the Department of Electrical
Engineering and Computer Science, Colorado School of Mines, Golden, users (bidders, sellers and service providers) offer their bids
CO 80401. Erica Wang is with Hershey High School, Hershey, PA 17033. for undertaking the task and selling their sensor data. Based on
Guoliang Xue is with Ira A. Fulton Schools of Engineering, Arizona State the bids, the cloud operator will selectively determine winners
University, Tempe, AZ 85287. This research was supported in part by NSF
grants 1218203, 1525920, 1444059 and 1461886. The information reported and after collecting sensor data from winners, it will make
here does not reflect the position or the policy of the federal government. payments to them. Auction mechanism design is crucial for
supporting MCS, because the trading rules between the buyer • We discuss how to achieve the optimal expected expen-
(the cloud operator) and the sellers (mobile users) heavily de- diture, and present a practical incentive mechanism to
pend on it. Specifically, among all the behavior characteristics solve the auction problem, which is shown to be truthful,
of bidders, truthfulness [17] and individual rationality [10] individually rational and computationally efficient.
are of special interest and most desirable in MCS. An auction • We conducted trace-driven simulation using the mobility
mechanism is truthful if a bidder will not increase its payoff dataset of San Francisco taxies [18] and compared the
by submitting any other bids instead of his/her true values. proposed incentive mechanism with two well-designed
An auction without truthfulness will be vulnerable to market baseline methods (rather than trivial random solutions).
manipulation and produce very poor outcomes [8]. An auction Extensive simulation results show the proposed mecha-
mechanism is individually rational if the payoff of every bidder nism achieves noticeable expenditure savings compared
is not negative by bidding his/her true values. to the baselines; moreover, it produces close-to-optimal
Besides the cost, the success of a crowdsourcing application solutions.
highly depends on whether a quality crowd can be recruited to
undertake the corresponding tasks. Recent research has been II. Q UALITY OF C ROWD (Q O C) M ODELS
focused on incentive mechanisms [2], [24] for mobile crowd-
sourcing, which determine how to recruit a crowd mainly TABLE I
based on their prices/costs. However, limited research efforts M AJOR N OTATIONS
have been made to quality of the recruited crowd, i.e., quality
Notation Explanation
of services/data each individual mobile user and the whole i and M Index of mobile users and the total number of
crowd are potentially capable of providing, which is the main mobile users
focus of the paper. We aim to develop mathematical models to ci and wi True and declared costs of mobile user i respectively
Y i and Zi True and declared quality score vectors of
characterize the quality of a recruited crowd (a set of mobile mobile user i respectively
users). We believe the models for Quality of Crowd (QoC) bi and B Bid of mobile user i and the corresponding
should be application-dependent and we introduce several such vector
models to serve various applications. Furthermore, Unlike [2], xi and x Winner selection variable of mobile user i
and the corresponding vector
[24], in our auction formulation, the bids are two-dimensional, pi and p Payment to mobile user i and the corresponding vector
which means the proof of mechanism properties in [2], [24] j and N Index of subtasks and the total number of subtasks
cannot be directly applied here; and we follow the Bayesian rj and R Quality requirement of subtask j and the corresponding
vector
setting [17] (See Section III), which is a more realistic model. gj (·) QoC model of subtask j
We consider fine-grained MCS, in which each sensing task
consists of multiple subtasks and a mobile user may make
contributions to multiple subtasks. For example, if the goal We focus on a general-purpose MCS system with a sensing
of a sensing task is to cover a target area, then each subtask crowd of M mobile users. A subset of mobile users will be
may corresponds to a sub-area. In this way, the recruited crowd recruited to undertake a sensing task including N subtasks. For
may provide a better coverage for the target area. In addition, a each selected mobile user, there is a cost of ci as explained
sensing task may even include a set of heterogeneous subtasks. above. A quality score is given for mobile user i participating
For example, subtask 1 may request the sensing crowd to in subtask j (denoted as yij ), which quantifies the quality
collect WiFi signal strengths, while subtask 2 may request of services/data the mobile user is potentially capable of
for signal strengths of cellular networks. Fine-grained MCS providing to that subtask. It is application-dependent and can
can lead to a better quality of service and allow a service be assigned according to various factors such as availability,
user to specify a sensing task more flexibly. However, it also accuracy of sensor data, reputation, etc. The cloud operator can
introduces additional complexity for crowd selection because calculate quality scores for mobile users and let them know
a mobile user may be a good candidate for multiple subtasks, their own quality scores. We use Yi = [yi1 , ..., yij , ..., yiN ] to
but may contribute differently to different subtasks. Existing denote the quality score vector of mobile user i for all sensing
incentive mechanisms [9] select the crowd for a single task, subtasks.
ignoring benefits that can be brought by sharing service/data The Quality of Crowd (QoC) for subtask j, qj , quantifies
with other tasks/subtasks. However, we aim to select a crowd the quality of services/data the sensing crowd is potentially
to undertake a sensing task, while meeting a certain quality capable of providing, which could be given by a function
requirement (explained in Section II) for each of its subtasks. gj (·) that can satisfy the following properties: 1) gj (·) is
We summarize our contributions in the following: a monotonically non-decreasing function of hyij i and hxi i,
• We introduce mathematical models for characterizing where xi is a binary value indicating whether mobile user i
QoC for different sensing applications. is recruited or not; and 2) gj (·) returns a value in [0, 1]. The
• Based on these models, we present a novel auction for- first property reflects the nature that with a larger population of
mulation for quality-aware and fine-grained MCS, which the recruited crowd and/or higher individual quality scores, the
minimizes the expected expenditure subject to the quality QoC for the corresponding subtask should not become worse.
requirement of each subtask. In order to make it easier for comparisons and understanding,
the value of QoC should be scaled into [0, 1], with 1 indicting Note that it has been shown by [24] that function (3) is
the corresponding subtask can be perfectly completed by the submodular, i.e., the increase of the return value diminishes
recruited crowd. Note that the auction-based incentive mecha- with the input set. We can easily show that function (4)
nisms presented later are not restricted to any particular QoC is submodular too. These two models are suitable for most
model (function). In the following, we introduce several QoC applications which extract meaningful information from sensor
models that can cover a large variety of sensing applications. data, because usually given a larger data set, the additional
information that can be obtained diminishes. Fig. 2 illustrates
1
how QoC changes with the population of the crowd according
to the three non-linear models. In this example, all mobile
0.8
users have a common quality score of 0.1.
As mentioned above, we consider fine-grained MCS, in
0.6 which each sensing task consists of multiple subtasks. Each
QoC

subtask needs to be completed with a minimum quality

0.4 requirement, rj . We use R = [r1 , ..., rj , ..., rN ] to denote a
Probabilistic coverage
Logarithmic vector of quality requirements of all subtasks. The cloud op-
0.2 Hyperbolic tangent erator recruits mobile users and makes sure qj = gj (Y, X) ≥
rj , ∀j ∈ {1, ..., N }, for the given sensing task, where X =
0 [x1 , ..., xi , ..., xM ].
0 10 20 30 40 50 60
Population of Sensing Crowd
III. AUCTION F ORMULATION
Fig. 2. QoC models In MCS, incentive mechanism design can be formulated as
a reverse or procurement auction mechanism design problem.
1) Linear model: In the auction, 1) the cloud operator (the buyer) announces
PM a sensing task to mobile users (bidders and sellers); 2) each
min( i yij xi , qmax )
qj = . (1) mobile user i submits a bid bi (defined below); 3) the cloud
qmax operator uses an incentive mechanism to select the winners
This model simply sums up quality scores of all mobile users and determine payments; 4) winners carry out the sensing
as the QoC if a goal qmax has not yet achieved; otherwise, the task and submit results to the cloud operator; 5) the cloud
QoC remains at qmax . This model is suitable for applications operator checks the results and makes payments to winners. In
with a goal/constraint of achieving a certain sensing duration the following, we use mobile user and bidder interchangeably.
or collecting a certain number of samples. Here, yij can be Specifically, bi = (wi , Zi ), in which wi is mobile user
the sensing duration or the number of sensing samples that i’s declared cost, and Zi is mobile user i’s declared quality
mobile user i can potentially provide for subtask j. Linear vector. If mobile user i does not want to participate in certain
models have been used in [7], [12]. subtasks, the corresponding declared quality scores can be set
2) Probabilistic coverage model: to 0. Because mobile user i’s true cost ci and true quality
M
Y vector Yi are private and only known to mobile user i
qj = 1 − (1 − yij xi ). (2) himself/herself, wi and Zi could be different from ci and
i Yi , respectively. Different from [23], mobile users’ private
If yij gives the probability that the target of subtask j (e.g., an costs, hci, are assumed to follow a known distribution here.
area or a set of points of interest) can by covered by recruiting This assumption is known as Bayesian setting [17], and it
mobile user i, then qj is the probability that the target can is a realistic assumption because such a distribution can be
be covered by the recruited crowd. This model is suitable for obtained from historical data of previous auction transactions.
sensing applications with a goal/constraint of covering a target fi (c) denotes the probability density function; and Fi (c)
area or a set of target points. denotes the corresponding cumulative distribution function. So
d
3) Logarithmic model: fi (c) = dc Fi (c). B = [b1 , ..., bi , ..., bM ] is the bid vector of
PM all mobile users. B−i denotes the bids of all mobile users
log(1 + i log(1 + yij xi )) except i, so B = [bi , B−i ]. In addition, each mobile user i is
qj = PM . (3)
log(1 + i log(1 + yij )) a single-minded bidder [17], i.e., at a cost of ci , he/she will
In the numerator, the inner log term causes the return value participate in those subtasks, to which he/she has non-zero
to have a diminishing increment with the quality score, and quality scores; or none at a cost of 0 otherwise.
the outer log term leads to diminishing increment with the The cloud operator must complete each subtask j to the
population of the recruited crowd. required quality rj , ∀j ∈ {1, ..., N }. Moreover, the cloud
4) Hyperbolic tangent model: operator also wishes to conserve money and minimize its
M
expected expenditure by selectively recruiting mobile users.
X Specifically, an auction mechanism takes the bid vector B and
qj = tanh( yij xi ). (4)
i
the quality requirement vector R as input and returns a winner
vector x = [x1 , ..., xi , ..., xM ], where xi = 1 if mobile user i Definition 4 (Virtual Valuation). In a forward auction, the
wins, and xi = 0 otherwise; it also returns a payment vector virtual valuation of bidder i with valuation vi is
P = [p1 , ..., pi , ..., pM ], where pi is the payment that the cloud 1 − Fi (vi )
operator will make to mobile user i. Based on the output of φi (vi ) = vi − , (6)
fi (vi )
the auction, the payoff of mobile user i is defined as
fi (vi )
( where the hazard rate 1−F is assumed to be monotonically
pi − ci , xi = 1; i (vi )
ui = (5) non-decreasing (regularity assumption).
0, xi = 0.
Theorem 2 ([17]). Consider any (forward) truthful mechanism
The expenditure
PM of a reverse auction is the sum of the and fix the bids b−i of all bidders except for bidder i. The
payments i pi to all mobile users (bidders). expected payment of bidder i satisfies:
A. Desirable Properties E[pi (vi )] = E[φi (vi )xi (vi )]. (7)
In this section, we describe three desirable properties for an
However, in a reverse auction, the valuation of a bidder can
auction mechanism:
be treated as the negative of its cost, i.e., vi = −ci . Therefore,
• Individual Rationality: an auction mechanism is indi-
vidually rational if for any bidder i, the payoff is non- 1 − Fi (vi )
φi (vi ) = −ci −
negative when bidder i bids his/her true value (ci , Yi ). fi (vi )
• Truthfulness: an auction mechanism is truthful if and Moreover, it can be easily derived that
only if for every bidder i and B−i , bidder i will not
increase his/her payoff by making a bid (wi , Zi ) that is Fi (vi ) = 1 − Fi (ci ), fi (vi ) = fi (−ci ) = fi (ci )
different from his/her true value (ci , Yi ); i.e., bidder i’s Hence, we have
payoff for bidding (ci , Yi ) is at least his/her payoff for
bidding any other bid (wi , Zi ). Fi (ci )
φi (vi ) = −(ci + )
• Computational Efficiency: an auction mechanism is fi (ci )
computationally efficient if the outcome can be computed Definition 5 (Virtual Cost). In a reverse auction, the virtual
in polynomial time. cost of bidder i with cost ci is
Of the three properties, truthfulness is the most difficult to
Fi (ci )
achieve. The bid is two-dimensional because for bidder i, the βi (ci ) = ci + (8)
fi (ci )
bid bi contains two parts: bidder i’s declared cost wi and
bidder i’s declared quality vector Zi . As a result, Myerson’s where the regularity assumption requires that Ffii(c i)
(ci ) is
theorem [16] about the properties of one-parameter truthful monotonically non-increasing. It is clear that βi (ci ) =
mechanisms cannot be directly applied. To design a truthful −φi (vi ).
auction mechanism with two dimensions, we introduce the
following definitions: Theorem 3. Consider any reverse truthful mechanism and fix
the bids b−i of all bidders except for bidder i. The expected
Definition 1 (w-Monotonicity). if bidder i wins by bidding payment to bidder i satisfies:
(wi∗ , (zi1
∗ ∗
, ..., zij ∗
, ..., ziN )), then he/she also wins by bidding
(wi , (zi1 , ..., zij , ..., ziN )) with any wi0 ≤ wi∗ .
0 ∗ ∗ ∗ E[pi (ci )] = E[βi (ci )xi (ci )] (9)
Definition 2 (z-Monotonicity). if bidder i wins by bidding Proof: The payment from the buyer to a seller in a reverse
(wi∗ , (zi1
∗ ∗
, ..., zij ∗
, ..., ziN )), then he/she also wins by bidding auction can be viewed as the negative of the payment from a
∗ 0 0 0 0 ∗
(wi , (zi1 , ..., zij , ..., ziN )) with all zij ≥ zij . buyer to the seller in a forward auction. Therefore:
Definition 3 (Critical Payment). the payment pi for winning E[pi (ci )] = E[−pi (vi )] = E[−φi (vi )xi (vi )] = E[βi (ci )xi (ci )]
bidder i is set to the critical value di such that bidder i wins
if wi < di , and loses if wi > di .
Because of Theorem 3 and the independence of all bidders’
Theorem 1. An auction mechanism for MCS is truthful if it costs, it is fairly easy to show that the expected expenditure of
satisfies w-Monotonicity, z-Monotonicity and critical payment. a reverse truthful mechanism is equal to the total virtual cost.
The details of proof can be found in the appendix. Therefore, to minimize the expected
PM expenditure, it suffices to
minimize the total virtual cost i βi (ci )xi .
B. Virtual Cost
IV. Q UALITY- AWARE I NCENTIVE M ECHANISMS (QIM S )
Next, we introduce virtual cost for reverse auctions and
show its relationship with the expected expenditure. The In this section, we present quality-aware incentive mecha-
concept of virtual valuation has been introduced for forward nisms (QIMs). First, we discuss how to achieve the optimal
auctions in [16]. expected expenditure. Then, we present a practical QIM that
is computationally efficient.
A. Optimal Solutions where vij is the marginal quality score mobile user i can
The QIM design problem consists of two subproblems: contribute to subtask j (according to a QoC model), given a
Winner Selection and Payment Determination. Winner se- prior winner set (i.e., crowd) S 0 :
(
lection problem can be formulated as the following Integer min(gj (S 0 ∪ {i}), rj ) − gj (S 0 ), gj (S 0 ) < rj ;
Programming (IP) problem: vij =
0, otherwise.
IP-Winner:
Then the algorithm updates hvij i and hαi i because in each
M
X iteration, gj (S 0 ) changes with the newly selected mobile user.
min βi (wi )xi (10) For those remaining mobile users with a marginal quality score
X
i=1 of 0 for all subtasks, they will be eliminated from the auction.
Subject to: The algorithm stops when there are no mobile users left.

qj = gj (Z, X) ≥ rj , ∀j ∈ {1, ..., N } (11) Algorithm 1: Winner Selection of QIM-E

xi ∈ {0, 1} (12) Input : Bid vector B, mobile user (bidder) set S,
subtask QoC models hgj (·)i and quality
The objective (10) is to minimize total virtual cost, i.e., the requirement vector R
expected expenditure of the cloud operator. Constraints (11) Output: Winner vector X
ensure that each subtask’s quality requirement is met. Let 1 xi := 0, ∀i ∈ {1, · · · , M };
Ψ(B) denote the optimal value of IP-Winner and Ψ(B−i ) 0
2 S := ∅;
denote the optimal value of IP-Winner with bid bi removed. 3 while S 6= ∅ do
We can achieve the optimal as follows:
4 αi := Pβ(w
N
i)
vij , ∀i ∈ S;
1) Winner Selection: Select winners X∗ by solving IP- j=1 rj

Winner; 5 k := arg mini∈S (αi );

2) Payment Determination: pi := βi−1 (Ψ(B−i ) − (Ψ(B) − 6 xk := 1;
βi (wi ))) if x∗i = 1; pi := 0, otherwise. 7 S := S \ {k};
This incentive mechanism is designed by following the 8 S0 := S0 ∪ {k};
VCG (Vickrey-Clarke-Groves [17]) auction mechanism. It can 9 update hvij i, ∀i ∈ S;
be proven to be truthful and individually rational. The details 10 forall the m ∈ S do
of the proof can be found in the appendix. Note that both 11 if vmj = 0, ∀j ∈ {1, ..., N } then
the Winner Selection and Payment Determination are different 12 S := S \ {m};
from those in [23]. 13 return X := [x1 , ..., xi .., xM ];
However, solving IP-Winner may take exponentially long
time for a large-sized problem instance. Even for the linear
QoC model, IP-Winner is still an Integer Linear Problem Note that the weight of each remaining mobile user changes
(ILP), which is usually hard to solve. In our simulation, we in each iteration; so instead of maintaining a fixed sorted
used an optimization solver to provide optimal solutions for bidder list, the algorithm updates their weights and makes
the linear QoC model. If we consider other QoC models, the selection based on the updated weights. In Payment
then IP-Winner becomes a non-linear integer programming Determination (Algorithm 2), to determine the payment for
problem, which is even much harder. In addition to time com- winning mobile user l, the algorithm repeats the above winner
plexity, it has been shown that truthfulness cannot be preserved selection for the mobile user set with l excluded. When a
by a VCG-based auction mechanism with an approximation winning mobile user k is found such that his/her selection can
(instead of optimal) algorithm [17]. Therefore, we present a disqualify l from winning the auction, the payment is set to the
non-VCG-based QIM with computational efficiency. highest cost that helps l disqualify k or any winning mobile
user before k.
B. Computationally Efficient QIM
C. Proof of Properties
Here, we present a QIM that is truthful, individually rational
Next, we show that QIM-E is truthful, individually rational,
and computationally efficient, which we call QIM-E. Similar
and computationally efficient.
to the above method, QIM-E consists of two phases: Winner
Selection and Payment Determination. Winner Selection (Al- Lemma 1. w-Monotonicity and z-Monotonicity are preserved
gorithm 1) is a heuristic approach, which keeps selecting the in the Winner Selection of QIM-E.
mobile user (bidder) with the smallest weight as a winner.
Proof: Suppose mobile user i wins by bidding (wi∗ , Z∗i ) =
We adopt the following metric αi as the weight to assist the ∗ ∗ ∗ ∗
(wi , (zi1 , ..., zij , ..., ziN )). We prove that: 1) he/she will also
selection:
win by bidding (wi , Z∗i ) = (wi0 , (zi1
0 ∗ ∗
, ..., zij ∗
, ..., ziN )) with any
β(wi ) wi < wi ; and 2) he/she will also win by bidding (wi∗ , Z0i ) =
0 ∗
αi = PN vij , (13)
j=1 rj
(wi∗ , (zi1
0 0
, ..., zij 0
, ..., ziN 0
)) with all zij > zij∗
.
 Algorithm 2: Price Determination of QIM-E Proof: According to Lemmas 1 and 2 as well as Theo-
Input : Bid vector B, mobile user (bidder) set S, rem 1, QIM-E is truthful.
subtask QoC models hgj (·)i, quality Theorem 5. QIM-E is individually rational.
requirement vector R, winner vector X
Output: Payment vector P Proof: We examine two possible cases. First, it is clear
1 forall the l ∈ S do that the payoff of mobile user l is 0 if mobile user l is not
2 pl := 0; a winner according to Algorithm 2. Second, if mobile user
3 if xl = 1 then l is a winner, let the critical value be dl and mobile user
4 S∗ := S \ {l}; l’s cost be cl . Since QIM-E preserves the critical payment
5 S0 := ∅; property as shown in Lemma 2, it is obvious that wl < dl and
6 calculate hvlj i; dl = pl . Since wl = cl in a truthful mechanism, it is clear
7 while S∗ 6= ∅ do that pl − cl > 0. Therefore, the payoff is always non-negative.
8 αi := Pβ(w i) ∗
vij , ∀i ∈ S ;
This completes the proof.
N
j=1 rj

9 k := arg mini∈S∗ (αi ); Theorem 6. QIM-E is computationally efficient.

10 S∗ := S∗ \ {k}; Proof: In Algorithm 1, line 4 takes O(M N ) time to
11 S0 := S0 ∪ {k}; calculate hαi i and update hvij i. Note that finding the mobile
PN v
12 pl := max(pl , βl−1 (αk j=1 rljj )); user with the minimum weight only takes O(M ) in line 5.
13 update hvij i, ∀i ∈ {S∗ , l}; Since the while-loop runs M times, the time complexity of
14 if vlj = 0, ∀j ∈ {1, ..., N } then Algorithm 1 is O(M 2 N ).
15 break; However, in Algorithm 2, the for-loop (lines 1–18) iter-
16 forall the m ∈ S∗ do ates M times, and the inner while-loop (lines 7–18) takes
17 if vmj = 0, , ∀j ∈ {1, ..., N } then O(M 2 N ) time because it has the same complexity with
18 S∗ := S∗ \ {m}; Algorithm 1. So Algorithm 2 takes O(M 3 N ) time. Therefore,
the overall time complexity of QIM-E is O(M 3 N ), which
19 return P := [p1 , ..., pi , ..., pM ]; completes the proof.

V. P ERFORMANCE E VALUATION
Let αi∗ , ∗
hvij i
denote the weight and marginal quality scores In this section, we present and discuss simulation results
respectively when mobile user i bids (wi∗ , Z∗i ). Let αi0 and based on real data to justify the effectiveness of the proposed
0
hvij i denote the weight and marginal quality scores respec- mechanisms.
tively when he/she bids (wi0 , Z∗i ) or (wi∗ , Z0i ). In either case of
(wi0 , Z∗i ) or (wi∗ , Z0i ), it is clear that vij
0 ∗
≥ vij and αi0 < αi∗ ; A. Baseline Methods
i.e., the weight becomes smaller in each iteration for him/her. For fair comparisons, we chose two well-designed incentive
Moreover, as illustrated in lines 10–12 in Algorithm 1, if mechanisms (one of them is truthful and individually rational)
he/she has not been eliminated by bidding (wi∗ , Z∗i ), he/she as the baselines, instead of trivial random solutions. The first
will not be eliminated by bidding (wi0 , Z∗i ) or (wi∗ , Z0i ) either. baseline is a revised version of the greedy method with a fixed
Therefore, he/she will still win with bid (wi0 , Z∗i ) or (wi∗ , Z0i ). list of bidders (referred to as Fix-L) presented in [25]. Since
This completes the proof. we deal with a two-parameter auction (cost and quality score),
Lemma 2. The payment pl is set to a critical value for each we use αi = Pβ(w N
i)
as the weight to sort the bidders in
j=1 zij
winning mobile user (bidder) l in QIM-E. non-decreasing order to obtain the fixed list. Then we iterate
through the fixed list and select winners until the quality
Proof: Let k be the index of mobile user with the smallest
requirements of all subtasks are met. The winners are paid
weight in each iteration until his/her P selection disqualifies
N v based on the corresponding critical values [25]. Similar as
mobile user l. Let dl = maxk (βl−1 (αk j=1 rljj )). Note that
in [25], it can be shown that Fix-L preserves truthfulness and
the marginal quality scores hvlj i are updated in each iteration.
individual rationality.
If mobile user l bids wl > dl , then αl > αk , ∀k, meaning
In the second baseline approach, all bidders are sorted in
l does not have the smallest weight in any iteration before
the non-decreasing order based on their virtual cost (referred
he/she is disqualified by k and thus will be eliminated from
to as Low-C). The algorithm repeatedly selects the bidder with
the auction. If mobile user l bids wl < dl , then αl < αk in
the lowest virtual cost among the remaining bidder set. This
one or more iterations, meaning l will be chosen as a winner
process stops when quality requirements of all subtasks are
the first time when αl < αk happens. Hence dl is the critical
met and winners are paid with critical values. Note that even
value for winning mobile user l. In Algorithm 2, the payment
though this approach is not truthful, it is still a good baseline
pl is set to dl . This completes the proof.
to compare with because the cloud operator tends to directly
Theorem 4. QIM-E is truthful. reduce the expenditure by selecting bidders with low costs.
B. Simulation Settings are presented in Fig. 6.
We conducted trace-driven simulation for performance eval- C. Simulation Results and Analysis
uation using the mobility dataset [18] of San Francisco taxies, We can make the following observations from the results.
which contains GPS coordinates of approximately 500 taxis 1) In Fig. 3, we show the expected expenditures under
collected over 30 days in the San Francisco Bay Area. For the different cost distributions, when the linear model was applied
distributions of mobile user (bidder) costs, we considered the for QoC. In Fig. 5, we show how the expected expenditure
uniform distribution fi (ci ) = 0.25 in the range of (0, 4], the changes with the number of subtasks. From these figures,
exponential distribution fi (ci ) = 0.5e−0.5ci in the range of we can see that the expected expenditures given by QIM-
(0, +∞) and χ2 -distribution with freedom degree of 2. Note E are consistently close to the optimal values. Specifically,
that these functions have the same mean value of 2 and the in Fig. 3, QIM-E produces only 3.9%, 5.1% and 4.4% more
first two distributions were also used in [11] and [25]. For expenditures than the optimal for the exponential, uniform and
QoC models of subtasks, we have implemented the linear χ2 -distributions of costs on average respectively. Moreover, in
model, the probabilistic coverage model and the hyperbolic Fig. 5, QIM-E gives only 3.2% more expenditures than the
tangent model introduced in Section II. In our simulation, each optimal on average.
subtask corresponds a sub-area, each of which is a square- 2) From Figs. 3–5, we can see that QIM-E consistently
like region with a randomly chosen center, whose left/top outperforms Fix-L and Low-C. The reason is that when se-
and right/bottom boundaries differ by 0.0005 degrees in both lecting winners, Low-C does not carefully consider the quality
longitude and latitude (about 160 feet). We derived the quality scores of the mobile users. Even though Fix-L considers the
score of each taxi i for a subtask j by dividing the number individual quality scores, it doesn’t carefully take QoC into
of samples of i within sub-area j by the number of weeks i consideration . On the contrary, QIM-E favors those mobile
showed up in the dataset, which captures the availability of users who contribute the most marginal QoC. Specifically,
the mobile user. Due to non-uniform distribution of samples, in Fig. 3, QIM-E produces about 11.9%, 10.7%, 12.6% less
to ensure the quality requirements are satisfied, we normalized expenditures than Fix-L for the exponential, uniform and
them by a large number, 50, and curved them with an upper χ2 -distributions of costs on average respectively. Moreover,
and lower bounds of 0.15 and 0.04 respectively. in Figs. 3(a) and 4, QIM-E produces about 11.9%, 13.2%,
We came up with the following scenarios for simulation. 10.6% less expenditures than Fix-L for the linear, probabilistic
Simulation runs were conducted on a computer with a 2.2GHz coverage and hyperbolic tangent model of QoC respectively.
Intel Core i7 CPU and 16GB memory. When the linear QoC Similar observations can be made from Fig. 5. Note that
model was used, the optimal expected expenditures were the performance of Low-C is very close to Fix-L in all the
obtained using the method presented in Section IV-A (labeled scenarios.
as QIM-Opt), in which Gurobi Optimizer [6] was employed to 3) Monotonicity can be observed in Figs. 3–5. As expected,
solve the corresponding ILP problems. Each number presented in Figs. 3 and 4, with more mobile users to choose from, all
here is an average over 30 runs. mechanisms yield lower expenditures. On the contrary, we can
1) In scenarios 1 and 2, the number of subtasks was fixed to see that more subtasks lead to higher expenditures no matter
15; quality requirements of subtasks were set to be uniformly which mechanism is used according to Fig. 5.
distributed in [0.7, 0.8]. In scenario 1, the linear model was 4) Fig. 6 shows the running time of different mechanisms
applied for QoC; the number of mobile users was varied for all with various numbers of mobile users. The running time of
the cost distributions described above. In scenario 2, the above QIM-E is only 8.8% of that of QIM-Opt on average, which
exponential distribution was applied for costs; the number of shows QIM-E is scalable. The running times of QIM-E, Fix-
mobile users was varied for the three QoC models mentioned L and Low-C are fairly close to each other, which matches
above. The results of scenario 1 are presented in Fig. 3 and the theoretical analyses that suggest they all have a time
results of scenario 2 are shown in Fig. 3(a) and Fig. 4. complexity of O(M 3 N ).
2) In scenario 3, the linear model was applied for QoC;
costs of mobile users were generated by following the above VI. R ELATED W ORK
exponential distribution; the number of mobile users was set Research efforts have been made to develop general-purpose
to 350. The number of subtasks was increased from 5 to 30 MCS systems, such as PRISM [1] and Medusa [19]. Incentive
with a step size of 5. The corresponding results are presented mechanism design has been addressed in the context general
in Fig. 5. MCS systems recently. Yang et al. introduced two models
3) In scenario 4, we evaluated the running time of proposed for MCS: platform-centric and user-centric; and designed
mechanisms. The number of subtasks was fixed to 15; the an incentive mechanism using a Stackelberg game for the
linear model was applied for QoC; costs of mobile users were platform-centric model as well as an auction-based incentive
generated according to the above exponential distribution; mechanism for the user-centric model in [24]. Duan et al.
quality requirements of subtasks were uniformly distributed proposed a reward-based collaboration mechanism in [2],
in [0.7, 0.8]. The number of mobile users was increased from in which collaborators share a total reward announced by
250 to 500 with a step size of 50. The corresponding results the client. In addition, they investigated how the client can
 5.5 16 9
Fix−L Fix−L Fix−L
Low−C Low−C Low−C
5 8
QIM−E 14 QIM−E QIM−E
QIM−Opt QIM−Opt QIM−Opt
4.5
7

Expenditure
Expenditure

Expenditure
12
4
6
3.5 10
5
3
8
2.5 4

2 6 3
250 300 350 400 450 500 250 300 350 400 450 500 250 300 350 400 450 500
Number of Mobile Users Number of Mobile Users Number of Mobile Users

(a) Exponential distribution (b) Uniform distribution (c) χ2 -distribution

Fig. 3. Performance with the linear QoC model and different cost distributions (Scenario 1)

10 5.5
Fix−L Fix−L
Low−C Low−C
9 5
QIM−E QIM−E

4.5
8
Expenditure

Expenditure
4
7
3.5
6
3

5
2.5

4 2
250 300 350 400 450 500 250 300 350 400 450 500
Number of Mobile Users Number of Mobile Users

(a) Probability coverage model (b) Hyperbolic tangent model

Fig. 4. Performance with different QoC models and the exponential cost distributions (Scenario 2)

4.5 0.8

0.7
4 Fix−L
0.6
Low−C
Running Time(s)
Expenditure

0.5 QIM−E
3.5 QIM−Opt
0.4
3 0.3
Fix−L
Low−C 0.2
2.5
QIM−E
0.1
QIM−Opt
2 0
5 10 15 20 25 30 250 300 350 400 450 500
Number of Subtasks Number of Mobile Users

Fig. 5. Performance with different numbers of subtasks (Scenario 3) Fig. 6. Running time (Scenario 4)

design an optimal contract by specifying different task-reward truthful incentive mechanisms for both the offline and online
combinations for different user types. In [26], Zhao et al. cases, given dynamic smartphones, uncertain arrivals of tasks,
considered the scenario where mobile users arrive one by one strategic behaviors and private information of smartphones.
online in a random order. They presented two online incentive In [27], the authors first designed an incentive mechanism,
mechanisms, in which mobile users submit their private types EFF, which eliminates dishonest behavior with the help from
to the crowdsourcer when arrive and the crowdsourcer aims a trusted third party for arbitration. They then designed another
to select a user subset for maximizing a utility function with mechanism DFF, which, without the help from any third party,
a budget constraint. Feng et al. presented a reverse auction discourages free-riding and false-reporting.
framework named TRAC in [4] to model location based Recently, several research works have addressed incentive
auction interactions between a cloud and smartphones, which mechanism design with quality considerations. In [9], Kout-
minimizes the social cost. In [5], the authors presented two sopoulos et al. seeked a mechanism for user participation
level determination and payment allocation which minimizes [4] Z. Feng, Y. Zhu, Q. Zhang, L. Ni and A. Vasilakos, TRAC: truthful auc-
the total cost of compensating participants, while delivering a tion for location-aware collaborative sensing in mobile crowdsourcing,
IEEE Infocom’2014, pp. 1231-1239.
certain quality of experience to service requesters. They de- [5] Z. Feng, Y. Zhu, Q. Zhang, H. Zhu and J. Yu, Towards truthful
signed a mechanism that optimally solves this problem. In [7], mechanisms for mobile crowdsourcing with dynamic smartphones, IEEE
the authors presented an approximation mechanism to find an ICDCS’2014, pp. 11-20.
[6] Gurobi Optimizer, http://www.gurobi.com/
efficient task allocation with quality of sensing requirements [7] S. He, D. Shin, J. Zhang and J. Chen, Toward optimal allocation of
as well as a pricing mechanism based on bargaining theory. location dependent tasks in crowdsensing, IEEE Infocom’2014, pp. 745-
Luo et al. designed an incentive mechanism [14] based on 753.
[8] P. Kemeperer, What really matters in auction design, Journal of Eco-
all-pay auctions to attract contributions from mobile users. nomic Perspectives, Vol. 16, No. 1, 2002, pp. 169-189.
In [12], Jin et al. designed a truthful, individually rational [9] I. Koutsopoulos, Optimal incentive-driven design of participatory sens-
and computationally efficient mechanism that approximately ing systems, IEEE Infocom’2013, pp. 1402-1410.
[10] V. Krishan, Auction theory, Academic Press, 2009.
maximizes the social welfare for single-minded combinatorial [11] J. Jia, Q. Zhang, Q. Zhang, and M. Liu, Revenue generation for truthful
models, which was shown to have an approximation ratio, spectrum auction in dynamic spectrum access, ACM MobiHoc’2009,
assuming a linear quality model. Moreover, they designed an pp. 3-12.
iterative descending mechanism with individual rationality for [12] H. Jin, L. Su, D. Chen, K. Nahrstedt and J. Xu, Quality of information
aware incentive mechanisms for mobile crowd sensing systems, ACM
multi-minded combinatorial models. MobiHoc’2015.
We summarize the differences between our work and these [13] N. D. Lane, E. Miluzzo, H. Lu and D. Peebles, A survey of mobile
related works in the following: 1) Unlike most related works, phone sensing, IEEE Communications Magazine, Vol. 48, No. 9, 2010,
pp. 140–150.
we consider fine-grained MCS, in which a sensing task [14] T. Luo, H. Tan, and L. Xia, Profit-maximizing incentive for participatory
consists of multiple subtasks and a mobile user may make sensing, IEEE Infocom’2014, pp. 127-135.
contributions to multiple subtasks. 2) Many related works, [15] K. Lin, A. Kansal, D. Lymberopoulos and F. Zhao, Energy-accuracy
trade-off for continuous mobile device location, ACM MobiSys’2010,
such as [2], [4], [5], [24], [26], [27], have not offered careful pp. 285–297.
consideration for QoC and quality requirements of subtasks, [16] R. Myerson, Optimal auction design, Math of Operations Research, Vol.
which, however, is the main focus of this paper. 4) The 6, No. 1, 1981, pp. 58-73.
[17] N. Nisan, T. Roughgarden, E Tardos and V. Vazirani, Algorithmic game
auction formulation here (with the objective of minimizing theory, Cambridge University Press, 2007.
the expected expenditure subject to quality requirements) is [18] M. Piorkowski, N. Sarafijanovic-Djukic and M. Grossglauser, A parsi-
mathematically different from those in related works [7], [12], monious model of mobile partitioned networks with clustering, IEEE
COMSNETS’2009, pp. 1-10.
[9], [14]. 5) Unlike some previous works mainly focusing on [19] M-R Ra, B. Liu, T. L. Porta and R. Govindan, Medusa: a program-
a specific quality model [7], [12] (such as the linear model), ming framework for crowd-sensing applications, ACM MobiSys’2012,
we conduct a comprehensive study for QoC models. pp. 337–350.
[20] Sensordrone, http://sensorcon.com/sensordrone/
VII. C ONCLUSIONS [21] X. Sheng, J. Tang, X. Xiao and G. Xue, Sensing as a service: challenges,
solutions and future directions, IEEE Sensor Journal, Vol. 13, No. 10,
In this paper, we have studied incentive mechanism design 2013, pp. 3733-3741.
for quality-aware and fine-grained MCS. First, we have intro- [22] Y. Singer, Budget feasible mechanisms, IEEE FOCS’2010, pp. 765-774.
[23] J. Wang, D. Yang, J. Tang and M. C. Gursoy, Radio-as-a-Service:
duced several models to characterize QoC for different sensing Auction-based Model and Mechanisms, IEEE ICC’2015, pp. 3567-
applications. Based on these models, we have presented a 3572.
novel auction formulation for quality-aware and fine-grained [24] D. Yang, G. Xue, X. Fang and J. Tang, Crowdsourcing to smartphones:
incentive mechanism design for mobile phone sensing, ACM Mobi-
MCS, which minimizes the expected expenditure subject to Com’2012, pp. 173-184.
the quality requirement of each subtask. We have discussed [25] D. Yang, X. Fang, and G. Xue, Truthful auction for cooperative
how to achieve the optimal expected expenditure, and pre- communications with revenue maximization, IEEE ICC’2012, pp. 4888-
4892.
sented a practical incentive mechanism to solve the auction [26] D. Zhao, X. Li and H. Ma, How to crowdsource tasks truthfully without
problem, which has been shown to be truthful, individual sacrificing utility: online incentive mechanisms with budget constraint,
rational and computational efficient. We have conducted trace- IEEE Infocom’2014, pp. 1213-1221.
[27] X. Zhang, G. Xue, R. Zhou, D. Yang and J. Tang, You better be honest:
driven simulation using the mobility dataset of San Francisco discouraging free-riding and false-reporting in mobile crowdsourcing,
taxies. Extensive simulation results have shown the proposed IEEE Globecom’2014, pp. 4971–4976.
incentive mechanism achieves noticeable expenditure savings
compared to two well-designed baseline methods, and more- VIII. A PPENDIX
over, it produces close-to-optimal solutions.
As discussed in Section III-A, we show that an MCS
R EFERENCES auction mechanism is truthful if it has the w-Monotonicity,
[1] T. Das, P. Mohan, V. Padmanabhan, R. Ramjee and A. Sharma, PRISM: z-Monotonicity and critical payment properties.
platform for remote sensing using smartphones, ACM MobiSys’2010,
pp. 63–76. Lemma 3. In an MCS auction mechanism, if w-
[2] L. Duan, T. Kubo, K. Sugiyama, J. Huang, T. Hasegawa and J. Walrand, Monotonicity, z-Monotonicity, and critical payment are sat-
Incentive mechanisms for smartphone collaboration in data acquisition isfied, bidder i will not increase his/her payoff by bidding
and distributed computing, IEEE Infocom’2012, pp. 1701–1709.
[3] K. El-Arini, G. Veda, D. Shahaf, and C. Guestrin, Turning down the (ci , Zi ) = (ci , (zi1 , ..., zij , ..., ziN )) instead of (ci , Yi ) =
noise in the blogosphere, ACM KDD’2009, pp. 289-298. (ci , (yi1 , ..., yij , ..., yiN )), when Yj 6= Zj .
 Proof: We examine two possible scenarios: Proof: Suppose mobile user i wins by bidding
1) zij < yij for every j. Let dy , dz denote the critical b∗i = (wi∗ , (zi1
∗ ∗
, ..., zij ∗
, ..., ziN )), or equivalently Ψ(B−i ) >
∗
payments for bidding (ci , Yi ) and (ci , Zi ) respectively. We Ψ((bi , B−i )). We will prove that mobile user i also wins
consider two sub-cases: a) bidder i wins by bidding (ci , Zi ). by bidding b0i = (wi0 , (zi1 ∗ ∗
, ..., zij ∗
, ..., ziN )) with any wi0 <
∗
Based on z-Monotonicity, we know that he/she will also win wi through contradiction. Suppose mobile user i will lose
by bidding (ci , Yi ). In other words, for any ci < dz , we have by bidding b0i . Then Ψ((b0i , B−i )) = Ψ(B−i ). Therefore,
ci < dy . Hence, dy ≥ dz ; the payment of bidding (ci , Yi ) Ψ((b0i , B−i )) > Ψ((b∗i , B−i )). However, with the same win-
will not be decreased. b) bidder i loses by bidding (ci , Zi ). ner vector x of (b∗i , B−i ), the total virtual cost of (b∗i , B−i )
In this sub-case, the payoff of bidding (ci , Yi ) is 0 if he/she would be greater than (b0i , B−i ) because wi∗ > wi0 ; this
loses and non-negative if he/she wins. contradicts the statement that Ψ((b0i , B−i )) > Ψ((b∗i , B−i )).
2) zij > yij for one or more j’s. Before actually making Hence, the supposition is false and mobile user i will also win
payments to bidder i, the cloud operator has a quality control by bidding b0i . This completes the proof.
that makes sure the actual quality score yij (derived from the Lemma 6. z-Monotonicity is satisfied by the Winner Selection
submitted sensor data) is equal to or greater than zij . If not, no of QIM-Opt.
payments will be made to bidder i, yielding negative payoff
for him/her with bidding (ci , Zi ). Proof: Suppose that mobile user i wins by bidding
The above two cases complete the proof. b∗i = (wi∗ , (zi1
∗ ∗
, ..., zij ∗
, ..., ziN )), or equivalently Ψ(B−i ) >
∗
Ψ((bi , B−i )). We will prove that mobile user i also wins
Lemma 4. In an MCS auction mechanism, if w-Monotonicity, by bidding b0i = (wi∗ , (zi1 0 0
, ..., zij 0
, ..., ziN 0
)) with all zij ≥
∗
z-Monotonicity, and critical payment are satisfied, bidder i zij through contradiction. Suppose mobile user i will lose
will not increase his/her payoff by bidding (wi , Zi ) instead of by bidding b0i . Then Ψ((b0i , B−i )) = Ψ(B−i ). Therefore,
(ci , Zi ), when ci 6= wi . Ψ((b0i , B−i )) > Ψ((b∗i , B−i )). However, with the same win-
ner vector x of (b∗i , B−i ), the total virtual cost of (b0i , B−i )
Proof: Denote the Critical Payment for bidding (ci , Zi ) is equal to the total virtual cost of (b∗i , B−i ); this contradicts
by d. We consider two cases: the statement that Ψ((b0j , B−i )) > Ψ((b∗i , B−i )). Hence, the
1) (ci , Zi ) is a losing bid. In this case, ci > d. We consider supposition is false and mobile user i will also win by bidding
two sub-cases: a) (wi , Zi ) is a losing bid. Bidder i would b0i . This completes the proof.
have a 0 payoff, which is not better than bidding (ci , Zi ).
b) (wi , Zi ) is a winning bid. He/she receives the payment d Lemma 7. pi = βi−1 (Ψ(B−i )−(Ψ(B)−βi (wi ))) is a critical
because the critical payment is independent of wi ; the payoff value for winning mobile user i in QIM-Opt.
of bidding (wi , Zi ) would be negative, since d < ci . Proof: In QIM-Opt for winning mobile user i, Ψ(B−i ) −
2) (ci , Zi ) is a winning bid. If (wi , Zi ) is a winning bid, (Ψ(B) − βi (wi )) is calculated based on the opportunity cost,
bidder i receives the same payment p with (ci , Zi ). If (wi , Zi ) which is the increment of total virtual cost of other mobile
is a losing bid, he/she receives a payment of 0. users caused by the absence of mobile user i. The opportunity
The above two cases complete the proof. cost in a reverse auction corresponds to the concept of oppor-
tunity cost in a forward auction introduced in [17]. Because of
Theorem 1. An auction mechanism for MCS is truthful if it the regularity assumption, βi (·) is a monotonically increasing
satisfies w-Monotonicity, z-Monotonicity and critical payment. function. Therefore if wi > βi−1 (Ψ(B−i )−(Ψ(B)−βi (wi ))),
Proof: Based on the definition of truthfulness, it suffices it will result in a virtual cost higher than the opportunity cost.
to show that bidder i will not increase his/her payoff by So mobile user i will not be selected as a winner. Otherwise if
bidding any other bid (wi , Zi ) instead of (ci , Yi ). Lemma 4 wi < βi−1 (Ψ(B−i ) − (Ψ(B) − βi (wi ))), it will yield a virtual
has shown that bidder i will not increase his/her payoff cost lower than the opportunity cost. So mobile user i will be
by bidding (wi , Zi ) instead of (ci , Zi ). In Lemma 3, we selected as a winner. This completes the proof.
have proved that bidder i will not increase his/her payoff by Theorem 7. QIM-Opt is truthful.
bidding (ci , Zi ) instead of (ci , Yi ). Therefore, bidder i will
not increase his/her payoff by bidding any (wi , Zi ) instead of Proof: According to Lemmas 5, 6, and 7 as well as
(ci , Yi ). This completes the proof. Theorem 1, QIM-Opt is truthful. This completes the proof.

Next, we show that QIM with the optimal expected expen- Theorem 8. QIM-Opt is individually rational.
diture discussed in Section IV-A(referred to as QIM-Opt) is
truthful and individually rational. To prove the truthfulness, we Proof: If mobile user i bids true value (ci , Yi ), his/her
show w-Monotonicity, z-Monotonicity and critical payment payoff is ui = pi − ci = βi−1 (Ψ(B−i ) − Ψ(B) + βi (ci )) −
properties are preserved in QIM-Opt. ci . The optimality of Ψ(B) causes Ψ(B−i ) − Ψ(B) ≥ 0.
Moreover, since βi (·) is monotonically increasing, we have
Lemma 5. w-Monotonicity is satisfied by the Winner Selection ui ≥ 0. This completes the proof.
of QIM-Opt.