IEEE INFOCOM 2017 - IEEE Conference on Computer Communications

Towards Truthful Auction Mechanisms for Task

Assignment in Mobile Device Clouds
Xiumin Wang†,‡ , Xiaoming Chen§ , Weiwei Wu
†
School of Computer Science and Engineering, South China University of Technology, Guangzhou, China
‡
School of Computer and Information, Hefei University of Technology, Hefei, China
§
College of Information Science and Electronic Engineering, Zhejiang University, China

School of Computer Science and Engineering, Southeast University, Nanjing, China
Email: wxiumin@hfut.edu.cn, chen xiaoming@zju.edu.cn, weiweiwu@seu.edu.cn.
Corresponding author: Weiwei Wu, weiweiwu@seu.edu.cn.

Abstract—Despite the increased capabilities of mobile devices, ask mobile devices to share their resources or execute tasks
resource-demanded mobile applications still transcend what can for others, as these may also incur extra cost to themselves,
be accomplished on a single device. As such, mobile device cloud such as battery outage.
(MDC), an environment that enables computation-intensive tasks
to be performed among a set of nearby mobile devices, offers a In the literature, several works have been done to motivate
promising architecture to support real-time mobile applications. mobile devices to provide their resources in mobile cloud
To stimulate mobile devices to execute tasks for others, it is platform [13]–[17]. For example, [13] imposes a bill backlog
essential to design an incentive mechanism that appropriately on each mobile device. Once a device’s bill backlog exceeds
charges the owners of the tasks, acted as the buyers, and rewards a threshold, it will be unable to get services from others.
the mobile devices, acted as the sellers. In this paper, we propose
two truthful auction mechanisms for two different task models, Although the fairness of mobile devices can be well achieved,
heterogeneous and homogeneous task models, which assume the it might not appeal to many mobile devices, as the mobile
different and the same resource requirements of the tasks, re- devices are always forced to provide services. The work in
spectively. Specifically, for heterogeneous task model, we propose [14] also discusses the possible incentive schemes that can
an efficient heuristic winning bids determination algorithm to be designed in MDCs. However, it only considers the cost of
allocate the tasks, and decide the payment of each seller for its
winning bids. For homogeneous task model, we design an optimal the waiting time and cellular payment during task allocation,
winning bid determination algorithm, and propose a Vickrey- while omitting the practical resource requirement of tasks.
Clarke-Groves (VCG) based auction mechanism to determine the [15] constructs a Stackelberg game model to investigate the
payment of each bid. Both theoretical analysis and simulations interaction between the tasks and the mobile devices that can
show that the proposed auction mechanisms achieve several participate in task execution. The Stackelberg equilibrium is
desirable properties such as individual rationality, truthfulness
and computational efficiency. also achieved by appropriately determining the price charged
to each task and the amount of tasks that each mobile device
I. I NTRODUCTION can work on. Nevertheless, this approach does not capture the
In recent years, mobile devices including smart phones have preference of task execution. It is noted that tasks executed
become ubiquitous in people’s daily life, whereas they are still on different mobile devices may get different performances
seriously constrained by their limited battery capacities and including completion time, communication latency, etc. Under
computation capabilities [1]–[3]. Various application tasks, such a circumstance, different mobile devices should get
such as face recognition and natural language processing, ex- heterogeneous payments for task executions.
ceed the limits of mobile devices. To solve this issue, one may Auction [18], a popular trading form that can efficiently
offload their complex or resource-demanded tasks to remote allocate resources of sellers to buyers at competitive prices, has
cloud [4]–[7]. However, this may suffer large internet latency been widely used as one of the most popular incentive schemes
and energy consumption, due to long communication distance. in many areas. By viewing the resource trading system as an
Fortunately, recent work shows that computational offloading ecosystem, the auction mechanism can appropriately address
can also be performed among a set of mobile devices forming the conflicts between the buyer’s and seller’s interests, the
what we called Mobile Device Clouds (MDCs) [8], [9]. internal competitions among themselves, and guarantee the
Generally, utilizing the unused resources of the nearby mobile truthfulness of the submitted information. Based on this, [16],
devices in MDCs can achieve better system performance, e.g., [17] design two auction mechanisms for cloudlet resource
reducing the latency and network congestion with short-range sharing in mobile cloud computing. However, these works
communications [10]–[14]. Nevertheless, it is non-trivial to assume the homogeneous resource requirement of the tasks.
Moreover, [16], [17] limit the auction mechanism in a one-to-
This work was supported by the National Natural Science Foundation of one matching manner, which omits the fact that the resource-
China under Grants No. 61300212, 61300024, 61672154, 61571178, and
Jiangsu Provincial Natural Science Foundation of China under Grants No. rich devices can support the resource requirements of multiple
BK20130634. buyers in a practical system. Task allocation in MDCs also

978-1-5090-5336-0/17/$31.00 ©2017 IEEE

 IEEE INFOCOM 2017 - IEEE Conference on Computer Communications

