# Optimal Computing Resource Management Based on Utility Maximization in Mobile Crowdsourcing

Authors: Haoyu Meng; Ying Zhu; Ruilong Deng
Journal: Wireless Communications and Mobile Computing
 (2017)

---

## Abstract

Mobile crowdsourcing, as an emerging service paradigm, enables the computing resource requestor (CRR) to outsource computation tasks to each computing resource provider (CRP). Considering the importance of pricing as an essential incentive to coordinate the real-time interaction among the CRR and CRPs, in this paper, we propose an optimal real-time pricing strategy for computing resource management in mobile crowdsourcing. Firstly, we analytically model the CRR and CRPs behaviors in form of carefully selected utility and cost functions, based on concepts from microeconomics. Secondly, we propose a distributed algorithm through the exchange of control messages, which contain the information of computing resource demand/supply and real-time prices. We show that there exist real-time prices that can align individual optimality with systematic optimality. Finally, we also take account of the interaction among CRPs and formulate the computing resource management as a game with Nash equilibrium achievable via best response. Simulation results demonstrate that the proposed distributed algorithm can potentially benefit both the CRR and CRPs. The coordinator in mobile crowdsourcing can thus use the optimal real-time pricing strategy to manage computing resources towards the benefit of the overall system.


---

## Body

## 1. Introduction

With the explosion of mobile devices, mobile computing has become an overwhelming trend in the development of mobile networks and Internet of things (IoT) [1–3]. However, mobile devices are facing some limitations on various resources, for example, computation, memory, and energy [4–6]. To overcome these limitations, mobile cloud computing has become a promising solution to enable mobile devices to use cloud server resources via wireless communications and networking [7–9]. Such mobile devices, that is, mobile as a computing resource requestor (CRR), can improve the computation capability and energy efficiency by offloading computation tasks to cloud servers.On the other hand, with the proliferation of increasingly powerful mobile devices, mobile users can collaboratively form a mobile cloud to provide pervasive services, such as data collection, processing, and computing [10–12]. Empowered by these capabilities, mobile devices shift from service consumers to service providers, that is, mobile as a computing resource provider (CRP) [13–16]. With the unprecedentedly powerful mobile cloud, mobile crowdsourcing has been gaining momentum as a viable platform for solving very large-scale problems with the help of the masses [17–19]. By outsourcing computation tasks to the crowd, cost-effective and pervasive computing services can be achieved at a societal scale, using a possibly large number of mobile devices to collaborate together in a distributed way.Resource management is one of the fundamental issues in mobile networks and IoT for network utility maximization (NUM) [20–22]. In mobile crowdsourcing, the CRR wants to adjust its demand amount of computing resources so as to pursuit the maximum benefit, while each CRP wants to adjust its supply amount of computing resources so as to pursuit the maximum benefit. Given the importance of computing resource management, in this paper, we focus on the real-time interaction among the CRR and CRPs and introduce an optimal real-time pricing strategy. At first, we analytically model the CRR and CRPs behaviors in form of carefully selected utility and cost functions, based on concepts from microeconomics. Then, we formulate the computing resource management in mobile crowdsourcing as an optimization problem to maximize the satisfaction of the CRR while minimizing the aggregate expense of all CRPs in the system. We show that there exist real-time prices that can align individual optimality with systematic optimality, that is, under such prices, when the CRR and CRPs selfishly optimize their own benefits, they also automatically maximize the system welfare. In order to preserve everyone’s privacy, we propose a distributed algorithm for the CRR and CRPs to jointly determine the optimal real-time prices and computing resource demand/supply. The coordinator in mobile crowdsourcing can thus use the optimal real-time pricing strategy to manage computing resources towards the benefit of the overall system. Finally, we take account of the interaction among CRPs and formulate the computing resource management as a game with Nash equilibrium achievable via best response.To the best of our knowledge, this is an early effort towards providing a systematic framework of optimal computing resource management in mobile crowdsourcing. We hope that this pioneering work can throw light on coordinating the real-time interaction among the CRR and CRPs via the optimal real-time pricing strategy. Specifically, the original contributions of this paper are summarized as follows:(1)
We model the CRR and CRPs behaviors and formulate the computing resource management in mobile crowdsourcing as an optimization problem. The proposed distributed algorithm does not require anyone to reveal its private information.(2)
We take account of the interaction among CRPs and formulate the computing resource management as a game with Nash equilibrium achievable via best response.(3)
Simulation results demonstrate that both the CRR and CRPs will benefit from the proposed algorithm.The remainder of this paper is organized as follows. The system model is introduced in Section2. We solve the problem of the one-CRR and one-CRP case in Section 3 and that of the one-CRR and multi-CRP case in Section 4. Numerical results are illustrated in Section 5 before conclusions drawn in Section 6.


## 2. System Model

Consider a mobile crowdsourcing system consisting of one CRR, one or multiple CRPs, and a coordinator. The time cycle is divided intoT time slots. In a certain time slot, let d denote the computing resource demand of the CRR; Similarly, let si denote the computing resource supply of the CRP i(i=1,2,…,n, where n is the total number of CRPs).(
1) The Utility Function for the CRR. The computing resource demand of the CRR depends on the resource price and the priority of the task, which can be modeled by the utility function. Specifically, the utility function U· represents the satisfaction obtained by the CRR as a function of the computing resource demand d, which is nondecreasing and concave. In this paper, we consider the following quadratic utility function: (1)Ud=ωd-α2d20≤d≤ωαω2αd≥ωα,where ω,α>0 are predetermined parameters. It corresponds to a linear decreasing marginal benefit Vd≜∂Ud/∂d=ω-αd≥0 when 0≤d≤ω/α.(
2) The Cost Function for the CRP. The cost function Ci· represents the expense of supplying the computing resource si by the CRP i, which is increasing and strictly convex. In this paper, we consider the following quadratic cost function: (2)Cisi=aisi2+bisi+ci,where ai>0 and bi,ci≥0 are predetermined parameters.


## 3. One-CRR and One-CRP Case

At the beginning, consider a simple case for a mobile crowdsourcing system consisting of one CRR, one CRP, and a coordinator. We formulate the interaction among the CRR, CRP, and coordinator as local and global optimization problems and obtain the solution in a distributed way. The resource price is taken as an incentive to reach the balance between the supply and demand, as well as the maximum benefit of both the CRR and CRP.


### 3.1. Problem Formulation

