title: A Bilateral Game Approach for Task Outsourcing in Multi-access Edge Computing
authors: Zheng Xiao Dan He Yu Chen Anthony Theodore Chronopoulos Schahram Dustdar Jiayi Du
text: 
  
  
  
  
  
  
  
  Shell et al.: Bare Demo of IEEEtran.cls for Computer Society Journals
  
  
  
  
  Multi-access edge computing (MEC) is a promising architecture to provide low-latency applications for future Internet of Things (IoT)-based network systems.
      Together with the increasing scholarly attention on task offloading, the problem of edge servers' resource allocation has been widely studied.
      Most of previous works focus on a single edge server (ES) serving multiple terminal entities (TEs), which restricts their access to sufficient resources.
      In this paper, we consider a MEC resource transaction market with multiple ESs and multiple TEs, which are interdependent and mutually influence each other.
      However, this many-to-many interaction requires resolving several problems, including task allocation, TEs' selection on ESs and conflicting interests of both parties.
      Game theory can be used as an effective tool to realize the interests of two or more conflicting individuals in the trading market.
      Therefore, we propose a bilateral game framework among multiple ESs and multiple TEs by modeling the task outsourcing problem as two noncooperative games: the supplier and customer side games. 
      In the first game, the supply function bidding mechanism is employed to model the ESs' profit maximization problem.
      The ESs submit their bids to the scheduler, where the computing service price is computed and sent to the TEs.
      While in the second game, TEs determine the optimal demand profiles according to ESs' bids to maximize their payoff.
      The existence and uniqueness of the Nash equilibrium in the aforementioned games are proved.
      A distributed task outsourcing algorithm (DTOA) is designed to determine the equilibrium.
      Simulation results have demonstrated the superior performance of DTOA in increasing the ESs' profit and TEs' payoff, as well as flattening the peak and off-peak load.
  
  
  
  
      Multi-access edge computing (MEC), Internet of Things (IoT), Task outsourcing, Bidding mechanism, Noncooperative game, Nash equilibrium.
  
  
  
  A Bilateral Game Approach for Task Outsourcing in Multi-access Edge Computing
      Zheng Xiao*, Member, IEEE,
          Dan He,
          Yu Chen,
          Anthony Theodore Chronopoulos, Senior member, IEEE,
          Schahram Dustdar, Fellow, IEEE,
          and Jiayi Du, Member, IEEE
          
  
  *Corresponding Author
  Zheng Xiao, Dan He, Yu Chen and Jiayi Du are with College of Computer Science and Electronic Engineering, Hunan University, Hunan, China, 410082. E-mail: {zxiao, danhe}@hnu.edu.cn, cy947205926@163.com, maxdujiayi@hnu.edu.cn,.
  Anthony Theodore Chronopoulos is with Department of Computer Science, University of Texas, San Antonio, TX, USA 78249 and Dept Computer Engineering Informatics 26500 Rio, University of Patras, Greece. Email: antony.tc@gmail.com.
  Schahram Dustdar is with Distributed Systems Group, Vienna University of Technology, Vienna, Austria. Email: dustdar@dsg.tuwien.ac.at.
  
  
      
  ======================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================
  
  
  
  § INTRODUCTION
  
  
  
  The Internet of Things (IoT) is a system of interrelated tens of billions of resource-hungry terminal entities (TEs), such as, sensors, wearable devices and unmanned aerial vehicles, which transfer data over a network with little or no human intervention.
  With the development of TEs and wireless networks, the demand for low-latency computing services has been growing exponentially.
  This paves the way for the development of Multi-access edge computing (MEC).
  
  
  
  Multi-access edge computing (MEC) enables a powerful cloud at the edge of the network. MEC decentralizes networks and allows any enterprise or mobile operator to place a cloud at the edge, adjacent to the user.
  In the MEC paradigm, plenty of machines are placed at the edge of the network so that computing services can be deployed on them for fast execution <cit.>.
  The MEC locates edge servers (ESs) with limited storage and computing resources at the edge of networks.
  Since the computation capabilities and battery lives of TEs are limited, TEs offload computationally intensive tasks (e.g., program execution) to ESs (e.g., 4G/5G base stations).
  The ESs execute these offloaded tasks and return results to TEs.
  However, to take full advantage of these available computational resources of ESs, TEs' tasks need to be allocated appropriately <cit.> .
  
  
  Due to the resource constraints of ESs, some computationally intensive tasks will be offloaded to cloud servers (CSs), which are normally distantly located.
  In that case, a higher transmission latency may be generated, which seriously degrades the quality of service (QoS).
  Moreover, task offloading from ESs to CSs incurs extra latency and energy consumption due to communication between TEs and CSs.
  Some important problems to be solved are how to satisfy the latency requirements of TEs and reduce the energy consumption in MEC.
  In order to meet a strict QoS, Nafiseh et al. <cit.> proposed a two-sided matching mechanism for edge services considering QoS requirements in terms of service response time.
  
  
  In order to achieve low-latency and energy-saving computations, several studies on task offloading in MEC have been proposed. Xinchen Lyu et al. <cit.> have attempted to encapsulate the latency requirements in offloading tasks and designed a selective offloading scheme. This scheme is achieved by enabling the devices to be self-denied or self-nominated for offloading. This can save energy consumption and minimize delays for task offloading. 
  Authors in <cit.> developed a threshold-based strategy to improve the QoS, which combines the advantages of ESs' with lower latency and abundant computational resources of CSs. A priority queue is also applied to solve the delay problem, wherein delay-sensitive tasks are executed ahead of delay-tolerant tasks. 
  
  
  However, most previous studies examined a single ES serving multiple TEs.
  In fact, the proliferation of applications puts a heavy load on the ESs.
  Since the ES has limited computing capacity and can't accommodate enough tasks, some task processes may have to wait longer to wake up.
  
  Thus, for a single ES is hard to cope with concurrent tasks of multiple TEs, which will hinder the development and popularity of MEC.
  
  In the future MEC market, there will be multiple different ESs offering optional computing service to TEs. Hence, TEs can choose different ESs according to their real-time and cost requirements.
  In that case, multiple ESs provide computing services in parallel, which can accelerate the speed of task processing and alleviate offloading delays.
  
  
  
  
  
  
  
  
  Task outsourcing has been employed as an effective paradigm by accommodating as many on-demand tasks as possible.
  Its principle is to distribute TEs' tasks in different time slots according to ESs' load of each time slot.
  Our work focuses on the problem of offloaded tasks outsourcing.
  It differs from most existing works which focus on the necessity of offloading or on selecting which tasks to be offloaded to ESs or CSs.
  The TEs' offloaded tasks are mapped to ESs according to their resource capacities.
  Thus, task outsourcing can enhance scalability of MEC and satisfy TEs' dynamic service demands.
  
  
  Fig. <ref> describes a MEC communication network in IoT, where ESs are deployed densely near TEs.
  The MEC network is similar to a real competitive market, in which a wide range of TEs can be grouped into virtual clusters and compete for the ESs' limited wireless resources. 
  They are interdependent and mutually influence each other.
  Several base stations with ESs also compete with each other to win more TEs.
  The ESs can communicate with the TEs via scheduler and inform them of their real-time service prices. 
  Through the scheduler, TEs can participate in ESs selection, and make wise decisions regarding their daily computing resources consumption.
  
  
  
  
  However, one of the main challenges of task outsourcing is to consider the interests of both parties.
  On the one hand, ESs aim to get more profits, and strive for attracting more TEs to use their computing resources.
  On the other hand, a rational TE will choose a task strategy that maximizes its own payoff.
  Game theory can be used as an effective tool to model the interests of two or more conflicting individuals in trading markets and also load balancing in distributed systems <cit.>.
  The game solution was proved to be a Nash equilibrium solution for the noncooperative game.
  
  
  In this paper, we propose a bilateral game framework among multiple ESs (the suppliers) and multiple TEs (the customers) to model the task outsourcing problem as two noncooperative games.
  These two games are related to each other and are played simultaneously.
  In the first game, the supply function bidding mechanism is employed to model the noncooperative game among ESs. 
  In the proposed scheme, each ES, with limited or idle resources, submits a bid to reveal the available capacity “supplied” to the market.  
  Then the scheduler collects these bids and computes a service price to clear the market so that the supply of the resource to be traded equals the demand.
  In particular, all TEs are charged the same service price at one time slot.
  The scheme can maximize the profits of ESs.
  In the second game, in order to reduce costs, TEs determine the amount of assigned tasks for each time slot
  based on the price of that time slot. 
  If the price of one time slot is high, there would be fewer tasks assigned,
  and if the price is low, there would be more tasks.
  
  This framework can encourage TEs to assign fewer tasks during peak times or shift some tasks to off-peak times, which flattens the demand curve by peak clipping or valley filling. 
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  In summary, the contributions of this paper are:
   
  	
    * A bilateral-game framework is developed to model the interactions among TEs and ESs.
  	
    * A supply function bidding mechanism is proposed, where each ES submits a bid to reveal the available capacity “supplied” to the market.
  	
  	
    * A DTOA is designed to compute the Nash equilibrium.
  	
    * Simulations show that the proposed mechanism achieves the maximization of bilateral interests.
  
  
  
  The remainder of this paper is organized as follows.
  In Section <ref>, the related work about task outsourcing in MEC is introduced.
  Section <ref> models the task outsourcing problem in the ESs' and TEs' sides.
  In Section <ref>, a DTOA is designed to compute the Nash equilibrium in both sides.
  Section <ref> presents simulations showing the performance of the new approach using DTOA.
  Finally, conclusions are presented in Section <ref>.
  
  
  
  § RELATED WORK
  
  
  In recent years, significant attention has been devoted to the resource allocation in MEC networks <cit.>.
  Shi Yan et al. <cit.> studied the access selection for unmanned aerial vehicles (UAV) and bandwidth allocation of the base station (BS) in a UAV assisted IoT communication network. Wherein, the access competition among groups of UAVs is modeled as a dynamical evolutionary game.
  The bandwidth allocation of BSs is formulated as a noncooperative game.
  Authors in <cit.> examined resource allocation for a multi-TE MEC offloading system, which is formulated as a convex optimization problem for minimizing the weighted sum of mobile energy consumption.
  
  Chunlin Li et al. <cit.> analysed a radio and computing resource allocation problem between an access point and multiple devices in MEC system.
  They designed a time average computation rate maximization algorithm to determine the optimal transmit power, and time allocation for the wireless devices.
  Junhui Zhao et al. <cit.> studied a cloud-MEC collaborative computation offloading problem that offloads tasks to automobiles in MEC vehicular networks.
  They developed a tasks allocation optimization and collaborative computation offloading scheme to decide the optimal strategies.
  An offloading algorithm for shortening the computation time and increasing the system utility was also designed.
  Yunlong Gao et al. <cit.> studied the optimal tradeoff between resource consumption and user experience in designing MEC systems.
  Cosmin Avasalcai et al. <cit.> introduced a decentralized resource management algorithm with the purpose of deploying IoT applications at the edge of the network such that end-to-end delay is minimized.
  
  Since the resources of an ES are limited, the ES can not undertake the tasks coming from multiple TEs.
  So multiple ESs are needed.
  Nevertheless, the matching problem between multiple ESs and multiple TEs becomes a key issue.
  Heli Zhang et al. <cit.> modeled the matching relationship between ESs and TEs as a commodity trading by applying a multi-round sealed sequential combinational auction mechanism.
  In <cit.>, the authors studied task offloading in vehicular MEC environments and modelled the interactions between edges and tasks as a matching game.
  They further developed two standalone heuristic algorithms to minimize the average delay while taking the energy consumption and vehicle mobility constraints into consideration.
  A three-tier IoT fog network was proposed in <cit.>, in which all fog nodes, data service operators and data service subscribers are jointly optimized to achieve the optimal resource allocation in a distributed fashion.
  
  Furthermore, authors in <cit.> adopted a price-based mechanism to design efficient resource allocation in a MEC network. For example, <cit.> proposed a price-based distributed method to manage the offloaded tasks from users. Wherein, edge cloud sets prices to maximize its revenue and each user makes an optimal decision to minimize her/his own cost.
  The work <cit.> proposed a price-based resource allocation mechanism among the MEC server and multiple base stations (BSs). The MEC server tries to provide prices to BSs so as to maximize its own revenue while the BSs determine the computing space to improve the quality of experience.
  
  To summarize the related work above, we observe that the existing resource allocation and matching problem in MEC generally involves edge nodes and clients using resource from an edge node.
  However, most of these studies focus either on the system performance or ESs' benefits, while ignoring the TEs' pursuit of maximizing payoff.
  Against this backdrop, our paper tries to balance the objectives of both ESs and TEs. 
  In this paper, we also adopt a priced-based supply bidding mechanism to solve the resource allocation problem. 
  
  
  
  § SYSTEM MODEL
  
  
  
  
  
   §.§ Interaction between TEs and ESs
   
  
  As shown in Fig. <ref>, we consider a scheduler-based resources transaction market, which consists of M ESs and N TEs in a MEC network.
  ESs act as suppliers who sell computing resources to TEs and TEs act as customers who purchase resources from ESs.
  The bidirectional interaction between ESs and TEs is performed through a scheduler, which serves as a third-party agency outsourcing TEs' tasks to ESs.
  
  On the one hand, TEs submit their demand profiles to the scheduler via a communication network. 
  On the other hand, ESs compete with each other for acquiring more TEs, and submit bids based on strategies of their opponents and their own resource capacities.
  As a response, the scheduler calculates the service price and the aggregated load based on ESs' bids and TEs' total demand.
  They are mutually dependent upon each other as decisions on either side can have a bearing on those of the other side.
  After receiving the real-time price signal, the TEs will update their demand profiles.
  Since the aggregate load depends on the TEs' demand profiles, the behavior of TEs will affect the ESs' bidding strategies. 
  The aforementioned process is repeated until both customers and suppliers are satisfied.
  
  We divide one day into a set of T (T=24) time slots, denoted as 𝒯 = { 1,⋯,T }.
  The set of ESs and TEs are represented as ℳ= { 1,⋯,M } and 𝒩={1, …, N}.
  How many resources should ESs provide to the market and how the ESs' bids affect the TEs' demand profiles are questions worth investigation.
  We next present the model of both sides in the MEC resources transaction market.
  
  
  
   §.§ Cost and profit of ES
  
  
  For ES j ∈ℳ, let C_j,t(.) denote the cost function of ES j at time slot t  (t ∈𝒯).
  Let R_j,t(.) denote the revenue function of ES j at the tth time slot by providing the computational load.
  The profit of ES equals the revenue by providing computing service minus its cost of system overhead. 
  Therefore, the profit P_j,t of ES j at time slot t can expressed as follows:
  
      P_j,t=R_j,t(.)-C_j,t(.).
   
  
  We consider that each ES is selfish and tries to maximize its own profit. Thus, the interaction among the profit maximizer ESs can be modeled as a noncooperative game.
  The ESs are the players while the bid profiles are the strategies.
  Let λ_j,t denote the bid of ES j at time slot t.
  The target of each ES j is to find the optimal bid λ_j,t to maximize its profit, which can be defined as:
  
      λ_j, tmaximize   P_j,t   j ∈ℳ, t ∈𝒯.
  
  By substituting Equ. (<ref>) into Equ. (<ref>), we can get
  
      λ_j, tmaximize   R_j,t(.)-C_j,t(.)    j ∈ℳ, t ∈𝒯.
  
  
  We denote by f_j, t the task load that ES j willing to generate in the time slot t.
  We assume that the service price of different ESs in one time slot is the same and denoted as p_e(t) at time slot t.
  The revenue of each ES is equal to the product of its load and the service price.
  Hence, the revenue of ES j at time slot t can be represented as
  
      R_j,t=f_j, t· p_e(t).
  
  
  Similar to <cit.>, the ES j's cost function is defined as a quadratic function
  
      C_j,t(f_j, t)=a_j,2 f_j, t^2+a_j,1 f_j, t+a_j,0,
  
  where a_j,2, a_j,1 and a_j,0 are positive coefficients and model the fact that different ESs incur different costs for serving the tasks.
  We note that the cost function is increasing and convex.
  Substituting Equ. (<ref>) into Equ. (<ref>), the optimization problem can be further rewritten as
  
      λ_j, tmaximize   f_j, t· p_e(t)-C_j,t(f_j,t) 
          subject to   f_j, t≥ 0,    j ∈ℳ, t ∈𝒯.
  
  
  
  
   §.§ Payoff and payout of TE
  
  The demand of each TE consists of two parts: a base demand and a shiftable demand.
  On the one hand, a base demand is primarily concerned with real-time tasks, which have high priority.
  On the other hand, a shiftable demand has low priority real-time requirements and it can be assigned at any time slot.
  The shiftable demand profile of TE i  (i ∈𝒩) is defined as χ_i=(χ_i,1, …, χ_i,T) and the base demand of TE i at time slot t is denoted as r_i,t, which is known and fixed.
  
  The utility of TE i represents the profit that TE i receives when it completes tasks and is denoted as U_i(.).
  Exactly, the utility function of TE i is the utility for the tasks rather than the service time or applications.
  Similar to <cit.>, we employ the quadratic utility function because it is non-decreasing and its marginal benefit is non-decreasing,
  
      U_i(x)=
      		{   w_i, t x-α_i, t/2 x^2,  0 ≤ x ≤w_i, t/α_i, t
         w_i, t^2/2 α_i, t,          x > w_i, t/α_i, t.,
  
  where x=(χ_i,t+r_i,t), w_i, t and α_i, t, i ∈𝒩 are coefficients that reflects the dynamic changes of TE i's demand.
  
  The payout function quantifies the payout that TE i needs to pay the ESs task completion.
  Without loss of generality, we define the payout of TE i' as the product of demand and the service, i.e.
  
      Payout_i,t=(χ_i,t+r_i,t) · p_e (λ_t, L_t).
  
  The payoff function quantifies the final benefits of TE i and represents the satisfaction of using the service.
  Thus, we denote the payoff of TE i as its utility minus payout i.e.
  
      Payoff_i = Utility_i - Payout_i.
  
  Let u_i denote the payoff of TE i.
  By substituting Equ. (<ref>) and Equ. (<ref>) into Equ. (<ref>), we can obtain
  
      u_i(χ_i, χ_-i)=∑_t ∈𝒯(   U_i(χ_i,t+r_i,t)
         -(χ_i,t+r_i,t) p_e(λ_t, L_t)),
  
  where χ_-i denotes the vector of the demand profile of other TEs and χ_-i=(χ_1, …, χ_i-1, χ_i+1, …, χ_N).  In Equ. (<ref>), the utility is a function related to (χ_i,t+r_i,t).
  
  Each TE tries to maximize its payoff by determining its shiftable demand profile.
  Thus, the interaction between TEs can be modeled as a noncooperative game.
  The TEs are participants while the shiftable demand profiles are the strategies of the noncooperative game.
  
  Let χ_i^* denote the optimal demand profile of TE i in the Nash equilibrium and Q_i^total denote the total daily shiftable demand of TE i which is fixed and known.
  Let L_t denote the aggregate load demand of the ESs at time slot t and L_t=∑_j ∈𝒩(χ_j,t+r_j,t). Considering TE i, the optimization problem can be formulated as follows when other TEs' profiles are fixed:
  
      χ_imaximize  
              u_i(χ_i, χ_-i) 
          subject to   ∑_t ∈𝒯χ_i, t=Q_i^total, 
                     χ_i, t≥ 0, ∀ i ∈𝒩.
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
   §.§ Market mechanism with supply function bidding
  
  In this section, we employ a supply function bidding mechanism to model the relationship between market demand for services and its price.
  We use a class of supply functions with parameters.
  The bids submitted by ESs reveal their available resource capacities “supplied” to the market. 
  
  
  
  The notations used in the supplier side model are presented in Table <ref>. We assume that the supply function f_j,t is chosen from the family of increasing and convex price-wise linear functions of p_e(t) <cit.>. 
  Fig. <ref>(a) shows an increasing and convex piece-wise linear supply function.
  The abscissa p_e(t) indicates the price and the ordinate f_j,t denotes the load supplied by the TE j at time slot t.
  There exists K break points on the abscissa of the Fig. <ref>(a).
  λ_j,t^k≥ 0 represents the slope of the function between the break points p_k-1 and p_k.
  Fig. <ref>(b) shows the affine supply function.
  
  At time slot t  (t ∈𝒯), we use the vector λ_j,t = (λ_j,t^1,⋯,λ_j,t^K) to denote the bid profile of ES j  (j ∈ℳ). Thus, we obtain
  
      f_j, t(p_e(t), λ_j, t) ={   λ_j, t^1 p_e(t),  0 ≤ p_e(t) ≤ p_1
      
         λ_j, t^k p_e(t) +λ_j, t^k-1 p_k-1,  p_k-1 < p_e(t) ≤ p_k..
  
  
  It is assumed that each ES submits λ_j,t as a bid profile to the scheduler at time slot t.
  For each ES j, the bid profile describes the number of tasks that it is willing to admit.
  We can use λ_t to represent the bid profiles of all ESs at time slot t and λ_t= {λ_1,t,⋯,λ_M,t}.
  In response to ESs, the scheduler sets the price p_e(t) to clear market.
  In economics, market clearing means the supply of what is traded equals the demand, so that there is no leftover supply or demand.
  In this case, the demand of all TEs is the same as the load supplied by all ESs.
  Although the fluctuation in TEs' demand will drive changes in ESs' bid profiles, the demand and supply remains balanced.
  The equivalence further builds up the connection between the supplier game and the customer game.
  Hence, it can expressed as
  
      ∑_j ∈ℳ f_j, t(p_e(t), λ_j, t)=L_t,    t ∈𝒯.
  
  According to Equ. (<ref>) and Equ. (<ref>), we have
  
      L_t={   ∑_j ∈ℳ( λ_j, t^1 p_e(t)),  0 ≤ p_e(t) ≤ p_1
      
         ∑_j ∈ℳ( λ_j, t^k p_e(t) +λ_j, t^k-1 p_k-1),  p_k-1 < p_e(t) ≤ p_k..
  
  According to Equ. <ref>, we can further calculate the service price function as follows:
  
      p_e(t)={   L_t/∑_j ∈ℳλ_j,t^1,  0 ≤ p_e(t) ≤ p_1
      
         L_t-∑_j ∈ℳ( λ_j, t^k-1 p_k-1)/∑_j ∈ℳλ_j, t^k,    p_k-1 < p_e(t) ≤ p_k.			
      		..
  
  At time slot t, the service price of different ESs is the same.
  
  In <cit.>, the affine supply function f_j, t(p_e(t), λ_j, t) =λ_j, t^1 p_e(t) is used as a special case of the aforementioned piece-wise linear functions.
  Almost all the results of affine supply functions can be generalized to the piece-price affine supply function <cit.>.
  As for Equ. (<ref>), it can be concluded that the affine function is equivalent to the piece-wise linear supply function between two break points.
  Each piecewise function of Fig. <ref>(a) can be regarded as a linear function in Fig. <ref>(b).
  As a matter of fact, the term λ_j, t^k-1 p_k-1 is fixed when we are between break points p_k-1 and p_k.
  Therefore, without loss of generality, we generalize the results from the affine functions to piece-wise linear functions. 
  Therefore, the computing service price can be given as follows for an affine supply function:
  
      p_e(t)=L_t/∑_j ∈ℳλ_j,t^1,    t ∈𝒯.
  
  
  For simplicity, we use the notation λ_j,t instead of λ_j,t^1 to represent the affine supply function of ES j. Meanwhile, we use λ_t=(λ_1, t, …, λ_M, t) to denote the bids profile for all ESs at time slot t. As Equ. (<ref>) shows, the computing service price is related to λ_j, t (j ∈ℳ) and L_t. Hence, the price function can be denoted as p_e(λ_t, L_t). As suggested by Equ. (<ref>), supply function f_j,t for ES j can be expressed as
  
      f_j, t(p_e(λ_t, L_t), λ_j, t)=λ_j, t L_t/∑_r ∈ℳλ_r, t,    t ∈𝒯.
  
  
  Similar to the computing service, the supply function can be represented by f_j, t(λ_t, L_t). Let λ_-j,t denote the submitted bids of other ESs except for ES j. So it can be defined as λ_-j,t=(λ_1, t, …, λ_j-1, t, λ_j+1, t, …, λ_M, t).
  Hence, According to Equ. (<ref>) and Equ. (<ref>), the profit function of ES j is rewritten as 
  
      P_j,t(λ_j, t, λ_-j, t) = λ_j, t L_t^2/( ∑_r ∈ℳλ_r, t)^2-C_j(λ_j, t L_t/∑_r ∈ℳλ_r, t).
  
  When other ESs' bids are fixed, the ES j tries to find the optimal bid λ_j,t^* by solving the following optimization problem:
  
      λ_j, tmaximize  λ_j, t L_t^2/( ∑_r ∈ℳλ_r, t)^2-C_j(λ_j, t L_t/∑_r ∈ℳλ_r, t)
      
          subject to   λ_j, t≥ 0,    j ∈ℳ, t ∈𝒯.
  
  
  
  
   §.§ Nash equilibrium analysis
  
  
  The following section will explain that the ES's game (Equ. (<ref>)) has a unique Nash equilibrium, as shown by the lemma below.
  
  
      Assume that the bids profile in Nash equilibrium at time slot t is denoted as λ_t^*. When the Nash equilibrium is reached, it will satisfy λ_j, t^*<∑_r ∈ℳ, r ≠ jλ_r, t^* for all ESs.
  
  
  The function Π_j, t(λ_j, t, λ_-j, t) is expressed as follows:
  
      Π_j, t(λ_j, t, λ_-j, t)=λ_j, t L_t^2/(∑_r ∈ℳλ_r, t)^2.
  
  
  As the formula above suggests, Π_j, t(λ_j, t, λ_-j, t) is the first term in P_j, t(λ_j, t, λ_-j, t).
  From Equ. (<ref>), we can calculate the first derivative function as follows
  
      d Π_j, t(λ_j, t, λ_-j, t)/d λ_j, t
         =L_t^2·(∑_r ∈ℳλ_r, t)^2-2 λ_j, t L_t^2(∑_r ∈ℳλ_r, t)/(∑_r ∈ℳλ_r, t)^4
  
  Let
  
      d Π_j, t(λ_j, t, λ_-j, t)/d λ_j, t>0,
  
  we can get
  
      (∑_r ∈ℳλ_r, t)^2-2 λ_j, t∑_r ∈ℳλ_r, t>0.
  
  The Equ. (<ref>) is equivalent to
  
      (λ_j, t+∑_r ∈ℳ, r ≠ jλ_r, t)^2-2 λ_j, t(λ_j, t+∑_r ∈ℳ, r ≠ jλ_r, t)>0.
  
  From Equ. (<ref>), we can derive that
  
      0 ≤λ_j, t<∑_r ∈ℳ, r ≠ jλ_r, t.
  
  
  In summary, we can conclude that P_j, t(λ_j, t, λ_-j, t) is an increasing function when 0 ≤λ_j, t<∑_r ∈ℳ, r ≠ jλ_r, t. And it becomes a decreasing function when λ_j, t≥∑_r ∈ℳ, r ≠ jλ_r, t. Thus, in order to maximize profit, we should meet the constraint 0 ≤λ_j, t<∑_r ∈ℳ, r ≠ jλ_r, t. In the Nash equilibrium, the bid of ES j at time slot t is denoted as λ_j,t^*. Therefore, we can conclude that λ_j, t^*<∑_r ∈ℳ, r ≠ jλ_r, t^* (j ∈ℳ).
  
  
  Similar to <cit.>, the proof for the following theorem given as follows.
  
  
  	The ES's noncooperative game has a unique Nash equilibrium. Furthermore, the Nash equilibrium is the solution of the following convex optimization problem:
  	
      [ 0 ≤ f_j, t<L_t/2maximize       ∑_j ∈ℳ-Ψ_j(f_j, t);                         ;               subject to       ∑_j ∈ℳ f_j, t=L_t, ]
  
  	where
  	
      Ψ_j(s_j, t)=(L_t-f_j, t/L_t-2 f_j, t) C_j(f_j, t)-∫_0^f_j, tL_t C_j(Π_j)/(L_t-2 Π_j)^2 d Π_j.
  
  
  
  	According to lemma <ref>, we can infer that the load supplied by each ES at time slot t does not exceed L_t/2 at the Nash equilibrium. The Lagrange function of the optimization problem in Equ. (<ref>) is denoted as F. Thus, we have
  	
      F=∑_j ∈ℳ-Ψ_j(f_j, t)+ϕ(∑_j ∈ℳ f_j, t-L_t),
  
  	where ϕ denotes the Lagrange multiplier.
  	We can obtain the following expression through the first-order optimality function.
  	
      (∂ F/∂ f_j, t^*)(f_j, t-f_j, t^*) ≤ 0,   ∀ j ∈ℳ,
  
  	where f_j, t^* is defined as the supply function in equilibrium, while ϕ^* is the Lagrange multiplier in equilibrium.
  
  	From Equ. (<ref>), (∂ F/∂ f_j, t^*) can be expressed as follows:
  	
      ∂ F/∂ f_j, t^*=ϕ^*-(L_t-f_j, t^*/L_t-2 f_j, t^*) C_j^'(f_j, t^*).
  
  	
  	We assume the first-order optimality condition for the optimization problem in Equ. (<ref>). Thus, we obtain
  	
      (∂ P_j, t/∂λ_j, t)(λ_j, t-λ_j, t^*) ≤ 0,   ∀ j ∈ℳ.
  
  	From Equ. (<ref>), ∂ P_j, t/∂λ_j, t is calculated as follows:
  	
      ∂ P_j, t/∂λ_j, t=p_e(λ_t, L_t)-L_t-f_j, t^*/L_t-2 f_j, t^* C_j^'(f_j, t^*).
  
  	By substituting Equ. (<ref>) into Equ. (<ref>), we can write the optimality condition for Nash equilibrium as follows
  	
      (p_e(λ_t, L_t)-L_t-f_j, t^*/L_t-2 f_j, t^* C_j^'(f_j, t^*))(λ_j, t-λ_j, t^*) ≤ 0.
  
  
  	From Equ. (<ref>) and Equ. (<ref>), we can see that the Lagrange multiplier is actually the price p_e(λ_t, L_t) of the computing service.
  	In addition, the optimality condition Equ. (<ref>) is equivalent to Equ.<ref>.
  	Therefore, the existence and uniqueness of the Nash equilibrium is equivalent to proving the existence and uniqueness of the optimal point of problem Equ. (<ref>).
  
  
  In Theorem <ref>, it is proved that the ES's game has a unique Nash equilibrium solution, whose strategies are determined by the aggregate load L_t. Besides, a ES can scale-up and scale-down its resource capacity according to different market demands. Thus, ESs will bid differently for different levels of load.
  
  We next analyze the existence of Nash equilibrium for the customer side game, which is proved by the theorem below.
  
  
  	The customers' optimization problem is a convex programming problem. In fact, the customer side game Equ. (<ref>) is an n-person game. It has a unique pure strategy Nash equilibrium.
  
  
  From the above discussion it follows that the objective function in Equ. (<ref>) is equal to
  
      ∑_t ∈𝒯    U_i(χ_i,t+r_i,t)
         -∑_t ∈𝒯((χ_i,t+r_i,t)^2 +∑_j ∈𝒩,j ≠ i(χ_j,t+r_j,t)/∑_r ∈ℳλ_r, t).
  
  Let k=1/(∑_r ∈ℳλ_r, t), k> 0. For simplicity, we denote the right part of Equ. (<ref>) as follows:
  
      h_i(χ_i,χ_-i)=∑_t ∈𝒯 k((χ_i,t+r_i,t)^2 +∑_j ∈𝒩,j ≠ i(χ_j,t+r_j,t)).
  
  We have
  
      ∇_χ_i h_i   (χ_i,χ_-i) 
      =[∂ h_i(χ_i,χ_-i)/∂χ_i,t]_t=1^T
         =(∂ h_i(χ_i,χ_-i)/∂χ_i,1, ⋯, ∂ h_i(χ_i,χ_-i)/∂χ_i,T)
         =2k[(χ_i,t+r_i,t)+∑_j ∈𝒩,j ≠ i(χ_j,t+r_j,t)]_t=1^T
  
  and the Hessian matrix is as follows:
  
      ∇^2_χ_i h_i(χ_i,χ_-i)=([ 2k 2k  ⋯ 2k; 2k 2k  ⋯ 2k;  ⋮  ⋮  ⋱  ⋮; 2k 2k  ⋯ 2k ])_N × T.
  
  This further leads to
  
      [ X^T∇^2_χ_i h_i(χ_i,χ_-i) X=2k (X_1+X_2+⋯+X_N × T)^2≥ 0,; ;                           ∀ X=(X_1, X_2, ⋯, X_N × T)^T. ]
  
  
  Therefore, the Hessian matrix of h_i(χ_i,χ_-i) is positive semi-definite and h_i(χ_i,χ_-i) is convex.
  Moreover, since the utility function U_i(.) is continuous and strictly concave in the strategy space, the payoff function Equ. (<ref>) of each TE i  (∀ i ∈𝒩) is strictly concave. So the objective function in Equ. (<ref>) is concave. Hence, Equ. (<ref>) is a convex optimization problem.
  Meanwhile, since the constraints of Equ. (<ref>) are inequalities or linear equations, the feasible domain is convex. Thus, the TEs' optimization problem is a convex programming problem.
  Hence, the TE's game is a strictly concave N-person game. Since the demand profile sets are closed, bounded and convex, the existence of Nash equilibrium can be proved based on <cit.>. Analogously to <cit.>, for a concave N-person game, there exists a unique equilibrium solution. Therefore, the theorem is proved.
  
  
  In the Nash equilibrium, for any given ESs' bids, no TE can increase its payoff by a unilateral change on its strategy. In the next section, a task outsourcing algorithm is developed to determine the point for both ES and TE's games.
  
  
  
  § DISTRIBUTED TASK OUTSOURCING ALGORITHM
  
  
  
  
  In this section, we propose a distributed task outsourcing algorithm to demonstrate the interaction among TEs and ESs. Our method is referred as DTOA. Let g be the iteration number. 
  
  Notations:
  
  Let χ_i,t^g denote the demand profiles of TE i in iteration g at time slot t and vector χ_i^g denote the demand profile of TE i for all time slots. The matrix χ=(χ_1, …,χ_t, …,χ_T)^T denotes the demand profiles of all TEs in iteration g for all time slots. Let matrix λ=(λ_1,…,λ_t,…,λ_T)^T denote the bids of all ESs for all time slots. L_t^g denotes the aggregate loads in iteration g at time slot t. p_e^g(λ_t^g, L_t^g) denotes the computing service price in iteration g at time slot t.
  
  
  As shown in Fig. <ref>, the interaction between ESs and TEs can be modeled as a two-stage game. They interact with each other to determine optimal bids and demand profiles. The detailed process is depicted in Algorithm 1 and 2.
  
  	
    * The ESs try to maximize their profits by determining their own bids according to optimization function Equ. (<ref>).
  	
    * The TEs will then adjust their demand profiles following optimization function Equ. (<ref>).
  
  
  
  
  
  
  The DTOA can be described as follows. Firstly, the scheduler randomly initializes the TEs' demand profiles and ESs' bid profiles. Secondly, the TE i  (i ∈𝒩) sends the shiftable demand profile χ_i^g to the broker and receives L_t^g from it. Then, the ESs will receive a signal to update their bids based on the following iterative equation:
  
      λ_j,t^g+1=[λ_j,t^g+η_1∂ P_j, t(λ_t^g)/∂λ_j,t^g]^+,   ∀ t ∈𝒯.
  
  where η_1 is the step size.
  [·]^+ in Equ. (<ref>) is the projection onto the feasible set defined by the constraints λ_j, t≥ 0.
  It is noticed that the ES j  (j ∈ℳ) does not know other ESs' bids. In this aspect, the DTOA can also preserve the privacy of participants. Thirdly, the computing service price p_e^g(λ_t^g, L_t^g) is updated by the scheduler according to Equ. (<ref>). The TEs will further be informed to update their shiftable demand profiles using a gradient boosting method:
  
      χ_i,t^g+1=[ χ_i,t^g+η_2∂ u_i(χ_t^g)/∂χ_i,t^g]^+,   ∀ t ∈𝒯.
  
  η_2 is the step size.
  [·]^+ in Equ. (<ref>) is the projection onto the feasible set defined by the constraints ∑_t ∈𝒯χ_i, t=Q_i^total and χ_i, t≥ 0.
  It is worth remarking that Equ. (<ref>) needs the updated price p_e^g(λ_t^g, L_t^g) and L_t^g to determine (∂ u_i(χ_t^g)/∂χ_i,t^g). Besides, since (∂ u_i(χ_t^g)/∂χ_i,t^g) only depends on its own demand profile and the price and there is no need to know the demand profile of other TEs. Thus, this fact protects the privacy of the TEs. Finally, the stopping criterion of the algorithm is checked by the scheduler. If the relative change of shiftable demand profiles during two consecutive iterations is lower than the value ϵ, the iterations can be stopped. Otherwise, the TEs will continue computing their demand profiles based on the newly updated price and bids.
  
  The optimization problems Equ. (<ref>) and Equ. (<ref>) will converge to the optimal point by the projected gradient method. In the end, the algorithm will converge.
  In the equilibrium, the ESs are playing their equilibrium strategies according to TEs' tasks strategies, and the TEs also choose their equilibrium strategies based on ESs' submitted bids.
  Thus when the Nash equilibrium is reached, none of the ESs and TEs improve their profit.
  
  
  § PERFORMANCE EVALUATION
  
  
  
  
  
   §.§ Simulation experiment
   
  
  
  In this section, we present a simulation experiment to validate our theoretical analysis.
  We assume a MEC resource exchange market has 10 ESs and 1000 TEs, which are willing to participate in the DTOA scheme.
  There are 24 time slots.
  The relevant parameters of the model are shown in Table <ref>.
  The base demand r_i,t of each TE at each time slot is randomly selected from [9660, 37065].
  The shiftable demand refers to real-time, non-shiftable tasks, which reflects the changes in the total demand of all TEs at different time slots.
  Since most loads are running in real-time pattern, it is plausible to assume relatively low shiftable loads for TEs.
  The shiftable demand χ_i,t of each TE is assumed to be chosen randomly from 10% to 12% of its base demand.
  And the total demand is the sum of the base demand and shiftable demand.
  Considering the generation cost function c(f_j, t)=a_j,2 f_j, t^2+a_j,1 f_j, t+a_j,0 for each ES j (j ∈ℳ), we assume that a_j,2 is randomly generated in the interval [4.76e-6, 4.76e-5], a_j,1=0.001 and a_j,0=0.001.
  The initial values of η_1 and η_2 are set as 0.05 and 0.01 respectively.
  In order to find the optimal solution, the step size of next iteration will be a little less than the previous one, namely η_1=η_1*0.985 and η_2=η_2*0.98.
  The initial bids λ_j,t of ESs are all set as 20000.
  The α_i,t is set as 0.5 and ω_i,t is randomly selected from interval [0.8, 1.0].
  Also, the ϵ is set equal to 0.3.
  
  
  
  
  
  
  
  
  
  
   §.§ Algorithm Convergence
  
  The performance of our proposed DTOA is evaluated in terms of its convergence.
  Fig. <ref> and Fig. <ref> show the convergence of ESs' bids and TEs' shiftable loads at time slot 5.
  From Fig. <ref>, these ten TEs (TEs 21-30) are randomly selected from 1000 TEs.
  The speed of convergence to the equilibrium point depends on the step sizes and the stopping criterion ϵ.
  As the number of iterations increases, the bids and the shiftable load demands start from the initial values and they gradually converge to stable values.
  In our experiment, the algorithm converges after around 248 iterations.
  Hence, the proposed DTOA is efficient and verifies the theoretical proof presented above.
  
  To demonstrate the computational complexity of the algorithm, we evaluate the running time of the algorithm for different number of TEs and ESs.
  As shown in Fig. <ref>, the running time of the algorithm increases linearly with the number of TEs N and it is almost independent of M.
  This is because that by increasing the number of TEs and ESs, the number of updates for TEs and ESs will increase proportional to N and M, respectively.
  The update process for TEs takes more time comparing with the updates for ESs since the TEs need to consider load shifting during T time slots (the projected gradient), which make the update process more complex.
  From Fig. <ref>, the running time of the algorithm is acceptable even for large number of TEs.
  So it can be concluded that the algorithm is efficient and can be implemented in scenarios with large number of TEs.
  
  
  
  
   §.§ Economic effects of algorithm
  
  
  By participating in the DTOA scheme, the payout (see Equ. (<ref>)) represents TE's expenditure on purchasing computing resources.
  Fig. <ref> shows the daily total payout for TE 1 to TE 30 before algorithm and after algorithm.
  Compared with before algorithm, the total payout of each TE after algorithm is reduced.
  We can see that TEs can save around 5% of they payout by participating in DTOA scheme.
  The vertical axis of Fig. <ref> shows the payouts of TEs are so huge, and even a 5% savings reduces a large expenditure.
  Furthermore, as shown in Fig. <ref>, the daily total payoff of each TE after using the algorithm has increased than before algorithm.
  The payoff (see Equ. (<ref>)) is the utility of the calculation tasks minus the payout.
  Although the green bar is only a little more than the red bar chart, the payoff has also increased a lot because its magnitude is large and arrives 10^9.
  
  
  
  
  
  Fig. <ref> displays the total profit of ESs 1-10 before and after algorithm.
  The total profit of ES is the sum of the profit of all time slots.
  From Fig. <ref>, we can see that the total profit of each ES increases after applying DTOA because the aggregate load profile becomes smoother; and hence, the ESs' generation cost decreases.
  Besides, the suppliers aim to submit optimal bids that maximize their profits in each time slot.
  The results of the algorithm are in line with expectations, which shows the supplier side's individual rationality of our proposed method.
  
  
  
  
   §.§ Peak-reducing effect of algorithm
  
  
  
  
  For simulations, the initial state of TEs' demand is assumed to be load profile before algorithm.
  The aggregate load profile becomes smoother after the DTOA.
  The dashed circle shows the fluctuation of the demand including valley filling and peak clipping.
  Normally, the peak load demand is 26200, while the peak load demand decreases to 23800 in the case of the DTOA.
  Therefore, the peak load demands are shifted from peak to off-peak time slots. 
  Furthermore, the load demand for each TE is shifted to time slots with higher w_j,t, which brings a higher payoff to the TEs.
  This demonstrates that the proposed DTOA performs satisfactorily in reducing the peak load demand.
  
  
  Fig. <ref> shows the PAR (peak-to-average ratio) index with and without task scheduling in 24 time slots and for different number of TEs.
  Before algorithm, since there are high peak load and low average load, PAR index is high.
  By applying DTOA, the peak clipping and valley filling are achieved and the PAR index is low even for high number of TEs.
  This demonstrates that the proposed task scheduling method can shift the shiftable loads from peak periods to off-peak periods effectively.
  
  
  
   §.§ Influence of parameters on iteration numbers
   
  
  In this section, we discuss the influence of some parameters on the convergence speed of the algorithm.
  The convergence speed of the algorithm is reflected in the round of algorithm updates (iteration numbers).
  The smaller the iteration numbers, the faster the algorithm converges.
  The bigger the iteration numbers, the slower the algorithm converges.
  
  Fig. <ref> shows the influence of the parameter ϵ on iteration numbers.
  ϵ is the stopping criterion of the algorithm.
  As can be seen, the smaller the parameter ϵ, the more iterations and the slower the algorithm convergence.
  This fact shows that the stricter of the stopping criterion, the more times the algorithm needs to be updated.
  
  In Fig. <ref>, the influence of the parameter η_2 on iteration numbers are shown.
  Since the parameter η_2 will change in every round, as shown in Table <ref>, we set different initial value of parameter η_2 to show its impact on iteration numbers.
  As can be seen, when other parameters are fixed, with the initial value of parameter η_2 becomes larger, the number of iterations also increases.
  In summary, the speed of the algorithm convergence is related to the setting of some parameters.
  
  
  
  
  
  § CONCLUSION
  
  
  
  In this paper, we analyze a practical resources transaction market in a MEC network, where multiple different ESs offering the optional computing service to TEs.
  Since the resources of each ES are limited, the dynamic demand of its TEs may not be met during spikes in demands.
  To overcome the bottleneck of resource limitation, task outsourcing has been regarded as an effective paradigm by accommodating as many on-demand tasks as possible.
  We focus on the task outsourcing problem among multiple ESs and multiple TEs.
  A bidding mechanism is utilized to describe the serving relationship between ESs and TEs, where the two parties are assigned as sellers and buyers.
  The computing resources of ESs are regarded as commodities.
  
  Simulations results demonstrate that the algorithm increases the ESs' profit and reduces the peak load by shifting the load demand to off-peak periods. Meanwhile, the TEs' payoff are also increased by participating in game process. As for future research, we will focus on the computing offloading of ESs in a three-tier IoT MEC networks.
  
  
  
  
    
  
  § ACKNOWLEDGMENTS
  
  
    
  
  § ACKNOWLEDGMENT
  
  This work is supported by National Natural Science Foundation of China (No.61872129).
  
  
  
  
  IEEEtran
  
  [
      < g r a p h i c s >
  ]Zheng Xiao
  	received the Ph.D. in Computer Science from Fudan University, China, in 2009, and B.S. in Communication Engineering from Hunan University in 2003. He is currently an associate professor in College of Information Science and Engineering of Hunan University. His major research interests include distributed artificial intelligence, high performance computing, parallel and distributed systems, intelligent information processing and collaborative optimization. He has published over 30 journal articles and conference papers. He is currently an associate editor of IEEE Access. He is a member of IEEE and CCF.
  
  
  [
      < g r a p h i c s >
  ]Dan He
  	received the B.S. degree in computer science and technology from Jiangxi Normal University, Nanchang, China, in 2018. She is currently working toward the M.S. degree at the College of Information Science and Engineering, Hunan University, Changsha, China. Her research interests focus on high performance computing, modeling and resource scheduling in cloud computing systems, big data pricing and game theory.
  
  
  [
      < g r a p h i c s >
  ]Yu Chen
      is currently working toward the M.S. degree at the Collage of Information Science and Engineering, Hunan University, China.
  	His research interests focus on machine learning and natural language processing.
  
  
  [
      < g r a p h i c s >
  ]Anthony Theodore Chronopoulos
  	obtained a Ph.D. in Computer Science from the University of Illinois at Urbana-Champaign in 1987. He is a full Professor at the Department of Computer Science, University of Texas, San Antonio, USA and a visiting professor, Department of Computer Engineering & Informatics, University of Patras, Greece. He is the author of 83 journal and 73 peer-reviewed conference proceedings publications in the areas of Distributed and Parallel Computing, Grid and Cloud Computing, Scientific Computing, Computer  Networks, Computational Intelligence. He is a Fellow of the Institution of Engineering and Technology (FIET), ACM Senior member, IEEE Senior member.
  
  
  [
      < g r a p h i c s >
  ]Schahram Dustdar
      is Full Professor of Computer Science (Informatics) with a focus on Internet Technologies heading the Distributed Systems Group at the TU Wien. He is Chairman of the Informatics Section of the Academia Europaea (since December 9, 2016).
      He is elevated to IEEE Fellow (since January 2016).
      From 2004-2010 he was Honorary Professor of Information Systems at the Department of Computing Science at the University of Groningen (RuG), The Netherlands.
      From December 2016 until January 2017 he was a Visiting Professor at the University of Sevilla, Spain and from January until June 2017 he was a Visiting Professor at UC Berkeley, USA.
      He is a member of the IEEE Conference Activities Committee (CAC) (since 2016), of the Section Committee of Informatics of the Academia Europaea (since 2015), a member of the Academia Europaea: The Academy of Europe, Informatics Section (since 2013).
      He is recipient of the ACM Distinguished Scientist award (2009) and the IBM Faculty Award (2012).
      He is an Associate Editor of IEEE Transactions on Services Computing, ACM Transactions on the Web, and ACM Transactions on Internet Technology and on the editorial board of IEEE Internet Computing. He is the Editor-in-Chief of Computing (an SCI-ranked journal of Springer).
  
  
  [
      < g r a p h i c s >
  ]Jiayi Du
  	received his Ph.D., M.S. and B.S. in computer science from Hunan University, China, in 2015, 2010 and 2004.
  	He is currently an assistant professor in Central South University of Forest and Technology, China.
  	His research interest includes modeling and scheduling for parallel and distributed computing systems, embedded system computing, cloud computing, parallel system reliability, and parallel algorithms.
  
  
  