involves a resource trading between the owners of the tasks we design an optimal auction mechanism based on VCG
and the mobile devices in the system. In this paper, we aim auction. Theoretical results also show the computational
to design an efficient auction mechanism to solve the task efficiency, individual rationality, and truthfulness of the
assignment problem in MDCs, by considering a more practical scheme.
model for resource requirements of the tasks and the resource • We validate the desirable properties of the proposed
availability of mobile devices. auction mechanisms through simulations.
Auction mechanisms in other areas have also been studied
The rest of the paper is organized as follows. Section II
in the literature [19]–[24]. Specifically, Vickrey-Clarke-Groves
describes the system model and problem formulation. The
(VCG) auction [19], [20] requires that the optimal allocation of
auction mechanisms for heterogeneous and homogeneous task
the resources must be guaranteed, otherwise, the truthfulness
models are designed in Section III and Section IV, respec-
cannot be achieved. [21] designs an auction mechanism for
tively. Section V presents the simulation results. Finally, we
crowdsourcing. However, it assumes that each mobile device
conclude the paper in Section VI.
holds a set of predefined services, and if one of the bids sub-
mitted by a mobile device wins the auction, all its predefined
services are traded, even if some of them are useless to the II. P ROBLEM F ORMULATION
tasks. Moreover, it does not consider the resource require-
ments of task executions. In a similar way, [22] proposes a In this section, we first introduce the auction model. Then,
location-aware auction mechanism when assigning tasks in we formulate the problem and present the desirable properties
crowdsourcing. A dynamic auction mechanism is proposed of the auction.
in [23], which captures the mobile users’ mobility patterns
through a sequence of correlated auctions. Nevertheless, most
of the previous works omit the resource requirements of the A. Auction Model
tasks and the resource availabilities at mobile devices, which is
We consider a set of m indivisible tasks in T =
quite important due to the resource scarcity of mobile devices
{t1 , t2 , · · · , tm } to be allocated to mobile devices in MDCs
in MDCs.
for executions. Without loss of generality, assume that running
Compared with the existing works, the auction problem
each task requires a certain amount of resources, e.g., CPU,
considered in this paper mainly has the following three differ-
memory, battery etc. Let rj be the amount of resources
ences: (1) the mobile tasks may require different amount of
required for task tj . Suppose that D = {d1 , d2 , · · · , dn } is the
resources for executions; (2) the number of tasks that can be
set of mobile devices in MDC that are willing to participate
executed at each mobile device is not a fixed value, depending
in task execution. Each mobile device di submits its bids for
on its resource availability and the resource requirements of
the tasks, Bi = {bi,1 , bi,2 , · · · , bi,m }, where bid bi,j ∈ Bi
the tasks allocated to it; (3) mobile device may have different
denotes the cost claimed by di  for executing task tj . To
preferences to the tasks allocated to it, because of different n
ease presentation, we use B = i=1 Bi to denote the set
computation complexities etc. To capture the interaction be-
of all the bids submitted by the sellers in D. It is noted
tween the owners of the tasks and the mobile devices partic-
that, the bids to different tasks may not be the same, even
ipating in the system, we aim to design an efficient auction
from the same mobile device. This is reasonable, as different
mechanism for task allocation in MDCs, where the tasks (or
tasks may consume different batteries or completion time on
saying the owners of the tasks) act as the buyers of mobile
mobile devices. Moreover, as each mobile device is also with
resources, and the mobile devices owning the resources act as
limited resources, we use Ri to denote the maximum amount
the sellers. In the rest of the paper, we use the terminology of
of resources that can be provided by di .
buyers and tasks, sellers and mobile devices, interchangeably.
Specifically, we consider two task models, heterogeneous and As mentioned above, in our auction model, the tasks re-
homogeneous task models, respectively. In heterogeneous task quiring the resources for executions act as the buyers, while
model, each task is assumed to require different amounts the mobile devices owning the resources act as the sellers. To
of resources for execution, while homogeneous task model assist the matching between the buyers and sellers, a trusted
assumes the same amount of resource requirement for each third party auctioneer is necessary to administrate the trading.
task. The main contributions of this paper can be summarized The detail of the auction process is described as follow.
as follows. • The auctioneer collects the tasks to be executed, including
• For heterogeneous task model, we design an efficient the information of the resource requirements of the tasks.
auction mechanism to allocate the tasks and determine Then, it initiates the auction to the sellers in D.
the payment. We prove that the proposed auction mech- • Each seller in D privately submits its bids and the
anism achieves certain properties, such as computational resource availability information to the auctioneer.
efficiency, individual rationality, and truthfulness. • Based on the bids and resource requirement/availability
• For homogeneous task model, we convert the task allo- information, the auctioneer follows a predefined auction
cation problem into finding a minimum weight bipartite mechanism to determine the set of winning bids and the
matching in an auxiliary bipartite graph. Based on that, corresponding payments of the sellers.
 IEEE INFOCOM 2017 - IEEE Conference on Computer Communications

To ease presentation, we define the following variants: • Truthfulness: The bid submitted by each mobile device
 should be truthful, i.e., bi,j = ci,j where ci,j is the true
1, if di wins its bid for task tj ; cost of executing task tj at device di .
xi,j = (1)
0, otherwise. In the following sections, we aim to design truthful auc-
pi,j : the final payment offered to di for bid bi,j . (2) tion mechanisms by considering two different task models,
heterogeneous and homogeneous task models, respectively. In
B. Problem Formulation heterogeneous task model, the tasks in T may require different
Due to the distributed nature of mobile devices, the real amounts of resources. As such, the winning bids determination
execution cost of each task is generally private and unknown problem defined in Eq. (4) is NP-hard, by a polynomial-time
to others. In this case, some selfish mobile devices may ma- reduction from Multiple Knapsack problem [25], a well-known
nipulate the claimed cost to gain higher utility. To differentiate NP-hard problem. For homogeneous task model, where the
from the submitted bid, we use ci,j to denote the true cost of tasks require the same amount of resources, we will show in
device di for executing task tj . Then, for each device di ∈ D, Section IV that the winning bids determination problem can
we can define its utility as follows: be converted into finding a minimum weight matching in an
m auxiliary bipartite graph, which can be optimally solved in

ui = (pi,j − xi,j ci,j ) , ∀di ∈ D, (3) polynomial time.
j=1
III. T RUTHFUL ACTION M ECHANISM FOR
which is the net revenue earned at device di by executing tasks H ETEROGENEOUS TASK M ODEL
for others. We now consider the heterogeneous task model, where the
Firstly, the auctioneer needs to determine the winning bids tasks require different amounts of resources. In this case, the
and allocate the tasks to the corresponding mobile devices. winning bids determination problem is a NP-hard problem, and
Such winning bids determination problem can be formulated finding the optimal solution is with high complexity. Hence,
as follows. we instead design a greedy algorithm which obtains a sub-
m 
 n optimal solution with low computational complexity. Then, we