Firstly, in a certain time slot, under the resource pricep, the benefit of the CRR by demanding the computing resource d is calculated as Brd=Ud-pd. The CRR wants to adjust its demand amount of computing resources so as to pursuit the maximum benefit. Thus the local optimization problem from the CRR perspective is (3)maxdUd-pd.Similarly, in a certain time slot, under the resource pricep, the benefit of the CRP by supplying the computing resource s is calculated as Bps=ps-Cs. The CRP wants to adjust its supply amount of computing resources so as to pursuit the maximum benefit. Thus the local optimization problem from the CRP perspective is (4)maxsps-Cs.From the system perspective, it is desirable that the satisfaction of the CRR is maximized and the expense of the CRP is minimized. Mathematically, we define the system welfare asWd,s=Ud-Cs, where s≥d. The individually optimal solution may not be systematically optimal under an arbitrary resource price. We take the utility function minus the cost function as the objective with the constraint that the supply should be at least equal to the demand. Thus the global optimization problem from the system perspective is (5)maxd,sUd-Css.t.s≥d.Note that the problem is a concave maximization problem, which can be solved by convex optimization techniques in a centralized way [23]. For example, we take the constraint into the objective by a Lagrangian multiplier. Thus the Lagrangian is defined as (6)Ld,s,λ=Ud-Cs+λs-d=Ud-λd+λs-Cs,where λ denotes the Lagrangian multiplier associated with the constraint in (5). By means of ∂L/∂d=∂L/∂s=∂L/∂λ=0 for (6), the coordinator wants to adjust the resource price (later we will show that λ can be interpreted as the resource price) so as to pursuit the maximum benefit of both the CRR and CRP.However, the arising challenge is that the coordinator needs to know the exact utility function of the CRP and cost function of the CRP. Since such information is private and no one wants to reveal any, the coordinator may not have sufficient information to solve problem (5). Nevertheless, the distributed algorithm will not require the coordinator to know the exact utility function of the CRP and cost function of the CRP and thus preserves their privacy. Therefore, in the following, we will present the distributed algorithm to approach the optimal resource price for computing resource management in mobile crowdsourcing.


### 3.2. Lagrange Duality

In order to solve problem (5) in a distributed way, we define the dual function as the maximum value of (6) over d,s: (7)Dλ=supd,s⁡Ld,s,λ=supd⁡Ud-λd+sups⁡λs-Cs.Furthermore, the Lagrange dual problem is (8)minλDλs.t.λ>0.We can solve the dual problem (8) instead of the primal problem (5) [23].Comparing (7) with (3) and (4), we find that the Lagrangian multiplier λ can be replaced by the resource price p to pursuit the global optimum. In this way, the dual problem can be decomposed into two separable subproblems: one is in the form of (3), which can be locally solved by the CRR, while the other is in the form of (4), which can be locally solved by the CRP. After both the CRR and CRP solve their own local optimization problem to obtain d∗ and s∗, the coordinator can solve the dual problem (8) to obtain p∗, which guarantees the constraint s∗≥d∗, such that the locally optimal solution will become globally optimal.Firstly, for the CRR, the locally optimal solution to (3) is (9)∂Brd∂d=∂Ud∂d-p=0⟹d∗=dp.Similarly, for the CRP, the locally optimal solution to (4) is (10)∂Bps∂s=p-∂Cs∂s=0⟹s∗=sp.Taking the resource pricep in place of the Lagrangian multiplier λ, together with the locally optimal solution d∗ and s∗, we rewrite the dual problem (8) as (11)minp>0Dp=Ud∗-pd∗+ps∗-Cs∗.The globally optimal solution to (11) is (12)∂Dp∂p=∂Ud∗∂d∗∂d∗∂p-d∗-p∂d∗∂p+s∗+p∂s∗∂p-∂Cs∗∂s∗∂s∗∂p=0.Note that from (9) and (10) we have ∂Ud∗/∂d∗=∂Cs∗/∂s∗=p, so (13)∂Dp∂p=s∗-d∗=0.Overall, by jointly solving (9), (10), and (13), we can obtain the optimal resource price p∗ and further calculate the specific d∗ and s∗, such that both the local and global optimums are achieved. In other words, the coordinator wants to make the locally optimal solution be globally optimal by adjusting the resource price.


### 3.3. Distributed Solution

In order to preserve everyone’s privacy, it is possible to approach the optimal resource price of the dual problem (11) in a distributed way [24–26]:(1)
The coordinator begins with any initial resource pricepk≥0 (k∈N+ is the iteration index) and announces it to both the CRR and CRP.(2)
On receiving the resource pricepk, the CRR updates its demand amount of computing resources dk by solving the local optimization problem dk=arg⁡maxd⁡Ud-pkd and feeds it back to the coordinator. Similarly, on receiving the resource price pk, the CRP also updates its supply amount of computing resources sk by solving the local optimization problem sk=arg⁡maxs⁡pks-Cs and feeds it back to the coordinator too.(3)
On receiving the local optimal computing resource demanddk and supply sk, the coordinator updates the resource price pk+1 for the next iteration using the following gradient projection method: (14)pk+1=pk-γ∂Dpk∂pk+=pk-γsk-dk+,whereγ>0 is the step size to adjust the convergence rate and x+ represents the larger one between x and 0.(4)
Repeat from(1) to (3) until the resource price remains unchanged.With the sufficiently small step sizeγ, the proposed distributed algorithm converges to the globally optimal supply s∗ and demand d∗, as long as the primal problem (5) is feasible. The reason is as follows. Since the utility function U· is concave and the cost function C· is convex, and thus the relationship from the supply s and demand d to the price p is monotone, there exists the sufficiently small step size γ that guarantees the convergence of the gradient projection method [27]. The proposed distributed algorithm converges when 0<γ<2/K, where K is the Lipschitz constant for the dual function: ∇Dp1-∇Dp22≤Kp1-p22. The convergence of the following proposed distributed algorithms is similar, which will be omitted due to the space limitation.The interaction among the CRR, CRP, and coordinator is shown in Figure1. Intuitively, from (14), if the supply is larger than the demand, that is, sk>dk, the coordinator will drop the price, that is, pk+1<pk; otherwise, if the supply is less than the demand, that is, sk<dk, the coordinator will rise the price, that is, pk+1>pk. In this way the iteration will converge to the globally optimal price which balances between the supply and demand.Figure 1
Interaction among CRR, CRP, and coordinator.Note that the globally optimal price which balances between the supply and demand will also achieve the maximum benefit of both the CRR and CRP. Otherwise, if the supply is less than the demand, the exceeded computing resource demanded by the CRR will not be satisfied, which reduces its benefit; similarly, if the supply is larger than the demand, the exceeded computing resource supplied by the CRP will be wasted, which reduces its benefit too.


## 3.1. Problem Formulation