min xi,j bi,j , (4) propose a payment scheme to determine the payoff of each bid.
i=1 j=1 Finally, we analyze the properties of the proposed mechanism.
subject to A. Greedy Winning Bids Determination Scheme
m
 For each bid submitted by the mobile devices, e.g., bi,j , we
xi,j rj ≤ Ri , ∀di ∈ D, (5) first define a parameter βi,j , named cost per unit resource, as
j=1
n
follows:

xi,j = 1, ∀tj ∈ T. (6) bi,j
βi,j = . (7)
i=1 rj
In the above formulation, the objective is to minimize the sum In general, the bid with smaller cost per unit resource should
of the claimed costs for executing tasks at mobile devices. The have higher chance to win the bid. Hence, based on this
constraint in Eq. (5) limits that the overall amount of resources parameter, we design a greedy algorithm to solve the winning
required by the tasks allocated to di is no more than Ri . The bid determination problem. The greedy rule is to pick the
constraint in Eq. (6) denotes that each task must be allocated next most unit-cost-efficient bid as the winning bid to allocate
to one and exactly one mobile device. the task, until all the tasks are assigned. Specifically, we
Secondly, based on the selected winning bids, the auctioneer define T as the set of the tasks that have been assigned with
further decides the final trading payment of the seller for each mobile devices so far, and B as the set of the bids that can
of its winning bid. It is noted that, seller di is willing to make still be chosenas the winning bids so far. Initially, we have
T = ∅, B = i=1 Bi and xi,j = 0. Then, in each step, we
m
trade with tj for its bid bi,j , only if the payment is no less
than its claimed cost bi,j . That is, pi,j ≥ bi,j . conduct the following procedure.
The goal of our work is to design a truthful auction • Select the bid, e.g., bi1 ,j1 , with the least cost per
mechanism that solves the above two problems. The designed unit resource among the bids in B. That is, βi1 ,j1 =
mechanism should achieve the following properties. min{βi,j |bi,j ∈ B}.
• Individual rationality: it means the utility of each • Add bi1 ,j1 as one of the winning bids, i.e., xi1 ,j1 = 1,
mobile device should be nonnegative, i.e., ui ≥ 0 for and allocate the task tj1 to mobile device di1 , i.e., T =

∀di ∈ D, which is a basic condition to stimulate the T {ti1 }. Correspondingly, remove bid βi1 ,j1 from B.
mobile devices participating in task execution. • We then remove the bids that may violate the resource
• Computational efficiency: The algorithm should be constraint of the device, or the bids that are useless for
solved in polynomial time, which is important to a future task allocations. That is, remove the bid bi,j from
practical system. T , if bi,j satisfies any of the following two conditions:
 IEEE INFOCOM 2017 - IEEE Conference on Computer Communications

Algorithm 1: Winning bids determination Algorithm 2: The payment for winning bid bi,j
begin begin
T = ∅, B = B; T = ∅, B = B\{bi,j };
xi,j = 0, for ∀i, j; xi ,j  = 0, for ∀bi ,j  ∈ B;
Calculate βi,j for each bid bi,j ∈ B; Calculate  βi ,j  for ∀bi ,j  ∈ B;
while T = T do while b  ∈B xi ,j < 1 do
i ,j
Choose the bid with the least cost per unit resource Choose the bid with the least cost per unit resource
from B, denoted as bi1 ,j1 ; from B, denoted as bi1 ,j1 ;
Set bi1 ,j1 as one of the winning bids, i.e., xi1 ,j1 = 1; Set bi1 ,j1 as one of the alternative winning bids, i.e.,
Remove bi1 ,j1 from B; xi1 ,j1 = 1;
for ∀bi,j ∈ B do Remove bi1 ,j1 from B;
Remove bi,j from B, if j = j1 ; Remove all the conflicting bids as in Algorithm 1;
end end
for ∀di ∈ D do Set pi,j = bi ,j for winning bid bi,j , where xi ,j = 1;
Remove each bid bi,j fromB, if  end
 
Ri − m j=1 xi,j rj ≤ min rj |tj ∈ T − T ;
 

end
end U  U  U  U 
end W W W W
  
   
    