Firstly, in a certain time slot, under the resource pricep, the benefit of the CRR by demanding the computing resource d is calculated as Brd=Ud-pd. The CRR wants to adjust its demand amount of computing resources so as to pursuit the maximum benefit. Thus the local optimization problem from the CRR perspective is (3)maxdUd-pd.Similarly, in a certain time slot, under the resource pricep, the benefit of the CRP by supplying the computing resource s is calculated as Bps=ps-Cs. The CRP wants to adjust its supply amount of computing resources so as to pursuit the maximum benefit. Thus the local optimization problem from the CRP perspective is (4)maxsps-Cs.From the system perspective, it is desirable that the satisfaction of the CRR is maximized and the expense of the CRP is minimized. Mathematically, we define the system welfare asWd,s=Ud-Cs, where s≥d. The individually optimal solution may not be systematically optimal under an arbitrary resource price. We take the utility function minus the cost function as the objective with the constraint that the supply should be at least equal to the demand. Thus the global optimization problem from the system perspective is (5)maxd,sUd-Css.t.s≥d.Note that the problem is a concave maximization problem, which can be solved by convex optimization techniques in a centralized way [23]. For example, we take the constraint into the objective by a Lagrangian multiplier. Thus the Lagrangian is defined as (6)Ld,s,λ=Ud-Cs+λs-d=Ud-λd+λs-Cs,where λ denotes the Lagrangian multiplier associated with the constraint in (5). By means of ∂L/∂d=∂L/∂s=∂L/∂λ=0 for (6), the coordinator wants to adjust the resource price (later we will show that λ can be interpreted as the resource price) so as to pursuit the maximum benefit of both the CRR and CRP.However, the arising challenge is that the coordinator needs to know the exact utility function of the CRP and cost function of the CRP. Since such information is private and no one wants to reveal any, the coordinator may not have sufficient information to solve problem (5). Nevertheless, the distributed algorithm will not require the coordinator to know the exact utility function of the CRP and cost function of the CRP and thus preserves their privacy. Therefore, in the following, we will present the distributed algorithm to approach the optimal resource price for computing resource management in mobile crowdsourcing.


## 3.2. Lagrange Duality

In order to solve problem (5) in a distributed way, we define the dual function as the maximum value of (6) over d,s: (7)Dλ=supd,s⁡Ld,s,λ=supd⁡Ud-λd+sups⁡λs-Cs.Furthermore, the Lagrange dual problem is (8)minλDλs.t.λ>0.We can solve the dual problem (8) instead of the primal problem (5) [23].Comparing (7) with (3) and (4), we find that the Lagrangian multiplier λ can be replaced by the resource price p to pursuit the global optimum. In this way, the dual problem can be decomposed into two separable subproblems: one is in the form of (3), which can be locally solved by the CRR, while the other is in the form of (4), which can be locally solved by the CRP. After both the CRR and CRP solve their own local optimization problem to obtain d∗ and s∗, the coordinator can solve the dual problem (8) to obtain p∗, which guarantees the constraint s∗≥d∗, such that the locally optimal solution will become globally optimal.Firstly, for the CRR, the locally optimal solution to (3) is (9)∂Brd∂d=∂Ud∂d-p=0⟹d∗=dp.Similarly, for the CRP, the locally optimal solution to (4) is (10)∂Bps∂s=p-∂Cs∂s=0⟹s∗=sp.Taking the resource pricep in place of the Lagrangian multiplier λ, together with the locally optimal solution d∗ and s∗, we rewrite the dual problem (8) as (11)minp>0Dp=Ud∗-pd∗+ps∗-Cs∗.The globally optimal solution to (11) is (12)∂Dp∂p=∂Ud∗∂d∗∂d∗∂p-d∗-p∂d∗∂p+s∗+p∂s∗∂p-∂Cs∗∂s∗∂s∗∂p=0.Note that from (9) and (10) we have ∂Ud∗/∂d∗=∂Cs∗/∂s∗=p, so (13)∂Dp∂p=s∗-d∗=0.Overall, by jointly solving (9), (10), and (13), we can obtain the optimal resource price p∗ and further calculate the specific d∗ and s∗, such that both the local and global optimums are achieved. In other words, the coordinator wants to make the locally optimal solution be globally optimal by adjusting the resource price.


## 3.3. Distributed Solution

In order to preserve everyone’s privacy, it is possible to approach the optimal resource price of the dual problem (11) in a distributed way [24–26]:(1)
The coordinator begins with any initial resource pricepk≥0 (k∈N+ is the iteration index) and announces it to both the CRR and CRP.(2)
On receiving the resource pricepk, the CRR updates its demand amount of computing resources dk by solving the local optimization problem dk=arg⁡maxd⁡Ud-pkd and feeds it back to the coordinator. Similarly, on receiving the resource price pk, the CRP also updates its supply amount of computing resources sk by solving the local optimization problem sk=arg⁡maxs⁡pks-Cs and feeds it back to the coordinator too.(3)
On receiving the local optimal computing resource demanddk and supply sk, the coordinator updates the resource price pk+1 for the next iteration using the following gradient projection method: (14)pk+1=pk-γ∂Dpk∂pk+=pk-γsk-dk+,whereγ>0 is the step size to adjust the convergence rate and x+ represents the larger one between x and 0.(4)
Repeat from(1) to (3) until the resource price remains unchanged.With the sufficiently small step sizeγ, the proposed distributed algorithm converges to the globally optimal supply s∗ and demand d∗, as long as the primal problem (5) is feasible. The reason is as follows. Since the utility function U· is concave and the cost function C· is convex, and thus the relationship from the supply s and demand d to the price p is monotone, there exists the sufficiently small step size γ that guarantees the convergence of the gradient projection method [27]. The proposed distributed algorithm converges when 0<γ<2/K, where K is the Lipschitz constant for the dual function: ∇Dp1-∇Dp22≤Kp1-p22. The convergence of the following proposed distributed algorithms is similar, which will be omitted due to the space limitation.The interaction among the CRR, CRP, and coordinator is shown in Figure1. Intuitively, from (14), if the supply is larger than the demand, that is, sk>dk, the coordinator will drop the price, that is, pk+1<pk; otherwise, if the supply is less than the demand, that is, sk<dk, the coordinator will rise the price, that is, pk+1>pk. In this way the iteration will converge to the globally optimal price which balances between the supply and demand.Figure 1
Interaction among CRR, CRP, and coordinator.Note that the globally optimal price which balances between the supply and demand will also achieve the maximum benefit of both the CRR and CRP. Otherwise, if the supply is less than the demand, the exceeded computing resource demanded by the CRR will not be satisfied, which reduces its benefit; similarly, if the supply is larger than the demand, the exceeded computing resource supplied by the CRP will be wasted, which reduces its benefit too.


## 4. One-CRR and Multi-CRP Case

Now, consider another case for a mobile crowdsourcing system consisting of one CRR, multiple CRPs, and a coordinator.


### 4.1. Without Interaction among CRPs