– Task tj has already been allocated n with mobile
device in the previous steps, i.e., i=1 xi,j = 1. As
such, the bids to task tj become useless, and should G G G
be removed. 5  5  5 
– The resource left at device di is not enough to
support any other task in T − T. That is, Fig. 1. An example to illustrate the winning bids determination process
m  
Ri − xi,j rj ≤ min rj  |tj  ∈ T − T . (8)
j=1
The detail of deciding the payment for winning bid bi,j is
Under such a circumstance, di is unable to accept
presented in Algorithm 2. We continue the above process, until
any new winning bid.
considering all the winning bids in Bw .
Continue the above process, until all the tasks are allocated To illustrate the above process, we use Fig. 1 as an example.
with mobile devices, i.e., T = T . The detail of the above We assume that four tasks t1 , t2 , t3 , t4 are to be allocated to
process is presented in Algorithm 1. mobile devices d1 , d2 , d3 . The amount of resources required
B. Payment Strategy by each task or available at each device is given near each
Based on the winning bids determined in the above subsec- vertex. The edge between task tj and device di denotes the
tion, we then introduce how to decide the payment of each value of the bid bi,j . According to Algorithm 1, four bids
mobile device/seller for its winning bids. The payment should b3,1 , b3,3 , b1,4 , b2,2 will be selected as the winning bids. Fur-
be such determined that each seller will honestly reports its thermore, with Algorithm 2, the alternative winning bids for
real cost. It is noted that the bid that loses in the above b3,1 , b3,3 , b1,4 , b2,2 are b1,1 , b2,3 , b2,4 , b1,2 respectively. Hence,
subsection, will be paid by 0, i.e., pi,j = 0 if xi,j = 0. tasks 1, 2, 3, 4 are allocated to devices 3, 2, 3, 1 with payments
The main idea of our payment scheme is to decide the 2, 3, 3, 5 respectively.
payments of the winning bids one by one. Without loss of
generality, we use Bw as the set of winning bids selected in C. Theoretical Analysis
the above subsection, i.e., Bw = {bi,j |xi,j = 1}. The payment
of winning bid bi,j ∈ Bw is then decided as follows: We now analyze the properties of the proposed mechanism,
• Remove bid bi,j from the consideration bids in B. That including individual rationality, truthfulness, and computa-
m
is, B = i=1 Bi − {bi,j }. tional efficiency.
• Re-select the winning bids from set B as in Algorithm 1,
until the task tj is allocated with a mobile device, e.g.,
di . That is, the bid bi ,j wins its bid for task tj without Lemma 1 The proposed auction mechanism achieves the in-
the presence of bid bi,j . dividual rationality for each mobile device.
• We then set the payment for device di ’s winning bid bi,j
determined in Algorithm 1, as bi ,j (i.e., the bid sent by Proof: Firstly, for a mobile device di that has no winning
device di ). bids, according to Algorithm 2, its payoff is zero, i.e., ui = 0.
 IEEE INFOCOM 2017 - IEEE Conference on Computer Communications

Secondly, for a mobile device di that has winning bids, its Proof: Suppose that bik ,jk is one of the winning bids
utility can be calculated as determined in the k-th step with Algorithm 1. Then, there
m
 are k − 1 bids won in the previous k − 1 steps. Let
ui = (pi,j − xi,j ci,j ) (bi1 ,j1 , bi2 ,j2 , · · · , bik ,jk ) be the list of the winning bids that
j=1 have been determined in the first k steps. Assume that bik ,jk
 was replaced by another bid, e.g., bik ,jk , where bi,j = bik ,jk −δ
= (pi,j − bi,j ) . (9)
bi,j ∈Bw
and δ > 0. According to Algorithm 1, it is easy to get that
bid bik ,jk must also win in the k-th step or even earlier step.
We then show that the utility obtained for each of its winning Thus, we prove that Algorithm 1 is monotonic.
bids, e.g., bi,j ∈ Bw , is non-negative, pi,j − bi,j ≥ 0. When
bi,j wins, its claimed cost must be smaller than its payment Lemma 4 Each winning bid is paid the critical value, with
pi,j = bi ,j , as otherwise, bi ,j will win its bid instead of bi,j . Algorithm 2.
Hence, for each winning bid that truthfully reports its bid, its
utility must be nonnegative. Proof: Suppose that bik ,jk wins its bid for task tjk , in the
We then analyze the computational efficiency as follows: k-th step with Algorithm 1, and bi ,jk is an alternative winning
bid for task tjk without the presence of bik ,jk , determined
Lemma 2 The proposed winning bids determination and with Algorithm 2. In this case, the payment of bik ,jk is set
payment schemes both have polynomial-time computational to bi ,jk , i.e., pik ,jk = bi ,jk . It is obvious that another bid
complexity. bi ,jk = pik ,jk − δ, where δ > 0, would win, because its cost
per unit resource must be lower than the cost per unit resource
Proof: We first discuss the computation complexity of of bid bi ,jk . On the contrary, the bid bi ,jk = pik ,jk +δ, where
Algorithm 1. In Algorithm 1, we need to choose |T | winning δ > 0, will not win, as its cost per unit resource must be higher
bids. To select each winning bid, the bid with the least cost than that of bi ,jk . Hence, we prove the above lemma.
per unit resource in B must be found, and its complexity With the above analysis, we can analyze the truthfulness as
is O(mn). Furthermore, updating set B consumes at most follows.
O(mn) complexity. Then, the complexity of selecting one
winning bid is at most O(mn). Hence, the complexity of Theorem 1 The proposed auction mechanism is truthful.
selecting all the winning bids for the tasks in T is O(m2 n)
with Algorithm 1 . Proof: According to [26], we can easily get the theorem
We then analyze the complexity of Algorithm 2, which with Lemma 3 and Lemma 4.
determines the payment for each winning bid. As presented, to
obtain the payment of winning bid bi,j , Algorithm 2 needs to IV. AUCTION M ECHANISM FOR H OMOGENEOUS TASK
find an alternative bid for task tj , whose complexity is at most M ODEL
O(m2 n). Then, the computation complexity of determining In this section, we consider the homogeneous task model,
the payments of all the winning bids is O(m3 n). where each task is assumed to require the same amount of
To sum up, both Algorithm 1 and Algorithm 2 have resources, i.e., rj = r. We first introduce an optimal winning
polynomial-time complexity, which thus proves the above bids determination algorithm. Then, we propose a VCG-based
lemma. auction mechanism. Finally, we analyze the performance of
To demonstrate the truthfulness, we should prove that each the proposed mechanism.
mobile device will honestly submit all of its real costs.
According to [26], the proposed mechanism is truthful if A. Optimal Winning Bids Determination Scheme
and only if it satisfies two conditions: 1) the wining bids Since the maximum amount of resources available at di is
determination algorithm is monotonic, and 2) each winning Ri , the number of tasks that di can accept is constrained by
bid is paid the critical value. The definitions of monotonicity  Rri  and the overall number of tasks in T , m. In this case,
and critical value [26] are described as follows: the constraint in Eq. (5) becomes
m
 Ri
Definition 1 Monotonicity: For each bid bi,j , if bi,j wins, xi,j ≤ min  , m , ∀di ∈ D. (10)
then bid bi,j also wins, where bi,j = bi,j − δ and δ > 0. j=1
r