Firstly, we focus on the interaction only between the coordinator and each CRP; that is, each CRP is expected to respond to the resource price announced by the coordinator. Under this paradigm, each CRP only communicates with the coordinator as depicted in Figure2, without the interaction among CRPs.Figure 2
Without interaction among CRPs.The problem formulation of this case is similar to that in Section3.1. The local optimization problem from the CRR perspective is the same as (3). Similarly, in a certain time slot, under the resource price p, the benefit of each CRP by supplying the computing resource si is calculated as (15)Bpisi=psi-Cisi.Each CRP wants to adjust its supply amount of computing resources so as to pursuit the maximum benefit. Thus the local optimization problem from each CRP perspective is (16)minsipsi-Cisi.From the system perspective, it is desirable that the satisfaction of the CRR is maximized and the sum of the expense of all CRPs is minimized. We take the utility function minus the sum of all cost functions as the objective with the constraint that the total supply should be at least equal to the demand. Thus the global optimization problem from the system perspective is(17)maxd,sUd-∑i=1nCisis.t.∑i=1nsi≥d.Note that the problem is a concave maximization problem, which can be solved by convex optimization techniques in a centralized way; for example, the Lagrangian is defined as(18)Ld,s,λ=Ud-∑i=1nCisi+λ∑i=1nsi-d=Ud-λd+∑i=1nλsi-Cisi,where λ is the Lagrangian multiplier associated with the constraint in (17).Similarly, in order to solve problem (17) in a distributed way, we define the dual function as the maximum value of (18) over d,s: (19)Dλ=supd,s⁡Ld,s,λ=supd⁡Ud-λd+∑i=1nsupsi⁡λsi-Cisi.Furthermore, the Lagrange dual problem is (20)minp>0Dp=Ud∗-pd∗+∑i=1npsi∗-Cisi∗.We can solve the dual problem (20) instead of the primal problem (17) [23].Similarly, in order to preserve everyone’s privacy, it is possible to approach the optimal resource price of the dual problem (20) in a distributed way, which is similar to that in Section 3.3 [28–30]:(1)
The coordinator begins with any initial resource pricepk≥0 and announces it to the CRR and all CRPs.(2)
On receiving the resource pricepk, the CRR updates its demand amount of computing resources dk by solving the local optimization problem dk=arg⁡maxd⁡Ud-pkd and feeds it back to the coordinator; similarly, on receiving the resource price pk, each CRP also updates its supply amount of computing resources sik by solving the local optimization problem sik=arg⁡maxsi⁡pksi-Cisi and feeds it back to the coordinator too.(3)
On receiving the local optimal computing resource demanddk and supply sk, the coordinator updates the resource price pk+1 for the next iteration using the following gradient projection method: (21)pk+1=pk-γ∂Dpk∂pk+=pk-γ∑i=1nsik-dk+.(4)
Repeat from(1) to (3) until the resource price remains unchanged.The interaction among the CRR, each CRP, and coordinator is shown in Figure3.Figure 3
Interaction among CRR, each CRP, and coordinator.


### 4.2. With Interaction among CRPs

Rather than focusing only on how each CRP behaves individually, we propose a framework with interaction among CRPs via message exchanges; for example, each CRP may share the information of its computing resource supplysi among others. As depicted in Figure 4, the blue arrows represent the two-way communication between the CRR and each CRP, while the red bidirectional arrows correspond to the interaction among CRPs.Figure 4
With interaction among CRPs.From (9) we know that p=∂Ud/∂d is the local optimal resource price for the CRR. From the above we also know that the global optimum exists at d=∑i=1nsi, by means of ∂L/∂λ=0 for (18). Therefore, in a certain time slot, if each CRP supplies the computing resource si, then the local optimal resource price for the CRR is calculated as (22)p=∂Ud∂dd=∑i=1nsi≜U′∑i=1nsi.


#### 4.2.1. Game Theory

Game theory is a study of selfish and rational players and a formal model of interactive decision-making situation [31]. A game G=N,S,Pi· consists of the following three components [32].(
1) Players. N={1,2,…,n} is a finite set of players, where n is the total number of players in the game.(
2) Strategies. S=×inSi is the strategy space of the game and each player i chooses a strategy si from its strategy set Si. Generally we denote a strategy vector by s=si,s-i, where s-i≜s1,…,si-1,si+1,…,sn are the strategies chosen by all the other players in the game.(
3) Payoff Functions. Pi· is a finite set of payoff functions. The payoff Pi of the player i is determined by the strategy vector s. Each selfish and rational player wishes to choose the optimal strategy si according to the other players’ strategies s-i to maximize its own payoff Pisi,s-i.Nash equilibrium (NE) is the most important concept of equilibrium condition in game theory. NE is such a static stable strategy vector that no player has any benefit from unilaterally deviating from this strategy. A strategy vectors∗=si∗,s-i∗ is called NE if and only if Pis∗≥Pisi,s-i∗,∀i∈N,∀si∈Si.Theorem 1.
A game can be shown to have NE if the following conditions are satisfied [33]:(1)
The player set is finite.(2)
The strategy sets are closed, bounded, and convex.(3)
The payoff functions are continuous in strategy space and quasi-concave.AnS-modular game restricts payoff function Pi· such that ∀i∈N either (23a) or (23b) is satisfied.(23a)∂2Pis∂si∂sj≥0∀j≠i∈N(23b)∂2Pis∂si∂sj≤0∀j≠i∈N.When (23a) is satisfied, the game is said to be supermodular, while when (23b) is satisfied, the game is said to be submodular. We can use best response to converge to NE [33].


#### 4.2.2. Game among CRPs

A basic modeling assumption in this paper is that each CRP behaves rationally in a self-interested manner. Each one wants to adjust its strategy to maximize its own payoff. We model the computing resource management in mobile crowdsourcing as a game among CRPs:(
1) Players. All CRPs in the mobile crowdsourcing system are the players in the game.(
2) Strategies. The strategy si of the player i is its computing resource supply.(
3) Payoff Functions. Taking (22) into (15), we have the payoff function of each CRP: (24)Pisi,s-i=U′∑i=1nsisi-Cisi.Taking (1) and (2) into (24), we have, ∀i∈N, (25)∂2Pis∂si∂sj=-α<0∀j≠i∈N.Based on Theorem 1, NE is considered to be the solution of the game. Meanwhile, the game corresponds to the submodular game, and we can use best response to converge to NE. Best response allows that, at each iteration, each player adapts its strategy to the strategies of others to maximize its own payoff. We design the best response algorithm as follows.(1)
Initial condition: each player chooses a random strategy.(2)
Adaption condition: each player chooses an optimal strategy according to the strategies of others to improve its own payoff:(26)si∗=argmaxsi∈SiPisi,s-i.Note that, at each iteration, each player updates its strategy while the others keep their strategies fixed.(3)
Repeat(2) until each player does not revise its strategy.


#### 4.2.3. Distributed Solution

Note that (26) is a concave maximization problem, which can be solved by convex optimization techniques in a centralized way. However, the arising challenge is that each CRP needs to know the exact utility function of the CRR. Since such information is private and the CRR does not want to reveal any, each CRP may not have sufficient information to solve problem (26). In order to preserve the CRR’s privacy, it is possible to approach the optimal strategy of the optimization problem (26) in a distributed way [34–36]:(1)
Each CRP shares the information of its current computing resource supplysi among others.(2)
The CRPi begins with any initial computing resource supply sik≥0 and aggregates the total supply of all CRPs, that is, sk≜sik+∑j=1,j≠insj, and sends it to the CRR.(3)
On receiving the total supply, the CRR calculates the value ofU′sk and U′′sk and feeds them back to the CRP i.(4)
On receiving the feedback, the CRPi updates its computing resource supply sik+1 for the next iteration using the following gradient projection method: (27)sik+1=sik+γ∂Pisik,s-i∂sik+=sik+γ-Ci′sik+U′sk+sikU′′sk+.(5)
Repeat from(2) to (4) until the CRP i does not revise its computing resource supply.The interaction among the CRR and each CRP is shown in Figure5.Figure 5
Interaction among CRR and each CRP.