Then, the winning bids determination problem can be trans-

Definition 2 Critical Value: For each bid bi,j , there is a
formed into finding a minimum weight bipartite matching,
critical value bi,j . Then, if the bid declares a cost that is not
where the bipartite graph G(L1 L2 , E) is constructed as
larger than bi,j , it must win, otherwise, it will not win.
follows:
Based on above definitions, we can obtain that • For each task tj , we use a vertex lj to denoted it, and add
it to L1 . In other words, L1 = {lj |tj ∈ T, 1 ≤ j ≤ m}.
R
Lemma 3 The winning bids determination process in Algo- • For each device di , we add min  ri , m vertices to
rithm 1 is monotonic. L2 , where we use vi,k to denote the k-th vertex of
 IEEE INFOCOM 2017 - IEEE Conference on Computer Communications

device di . Hence, L2 = {vi,k |∀di ∈ D, 1 ≤ k ≤ O O O O

min  Rri , m }.
• For each pair of vertices (lj , vi,k ), where lj ∈ L1 , vi,k ∈
L2 , we add an edge between them. That is, E =
{(lj , vi,k )|∀lj ∈ L1 , ∀vi,k ∈ L2 }.
• For each edge (lj , vi,k ) ∈ E, we assign weight bi,j on it.

With the above graph G(L1 L2 , E), we can get that Y Y Y Y Y Y Y

Lemma 5 The winning bid determination problem of mini- Fig. 2. The auxiliary bipartite graph for Fig. 1 with rj = r = 2
mizing the overall cost is equivalent to finding
 a minimum
weight bipartite matching in graph G(L1 L2 , E), when
rj = r for ∀j.
B. Payment Strategy with VCG Mechanism
Proof: We
 first show that a feasible bipartite matching in In the above subsection, the winning bids can be optimally
graph G(L1 L2 , E) is one of the feasible solutions of the determined in polynomial time. To guarantee the truthfulness
problem defined in Section II-B. Without loss of generality, of the submitted bids, we now design a VCG auction mech-
we use  M = {(lj , vi,k )} to denote a feasible matching in anism to determine the payment to each mobile device that
G(L1 L2 , E). Moreover, we set xi,j = 1 if there exists a wins bids.
matching (li , vi,k ) ∈ M for ∀k ∈ {1, · · · , min  Rri , m ,
VCG auction is one of the most popular auctions that
otherwise, we set it to 0.
ensure the truthfulness when the optimal allocation can be
It is observed that for ∀di ∈ D, we have found. In VCG auction, the bid winning the game will be
 Ri paid with the “opportunity cost” that its presence incurs to
xi,j ≤ min  , m . (11) others. Without loss of generality, we use CBR and CB\{b R
r i,j }
(lj ,vi,k )∈M
to denote the minimum overall cost required under the above
This is reasonable, as for each device di , there are only  Rri  optimal winning bids determination scheme, with and without
vertices in L2 , and thus at most  Rri  matchings to it will the presence of the bid bi,j , by using the available resources
be chosen. Thus, the matching M satisfies theconstraint in R = {Ri |∀di ∈ D}. It is noted that CBR − xi,j bi,j denotes
Eq. (10). Moreover, the bipartite graph G(L1 L2 , E) is a the total cost except for bid bi,j under the above optimal
complete bipartite graph, which reveals that there exists a winning bids determination scheme. Then, bid bi,j ’s “oppor-
R
feasible matching with cardinality min{|L1 |, |L2 |}. Hence, the tunity cost” is defined as the difference between CB\{b i,j }
and
R
constraint in Eq. (6) CB − xi,j bi,j . In this way, bid bi,j ’s payment, denoted by pi,j ,
 can also be met. To sum up, a feasible
matching in G(L1 L2 , E) is one of the feasible solutions of can be derived as follows:
the winning bids determination problem. R

pi,j = CB\{b i,j }
− CBR − xi,j bi,j . (12)
Then, the matching with minimum weight in graph
G(L1 L2 , E) denotes a solution with minimum overall cost The detail of the designed VCG mechanism is presented in
of task allocation. Hence, our problem can beconverted into Algorithm 3.
finding a minimum weight matching in G(L1 L2 , E).
With the above Lemma, winning bids determination prob- C. Theoretical Analysis
lem with the objective of minimizing the overall cost can
be optimally solved by running an existing We now theoretically analyze the performance of the above
 minimum weight VCG-based auction mechanism on achieving the truthfulness,
matching algorithm in graph G(L1 L2 , E), which has
polynomial-time computational complexity [26]. Let M ∗ = individual rationality, and computational efficiency.
{(lj , vi,k )} be We first discuss the truthfulness.
 the optimal matching with minimum weight in
graph G(L1 L2 , E). Then, we can get the solution of win-
ning bids determination as follows: set xi,j = 1 if there exists Lemma 6 The proposed VCG-based auction mechanism
an edge (lj , vi,k ) ∈ M ∗ , where 1 ≤ k ≤ min  Rri , m , guarantees the truthfulness of the bids.
otherwise, we set xi,j = 0.
Still take Fig. 1 as an example. We assume that all the tasks Proof: We assume that when bid bi,j is submitted truth-
require the same amount of resources, e.g., rj = r = 2. Then, fully, i.e., bi,j = ci,j , the decision of task allocation is denoted
the auxiliary bipartite graph can be constructed in Fig. 2, where as {x∗i,j } with the optimal winning bids determination process
we omit the weights of the edges in the graph for simplicity. shown in the above subsection. We also use p∗i,j to denote the
By running the existing minimum weight matching algorithm, payment offered for bid bi,j with truthful information.
we can get optimal winning bids {b1,4 , b2,2 , b3,1 , b3,3 }. That Suppose that bid bi,j is submitted untruthfully, i.e., bi,j =
is, the tasks t1 , t2 , t3 , t4 will be assigned to devices 3, 2, 3, 1, ci,j . Then, there are two cases for bid bi,j : 1) xi,j = x∗i,j ; 2)
respectively. xi,j = x∗i,j .
 IEEE INFOCOM 2017 - IEEE Conference on Computer Communications

Algorithm 3: The payments of winning bids follows:

m
 m
begin   
Construct G(L1 L2 , E) by considering all the bids in B; u∗i − ui = p∗i,j − x∗i,j ci,j − (pi,j − xi,j ci,j )
Find aminimum weight matching M ∗ in graph j=1 j=1
G(L1 L2 , E); m
 
Set xi,j = 1 if there exists an edge (lj , vi,k ) belonging to = p∗i,j − x∗i,j ci,j − (pi,j − xi,j ci,j )
the found matching M ∗ , for ∀k; j=1
Calculate the overall cost CBR with {xi,j };
for ∀xi,j = 1 do
≥ 0. (16)

Construct new graph G (L1 L2 , E) without the To sum up, only if submitting the bids truthfully, the best
presence of bi,j ;
Finding a minimum weight matching M  in graph G ;
utility can be achieved, which thus proves the above lemma.
R
Calculate the overall cost CB\{b i,j }
on the found
matching M ;  Based on the above result, we now analyze the individual
R
 
Set pi,j = CB\{b i,j }
− CBR − bi,j ; rationality as follows.
end
for ∀xi,j = 0 do Lemma 7 With the above scheme, each mobile device
Set pi,j = 0; achieves nonnegative utility.
end
end Proof: As analyzed in Lemma 6, each bid must be
submitted truthfully, i.e., bi,j = ci,j . We now study the utility
that can be achieved for each bid, by considering two cases:
Case 1 (xi,j = x∗i,j ): If xi,j = x∗i,j = 0, it is easy to get 1) x∗i,j = 0, and 2) x∗i,j = 1.
that their utilities are the same and both 0. Alternatively, if Case 1 (x∗i,j = 0): In this case, the utility achieved for bid
xi,j = x∗i,j = 1, we can obtain that bi,j is 0.
 Case 2 (x∗i,j = 1): We can derive the utility of bid bi,j as
(R\{R }) {R −r }
CBR = CB\{bi,ji} i j
+ bi,j (13) follows:
 p∗i,j − x∗i,j ci,j
where (R\{Ri }) {Ri − rj } means that the left resources at
R
device di should exclude the resource used for task tj . Then, = CB\{c i,j }
− CBR . (17)
we have
R
 It is noted that CB\{c i,j }
must be no less than CBR . This is
R
pi,j = CB\{b i,j }
− CBR − bi,j R
because, CB\{ci,j } is only a feasible solution where bi,j fails
  
R
= CB\{b − C
(R\{Ri }) {Ri −rj }
+ b i,j − b i,j
its bid, and thus must be no less than the optimal solution CBR .
i,j } B\{bi,j }
(R\{R })

{Ri −rj }
Hence, the utility is no less than 0.
R
= CB\{b i,j }
− CB\{bi,ji} . (14) To sum up, for each truthful bid, the utility achieved must
 be nonnegative. Hence, the sum of the utilities of all the bids
R (R\{R }) {Ri −rj }
It is noted that CB\{b i,j }
and CB\{bi,ji}are both submitted by each device must be also nonnegative, which
independent of the bid bi,j submitted by device di . In this proves the above lemma.
case, p∗i,j = pi,j . Hence, the utilities are the same.
Case 2 (xi,j = x∗i,j ): We now derive the utility of bid bi,j Lemma 8 The proposed VCG-based auction mechanism is
in truthful case as follows: computationally efficient.
p∗i,j − x∗i,j ci,j Proof: As descried in Section IV-A, winning bids deter-
R