## 4.1. Without Interaction among CRPs

Firstly, we focus on the interaction only between the coordinator and each CRP; that is, each CRP is expected to respond to the resource price announced by the coordinator. Under this paradigm, each CRP only communicates with the coordinator as depicted in Figure2, without the interaction among CRPs.Figure 2
Without interaction among CRPs.The problem formulation of this case is similar to that in Section3.1. The local optimization problem from the CRR perspective is the same as (3). Similarly, in a certain time slot, under the resource price p, the benefit of each CRP by supplying the computing resource si is calculated as (15)Bpisi=psi-Cisi.Each CRP wants to adjust its supply amount of computing resources so as to pursuit the maximum benefit. Thus the local optimization problem from each CRP perspective is (16)minsipsi-Cisi.From the system perspective, it is desirable that the satisfaction of the CRR is maximized and the sum of the expense of all CRPs is minimized. We take the utility function minus the sum of all cost functions as the objective with the constraint that the total supply should be at least equal to the demand. Thus the global optimization problem from the system perspective is(17)maxd,sUd-∑i=1nCisis.t.∑i=1nsi≥d.Note that the problem is a concave maximization problem, which can be solved by convex optimization techniques in a centralized way; for example, the Lagrangian is defined as(18)Ld,s,λ=Ud-∑i=1nCisi+λ∑i=1nsi-d=Ud-λd+∑i=1nλsi-Cisi,where λ is the Lagrangian multiplier associated with the constraint in (17).Similarly, in order to solve problem (17) in a distributed way, we define the dual function as the maximum value of (18) over d,s: (19)Dλ=supd,s⁡Ld,s,λ=supd⁡Ud-λd+∑i=1nsupsi⁡λsi-Cisi.Furthermore, the Lagrange dual problem is (20)minp>0Dp=Ud∗-pd∗+∑i=1npsi∗-Cisi∗.We can solve the dual problem (20) instead of the primal problem (17) [23].Similarly, in order to preserve everyone’s privacy, it is possible to approach the optimal resource price of the dual problem (20) in a distributed way, which is similar to that in Section 3.3 [28–30]:(1)
The coordinator begins with any initial resource pricepk≥0 and announces it to the CRR and all CRPs.(2)
On receiving the resource pricepk, the CRR updates its demand amount of computing resources dk by solving the local optimization problem dk=arg⁡maxd⁡Ud-pkd and feeds it back to the coordinator; similarly, on receiving the resource price pk, each CRP also updates its supply amount of computing resources sik by solving the local optimization problem sik=arg⁡maxsi⁡pksi-Cisi and feeds it back to the coordinator too.(3)
On receiving the local optimal computing resource demanddk and supply sk, the coordinator updates the resource price pk+1 for the next iteration using the following gradient projection method: (21)pk+1=pk-γ∂Dpk∂pk+=pk-γ∑i=1nsik-dk+.(4)
Repeat from(1) to (3) until the resource price remains unchanged.The interaction among the CRR, each CRP, and coordinator is shown in Figure3.Figure 3
Interaction among CRR, each CRP, and coordinator.


## 4.2. With Interaction among CRPs

Rather than focusing only on how each CRP behaves individually, we propose a framework with interaction among CRPs via message exchanges; for example, each CRP may share the information of its computing resource supplysi among others. As depicted in Figure 4, the blue arrows represent the two-way communication between the CRR and each CRP, while the red bidirectional arrows correspond to the interaction among CRPs.Figure 4
With interaction among CRPs.From (9) we know that p=∂Ud/∂d is the local optimal resource price for the CRR. From the above we also know that the global optimum exists at d=∑i=1nsi, by means of ∂L/∂λ=0 for (18). Therefore, in a certain time slot, if each CRP supplies the computing resource si, then the local optimal resource price for the CRR is calculated as (22)p=∂Ud∂dd=∑i=1nsi≜U′∑i=1nsi.


### 4.2.1. Game Theory

Game theory is a study of selfish and rational players and a formal model of interactive decision-making situation [31]. A game G=N,S,Pi· consists of the following three components [32].(
1) Players. N={1,2,…,n} is a finite set of players, where n is the total number of players in the game.(
2) Strategies. S=×inSi is the strategy space of the game and each player i chooses a strategy si from its strategy set Si. Generally we denote a strategy vector by s=si,s-i, where s-i≜s1,…,si-1,si+1,…,sn are the strategies chosen by all the other players in the game.(
3) Payoff Functions. Pi· is a finite set of payoff functions. The payoff Pi of the player i is determined by the strategy vector s. Each selfish and rational player wishes to choose the optimal strategy si according to the other players’ strategies s-i to maximize its own payoff Pisi,s-i.Nash equilibrium (NE) is the most important concept of equilibrium condition in game theory. NE is such a static stable strategy vector that no player has any benefit from unilaterally deviating from this strategy. A strategy vectors∗=si∗,s-i∗ is called NE if and only if Pis∗≥Pisi,s-i∗,∀i∈N,∀si∈Si.Theorem 1.
A game can be shown to have NE if the following conditions are satisfied [33]:(1)
The player set is finite.(2)
The strategy sets are closed, bounded, and convex.(3)
The payoff functions are continuous in strategy space and quasi-concave.AnS-modular game restricts payoff function Pi· such that ∀i∈N either (23a) or (23b) is satisfied.(23a)∂2Pis∂si∂sj≥0∀j≠i∈N(23b)∂2Pis∂si∂sj≤0∀j≠i∈N.When (23a) is satisfied, the game is said to be supermodular, while when (23b) is satisfied, the game is said to be submodular. We can use best response to converge to NE [33].


### 4.2.2. Game among CRPs

A basic modeling assumption in this paper is that each CRP behaves rationally in a self-interested manner. Each one wants to adjust its strategy to maximize its own payoff. We model the computing resource management in mobile crowdsourcing as a game among CRPs:(
1) Players. All CRPs in the mobile crowdsourcing system are the players in the game.(
2) Strategies. The strategy si of the player i is its computing resource supply.(
3) Payoff Functions. Taking (22) into (15), we have the payoff function of each CRP: (24)Pisi,s-i=U′∑i=1nsisi-Cisi.Taking (1) and (2) into (24), we have, ∀i∈N, (25)∂2Pis∂si∂sj=-α<0∀j≠i∈N.Based on Theorem 1, NE is considered to be the solution of the game. Meanwhile, the game corresponds to the submodular game, and we can use best response to converge to NE. Best response allows that, at each iteration, each player adapts its strategy to the strategies of others to maximize its own payoff. We design the best response algorithm as follows.(1)
Initial condition: each player chooses a random strategy.(2)
Adaption condition: each player chooses an optimal strategy according to the strategies of others to improve its own payoff:(26)si∗=argmaxsi∈SiPisi,s-i.Note that, at each iteration, each player updates its strategy while the others keep their strategies fixed.(3)
Repeat(2) until each player does not revise its strategy.


### 4.2.3. Distributed Solution