= CB\{c i,j }
− CBR − x∗i,j ci,j − x∗i,j ci,j mination can be optimally solved with an existing minimum
R weight matching algorithm, whose complexity is at most
= CB\{ci,j } − CBR
 (R\{R }) {R −x∗ r }  O((max{|L1 |, |L2 |)3 ). As |L1 | = m and |L2 | ≤ nm, the
R
+ x∗i,j ci,j
i i i,j j
= CB\{c i,j }
− CB\{ci,j } complexity of our winning bids determination process is at
   most O(n3 m3 ). Moreover, according to Algorithm 3, the
R (R\{R }) {Ri −xi,j rj }
≥ CB\{c i,j }
− CB\{ci,ji} + xi,j ci,j complexity of determining the payments for all the winning

R (R\{R }) {Ri −xi,j rj } bids is O(n3 m4 ). Thus, the proposed auction mechanism runs
= CB\{c i,j }
− CB\{bi,ji} − xi,j ci,j
 in polynomial time, and is computationally efficient.
R
= CB\{c i,j }
− CBR − xi,j bi,j − xi,j ci,j
V. S IMULATION R ESULTS
= pi,j − xi,j ci,j . (15)
In this section, we conduct simulations to evaluate the
Hence, the utility with truthful information ci,j is no less than performance of the proposed mechanisms. Specifically, we
the utility with untruthful information bi,j . study the properties such as individual rationality, truthfulness,
We then compare the utilities of the truthful and untruthful computational efficiency, and system efficiency. Similar to
cases at device di , denoted as u∗i and ui respectively, as [16], [17], we randomly generate the bids of the buyers
 IEEE INFOCOM 2017 - IEEE Conference on Computer Communications

(a) In heterogeneous case (b) In homogeneous case 0.25

The final payment The final payment

0.2 0.2 The submitted cost
The submitted cost 0.2

The bids/payments
The bids/payments

The utility of a single buyer

0.15 0.15
0.15

0.1 0.1

0.1
0.05 0.05

0.05
0 0
5 10 15 20 5 10 15 20 with heterogeneous tasks
The selected winning bids The selected winning bids with homogeneous tasks
0
0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2
Fig. 3. Performance on individual rationality The ratio of the submitted bid to the truthful cost

Fig. 4. Performance on the truthfulness

according to a uniform distribution within (0, 1]. The amount

of resources required by each task is randomly selected from
[1, 10], whereas the amount of resources available at each system efficiency is defined as the overall execution cost of
device is generated from [10, 30]. Moreover, these generated the tasks, which is the objective function defined in Eq. (4).
resource information must be able to guarantee that each task It is noted that in homogeneous task model, the minimum
can finally be allocated to a mobile device successfully, as execution cost can be achieved by running a minimum weight
otherwise, we cannot find any feasible solution of the problem, matching algorithm in polynomial time, which achieves the
i.e., violating the constraint in Eq. (6). best system efficiency. Hence, we here omit homogeneous
task model, and only investigate the system efficiency for
A. Performance on Individual Rationality heterogeneous task model.
We first investigate the performance of the proposed mech- For fairly comparison, we introduce a baseline algorithm,
anisms on individual rationality. named optimal task allocation scheme, by running an exhaus-
In this simulation, we study the proposed mechanisms for tive searching algorithm in exponential time. After optimally
both heterogeneous and homogeneous task models. As shown allocating tasks to the corresponding mobile devices, the
in Fig. 3, we set m = 40, n = 20. Among all the winning traditional VCG auction can then be used to decide the final
buyers and sellers, we select 20 pairs of them, and present their payments of the sellers, so as to guarantee the truthfulness of
submitted bids and the corresponding payments. From Fig. 3, the bids. As shown in Fig. 5, we set n = 20, and vary the
we can see that in both models, the final payment earned at number of tasks from 5 to 40. It is observed that our proposed
each seller must be no less than the bid it submitted. In other mechanism performs worse than the optimal task allocation
words, the individual rationality of the buyers can be achieved scheme in minimizing the overall execution cost. However,
with the proposed auction mechanisms, which validates the the gap between them is very small. Moreover, we present the
theoretical analysis. running times of the proposed mechanism and the optimal
B. Performance on the Truthfulness task assignment scheme in Fig. 6. It shows that although
the proposed mechanism achieves lower system efficiency, its
We now study the performance of the proposed mechanisms
running time is much less than the optimal task allocation
on guaranteeing the truthfulness of the bids.
scheme, which is particularly important for a large mobile
As shown in Fig. 4, the value in x-axis is defined as the
cloud system. Furthermore, from Fig. 5 and Fig. 6, we can also
ratio of the submitted bid to the truthful valuation, i.e., cbi,j .
i,j see that both the overall cost and the running time increase
For both heterogeneous and homogeneous task models, we
with the number of tasks.
randomly select one of the sellers, e.g., di , and generate its
bids bi,j according to the ratio shown in x-axis. Specifically, VI. C ONCLUSION
when the ratio is 1, the submitted bid bi,j is equal to the
truthful information ci,j . According to Fig. 4, it is observed In this paper, we consider mobile task assignment problem
that the maximum utility is achieved when the seller sends in MDCs. To capture the interactions between the owners
b of the tasks and the mobile devices, we construct an auc-
the truthful information, i.e., ci,j
i,j
= 1. Moreover, the larger
the gap between the submitted bid and the truthful valuation, tion model, where the mobile devices act as the sellers of
the lower the utility achieved at the seller. That is, only if resources, and the tasks act as the buyers. We design two
the seller submits truthful information, the best utility can be auction mechanisms for two task models, heterogeneous and
obtained, which guarantees the truthfulness of the bids. homogeneous tasks, respectively. Specifically, for heteroge-
neous task model, we design an efficient sub-optimal winning
C. Performance on System Efficiency and Running Time bids determination algorithm and decide the payment for
Finally, we study the performance of the proposed mech- each winning bid. For homogeneous task model, we show
anism on the system efficiency and the running time. Here, that the optimal winning bids determination problem can
 IEEE INFOCOM 2017 - IEEE Conference on Computer Communications

3
Optimal task assignment scheme [6] B. Chun, S. Ihm, P. Maniatis, M. Naik, and A. Patti, “Clonecloud: elastic
The proposed mechanism
execution between mobile device and cloud,” in Proceedings of the sixth
2.5 Conference on Computer Systems (EuroSys), pp. 301–314, Salzburg,
Austria, 2011.
[7] A. Khan, M. Othman, S. Madani and S. U. Khan, “A survey of mobile
The overal cost

2
cloud computing application models,” IEEE Communications Surveys &
Tutorials, vol. 16, no. 1, pp. 393–413, 2014.
1.5
[8] A. Mtibaa, A. Fahim, K. Harras, and M. Ammar, “Towards resource
sharing in mobile device clouds: Power balancing across mobile devices,”
1 in Proceedings of the second edition of the MCC workshop on Mobile
cloud computing (MCC), pp. 51–56, Hong Kong, 2013.
0.5 [9] A. Mtibaa, K. A. Harras, and A. Fahim, “Towards computational of-
floading in mobile device clouds,” in Proceedings of IEEE International
Conference on Cloud Computing Technology and Science, pp. 331–338,
0 Bristol, 2013.
5 10 15 20 25 30 35 40
The number of tasks [10] Y. Kao, B. Krishnamachari, M. Ra,and F. Bai, “Hermes: latency optimal
task assignment for resource-constrained mobile computing,” in Proceed-
Fig. 5. Performance on system efficiency for heterogeneous task model ings of IEEE International Conference on Computer Communications
(INFOCOM), pp. 1894–1902, Hong Kong, 2015.
[11] F. Liu, P. Shu, H. Jin, L. Ding, J. Yu, D. Niu, and B. Li, “Gearing
4 resource poor mobile devices with powerful clouds: architectures, chal-
x 10
lenges, and applications,” IEEE Wireless Communications, vol. 20, no. 3,
Optimal task assignment scheme pp. 14–22, 2013.
2
The proposed mechanism [12] S. Noor, R. Hasan and M. Haque, “Cellcould: a novel cost effective
formation of mobile cloud based on bidding incentives,” in Proceedings
of IEEE International Conference on Cloud Computing, pp. 200–207,
The running time (ms)

1.5 Anchorage, AK, 2014.

[13] J. Song, Y. Cui, M. Li, J. Qiu and R. Buyya, “Energy-traffic tradeoff
cooperative offloading for mobile cloud computing,” in Proceedings of
1 IEEE 22nd International Symposium of Quality of Service (IWQoS), pp.
284– 289, Hong Kong, 2014.
[14] E. Miluzzo, R. C. Ceres and Y. Chen, “Vision: mClouds - computing on
clouds of mobile devices,” in Proceedings of the third ACM workshop on
0.5
Mobile Cloud Computing and Services (MCS’12), pp. 9–14, New York,
NY, USA, 2012.
[15] X. Wang, X. Chen, W. Wu, N. An, L. Wang, “Cooperative application
0 execution in mobile cloud computing: a stackelberg game approach,”
5 10 15 20 25 30 35 40
IEEE Communications Letters, vol. 20, no. 5, pp. 946–949, 2016.
The number of tasks
[16] A. L. Jin, W. Song, P. Wang, D. Niyato, P. Ju, “Auction mechanisms to-
ward efficient resource sharing for cloudlets in mobile cloud computing,”
Fig. 6. Performance on running time for heterogeneous task model IEEE Transactions on Services Computing, vol. PP, no. 99, pp. 1–14, doi:
10.1109/TSC.2015.2430315, 2015.
[17] A. L. Jin, W. Song, W. Zhuang, “Auction-based resource allocation
for sharing cloudlets in mobile cloud computing,” IEEE Transactions
be converted into finding a minimum weight matching in on Emerging Topics in Computing, vol. PP, no. 99, pp. 1–12, doi:
10.1109/TETC.2015.2487865, 2015.
an auxiliary bipartite graph, based on which, a VCG-based [18] V. Krishna, Auction Theory, 2nd ed. Academic Press, Aug. 2009.
auction mechanism is designed to decide the payments of the [19] E. Clarke, “Multipart pricing of public goods,” Public Choice, vol. 11,
winning bids. Theoretical analysis and simulation results show no. 1, pp. 17–33, 1971.
[20] W. Vickrey, “Counterspeculation, auctions, and competitive sealed ten-
that the proposed auction mechanisms both achieve certain ders,” The Journal of Finance, vol. 16, no. 1, pp. 8–37, 2012.
desired properties including individual rationality, truthfulness, [21] X. Zhang, G. Xue, R. Yu, D. Yang, J. Tang, “Truthful incentive
and computational efficiency. mechanisms for crowdsourcing,” in Proceedings of IEEE Conference
on Computer Communications (INFOCOM), pp. 2830–2838, Kowloon,
Hong Kong, 2015.
R EFERENCES [22] Z. Feng, Y. Zhu, Q. Zhang, L. M. Ni and A. V. Vasilakos, “TRAC: Truth-
[1] J. Paczkowski, “iPhone owners would like to replace battery,” Available: ful auction for location-aware collaborative sensing in mobile crowdsourc-
http://digitaldaily.allthingsd.com/20090821/iphone-owners-wouldlike- to- ing,” in Proceedings of IEEE Conference on Computer Communications
replace-battery-att, Aug. 2009. (INFOCOM), pp. 1231–1239, Toronto, 2014.
[2] A. P. Miettinen, and J. K. Nurminen, “Energy efficiency of mobile clients [23] H. Zhang, B. Liu, H. Susanto, G. Xue and T. Sun, “Incentive Mechanism
in cloud computing,” in Proceedings of the 2nd USENIX conference on for Proximity-based Mobile Crowd Service Systems,” in Proceedings of
hot topics in cloud computing, pp. 1–7, Berkeley, CA, USA, 2010. IEEE Conference on Computer Communications (INFOCOM), pp. 1–9,
[3] M. Satyanarayanan, “Fundamental challenges in mobile computing” in San Francisco, CA, USA, 2016.
Proceedings of ACM Symposium on Principles of Distributed Computing [24] Y. Zhang, S. Tang, T. Chen, S. Zhong, “Competitive Auctions for Cost-
(PODC), pp. 1–7, Philttdelphia PA, USA, 1996. aware Cellular Traffic Offloading with Optimized Capacity Gain,” in
[4] E. Cuervo, A. Balasubramanian, D. Cho, A. Wolman, S. Saroiu, R. Proceedings of IEEE Conference on Computer Communications (INFO-
Chandra, and P. Bahl, “Maui: making smartphones last longer with code COM), pp. 1–9, San Francisco, CA, USA, 2016.
offload,” in Proceedings of the 8th International Conference on Mobile [25] C. Chekuri and S. Khanna, “A ptas for the multiple knapsack problem,”
Systems, Applications, and Services (ACM MobiSys), pp. 49–62, San in Proceedings of the ACM-SIAM Symposium on Discrete Algorithms
Francisco, CA, USA, 2010. (SODA), pp. 213–222, 2000.
[5] J. Wu, C. Yuen, N.-M. Cheung, J. Chen, C. W. Chen, “Enabling adaptive [26] N. Nisan, T. Roughgarden, E. Tardos, and V. V Vazirani, Algorithmic
high-frame-rate video streaming in mobile cloud gaming applications,” game theory, Cambridge University Press, 2007.
IEEE Transactions on Circuits and Systems for Video Technology, vol.
25, no. 12, pp. 1988–2001, 2015.