Note that (26) is a concave maximization problem, which can be solved by convex optimization techniques in a centralized way. However, the arising challenge is that each CRP needs to know the exact utility function of the CRR. Since such information is private and the CRR does not want to reveal any, each CRP may not have sufficient information to solve problem (26). In order to preserve the CRR’s privacy, it is possible to approach the optimal strategy of the optimization problem (26) in a distributed way [34–36]:(1)
Each CRP shares the information of its current computing resource supplysi among others.(2)
The CRPi begins with any initial computing resource supply sik≥0 and aggregates the total supply of all CRPs, that is, sk≜sik+∑j=1,j≠insj, and sends it to the CRR.(3)
On receiving the total supply, the CRR calculates the value ofU′sk and U′′sk and feeds them back to the CRP i.(4)
On receiving the feedback, the CRPi updates its computing resource supply sik+1 for the next iteration using the following gradient projection method: (27)sik+1=sik+γ∂Pisik,s-i∂sik+=sik+γ-Ci′sik+U′sk+sikU′′sk+.(5)
Repeat from(2) to (4) until the CRP i does not revise its computing resource supply.The interaction among the CRR and each CRP is shown in Figure5.Figure 5
Interaction among CRR and each CRP.


## 4.2.1. Game Theory

Game theory is a study of selfish and rational players and a formal model of interactive decision-making situation [31]. A game G=N,S,Pi· consists of the following three components [32].(
1) Players. N={1,2,…,n} is a finite set of players, where n is the total number of players in the game.(
2) Strategies. S=×inSi is the strategy space of the game and each player i chooses a strategy si from its strategy set Si. Generally we denote a strategy vector by s=si,s-i, where s-i≜s1,…,si-1,si+1,…,sn are the strategies chosen by all the other players in the game.(
3) Payoff Functions. Pi· is a finite set of payoff functions. The payoff Pi of the player i is determined by the strategy vector s. Each selfish and rational player wishes to choose the optimal strategy si according to the other players’ strategies s-i to maximize its own payoff Pisi,s-i.Nash equilibrium (NE) is the most important concept of equilibrium condition in game theory. NE is such a static stable strategy vector that no player has any benefit from unilaterally deviating from this strategy. A strategy vectors∗=si∗,s-i∗ is called NE if and only if Pis∗≥Pisi,s-i∗,∀i∈N,∀si∈Si.Theorem 1.
A game can be shown to have NE if the following conditions are satisfied [33]:(1)
The player set is finite.(2)
The strategy sets are closed, bounded, and convex.(3)
The payoff functions are continuous in strategy space and quasi-concave.AnS-modular game restricts payoff function Pi· such that ∀i∈N either (23a) or (23b) is satisfied.(23a)∂2Pis∂si∂sj≥0∀j≠i∈N(23b)∂2Pis∂si∂sj≤0∀j≠i∈N.When (23a) is satisfied, the game is said to be supermodular, while when (23b) is satisfied, the game is said to be submodular. We can use best response to converge to NE [33].


## 4.2.2. Game among CRPs

A basic modeling assumption in this paper is that each CRP behaves rationally in a self-interested manner. Each one wants to adjust its strategy to maximize its own payoff. We model the computing resource management in mobile crowdsourcing as a game among CRPs:(
1) Players. All CRPs in the mobile crowdsourcing system are the players in the game.(
2) Strategies. The strategy si of the player i is its computing resource supply.(
3) Payoff Functions. Taking (22) into (15), we have the payoff function of each CRP: (24)Pisi,s-i=U′∑i=1nsisi-Cisi.Taking (1) and (2) into (24), we have, ∀i∈N, (25)∂2Pis∂si∂sj=-α<0∀j≠i∈N.Based on Theorem 1, NE is considered to be the solution of the game. Meanwhile, the game corresponds to the submodular game, and we can use best response to converge to NE. Best response allows that, at each iteration, each player adapts its strategy to the strategies of others to maximize its own payoff. We design the best response algorithm as follows.(1)
Initial condition: each player chooses a random strategy.(2)
Adaption condition: each player chooses an optimal strategy according to the strategies of others to improve its own payoff:(26)si∗=argmaxsi∈SiPisi,s-i.Note that, at each iteration, each player updates its strategy while the others keep their strategies fixed.(3)
Repeat(2) until each player does not revise its strategy.


## 4.2.3. Distributed Solution

Note that (26) is a concave maximization problem, which can be solved by convex optimization techniques in a centralized way. However, the arising challenge is that each CRP needs to know the exact utility function of the CRR. Since such information is private and the CRR does not want to reveal any, each CRP may not have sufficient information to solve problem (26). In order to preserve the CRR’s privacy, it is possible to approach the optimal strategy of the optimization problem (26) in a distributed way [34–36]:(1)
Each CRP shares the information of its current computing resource supplysi among others.(2)
The CRPi begins with any initial computing resource supply sik≥0 and aggregates the total supply of all CRPs, that is, sk≜sik+∑j=1,j≠insj, and sends it to the CRR.(3)
On receiving the total supply, the CRR calculates the value ofU′sk and U′′sk and feeds them back to the CRP i.(4)
On receiving the feedback, the CRPi updates its computing resource supply sik+1 for the next iteration using the following gradient projection method: (27)sik+1=sik+γ∂Pisik,s-i∂sik+=sik+γ-Ci′sik+U′sk+sikU′′sk+.(5)
Repeat from(2) to (4) until the CRP i does not revise its computing resource supply.The interaction among the CRR and each CRP is shown in Figure5.Figure 5
Interaction among CRR and each CRP.


## 5. Results and Discussion

We provide numerical examples to evaluate the proposed distributed approach.


### 5.1. One-CRR and One-CRP Case

Consider a mobile crowdsourcing system with one CRR and one CRP. The simulation parameters are set asω=3, α=0.5, a=0.1, b=0.5, and c=0. That is, we assume that the CRR has the utility function Ud=3d-0.5/2d2, while the CRP has the cost function Cs=0.1s2+0.5s. Firstly, in Figure 6, we fix the step size at γ=0.1, while setting the initial price at p1=0 and p1=3, respectively. It is shown that in both cases the price converges to the global optimum which balances between the supply and demand. The system welfare achieves the best with the convergence of the price, where the locally optimal solution of both the CRR and CRP becomes globally optimal at the converged price.Figure 6
Computing resource management in a mobile crowdsourcing system of the one-CRR and one-CRP case.Next, in Figure7(a), γ is fixed while p1 varies from 0 to 3, to study how the initial price impacts the convergence performance. The figure indicates that the price will finally converge to the equilibrium regardless of any initial value, although the convergence rates may be different. Similarly, in Figure 7(b), p1 is fixed while γ varies from 0.025 to 0.25, to study the impact of the step size on the price convergence. We find that the smaller the step size, the slower the convergence rate, while the larger the step size, the faster the convergence rate, but the system may only approach within a certain neighborhood of the equilibrium. This is a general characteristic of any gradient based method. In practice, we can first choose a large step size to ensure fast convergence and subsequently reduce the step size once the price starts oscillating around a certain value.Figure 7
Impact of adjustable parameters.
(a)
γ
=
0.1
(b)
p
1
=
0


### 5.2. One-CRR and Multi-CRP Case

Consider a mobile crowdsourcing system with one CRR and three CRPs. The simulation parameters for the CRR are the same as those in Section5.1, while the cost functions of different CRPs are assumed to be different. The initial price and step size are fixed at p1=3 and γ=0.05.


#### 5.2.1. Without Interaction among CRPs

In Figure8, we first set b=0.5 while a varies from 0.1 to 0.3 for different CRPs. It is shown that the larger the value of a, the less computing resource the CRP will supply. Then we set a=0.1 while b varies from 0.4 to 0.6 for different CRPs. The figure indicates that the larger the value of b, the less computing resource the CRP will supply. The system welfare achieves the best with the convergence of the price, where the locally optimal solution of the CRR and each CRP becomes globally optimal under the converged price.Figure 8
Computing resource management in a mobile crowdsourcing system of the one-CRR and multi-CRP case.


#### 5.2.2. With Interaction among CRPs

In Figure9, we set b=0.5 while a varies from 0.1 to 0.3 for different CRPs. It is shown that the larger the value of a, the less computing resource the CRP will supply. Initially the supplies of the three CRPs are random, so their payoffs are very low. Then, at each iteration, each CRP chooses the most selfish strategy according to the strategies of others to improve its own payoff. We can see from the figure that the best response algorithm guarantees that the CRPs’ strategies and payoffs converge to NE. The convergence rate is considerably fast, which is desirable for the real-time requirement of mobile crowdsourcing. At NE, each CRP achieves the best payoff. Through the CRP game, each CRP can strategically adjust its supply to improve its individual benefit. We also evaluate the distributed approach to (26). The initial supplies of the three CRPs are the same as those in the CRP game and the step size is fixed at γ=0.5. It is shown that the supplies of all CRPs converge to the optimal solution solved by a centralized way.Figure 9
CRP game in a mobile crowdsourcing system of the one-CRR and multi-CRP case (a1=0.1,a2=0.2,a3=0.3).In Figure10, we set a=0.1 while b varies from 0.4 to 0.6 for different CRPs. The figure indicates that the larger the value of b, the less computing resource the CRP will supply. We can see from the figure that the best response algorithm guarantees that the CRPs’ strategies and payoffs converge to NE. At NE, each CRP achieves the best payoff. We also evaluate the distributed approach to (26). The initial supplies of the three CRPs are the same as those in the CRP game and the step size is fixed at γ=0.5. It is shown that the supplies of all CRPs converge to the optimal solution solved by a centralized way.Figure 10
CRP game in a mobile crowdsourcing system of the one-CRR and multi-CRP case (b1=0.4,b2=0.5,b3=0.6).In Section4.1, we solve the computing resource management problem in mobile crowdsourcing while assuming that there is no interaction among CRPs. We refer to it as “solution 1” (without interaction). In Section 4.2, we assume the interaction among CRPs and formulate the CRP game to solve the computing resource management problem in mobile crowdsourcing. We refer to it as “solution 2” (CRP game). In Figure 11, we compare the performance of these two solutions. We first set b=0.5 while a varies from 0.1 to 0.3 for different CRPs. Then we set a=0.1 while b varies from 0.4 to 0.6 for different CRPs. It is shown that in both cases each CRP benefit in solution 1 outperforms that in solution 2, while the CRR benefit and system welfare are a little lower than those in solution 2. The reason is that the algorithm in Section 4.1 takes the system welfare into the first consideration, while the CRP game in Section 4.2 guarantees that each CRP is selfish and rational who only wants to maximize its individual benefit, regardless of the CRR benefit and system welfare.Figure 11
Comparison between solutions in Sections4.1 and 4.2.
(a)
a
1
=
0.1
,
a
2
=
0.2
,
a
3
=
0.3
(b)
a
1
=
0.1
,
a
2
=
0.2
,
a
3
=
0.3
(c)
b
1
=
0.4
,
b
2
=
0.5
,
b
3
=
0.6
(d)
b
1
=
0.4
,
b
2
=
0.5
,
b
3
=
0.6


## 5.1. One-CRR and One-CRP Case

Consider a mobile crowdsourcing system with one CRR and one CRP. The simulation parameters are set asω=3, α=0.5, a=0.1, b=0.5, and c=0. That is, we assume that the CRR has the utility function Ud=3d-0.5/2d2, while the CRP has the cost function Cs=0.1s2+0.5s. Firstly, in Figure 6, we fix the step size at γ=0.1, while setting the initial price at p1=0 and p1=3, respectively. It is shown that in both cases the price converges to the global optimum which balances between the supply and demand. The system welfare achieves the best with the convergence of the price, where the locally optimal solution of both the CRR and CRP becomes globally optimal at the converged price.Figure 6
Computing resource management in a mobile crowdsourcing system of the one-CRR and one-CRP case.Next, in Figure7(a), γ is fixed while p1 varies from 0 to 3, to study how the initial price impacts the convergence performance. The figure indicates that the price will finally converge to the equilibrium regardless of any initial value, although the convergence rates may be different. Similarly, in Figure 7(b), p1 is fixed while γ varies from 0.025 to 0.25, to study the impact of the step size on the price convergence. We find that the smaller the step size, the slower the convergence rate, while the larger the step size, the faster the convergence rate, but the system may only approach within a certain neighborhood of the equilibrium. This is a general characteristic of any gradient based method. In practice, we can first choose a large step size to ensure fast convergence and subsequently reduce the step size once the price starts oscillating around a certain value.Figure 7
Impact of adjustable parameters.
(a)
γ
=
0.1
(b)
p
1
=
0


## 5.2. One-CRR and Multi-CRP Case

Consider a mobile crowdsourcing system with one CRR and three CRPs. The simulation parameters for the CRR are the same as those in Section5.1, while the cost functions of different CRPs are assumed to be different. The initial price and step size are fixed at p1=3 and γ=0.05.


### 5.2.1. Without Interaction among CRPs

In Figure8, we first set b=0.5 while a varies from 0.1 to 0.3 for different CRPs. It is shown that the larger the value of a, the less computing resource the CRP will supply. Then we set a=0.1 while b varies from 0.4 to 0.6 for different CRPs. The figure indicates that the larger the value of b, the less computing resource the CRP will supply. The system welfare achieves the best with the convergence of the price, where the locally optimal solution of the CRR and each CRP becomes globally optimal under the converged price.Figure 8
Computing resource management in a mobile crowdsourcing system of the one-CRR and multi-CRP case.


### 5.2.2. With Interaction among CRPs

In Figure9, we set b=0.5 while a varies from 0.1 to 0.3 for different CRPs. It is shown that the larger the value of a, the less computing resource the CRP will supply. Initially the supplies of the three CRPs are random, so their payoffs are very low. Then, at each iteration, each CRP chooses the most selfish strategy according to the strategies of others to improve its own payoff. We can see from the figure that the best response algorithm guarantees that the CRPs’ strategies and payoffs converge to NE. The convergence rate is considerably fast, which is desirable for the real-time requirement of mobile crowdsourcing. At NE, each CRP achieves the best payoff. Through the CRP game, each CRP can strategically adjust its supply to improve its individual benefit. We also evaluate the distributed approach to (26). The initial supplies of the three CRPs are the same as those in the CRP game and the step size is fixed at γ=0.5. It is shown that the supplies of all CRPs converge to the optimal solution solved by a centralized way.Figure 9
CRP game in a mobile crowdsourcing system of the one-CRR and multi-CRP case (a1=0.1,a2=0.2,a3=0.3).In Figure10, we set a=0.1 while b varies from 0.4 to 0.6 for different CRPs. The figure indicates that the larger the value of b, the less computing resource the CRP will supply. We can see from the figure that the best response algorithm guarantees that the CRPs’ strategies and payoffs converge to NE. At NE, each CRP achieves the best payoff. We also evaluate the distributed approach to (26). The initial supplies of the three CRPs are the same as those in the CRP game and the step size is fixed at γ=0.5. It is shown that the supplies of all CRPs converge to the optimal solution solved by a centralized way.Figure 10
CRP game in a mobile crowdsourcing system of the one-CRR and multi-CRP case (b1=0.4,b2=0.5,b3=0.6).In Section4.1, we solve the computing resource management problem in mobile crowdsourcing while assuming that there is no interaction among CRPs. We refer to it as “solution 1” (without interaction). In Section 4.2, we assume the interaction among CRPs and formulate the CRP game to solve the computing resource management problem in mobile crowdsourcing. We refer to it as “solution 2” (CRP game). In Figure 11, we compare the performance of these two solutions. We first set b=0.5 while a varies from 0.1 to 0.3 for different CRPs. Then we set a=0.1 while b varies from 0.4 to 0.6 for different CRPs. It is shown that in both cases each CRP benefit in solution 1 outperforms that in solution 2, while the CRR benefit and system welfare are a little lower than those in solution 2. The reason is that the algorithm in Section 4.1 takes the system welfare into the first consideration, while the CRP game in Section 4.2 guarantees that each CRP is selfish and rational who only wants to maximize its individual benefit, regardless of the CRR benefit and system welfare.Figure 11
Comparison between solutions in Sections4.1 and 4.2.
(a)
a
1
=
0.1
,
a
2
=
0.2
,
a
3
=
0.3
(b)
a
1
=
0.1
,
a
2
=
0.2
,
a
3
=
0.3
(c)
b
1
=
0.4
,
b
2
=
0.5
,
b
3
=
0.6
(d)
b
1
=
0.4
,
b
2
=
0.5
,
b
3
=
0.6


## 5.2.1. Without Interaction among CRPs

In Figure8, we first set b=0.5 while a varies from 0.1 to 0.3 for different CRPs. It is shown that the larger the value of a, the less computing resource the CRP will supply. Then we set a=0.1 while b varies from 0.4 to 0.6 for different CRPs. The figure indicates that the larger the value of b, the less computing resource the CRP will supply. The system welfare achieves the best with the convergence of the price, where the locally optimal solution of the CRR and each CRP becomes globally optimal under the converged price.Figure 8
Computing resource management in a mobile crowdsourcing system of the one-CRR and multi-CRP case.


## 5.2.2. With Interaction among CRPs

In Figure9, we set b=0.5 while a varies from 0.1 to 0.3 for different CRPs. It is shown that the larger the value of a, the less computing resource the CRP will supply. Initially the supplies of the three CRPs are random, so their payoffs are very low. Then, at each iteration, each CRP chooses the most selfish strategy according to the strategies of others to improve its own payoff. We can see from the figure that the best response algorithm guarantees that the CRPs’ strategies and payoffs converge to NE. The convergence rate is considerably fast, which is desirable for the real-time requirement of mobile crowdsourcing. At NE, each CRP achieves the best payoff. Through the CRP game, each CRP can strategically adjust its supply to improve its individual benefit. We also evaluate the distributed approach to (26). The initial supplies of the three CRPs are the same as those in the CRP game and the step size is fixed at γ=0.5. It is shown that the supplies of all CRPs converge to the optimal solution solved by a centralized way.Figure 9
CRP game in a mobile crowdsourcing system of the one-CRR and multi-CRP case (a1=0.1,a2=0.2,a3=0.3).In Figure10, we set a=0.1 while b varies from 0.4 to 0.6 for different CRPs. The figure indicates that the larger the value of b, the less computing resource the CRP will supply. We can see from the figure that the best response algorithm guarantees that the CRPs’ strategies and payoffs converge to NE. At NE, each CRP achieves the best payoff. We also evaluate the distributed approach to (26). The initial supplies of the three CRPs are the same as those in the CRP game and the step size is fixed at γ=0.5. It is shown that the supplies of all CRPs converge to the optimal solution solved by a centralized way.Figure 10
CRP game in a mobile crowdsourcing system of the one-CRR and multi-CRP case (b1=0.4,b2=0.5,b3=0.6).In Section4.1, we solve the computing resource management problem in mobile crowdsourcing while assuming that there is no interaction among CRPs. We refer to it as “solution 1” (without interaction). In Section 4.2, we assume the interaction among CRPs and formulate the CRP game to solve the computing resource management problem in mobile crowdsourcing. We refer to it as “solution 2” (CRP game). In Figure 11, we compare the performance of these two solutions. We first set b=0.5 while a varies from 0.1 to 0.3 for different CRPs. Then we set a=0.1 while b varies from 0.4 to 0.6 for different CRPs. It is shown that in both cases each CRP benefit in solution 1 outperforms that in solution 2, while the CRR benefit and system welfare are a little lower than those in solution 2. The reason is that the algorithm in Section 4.1 takes the system welfare into the first consideration, while the CRP game in Section 4.2 guarantees that each CRP is selfish and rational who only wants to maximize its individual benefit, regardless of the CRR benefit and system welfare.Figure 11
Comparison between solutions in Sections4.1 and 4.2.
(a)
a
1
=
0.1
,
a
2
=
0.2
,
a
3
=
0.3
(b)
a
1
=
0.1
,
a
2
=
0.2
,
a
3
=
0.3
(c)
b
1
=
0.4
,
b
2
=
0.5
,
b
3
=
0.6
(d)
b
1
=
0.4
,
b
2
=
0.5
,
b
3
=
0.6


## 6. Conclusions

In this paper, we propose an optimal real-time pricing strategy for computing resource management in mobile crowdsourcing, which is based on utility maximization. It can be implemented in a distributed manner such that the real-time interaction among the CRR and CRPs is coordinated through a limited number of message exchanges. We show that there exist real-time prices that can align individual optimality with systematic optimality. We also take account of the interaction among CRPs and formulate the computing resource management as a game with Nash equilibrium achievable via best response. Simulation results demonstrate that, by using our proposed optimization-based real-time pricing strategy, not only the CRR but also CRPs will benefit. The coordinator in mobile crowdsourcing can thus use the optimal real-time pricing strategy to manage computing resources towards the benefit of the overall system.



---

*Source: 1494851-2017-09-17.xml*