paper on price based product allocation for edge computing: market equilibrim approach
ramnath
1805.029821.pdf
ar X
iv :1
80 5.
02 98
2v 1
[ cs
.G T
] 8
M ay
2 01
8 1
Price-based Resource Allocation for Edge Computing: A Market Equilibrium Approach
Duong Tung Nguyen, Student Member, IEEE, Long Bao Le, Senior Member, IEEE,
and Vijay Bhargava, Life Fellow, IEEE
Abstract—The emerging edge computing paradigm promises to deliver superior user experience and enable a wide range of Internet
of Things (IoT) applications. In this work, we propose a new market-based framework for efficiently allocating resources of
heterogeneous capacity-limited edge nodes (EN) to multiple competing services at the network edge. By properly pricing the
geographically distributed ENs, the proposed framework generates a market equilibrium (ME) solution that not only maximizes the
edge computing resource utilization but also allocates optimal (i.e., utility-maximizing) resource bundles to the services given their
budget constraints. When the utility of a service is defined as the maximum revenue that the service can achieve from its resource
allotment, the equilibrium can be computed centrally by solving the Eisenberg-Gale (EG) convex program. drawn from the economics
literature. We further show that the equilibrium allocation is Pareto-optimal and satisfies desired fairness properties including sharing
incentive, proportionality, and envy-freeness. Also, two distributed algorithms are introduced, which efficiently converge to an ME.
When each service aims to maximize its net profit (i.e., revenue minus cost) instead of the revenue, we derive a novel convex
optimization problem and rigorously prove that its solution is exactly an ME. Extensive numerical results are presented to validate the
effectiveness of the proposed techniques.
Index Terms—Market equilibrium, Fisher market, fairness, algorithmic game theory, edge computing, fog computing.
✦
1 INTRODUCTION
The last decade has witnessed an explosion of data traffic over the communication network attributed to the rapidly growing cloud computing and pervasive mobile devices. This trend is expected to continue for the foreseeable fu- ture with a whole new generation of applications includ- ing 4K/8K UHD video, hologram, interactive mobile gam- ing, tactile Internet, virtual/augmented reality (VR/AR), mission-critical communication, smart homes, and a variety of IoT applications [1]. As the cloud infrastructure and number of devices will continue to expand at an accelerated rate, a tremendous burden will be put on the network. Thus, it is imperative for network operators to develop innovative solutions to meet the soaring traffic demand and accommodate diverse requirements of various services and use cases in the next generation communication network.
Thanks to the economy of scale and supercomputing capability advantages, cloud computing will likely continue to play a prominent role in the future computing landscape. However, cloud data centers (DC) are often geographically distant from the end-user, which induces enormous network traffic, along with significant communication delay and jit- ter. Hence, despite the immense power and potential, cloud computing alone is facing growing limitations in satisfying the stringent requirements in terms of latency, reliability, security, mobility, and localization of many new systems and applications (e.g., embedded artificial intelligence, man- ufacture automation, 5G wireless systems) [1]. To this end, edge computing (EC) [2], also known as fog computing (FC) [1], has emerged as a new computing paradigm that complements the cloud to enable the implementation of innovative services right at the network edge.
EC forms a virtualized platform that distributes com-
puting, storage, control, and networking services closer to end-users to smarten the edge network. The size of an EN is flexible ranging from smartphones, PCs, smart access points (AP), base stations (BS) to edge clouds [3]. For example, a smartphone is the edge between wearable devices and the cloud, a home gateway is the edge between smart appliances and the cloud, a cloudlet, a telecom central office, a micro DC is the edge between mobile devices and cloud core network. Indeed, the distributed EC infrastructure en- compasses any computing, storage, and networking nodes along the path between end devices and cloud DCs, not just exclusively nodes located at the customer edge [3]. By providing elastic resources and intelligence at the edge of the network, EC offers many remarkable capabilities, including local data processing and analytics, distributed caching, location awareness, resource pooling and scaling, enhanced privacy and security, and reliable connectivity.
These capabilities combined with the shorter communi- cation distance allow operators to efficiently handle both downstream and upstream data between the cloud and the customer edge, which translates into drastic network traffic reduction and significant user experience improve- ment. For instance, with edge caching, location-awareness, and real-time data processing and analysis, not only can service providers serve user content requests locally, but also can adaptively optimize video coding and resolution according to the user device information and the varying wireless channel conditions. Also, it is envisioned that most of data produced by IoT sensors will be processed at the edge and only important information and metadata will be sent to the cloud for further analytics. Additionally, EC is the key enabler for ultra-reliable low-latency applications such as AR/VR, cognitive assistance, autonomous driving,
2
industrial automation, remote robotics, and healthcare. A myriad of benefits and other use cases (e.g., computation offloading, caching, advertising, smart homes/grids/cities) of EC can be found in [1]–[3].
Today, EC is still in the developing stages and presents many new challenges, such as network architecture design, programming models and abstracts, IoT support, service placement, resource provisioning and management, security and privacy, incentive design, and reliability and scalability of edge devices [1]–[3]. To unlock the huge potential of this new technology, it requires significant collaborative efforts between various entities in the ecosystem. In this work, we focus on the EC resource allocation problem. Unlike cloud computing, where computational capacity of large DCs is virtually unlimited and network delay is high, EC is characterized by relatively low network latency but consid- erable processing delay due to the limited computing power of ENs. Also, there are a massive number of distributed computing nodes compared to a small number of large DCs. Moreover, ENs may come with different sizes (e.g., number of computing units) and configurations (e.g., computing speed) ranging from a smartphone to an edge cloud with tens/hundreds of servers. These nodes are dispersed in numerous locations with varying network and service delay towards end-users.
On the other hand, different services may have different requirements and properties. Some services can only be handled by ENs satisfying certain criteria. Additionally, different services may be given different priorities. While every service not only wants to obtain as much resource as possible but also prefers to be served by its closest ENs with low response time, the capacities of ENs are limited. Also, due to the diverse preferences of the services towards the ENs, some nodes can be under-demanded while other nodes are over-demanded. Thus, a fundamental problem is: given a set of geographically distributed heterogeneous ENs, how can we efficiently allocate their limited computing resources to competing services with different desires and characteristics, considering service priority and fairness? This work introduces a novel market-based solution framework which aims not only to maximize the resource utilization of the ENs but also to make every service happy with the allocation decision.
The basic idea behind our approach is to assign dif- ferent prices to resources of different ENs. In particular, highly sought-after resources are priced high while prices of under-demanded resources are low. We assume that each service has a certain budget for resource procurement. The budget can be virtual or real money. Indeed, budget is used to capture service priority/differentiation. It can also be interpreted as the market power of each service. Given the resource prices, each service buys the favorite resource bundle that it can afford. When all the resources are fully allocated, the resulting prices and allocation form a market equilibrium (ME). If there is only one EN, an ME can be found easily by adjusting the price gradually until demand equals supply or locating the intersection of the demand and supply curves. However, when there are multiple heteroge- neous ENs and multiple services with diverse objectives and different buying power, the problem becomes challenging. We consider two distinct market models in this work.
In the first model, the money does not have intrinsic
value to the services. Given resource prices, each service aims to maximize its revenue from the allocated resources, without caring about how much it has to pay as long as the total payment does not exceed its budget. This model arises in many real-world scenarios. For example, in 5G networks, the Mobile Edge Computing (MEC) servers of a Telco are shared among different network slices, each of which runs a separate service (e.g., voice, video streaming, AR/VR, connected vehicles, sensing) and serves a group of customers who pay for the service. The Telco can allot dif- ferent budgets to the slices depending on their importance and/or potential revenue generation (e.g., the total fee paid by the users/subscribers of each slice).
Similarly, an application provider (e.g., Uber, Pokemon Go) or a sensor network may own a number of ENs in a city and need to allocate the edge resources to handle requests of different groups of users/sensors. The budget can be decided based on criteria such as the populations of users/sensors in different areas and/or payment levels (subscription fees) of different groups of users. Another example is that a university (or other organizations) can grant different virtual budgets to different departments or research labs so that they can fairly share the edge servers on the campus. The first model may also emerge in the setting of cloud federation at the edge where several companies (i.e., services) pool their resources together and each of them contributes a fixed portion of resource of every EN. Here, the budgets are proportional to the initial contributions of the companies. Instead of resource pooling, these companies may agree upfront on their individual budgets, and then buy/rent a given set of ENs together.
In these scenarios, it is important to consider both fair- ness and efficiency. Thus, conventional schemes such as social welfare maximization, maxmin fairness, and auction models may not be suitable. In particular, a welfare max- imization allocation often gives most of the resources to users who have high marginal utilities while users with low marginal utilities receive a very small amount of resources, even nothing. Similarly, in auction models, the set of losers are not allocated any resource. Hence, these solutions can be unfair to some users. On the other hands, a maxmin fairness solution often allocates too many resources to users with low marginal utilities, hence, it may not be efficient.
To strive the balance between fairness and efficiency, we advocate the General Equilibrium Theory [4], with a specific focus on the Fisher market model [5], as an effec- tive solution concept for this problem. Specifically, the first model can be cast as a Fisher market in which services act as buyers as ENs act as different goods in the market. For the linear additive utility function as considered in this work, given resource prices, a service may have an infinite set of optimal resource bundles, which renders difficulty in designing distributed algorithms. We suggest several methods to overcome this challenge. Moreover, we show that the obtained allocation is Pareto-optimal, which means there is no other allocation that would make some service better off without making someone else worse off [6]. In other words, there is no strictly “better” allocation. Thus, a Pareto-optimal allocation is efficient.
We furthermore link the ME to the fair division literature [7] and prove that the allocation satisfies remarkable fairness
3
properties including envy-freeness, sharing-incentive, and proportionality, which provides strong incentives for the services to participate in the proposed scheme. Indeed, these properties were rarely investigated explicitly in the ME literature. Envy-freeness means that every service prefers its allocation to the allocation of any other service. In an envy-free allocation, every service feels that its share is at least as good as the share of any other service, and thus no service feels envy. Sharing-incentive is another well-known fairness concept. It ensures that services get better utilities than what they would get in the proportional sharing scheme that gives each service an amount of resource from every EN proportional to its budget. Note that proportional sharing is an intuitive way to share resources fairly in terms of quan- tity. For the federation setting, sharing-incentive implies that every service gets better off by pooling their resources (or money) together. Finally, it is natural for a service to expect to obtain a utility of at least b/B of the maximum utility that it can achieve by getting all the resources, where b is the payment of the service and B is the total payment of all the services. The proportionality property guarantees that the utility of every service at the ME is at least proportional to its payment/budget. Thus, it makes every service feel fair in terms of the achieved utility.
In the second model, the money does have intrinsic value to the services. The services not only want to maximize their revenues but also want to minimize their payments. In particular, each service aims to maximize the sum of its remaining budget (i.e., surplus) and the revenue from the procured resources, which is equivalent to maximizing the net profit (i.e., revenue minus cost). This model is prevalent in practice. For example, several service providers (SP), each of which has a certain budget, may compete for the available resources of an edge infrastructure provider (e.g., a Telco, a broker). The SPs only pay for their allocated resources and can take back their remaining budgets. Obviously, a SP will only buy a computing unit if the potential gain from that unit outweighs the cost. It is natural for the SPs to maximize their net profits in this case. The traditional Fisher market model does not capture this setting since the utility functions of the services depend on the resource prices.
It is worth mentioning that, conventionally, the optimal dual variables associated with the supply demand con- straints (i.e., the capacity constraints of the ENs) are often interpreted as the resource prices [32] and common ap- proaches such as network utility maximization (NUM) [33] can be used to compute an ME. However, these approaches do not work for our models that take budget into considera- tion. Indeed, the main difficulty in computing an ME in both models stems from the budget constraints which contain both the dual variables (i.e., prices) and primal variables (i.e., allocation). In the second model, the prices also appear in the objective functions of the services. Therefore, the ME computation problem becomes challenging. Note that the pair of equilibrium prices and equilibrium allocation has to not only clear the market but also simultaneously maximize the utility of every service (as elaborated later in Section 4).
Fortunately, for a wide class of utility functions, the ME in the first model can be found by solving a simple Eisenberg-Gale (EG) convex program [8]–[10]. However, the EG program does not capture the ME in the second
model. Interesting, by reverse-engineering the structure of the primal and dual programs in the first model, we can rigorously construct a novel convex optimization problem whose solution is an ME of the second model. Our main contributions include:
• Modeling. We formulate a new market-based EC resource allocation framework and advocate the General Equilibrium theory as an effective solution method for the proposed problem.
• Centralized solution. The unique ME in the first model can be determined by the EG program. We also prove some salient fairness features of the ME.
• Decentralized algorithms. We introduce several dis- tributed algorithms that efficiently overcome the dif- ficulty raised by the non-unique demand functions of the services and converge to the ME.
• Extended Fisher market. We systematically derive a new convex optimization problem whose optimal solution is an exact ME in the extended Fisher market model where buyers value the money.
• Performance Evaluation. Simulations are conducted to illustrate the efficacy of the proposed techniques.
The rest of the report is organized as follows. Section 2 describes related work. The system model and problem formulation are given in Section 3 and Section 4, respec- tively. The centralized solution using the EG program is an- alyzed in Section 5. Then, we introduce several distributed algorithms in Section 6. The market model in which buyers aim to maximize their net profits is studied in Section 7. Simulation results are shown in Section 8 followed by conclusions and discussion of future work in Section 9.
2 RELATED WORK
The potential benefits and many technical aspects of EC have been studied extensively in the recent literature. First, the hybrid edge/fog-cloud system can be leveraged to im- prove the performance of emerging applications such as cloud gaming and healthcare [11], [12]. A. Mukherjee et. al. [13] present a power and latency aware cloudlet selec- tion strategy for computation offloading in a multi-cloudlet environment. The tradeoff between power consumption and service delay in a fog-cloud system is investigated in [14] where the authors formulate a workload allocation problem to minimize the system energy cost under latency constraints. A latency aware workload offloading scheme in a cloudlet network is formulated in [15] to minimize the average response time for mobile users.
In [16], M. Jia et. al. explore the joint optimization of cloudlet placement and user-to-cloudlet assignment to min- imize service latency while considering load balancing. A unified service placement and request dispatching frame- work is presented in [17] to evaluate the tradeoffs between the user access delay and service cost. Stackelberg game and matching theory are employed in [18] to study the joint optimization among data service operators (DSO), data service subscribers (DSS), and a set of ENs in a three- tier edge network where the DSOs can obtain computing resources from different ENs to serve their DSSs.
Another major line of research has recently focused on the joint allocation of communication and computational
4
resources for task offloading in the Mobile Edge Computing (MEC) environment [19]–[21]. MEC allows mobile devices to offload computational tasks to resource-rich servers lo- cated near or at cellular BSs, which could potentially reduce the devices’ energy consumption and task execution delay. However, these benefits could be jeopardized if multiple users offload their tasks to MEC servers simultaneously. In this case, a user may not only suffer severe interference but also receive a very small amount of EC resource, which would consequently reduce data rate, increase transmission delay, and cause high task execution time on the servers. Hence, offloading decision, allocation and scheduling of radio resources, and computational resources should be jointly considered in an integrated framework.
Instead of optimizing the overall system performance from a single network operator’s point of view, we study the EC resource allocation problem from the game theory and market design perspectives [8]. Specifically, we exploit the General Equilibrium [4], a Nobel prize-winning theory, to construct an efficient market-based resource allocation framework. Although this concept was proposed more than 100 years ago [5], only until 1954, the existence of an ME was proved under mild conditions in the seminal work of Arrow and Debreu [4]. However, their proof of existence based on fixed-point theorem is non-constructive and does not give an algorithm to compute an equilibrium [8]. Recently, theoretical computer scientists have expressed great interests in understanding algorithmic aspects of the General Equilibrium concept. Various efficient algorithms and complexity analysis for ME computation have been accomplished over the past decade [8], [22]–[26]. Note that although the existence result has been established, there is no general technique for computing an ME.
Our proposed models are inspired by the Fisher market [5] which is a special case of the exchange market model in the General Equilibrium theory. An exchange market model consists of a set of economic agents trading different types of divisible goods. Each agent has an initial endowment of goods and a utility function representing her preferences for the different bundles of goods. Given the goods’ prices, every agent sells the initial endowment, and then uses the revenue to buy the best bundle of goods they can afford [4], [8]. The goal of the market is to find the equilibrium prices and allocations that maximize every agent’s utility respecting the budget constraint, and the market clears. In the Fisher market model, every agent comes to the market with an initial endowment of money only and wants to buy goods available in the market. We cast the EC resource allocation problem as a Fisher market. We not only show appealing fairness properties of the equilibrium allocation, but also introduce efficient distributed algorithms to find an ME. More importantly, we systematically devise a new and simple convex program to capture the market in which money has intrinsic value to the buyers, which is beyond the scope of the Fisher and exchange market models.
Note that there is a rich literature on cloud resource allo- cation and pricing [34]. In [35], [36], the authors propose dif- ferent profit maximization frameworks for cloud providers. References [37]–[39] study how to efficiently share resource and profit among cloud providers in a cloud federation. Several resource procurement mechanisms are introduced
in [40] to assist a cloud user to select suitable cloud vendors in a multi-cloud market. In [41], the interaction between a cloud provider and multiple services is modeled as a generalized Nash game. This model is extended to a multi- cloud multi-service environment in [42]. A single-cloud multi-service resource provision and pricing problem with flat, on-demand, and on-spot VM instances is formulated in [43] as a Stackelberg game, which not only maximizes the revenue of the cloud provider but also minimizes costs of the services.
Auction theory has been widely used to study cloud resource allocation [44]–[46]. A typical system consists of one or several clouds and multiple users. First, the users submit bids, which include their desired resource bundles in terms of VM types and quantities as well as the price that they are willing to pay, to an auctioneer. Then, the auctioneer solves a winner determination problem to identify accepted bids. Finally, the auctioneer calculates the payment that each winner needs to pay to ensure truthfulness. In auction, the common objectives are to maximize the social welfare or maximize the profit of the cloud provider. Additionally, only winners receive cloud resources. Furthermore, most of ex- isting auction models do not consider elastic user demands. For example, previous works often assume that cloud users are single-minded, who are interested in a specific bundle only and have zero value for other bundles.
Different from the existing works on cloud economics and resource allocation in general, our design objective is to find a fair and efficient way to allocate resources from multiple nodes (e.g., ENs) to budget-constrained agents (i.e., services), which makes every agent happy with her resource allotment and ensures high edge resource utilization. The proposed model also captures practical aspects, for example, a service request can be served at different ENs and service demands can be defined flexibly rather than fixed bundles as in auction models.
3 SYSTEM MODEL
An EC environment is depicted in Fig. ??. Besides local execution and remote processing at cloud DCs, data and requests from end-devices (e.g., smartphones, set-top-boxes, sensors) can be handled by the EC platform. Note that some data and computing need to be done in the local to keep data privacy. A request typically first goes to a Point of Aggre- gation (PoA) (e.g., switches/routers, BSs, APs), then it will be routed to an EN for processing. Indeed, enterprises, fac- tories, organizations (e.g., hospitals, universities, museums), commercial buildings (shopping malls, hotels, airports), and other third parties (e.g., sensor networks) can also outsource their services and computation to the intelligent edge net- work. Furthermore, service/content/application providers like Google, Netflix, and Facebook can proactively install their content and services onto ENs to serve better their cus- tomers. In the EC environment, various sources (e.g., smart- phones, PCs, servers in a lab, underutilized small/medium data centers in schools/hospitals/malls/enterprises, BSs, telecom central offices) can act as ENs.
We consider a system encompassing various services and a set of geographically distributed ENs with different configurations and limited computing capacities. Each ser- vice has a budget for resource procurement and wants to
5
offload as many requests as possible to the edge network. The value of an EN to a service is measured in terms of the maximum revenue that it can generate by using the EN’s resource. An EN may have different values to different ser- vices. Since some ENs (e.g., ones with powerful servers) can be over-demanded while some others are under-demanded, it is desirable to harmonize the interests of the services so that each service is happy with its allotment while ensuring high resource utilization. An intuitive solution is to assign prices to ENs and let each service choose its favorite re- source bundle. We assume that there is a platform lying between the services and the ENs. Based on the information collected from the ENs (e.g., computing capacity) and the services (e.g., budgets, preferences), the platform computes an ME solution including resource prices and allocation, which not only maximizes the satisfaction of every service but also fully allocates the ENs’ resources.
In the first model, each service seeks solely to maximize its revenue under the budget constraint, without concerning about the money surplus after purchasing resources. This can be the case where the services and ENs belong to the same entity, and each service is assigned a virtual budget representing the service’s priority. For instance, a Telco can give different budgets to different network slices, each of which runs a service (e.g., voice, video streaming, AR/VR, connected vehicles). In the second model, the remaining money does have intrinsic value to the services. In this case, each service aims to maximize the sum of its remaining bud- get and the revenue from the procured resources. For exam- ple, this can be the case where services and ENs are owned by different entities, and each SP (e.g., Google, Facebook, enterprises) has a certain budget for leasing resources from an infrastructure provider (e.g., a Telco). For simplicity, we assume that the values of ENs to the services are fixed. Our model can be extended to capture time-varying valuation in a multi-period model by considering each pair of an EN and a time slot as an independent EN.
4 PROBLEM FORMULATION
4.1 EC Resource Allocation Problem
Let M, N , M, and N be the sets of ENs and services, and the numbers of ENs and services, respectively. Denote i as the service index and j as the EN index. We assume that each EN j has cj homogeneous computing units (e.g., servers) [18]. If an EN has several types of computing units, we can always divide the EN into several clusters, each of which contains only homogeneous units. Then, each cluster can be considered as a separate EN. While the computing units in each EN are homogeneous, different ENs can have different types of computing units. Let xi,j be the number of computing units of EN j allocated to service i. The vector of resources allocated to service i is xi =
(
xi,1, xi,2, . . . , xi,M )
. Finally, define Bi as the budget of service i.
Our goal is to compute an ME including an equilibrium price vector p = (p1, p2, ..., pM), where pj is price of EN j, and a resource allocation matrix X , in which the element at the ith row and jth column is xi,j . The utility Ui(xi, p) of service i is defined as a function of the amount of resources xi that it receives and the resource prices p. The capacity constraint of ENs renders:
∑N i=1 xi,j ≤ cj, ∀j ∈ M. Without
loss of generality, we normalize the capacity of every EN to be 1 (i.e., cj = 1, ∀j) and scale related parameters (e.g., price, resource allocation) accordingly. This normalization is just to simplify expressions and equations. Hence, we have: ∑N
i=1 xi,j ≤ 1, ∀j, xi,j ≥ 0, ∀j. Each service is a player in our market game. Given a
price vector p, service i aims to maximize its utility Ui(xi, p) subject to the budget constraint
∑
j xi,jpj ≤ Bi.
Definition 4.1. An ME solution (p∗,X∗) needs to satisfy the two conditions:
• Condition 1: Given the equilibrium resource price vector p∗ = (p∗1, p
∗ 2, ..., p
∗ M ), every service i receives
its optimal resource bundle x∗i , i.e., we have
x∗i = (x ∗ i,1, . . . , x
∗ i,M ) ∈ argmax
xi≥0; ∑
j p∗ j xi,j≤Bi
Ui(xi, p ∗) (1)
• Condition 2: All the resources are fully allocated, i.e. , we have:
∑
i xi,j = 1, ∀j.
The first condition can be interpreted as the user satisfac- tion condition while the second condition is often called the market clearing condition in Economics [6]. The first condition ensures that the equilibrium allocation x∗i maximizes the utility of service i at the equilibrium prices p∗ considering the user budget constraint. The second condition maximizes the resource utilization of the ENs. It also means the ENs’ resources are fully sold in the market, which consequently maximizes the profit of every EN since the equilibrium prices are non-negative. The services are players competing for the limited EC resources, while the platform tries to satisfy the market clearing condition. Prices are used to coordinate the market.
Let ui(xi) be the gain/profit/revenue of service i can achieve from the procured resources. We consider two mod- els. In the first model (basic model), every service i wants to maximize Ui(xi, p) = ui(xi) and does not care about how much it has to pay as long as the total payment is under its budget. Here, utility of a service is its revenue. In the second model, instead of revenue, the services aim to maximize their net profits (i.e., revenue minus cost). The service utility in this model is Ui(xi, p) = ui(xi) −
∑
j pjxi,j, ∀i. We focus on the first model throughout the report. The second model is examined in Section 7.
4.2 Service Utility Model
In practice, the services may use different criteria to define ui(xi). Our framework takes ui(xi) as an input to compute an ME solution. How each service evaluates the ENs is not the focus of this work. While the proposed model is generic, we consider linear functions for the ease of exploring the framework. Extensions to more general functions will be discussed throughout the work. Let ai,j be the gain of service i from one unit of resource of EN j. Then, we have: ui(xi) =
∑
j ai,jxi,j, ∀i. In the following, we present an example of how ai,j
can be computed. We consider only delay-sensitive services, which are also the main target application of EC. For simplicity, we assume that the transmission bandwidth is sufficiently large and the data size of a request is small (e.g., Apple Siri, Google Voice Search, Google Maps, AR, and Translation). Hence, the data transmission delay (i.e.,
6
size/bandwidth) is assumed to be negligible and we con- sider only propagation delay and processing delay [27], [41].
The total delay of a request of service i from the time a user sends the request to the time she receives a response includes the round-trip delay dUE−PoAi between the user and a PoA of the service, the round-trip network delay dni,j between the PoA and an EN i hosting the service, and the processing delay at the EN d
p i,j . Note that an EN can be
located in the same place with a PoA (e.g., a BS). In reality, dUE−PoAi is quite small, and we assume it is fixed similar to [15]. In other words, we study the system only from the aggregation level to the EC platform. For simplicity, we assume that each service is located at one PoA (e.g., an IoT gateway, a BS, a building). If a service has several PoAs, we need to take sum over all the PoAs to get the total number of requests of the service handled by the EC platform. Denote T maxi as the maximum tolerable delay of service i, we have
d p i,j + d
n i,j ≤ T
max i , ∀i, j. (2)
Obviously, the maximum number of requests λmaxi,j that EN j can process is zero if dni,j ≥ T
max i .
We model the processing delay at ENs using the widely used M/G/1 queues and assume that the workload is evenly shared among computing units [18], [27], [28], [41]. The average response time d
p i,j of EN j for processing
service i can be computed as follows:
d p i,j =
1
µi,j − λi,j xi,j
, ∀i, j (3)
where µi,j be the service rate of one computing unit of EN j for handling service i, and λi,j is the request arrival rate (i.e., number of requests per time unit) of service i to EN j.
For queue stability, we have λi,j xi,j
< µi,j, ∀i, j. Otherwise, the queuing delay will be infinite as requests accumulated.
From (3), we have
1
µi,j − λi,j xi,j
≤ T maxi − d n i,j (4)
⇒ λi,j ≤ xi,j (
µi,j − 1
T maxi − di,j
)
.
Therefore, if dni,j < T max i , the maximum number of
requests that service i can process at EN j is
λmaxi,j = max {
xi,j (
µi,j − 1
T maxi − di,j
)
, 0 }
(5)
= xi,jqi,j, ∀i, j
where qi,j = max {(
µi,j − 1
T max i
−di,j
)
, 0 }
. Define a success-
ful request as the request whose total delay is smaller or equal to the maximum delay tolerance. Let ri be the benefit of successfully serving one request of service i [18]. Then, given xi,j computing units, the revenue of service i is
ui,j(xi,j) = riqi,jxi,j = ai,jxi,j, ∀i, j (6)
with ai,j = riqi,j . Thus, we have
ui(xi) = M ∑
j=1
ui,j = M ∑
j=1
ai,jxi,j, ∀i (7)
in which ai,j can be computed beforehand. Note that we implicitly assume the request pool of a service is unlimited. We will discuss later how some assumptions can be relaxed.
Definition 4.2. A function u(.) is homogeneous of degree d, where d is a constant, if u(αx) = αdu(x), ∀ α > 0 [8].
From (7), it is easy to verify that ui(xi) is a linear function that is homogeneous of degree 1.
Remark: The value of an EN to a service can be defined flexibly. For example, a service may give higher values to ENs in a populated area or ENs with high reliability. A suitable weight can be added to ai,j . In the proposed model, each service informs the platform its budget and how much it values different ENs. Based on these information, the plat- form computes suitable resource allocation satisfying given design objectives. How each service utilizes its allocated resources in the operation stage is not the focus of this work. The key concern of our work is how to harmonize the interests of different services that may have different preferences towards the ENs. Also, we consider only delay- sensitive services to illustrate one way to model the service utility function. It can be justified by the fact that non- delay-sensitive services can be handled effectively by cloud DCs and the precious edge resources can be reserved for important low-latency services. Nevertheless, our model is generic enough to handle other service types as long as we can define the utility of a service as a suitable function of its allocated EC resources. Finally, although we consider computing resources only, the proposed framework can apply to a system in which each service evaluates an EN based on a combination of different resource types of the EN, such as computing, storage, and bandwidth.
5 CENTRALIZED SOLUTION
In the first model, each service i aims to maximize Ui(xi, p) = ui(xi) =
∑
j ai,jxi,j subject to the budget constraint
∑
j pjxi,j ≤ Bi, ∀i. If p is a price vector, the ratio ai,j/pj is defined as the bang-per-buck of EN j to service i, which indicates the utility gained by service i through one unit of money spent on EN j (assuming 0/0 = 0). The maximum bang-per-buck (MBB) of service i over the set of ENs is αi = maxj{ai,j/pj} [22]. The demand set Di(p) of service i includes all ENs giving it the MBB value, i.e., Di(p) = {j : ai,j/pj = αi}, ∀i. Intuitively, to maximize its utility, each service will spend full budget to buy resources from only ENs giving it the MBB. Therefore, a pair (X, p) is an ME if: i) given prices p, service i will exhaust its budget to buy resources only from ENs in Di(p); and ii) the market clears at prices p. In the following, we will show that the ME in the first model can be inferred from the optimal solution of a convex optimization problem. Also, we will describe some properties of the equilibrium. Specifically, for the case of buyers with linear utilities, the ME can be found by solving the EG convex program given below [8], [9]:
maximize X ,u
N ∑
i=1
Bi ln ui (8)
subject to ui =
M ∑
j=1
ai,jxi,j, ∀i (9)
N ∑
i=1
xi,j ≤ 1, ∀j (10)
xi,j ≥ 0, ∀i, j. (11)
7
This problem always has an interior feasible solution by simply setting xi,j = ǫ > 0, for all i and j, where ǫ is suffi- ciently small such that all constraints (50)-(51) are satisfied with strict inequality. Hence, Slaters condition holds and the the Karush–Kuhn–Tucker (KKT) conditions are necessary and sufficient for optimality [32]. Denote ηi, pj , and νi,j as the dual variables associated with constraints (49), (50), and (51), respectively. We have the Lagrangian
L(u, X, η, p, ν) = ∑
i
Bi ln ui + ∑
j
pj(1 − ∑
i
xi,j) (12)
+ ∑
i
ηi (
∑
j
ai,jxi,j − ui )
+ ∑
i
∑
j
νi,jxi,j.
The KKT conditions give ∂L
∂ui =
Bi ui
− ηi = 0, ∀i (13)
∂L
∂xi,j = Bi
ai,j ui
− pj + νi,j = 0, ∀i, j (14)
ui = ∑
j
ai,jxi,j, ∀i; pj(1 − ∑
i
xi,j) = 0, ∀j (15)
νi,jxi,j = 0, ∀i, j; pj ≥ 0, ∀j; νi,j ≥ 0, ∀i, j. (16)
We can infer the following
∀i, j : ui Bi
≤ ai,j pj
(17)
∀i, j : if xi,j > 0 ⇒ νi,j = 0 ⇒ ui Bi
= ai,j pj
(18)
∀j : pj > 0 ⇒ ∑
i
xi,j = 1; ∑
i
xi,j < 1 ⇒ pj = 0. (19)
If p is a price vector, the ratio ai,j/pj is defined as the bang-per-buck of EN j to service i, which indicates the utility gained by service i through one unit of money spent on EN j (assuming 0/0 = 0). The maximum bang-per-buck (MBB) of service i over the set of ENs is αi = maxj{ai,j/pj} [22]. The demand set Di(p) of service i includes all ENs giving it the MBB value, i.e., Di(p) = {j : ai,j/pj = αi}, ∀i.
The dual variable pj in the EG program can be inter- preted as the price of EN j. Hence, conditions (77) and (87) imply that xi,j > 0 if and only if j ∈ Di(p), i.e., each service buys resources only from ENs giving it the MBB. This also maximizes ui(xi). The following theorem captures the relationship between the EG program and the ME solution as well as some properties of the equilibrium.
Theorem 5.1. The optimal solution to the EG convex pro- gram (48)-(51) is an ME. Specifically, the Lagrangian dual variables corresponding to the ENs’ capacity constraints (50) are the equilibrium prices. At the equilibrium, the resource allocation not only maximizes the utility but also exhausts the budget of every service. Furthermore, each service purchases resources only from ENs giving its MBB. Additionally, the optimal utilities of the services as well as equilibrium prices are unique.
Proof: Let X∗ and u∗i be the optimal solution to the EG pro- gram. Then, X∗ and u∗i need to satisfy the KKT conditions (73)-(88). Denote η∗, p∗, and ν∗ as the optimal dual variables. From (74), we have
Bi ai,j u∗i
= p∗j − ν ∗ i,j, ∀i, j. (20)
Multiplying both sides of (20) by x∗i,j and adding the result- ing equalities, we get
Bi u∗i
∑
j
ai,jx ∗ i,j =
∑
j
(p∗j − ν ∗ i,j)x
∗ i,j, ∀i, j. (21)
Since ν∗i,jx ∗ i,j = 0, ∀i, j, and ui∗ =
∑
j ai,jx ∗ i,j, ∀i, equation
(21) implies ∑
j p ∗ jx
∗ i,j = Bi, ∀i. Thus, the optimal solution
to the EG program (48)-(51) fully exhausts the budget of every service. Furthermore, as shown above, at the optimal- ity, each service buys resources only from ENs giving its MBB value. In other words, the optimal solution to the EG program maximizes the utility of every service subject to the budget constraint because every service uses all of its money to purchase its MBB resources. This can be inferred from (77) and (87).
We now consider the market clearing condition. From (88), we can observe that resources of ENs with positive price pj are fully allocated. For ENs with zero prices, their resources can be allocated arbitrarily without affecting the optimal utility of service since the price is zero [8]. Thus, the market clears. Since (X∗, p∗) satisfies both conditions of an ME, the optimal solution to the EG program is an ME.
Finally, since the objective function (48) is strictly con- cave in ui for all i, the optimal utilities are unique. The uniqueness of equilibrium prices can be inferred from (87). �
From (20), if p∗j = 0, then ν ∗ i,j = 0 and ai,j = 0, ∀i, j,
which means an EN has price of zero only when it is not wanted by all services. We can remove this EN from our system. In the following, we consider only the case where pj > 0, ∀j. Also, it can be shown that Theorem 5.1 is not only applied to linear utilities, but also true for a wider class of homogeneous concave utility functions [10]. Please refer to Appendix D for more details.
Next, we study the properties of the equilibrium alloca- tion. First, from (48)-(51), it can be easily verified that the equilibrium allocation is scale-free. It means that it does not matter if service i reports ai = (ai,1, . . . , ai,M ) or eiai for some constant ei, the allocation that it receives is the same. Also, if a service divides its budget into two parts and acts as two different services with the same original utility function, then the total allocation it obtains from the new ME is equal to the original equilibrium allocation. Furthermore, the equilibrium allocation is not only Pareto-optimal but also possesses many appealing fairness properties such as envy-freeness, sharing incentive, and proportionality.
An allocation is Pareto-optimal if there is no other al- location that would make some service better off without making someone else worse off [6], which means there is no strictly “better” allocation. Hence, a Pareto-optimal alloca- tion is efficient and non-wasteful because the remaining re- sources (if any) cannot improve utility of any service. Envy- freeness means that every service prefers its allocation to the allocation of any other service. When the services have equal budgets, an envy-free allocation X implies ui(xi) ≥ ui(xi′ ) for all i and i′ ∈ N [7]. In an envy-free allocation, every service feels that her share is at least as good as the share of any other service, and thus no service feels envy. Since the budgets can be different, we need to extend the classical definition of envy-freeness. An allocation X is envy-free if ui(
xi Bi
) ≥ ui( xi′ Bi′
), ∀i, i′ ∈ N .
8
Let x̂ be the allocation where each service receives resource from every EN proportional to its budget, i.e., x̂i,j =
Bi ∑
′
i Bi′
, ∀i, j. Sharing-incentive property implies
ui(xi) ≥ ui(x̂i), ∀i. Indeed, x̂ is an intuitive resource- fair allocation that allocates resources from every EN to each service proportional to the service budget. We can also understand that each service i contributes an amount of x̂i,j to EN j in a resource pool consisting of the ENs. Sharing- incentive ensures that every service prefers the equilibrium allocation to its initial resource contribution to the pool. This can be interpreted as resource-fairness.
Finally, if ui(xi) ≥ Bi
∑
i′ Bi′ ui(C), for all i, in which ui(C)
is the utility of service i when it receives all the resources from the market (i.e., C = (1, ..., 1), C ∈ RM ), we say that the allocation X satisfies the proportionality property. Indeed, ui(C) is the maximum utility that every service i can achieve from the EC resource pool. The proportion- ality property guarantees that the utility of every service at the ME is at least proportional to its payment/budget. Thus, this property can be interpreted as utility-fairness. Obviously, these fairness properties encourage services to participate in the proposed resource allocation scheme.
Theorem 5.2. At equilibrium, the allocation is Pareto-optimal and envy-free. It also satisfies the sharing-incentive and proportionality properties.
Proof: Since at the equilibrium, every service exhausts its budget and receives its favorite resource bundle, it does not envy with other services. Hence, the equilibrium allocation is envy-free. The Pareto-optimality follows directly from the first-welfare theorem in Economics [6], [8]. Indeed, Pareto- optimality can also be inferred from the Nash Bargaining concept [31]. In particular, the problem (48)-(51) has the objective in the form of a Nash Social Welfare function with closed, compact, and convex feasible region. Thus, it enjoys all compelling properties of a Nash Bargaining solution such as Pareto efficiency and scale-invariance. For linear utilities, we can prove the properties above directly as follows.
- Pareto Optimality: We show this by contradiction. As- sume allocation X∗ is not Pareto-optimal. Then, there exists an allocation X′ such that ui(x
′ i) ≥ ui(x
∗ i ) for all i, and
ui(x ′ i) > ui(x
∗ i ) for some i. Note that ui(xi) =
∑
j ai,jxi,j . Consider any feasible allocation X′. Recall the MBB of buyer i is αi = maxj
ai,j pj
. We have
∑
j
x′i,jpj ≥ ∑
j
x′i,j ai,j αi
≥ ∑
j
x∗i,jai,j 1
αi =
∑
j
x∗i,jpj. (22)
The second inequality is due to ui(x ′ i) ≥ ui(x
∗ i ), ∀i. Thus
∑
j
x′i,jpj ≥ Bi, ∀i. (23)
Since ui(x ′ i) > ui(x
∗ i ) for some i,
∑
j x ′ i,jpj ≥ Bi for some
i. Adding both sides of (23) over all buyers renders
∑
i
Bi < ∑
i
∑
j
x′i,jpj = ∑
i
xi,j ∑
j
pj ≤ ∑
j
pj (24)
because ∑
i x ′ i,j ≤ 1, ∀j (i.e., the capacity constraints of
ENs). However, (24) means the total prices of all the ENs is greater than the total budget of all buyers, which cannot occur. Thus, the equilibrium allocation X∗ is Pareto-optimal.
- Envy-freeness: To prove that X∗ is envy-free, we need to show: Bi′ui(x
∗ i ) ≥ Biui(x
∗ i′ ), ∀i, i
′ ∈ N . Let bi,j be the total money that service i spends on EN j. We have
Bi′ui(x ∗ i ) = Bi′
∑
j
ai,jx ∗ i,j = Bi′
∑
j
ai,j b∗i,j pj
(25)
= Bi′ ∑
j
ai,j pj
b∗i,j = B ′ iαi
∑
j
b∗i,j
= B′iαiBi = Biαi ∑
j
b∗i′,j
≥ Bi ∑
j
ai,j pj
b∗i′,j = Bi ∑
j
ai,j b∗i′,j pj
= Bi ∑
j
ai,jx ∗ i′,j = Biui(x
∗ i′ ), ∀i, j.
Note that the equalities in the second line of (25) can be inferred from the fact that each buyer only buys resources from ENs in its demand set Di while the first inequality in the fourth line holds because αi ≥
ai,j pj
, ∀i, j. - Proportionality: From Theorem 5.1,
∑
i x ∗ i,j = 1, ∀j.
Thus, for linear utilities and the envy-free property, we have
ui(C) = ui (
∑
i
x∗i )
= ui (
x∗i )
+ ∑
i′ 6=i
ui (
x∗i′ )
(26)
≤ ui (
x∗i )
+ ∑
i′ 6=i
Bi′
Bi ui (
x∗i )
=
∑
i′ Bi′
Bi ui (
x∗i )
.
Hence, ui(x ∗ i ) ≥
Bi ∑
i′ Bi′
ui(C), ∀i. - Sharing-incentive: At the ME (X∗, p∗), no service spends
more than its budget. We have ∑
i
∑
j
x∗i,jp ∗ j ≤
∑
i
Bi ⇒ ∑
j
p∗j ∑
i
x∗i,j ≤ ∑
i
Bi (27)
Thus, ∑
j p ∗ j ≤
∑
i Bi. Consequently, resource bundle x̂i costs service i:
∑
j x̂i,jp ∗ j =
∑
j Bi
∑
i′ Bi′
p∗j ≤ Bi, ∀i. So, service i can afford to buy bundle x̂i at prices p
∗. However, out of all feasible bundles that are affordable to service i, its favorite one is x∗i . It means ui(x
∗ i ) ≥ ui(x̂i), ∀i. �
6 DECENTRALIZED SOLUTION
A common approach for implementing distributed algo- rithm is to let the platform iteratively compute prices of the ENs and broadcast the updated prices to the services. Then, each service finds its optimal demand bundle and sends the updated demand to the platform. This price-based strategy can be implemented in a tatonnment style or using the dual decomposition method [33]. Unfortunately, linear utilities may result in non-unique optimal demand bundles because multiple ENs may give the same MBB to a buyer. Hence, the algorithm cannot terminate without aggregated demand coordination from the platform. Consider an example with two services and three ENs. The system parameters are: B1 = $1, B2 = $4, a1 = (1, 10, 4), and a2 = (4, 8, 8).
Fig. 1(a) presents the ME from the centralized EG pro- gram. The value associated with each edge between a ser- vice and an EN indicates the amount of resource that the service buys from the EN. For example, in Fig. 1(a), we have: x1,1 = 0, x1,2 = 0.5, and x1,3 = 0. The equilibrium price vector is p = (1, 2, 2). The demand sets are: D1 = {2} and D2 = {1, 2, 3}. Given the equilibrium prices, the set of
9
optimal (i.e., utility-maximizing) resource bundles of service 2 is infinite. Hence, even if a distributed algorithm reaches the exact equilibrium prices at some iteration, it may not stop since the total demand reported by the buyers may not equal to the total supply. For instance, in Fig. 1(b), although the platform announces the exact equilibrium prices, service 2 may choose to buy all resources from EN2 and EN3. Then, the algorithm may never terminate. In the following, we present two distributed algorithms to find the ME.
��� ��� ���
�� ��
�� �� ��
��� � ����
�� � ��
��
�� �
�
(a) With coordination
��� ��� ���
�� ��
�� �� ��
��� � ����
�� � ��
�
�� �
(b) Without coordination
Fig. 1: Market equilibrium with linear utilities
6.1 Dual Decomposition with Function Approximation
Using Lagrangian relaxation [32], [33], we can decompose the EG convex program into sub-problems, each of which can be solved by a service. We observe that the EG program (48)-(51) can be written equivalently as follows.
maximize X
N ∑
i=1
Bi ln ui(xi) (28)
subject to N ∑
i=1
xi,j ≤ 1, ∀j; xi,j ≥ 0, ∀i, j.
Relaxing the coupling constraints, the partial Lagrangian is
L(X, p) = ∑
i
Bi ln ui(xi) + ∑
j
pj (
1 − ∑
i
xi,j )
(29)
= ∑
i
(
Bi ln ui(xi) − ∑
j
pjxi,j )
+ ∑
j
pj.
Thus, given a price vector p, each service solves
maximize xi≥0
Bi ln ui(xi) − ∑
j
pjxi,j. (30)
To overcome the difficulty raised by the non-uniqueness of the optimal demand of the services with linear utilities, we propose to approximate the linear utility function by a Constant Elasticity of Substitution (CES) function, which is widely used in Economics and Computer Science [6], [8]. A CES function has the following form: uCESi (xi) = (
∑M j=1(ai,jxi,j)
ρ )
1
ρ
, ρ < 1, ρ 6= 0. Indeed, the linear utility
function is a special case of the CES function family as ρ → 1. We can approximate the original linear utility function by a CES function where ρ = 1−ǫ with ǫ is arbitrarily small. As ǫ → 0, uCESi → ui. Clearly, a CES function is strictly concave and homogeneous [6]. Hence, the EG program and Theorem 5.1 also apply to CES functions [8], [10]. Additionally, we can observe that maximizing a CES function above is equivalent to maximizing ui(xi) =
∑
j(ai,jxi,j) ρ. Since a CES function
is strictly concave, the optimal demand bundle of a service is unique. Consider the following optimization problem
maximize xi≥0
ui(xi) subject to ∑
j
pjxi,j ≤ Bi. (31)
Proposition 6.1. Given a positive price vector p and a CES approximation function, each service i can either solve Problem (38) or Problem (36). Both the problems have the same closed form solution as follows:
xi,j = (a
ρ i,j
pj
) 1
1−ρ Bi ∑M
j=1
(
ai,j pj
)
ρ 1−ρ
. (32)
Proof: Refer to Appendix A. �
Thus, based on the dual decomposition method where each service solves the sub-problem (38), we have the fol- lowing distributed algorithm with CES function approxima- tion (Algorithm 1). With a sufficiently small step size, it is guaranteed to terminate and converge to an (approximate) global optimal solution [32], [33]. Our simulation results confirm that Algorithm 1 produces a solution arbitrarily close to the optimal one from the centralized EG program.
Algorithm 1 FUNCTION APPROXIMATION ALGORITHM
1: Initialization: iteration t = 0, set initial prices of ENs p(0) = p0, and set step size α(0) and tolerance γ to be small.
2: repeat 3: At iteration t, the platform broadcasts prices p(t) to the buyers. 4: Each buyer computes its optimal demand xi(t) using (39) and
sends it to the platform. 5: The platform updates the prices
pj(t + 1) = max {
pj(t) + α(t) (
1 − ∑N
i=1 xi,j(t)
)
, 0 }
, ∀j 6: until
∣
∣pj(t + 1) − pj(t) ∣
∣ < γ, ∀j, or the number of iterations t is too large.
7: Output: equilibrium prices p∗ and optimal allocation X∗.
6.2 Proportional Response Dynamics Strategy
In this section, we present the Proportional Response Dy- namics (PropDyn) algorithm proposed by the P2P com- munity. This distributed algorithm is very simple to im- plement and has been proved to converge to an ME [29]. Basically, in every iteration t, each service updates its bids proportional to the utilities it receives from the previous
iteration. Specifically, bi,j(t) = Bi ui,j(t−1) ui(t−1)
, ∀i, j, t. Since the ENs’ capacities are normalized, the price of an EN equals to the total bids sent to it, i.e., pj(t) =
∑
i bi,j(t). By bidding bi,j(t − 1) to EN j, service i obtains an amount of resource xi,j(t − 1) = bi,j(t − 1)/pj, and gains a utility ui,j(t−1) = ai,jxi,j(t−1). Finally, ui(t−1) =
∑
j ui,j(t−1) is the total utility of service i at iteration t − 1. The salient feature of this algorithm is that it can be implemented efficiently in a distributed manner. In particular, each EN only needs to know the total bid that it receives to compute the price while each buyer only needs to know its own information and learns its utilities achieved in the previous iteration to compute its new bids. The algorithm terminates when the price deviation of every EN is sufficiently small [29]. The major difference between this novel algorithm and traditional distributed algorithms is that in each iteration, every service computes its new bids as mentioned above instead of its optimal demand bundle.
10
Algorithm 2 BEST RESPONSE DYNAMICS ALGORITHM [30]
1: Sort ENs according to the decreasing order of ai,j b −i,j
.
Output a sorted list Li = {i1, i2, . . . , iM }. 2: Find the largest k such that
√ ai,ik
b −i,ik
∑
k j=1
√
ai,ij b −i,ij
(
Bi + ∑
k j=1
b−i,ij
)
− b−i,ik ≥ 0
3: Set bil = 0 for l > k, and for 1 ≤ l ≤ k, set
bil =
√ ai,il
b −i,il
∑
k j=1
√
ai,ij b −i,ij
(
Bi + ∑k
j=1 b−i,ij
)
− b−i,il
To illustrate the effectiveness of the PropDyn mecha- nism as well as the ME concept, we compare it with the Proportional Sharing Best Response (BR) mechanism (PropBR) proposed in [30], which aims to find a Nash Equilibrium (NE). In a non-cooperative game, a NE is a stable state of a system where no player can gain by a unilateral change of strategy if the strategies of the others are fixed [8]. Both [29] and [30] study a proportional sharing system where the resource of every node is shared proportionally to the services according to their bids. Specifically, we have
xi,j = bi,j
bi,j+b−i,j , ∀i, j, where b−i,j is the total bid of all
the services except i. In both mechanisms, the actions of the services are the bids (bi,j ) submitted to the ENs. However, instead of updating its bids following the rule in PropDyn, each service in the PropBR mechanism tries to selfishly maximize its utility given strategies taken by other services [30].
Algorithm 2 is the BR algorithm that buyer i will execute given the total bid b−i,j of other buyers. The whole algo- rithm is implemented in rounds. In each round, each buyer in turns runs Algorithm 2 and updates its bid vector bi to the platform. The platform broadcasts new bids to all buyers in the system. A round completes when all buyers have updated their bids. Obviously, whenever this BR dynamics strategy converges, it converges to an NE. As mentioned in [30], the algorithm normally converges after a few rounds.
Interestingly, our simulation shows that buyers do not gain significantly by playing BR. Indeed, most of buyers achieve lower utilities in the PropBR scheme compared to the PropDyn scheme. Furthermore, to play BR dynamics, each buyer has to know total bids of others and the actual capacity of every EN [30]. In PropDyn, buyers only need to know their own information. Therefore, in a proportional sharing system, buyers may not have incentives to play BR.
7 NET PROFIT MAXIMIZATION
Different from the basic model, in the second model, the services try to optimize their net profits (i.e., revenue minus cost) instead of revenue. Specifically, the net profit of service i is vi(xi) =
∑
j(ai,j − pj)xi,j, ∀i. Given prices p, the objective of service i is to maximize Ui(xi, p) = vi(xi) subject to:
∑
j xi,jpj ≤ Bi, ∀i and xi,j ≥ 0, ∀i, j. Indeed, maximizing the net profit vi(xi) is equivalent to maximizing
∑
j(ai,j −pj)xi,j +Bi = ∑
j ai,jxi,j +si, where si = Bi −
∑
j pjxi,j is the surplus money of service i after purchasing xi. Inspired by the EG program for the basic model, we would like to construct a similar convex program to capture the ME in this new model.
Note that without budget consideration, this game- theoretic problem can be solved efficiently by writing down
a social welfare maximization problem (i.e., maximizing sum of utilities of all the services), then use the dual decom- position method [33] to decompose it into sub-problems, each of which is solved by one service. Each sub-problem is exactly a net profit maximization problem of a service. Unfortunately, this strategy fails when we consider budget since the social welfare maximization problem cannot be decomposed due to the coupling budget constraints.
Our derivation of the new convex optimization problem is based on reverse-engineering the basic model.
Proposition 7.1. The equilibrium prices in the basic model can be found by solving the following convex problem.
minimize p,η
M ∑
j=1
pj − N ∑
i=1
Bi ln(ηi) (33)
subject to pj ≥ ai,jηi, ∀i, j; pj ≥ 0, ∀j.
Proof: We can obtain this convex problem by using La- grangian and Fenchel conjugate function [32] to construct the dual problem of the original EG program. Indeed, ηi and pj are the dual variables associated with (49) and (50). See our Appendix B for the full proof. �
Clearly, to maximize vi(xi) = ∑
j(ai,j − pj)xi,j , service i will never buy resource from EN j if ai,j < pj . In other words, service i would only buy resources from ENs in the set Ai =
{
j : pj ai,j
≤ 1 }
. From (61), we have ηi ≤ pj ai,j
, ∀i. From these observations, we conjecture that the following prorgram captures the equilibrium prices in our second market model (i.e., net profit maximization).
minimize p,η
M ∑
j=1
pj − N ∑
i=1
Bi ln(ηi) (34)
subject to pj ≥ ai,jηi, ∀i, j; ηi ≤ 1, ∀i; ηi ≥ 0, ∀i; pj ≥ 0, ∀j.
Theorem 7.2. The solution of the following convex program is exactly an ME of the new market model.
maximize X ,u,s
N ∑
i=1
(
Bi ln ui − si )
(35)
subject to ui ≤ M ∑
j=1
ai,jxi,j + si, ∀i
N ∑
i=1
xi,j ≤ 1, ∀j; xi,j ≥ 0, ∀i, j; si ≥ 0, ∀i.
At the equilibrium, the total of money spent and surplus money of every service equals to its budget. Addition- ally, the optimal utility of every service is unique and greater or equal to its budget. For any buyer who has surplus money, her utility equals her budget.
Proof: See our Appendix C . � The convex problem (63) is indeed the dual program
of problem (62). We can interpret problem (63) as follows. First, the utility of a service is the sum of its revenue and its surplus money. The first part of the objective function is the weighted sum of logarithmic utilities of the services similar to that of the EG program. However, since the surplus money does not contribute (i.e., not visible) to the market, we should subtract this amount from the aggregated utility
11
function, i.e., the objective function. Finally, similar to the EG program, although budget constraints are not included in (63), the optimal solution satisfies these constraints. It is worth noting that, somewhat surprisingly, although our reverse-engineering approach is specialized for linear rev- enue functions only, the convex program (63) works also for a wider class of homogeneous concave revenue functions. Interested readers can find more details in Appendix E.
8 NUMERICAL RESULTS
8.1 Simulation Settings
We consider a square area with dimensions of 10km x 10km. The locations of ENs and services are generated randomly in the area. We generate a total of 100 ENs and 1000 locations. We assume that each service is located at one location. For the sake of clarity in analysis, in the base case, we consider a small system with 8 ENs and 4 services (i.e., M = 8 and N = 4), which are selected randomly in the set of 100 ENs and 1000 services. The network delay between a service and an EN is assumed to be proportional to the distance between them. The maximum tolerable delay of the services follows a uniform distribution over the interval [15, 25]. The service rate µi,j is generated randomly from 80 to 240 requests per time unit. The service price is from 2 to 3 per 100000 requests. The number of computing units in the ENs ranges from 10 to 20. From these parameters, we can compute ai,j of the services as in (6). The net profit maximization model is considered in Section 8.5. In the base case, we assume that the services have equal budget. Fig. 2 depicts the valuations of the ENs to the buyers in the base case. The base case is used in all the simulations unless mentioned otherwise.
1 2 3 4 Buyer
0
0.01
0.02
0.03
0.04
0.05
0.06
0.07
Va lua
tio n
EN1 EN2 EN3 EN4 EN5 EN6 EN7 EN8
Fig. 2: Valuations of ENs to the buyers
8.2 Performance Comparison
In the first model captured by the EG program, the absolute value of the budget only affects the equilibrium prices by a scaling factor (e.g., all the prices increase twice as the budget of every service is double) and does not affect the allocation and utilities of the services. The budget is normalized such that the total budget of all services is one. The prices act as a means to allocate resources only.
1 2 3 4
Buyer
0
0.1
0.2
0.3
0.4
U til
ity
ME Prop. SW1 SW2 MaxMin
Total Utility - ME: 0.32 - Prop: 0.24 - SW1: 0.41 - SW2: 0.41 - MaxMin: 0.16
(a) Same budget
1 2 3 4
Buyer
0
0.1
0.2
0.3
0.4
U til
ity
ME Prop. SW1 SW2 MaxMin
Total Utility - ME: 0.29 - Prop: 0.21 - SW1: 0.41 - SW2: 0.34 - MaxMin: 0.16
(b) Budget ratio (4/4/1/4)
Fig. 3: Performance comparison
We consider five schemes, including: the proposed ME, the proportional sharing (Prop.), the social welfare maxi- mization with equal weights (SW1), social welfare maxi- mization with different weights (SW2), and the maxmin fairness (maxmin) schemes. In the proportional sharing, each buyer i receives Bi∑
i Bi
portion of resource of every EN.
In the social welfare maximization schemes, budget is not considered, and the objective is to maximize
∑
i wiui(xi) subject to the capacity constraints of the ENs. wi is the weighting factor of service i. In SW1, all weights are equal. In SW2, the weight of each service is its budget. Finally, without budget consideration, the maxmin scheme aims to maximize mini ui(xi) under ENs’ capacity constraints.
0 10 20 30 40 50 60 70 80 90 100 M
0
0.5
1
1.5
2
2.5
3
U til
ity
ME Prop. SW1 SW2 MaxMin
(a) Same budget
0 10 20 30 40 50 60 70 80 90 100 M
0
0.5
1
1.5
2
2.5
3
U til
ity
ME Prop. SW1 SW2 MaxMin
(b) Budget ratio (4/4/1/4)
Fig. 4: Utility efficiency comparison (N = 4)
0 10 20 30 40 50 60 70 80 90 100 M
0
0.2
0.4
0.6
0.8
1 E
F ME Prop. SW1 SW2 MaxMin
(a) Same budget
0 10 20 30 40 50 60 70 80 90 100 M
0
0.2
0.4
0.6
0.8
1
E F
ME Prop. SW1 SW2 MaxMin
(b) Budget ratio (4/4/1/4)
Fig. 5: Envy-freeness comparison (N = 4) Figs. 3(a)–5(b) present performance comparison among
these schemes under both equal budget and different bud- get settings. We can observe that the ME scheme balances well the tradeoff between system efficiency and fairness. First, the ME scheme considerably outperforms the Prop. scheme, which confirms the sharing-incentive property of the ME solution. The maxmin scheme produces a fair al- location among the buyers but the total utility of the buyers is much lower compared to other schemes. No- ticeably, although the total utility is largest, both schemes SW1 and SW2 produce undesirable allocations since some buyers (e.g., buyer 1) are not allocated anything and have zero utility in these schemes. Also, as can be seen from Figs. 5(a), 5(b) which compare envy-freeness indices (EF =
mini,j ui(xi)/Bi ui(xj)/Bj
[30]) among the different schemes. An al-
location is envy-free if EF equals to one. We can observe that our proposed ME scheme significantly outperforms the social welfare maximization and maxmin schemes in terms of envy-free fairness. Finally, Figs. fig:pr1–fig:pr3 depict the proportionality ratio (PR) of different schemes. When there are 4 buyers with equal budget, every buyer naturally expects to obtain a PR of at least 1/4. It can be observed that our proposed ME scheme satisfies the proportionality property as shown in Theorem 5.2.
8.3 Sensitivity Analysis
First, we examine the impact of budget on the equilibrium allocation by varying the budget ratio among the buyers.
12
8 16 24 32 40 48 56 64 72 80 M
0.25
0.35
0.45
0.55
0.65
PR
Buyer 1 Buyer 2 Buyer 3 Buyer 4
(a) ME scheme
8 16 24 32 40 48 56 64 72 80 M
0
0.2
0.4
0.6
0.8
1
PR
Buyer 1 Buyer 2 Buyer 3 Buyer 4
(b) SW scheme
8 16 24 32 40 48 56 64 72 80 M
0
0.2
0.4
0.6
0.8
1
PR
Buyer 1 Buyer 2 Buyer 3 Buyer 4
(c) MM scheme
Fig. 6: Proportionality ratio comparison (N = 4, same budget)
1 2 3 4 5 6 7 8 EN
0
0.2
0.4
0.6
0.8
1
All oc
ati on
Buyer 1 Buyer 2 Buyer 3 Buyer 4
u1 = 0.0164 u2 = 0.1066 u3 = 0.1167 u4 = 0.0961
(a) Budget ratio 0.67/1.33/1/1
1 2 3 4 5 6 7 8 EN
0
0.2
0.4
0.6
0.8
1
All oc
ati on
Buyer 1 Buyer 2 Buyer 3 Buyer 4
u1 = 0.0227 u2 = 0.0813 u3 = 0.1187 u4 = 0.0977
(b) Budget ratio 1/1/1/1
1 2 3 4 5 6 7 8 EN
0
0.2
0.4
0.6
0.8
1
All oc
ati on
Buyer 1 Buyer 2 Buyer 3 Buyer 4
u1 = 0.0285 u2 = 0.0558 u3 = 0.1221 u4 = 0.1005
(c) Budget ratio 1.33/0.67/1/1
Fig. 7: Impact of budget ratio on the equilibrium allocation
Figs. 7(a)-7(c) show impact of budget on the equilibrium allocation as we vary the budget ratio between services 1 and 2. We observe that buyer 1 is allocated more resources as her budget increases, which also increases her utility. The allocation and utility of buyer 2 decrease as her budget decreases. Fig. 8 further supports this observation where r is the budget ratio between services 1 and 2. Hence, we can conclude that the proposed algorithm is effective to capture service priority in terms of budget in the allocation decision.
0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2
r
0
0.02
0.04
0.06
0.08
0.1
0.12
0.14
U til
ity
u1 u2 u3 u4
Fig. 8: Impact of budget ratio on the buyers’ utilities
Fig. 9 shows the dependence of the equilibrium prices on the budget ratio of the buyers. For example, since only EN2, EN7, and EN8 can satisfy the delay requirement of service 1 as seen in Fig. 2, the prices of EN7 and EN8 change consid- erably as budget of service 1 varies. Also, because EN5 and EN6 are less valuable to the buyers, their equilibrium prices are significantly lower than the prices of other ENs while the prices of EN2 and EN8 are highest because they have high values to all the buyers. These observations imply the proposed method is effective in pricing.
1 2 3 4 5 6 7 8 EN
0
0.04
0.08
0.12
0.16
0.2
Pr ice
r = 0.5 r = 1.0 r = 2.0
Fig. 9: Impact of budget ratio on the equilibrium prices
In Fig. 10, we change the equilibrium prices by a small amount to obtain different price vectors P1, P2, P3, P4 such that demand of each buyer at these prices is unique. Price vector P1 (P2) is obtained by increasing (decreasing) every price in the equilibrium price vector in the base case by 0.01. Price vectors P3 (P4) is generated by adding a ran- dom number between 0 and 0.0005 (0.0003). We can observe that even under small price variation, the market is not cleared. Some ENs are over-demanded while some others are under-demanded. It means proper equilibrium pricing is important to clear the market.
1 2 3 4 5 6 7 8 EN
0
0.4
0.8
1.2
1.6
2
De ma
nd
P1 P2 P3 P4
Fig. 10: Impact of resource prices on total demand
The impact of the number of players (i.e., number of ENs and number of services) on the ME is illustrated in Figs. 11(a), 11(b). The buyers have the same budget in this case. We show the utilities of buyers 1, 2, 3, and 4 in these figures. As expected, as the number of buyers increases, the utility of individual buyer decreases since the same set of ENs has to be shared among more services. On the other hand, the service utility increases significantly as the number of ENs increases.
0 10 20 30 40 50 60 70 80 90 100 N
0
0.02
0.04
0.06
0.08
0.1
0.12
U til
ity
u1 u2 u3 u4
(a) M = 8, varying N
0 10 20 30 40 50 60 70 80 90 100 M
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
U til
ity
u1 u2 u3 u4
(b) N = 4, varying M
Fig. 11: Impact of M and N on the players’ utilities
13
8.4 Analysis of Distributed Algorithms
8.4.1 Proportional Dynamics Allocation
The proportional dynamics mechanism (PropDyn) has low complexity and can be implemented in a distributed man- ner. The convergence properties of this algorithm in the base case with 8 ENs and 4 services is shown in Figs. 12(a), 12(b). As we can see, the prices and the bids converge after a few tens of iterations. The running time of the algorithm is in order of milliseconds. Figs. 77–13(d) show the convergence properties of PropDyn as we change the number of ENs and the number of services. The the stopping condition is defined according the relative change of the prices between iterations (i.e., absolute value of the price deviation over the price in the previous iteration). In other words, at iteration
t + 1, if maxj (
|pj(t + 1) − pj(t)|/pj(t) )
is sufficiently small
(i.e., smaller than a tolerance threshold), the PropDyn algo- rithm terminates/converges. We have plotted the number of iterations of the PropDyn algorithm with different values of number of services (N) and number of ENs (M) as well as different tolerance thresholds in Figs. 77–13(d). The goal of these figures is to give a rough idea about the number of iterations. For each of these figures, we generated 50 different datasets and took the average number of iterations over 50 runs. Theoretical results on the convergence rate of PropDyn can be found in [?], [?], [29]. Specifically, the number of iterations depends on the number of ENs, the tolerance threshold, and the system parameters ai,j -which is indirectly related to the number of services.
0 10 20 30 40 50 60 70 80 90 100 110 Iteration
0.07
0.1
0.13
0.16
0.19
0.22
P ric
e
EN1 EN2 EN3 EN4
(a) Price trace
0 10 20 30 40 50 60 70 80 90 100 110 Iteration
0
0.04
0.08
0.12
0.16
0.2
B id
EN2
EN7
EN8
(b) Buyer 1’s bids
Fig. 12: Convergence of EN prices and bids
10 20 30 40 50 60 70 80 90 100 N
100
120
140
160
180
200
220
240
# Ite
ra tio
ns
M = 20 M = 40 M = 60 M = 80 M = 100
(a) Tolerance = 10−4
10 20 30 40 50 60 70 80 90 100 N
400
500
600
700
800
900
1000
1100
# Ite
ra tio
ns
M = 20 M = 40 M = 60 M = 80 M = 100
(b) Tolerance = 10−5
100 200 300 400 500 600 700 800 900 1000 N
40
60
80
100
120
140
160
180
# Ite
ra tio
ns
M = 20 M = 40 M = 60 M = 80 M = 100
(c) Tolerance = 10−4
100 200 300 400 500 600 700 800 900 1000 N
200
400
600
800
1000
1200
# Ite
ra tio
ns
M = 20 M = 40 M = 60 M = 80 M = 100
(d) Tolerance = 10−5
Fig. 13: Number of iterations of PropDyn
Figs. 14(a), 14(b), 14(c) compare the buyers’ utilities in the PropDyn and PropBR schemes. We select a particular instance with a set of 10 buyers and 20 ENs from the generated system data. Note that we have run simulation
with numerous instances and obtain similar trends. The utility of each buyer in the particular instance is presented in Fig. 14(a). As we can see, the utility values are higher for most of the buyers in the PropDyn scheme compared to the those in the PropBR scheme. In 14(b), we add a random variable to each ai,j and run the schemes 100 times and take the average results. In 14(c), we generate ai,j randomly in the range between 0.01 and 0.09. As we can observe, the buyers’ utilities tend to be higher in the PropDyn scheme in comparison with the PropBR scheme. Furthermore, the PropBR requires buyers to know more system information to play their BR actions in each round. The numerical results show that it brings almost no benefit to the buyers (no utility gain in most cases) to play PropBR scheme.. Hence, we can infer that the buyers should just follow the PropDyn scheme and obtain an ME allocation.
8.4.2 Function Approximation Algorithm
The convergence properties of the CES approximation scheme as well as its performance are reported. Thanks to the closed form expression of the optimal demand, the algo- rithm runs very fast even with high number of iterations. As expected, the number of iterations depends strongly on the step size and the initial prices. The convergence of EN6’s price (p6) is shown in Fig. 15(a). The number of iterations decreases as the initial prices are close to the final ME prices, which are unknown. The number of iterations decreases as the step size increases, but we cannot increase the step size γ too much to ensure convergence. Fig. 15(b) presents the price traces of different ENs until convergence with α = 0.001 and p0 = 0.2.
In Fig. 16(a), we study the performance of the approxi- mation scheme by comparing utility of the buyers under the centralized convex program (EG), the approximation CES utility (CES), and the approximation linear utility (Approx.). In the Approx. scheme, the utility of buyer i is xi,jai,j where xi,j is the solution of the optimization problem with CES approximation utilities. As we can observe, the values of the utilities are very similar, which confirms that the proposed approximation scheme performs well. In this figure, we set ρ to be 0.99. Finally, the equilibrium prices with different values of ρ is shown in Fig. 16(b). It is easy to see that the prices are almost equal for different values of ρ.
8.5 Net Profit Maximization Model
We now evaluate the second model where the services aim to maximize their net profits. We use the same system setting with 4 services and 8 ENs in the base case as before. From the objective function of the buyer, we know that a buyer will buy resource from an EN only when the price of the EN is less than or equal to its utility gain from the EN. In the revenue maximization case as in the basic model, the equilibrium prices increase linearly at the same rate as the budget. However, as can be seen in Fig. 17(a), this prop- erty does not hold in the net profit maximization model. Budget scale is the scaling factor by which we multiply the original budget. The figure shows that the equilibrium prices increase then become saturated after certain values of the budgets. At these (saturated) prices, buying resources from the ENs or not does not change the utility for a buyer (i.e., pj = ai,j ). When the budget is large enough,
14
1 2 3 4 5 6 7 8 9 10 Buyer
0
0.02
0.04
0.06
0.08
0.1
0.12
0.14
Ut ilit
y
M = 10, PropDyn M = 10, PropBR M = 20, PropDyn M = 20, PropBR
(a) Utility in one instance
1 2 3 4 5 6 7 8 9 10 Buyer
0
0.02
0.04
0.06
0.08
0.1
0.12
0.14
0.16
Ut ilit
y
M = 10, PropDyn M = 10, PropBR M = 20, PropDyn M = 20, PropBR
(b) Average utility in case 1
1 2 3 4 5 6 7 8 9 10 Buyer
0
0.02
0.04
0.06
0.08
0.1
Ut ilit
y
M = 10, PropDyn M = 10, PropBR M = 20, PropDyn M = 20, PropBR
(c) Average utility in case 2
Fig. 14: Utility comparison between PropBR and PropDyn
0 100 200 300 400 500 600 700 800 Iteration
0
0.2
0.4
0.6
0.8
1
P ric
e
α = 0.002, p 0 = 1.0
α = 0.002, p 0 = 0.5
α = 0.002, p 0 = 0.2
α = 0.001, p 0 = 0.2
(a) Number of iterations (p6)
0 100 200 300 400 500 600 Iteration
0
0.1
0.2
0.3
0.4
0.5 P
ric e
EN1 EN2 EN5 EN8
(b) Price convergence
Fig. 15: Convergence of CES approximation
1 2 3 4
Buyer
0
0.02
0.04
0.06
0.08
0.1
0.12
0.14
U til
ity
EG Approx. CES
(a) Utility comparison
1 2 3 4 5 6 7 8 EN
0
0.05
0.1
0.15
0.2
P ric
e
ρ = 1.00 ρ = 0.99 ρ = 0.98 ρ = 0.97
(b) Varying ρ
Fig. 16: CES approximation utility comparison
the utilities of the buyers become equal to their budgets. It means procuring resources or not does not bring any additional benefit to the buyers. These results are shown in Figs. 17(b), 17(c).
Figs. 18(a), 18(b) present equilibrium prices and opti- mal utilities, respectively, as the budget varies. Rev.max corresponds to the first model (i.e., revenue maximization) with scale equal to 1. As we can observe, for the same budget (i.e., scale = 1), equilibrium prices in the second model are smaller than equilibrium prices in the first model because in the net profit maximization model, a service only buys resource from an EN that gives it positive gain. Also, the service utilities at the equilibrium in the second model is greater than those in the first model due to lower equilibrium prices and budget surplus is considered in the second model. Finally, in the second model, the equilibrium prices and optimal utilities increase as the budget increases. As explained above, equilibrium prices become saturated in the second model at certain points. Hence, the equilibrium prices increase very little as budget scale increases from 1 to 1.5.
9 CONCLUSION AND FUTURE WORKS
In this work, we consider the resource allocation for an EC system which consists geographically distributed heteroge- neous ENs with different configurations and a collection of services with different desires and buying power. Our main contribution is to suggest the famous concept of General
Equilibrium in Economics as an effective solution for the underlying EC resource allocation problem. The proposed solution produces an ME that not only Pareto-efficient but also possesses many attractive fairness properties. The po- tential of this approach are well beyond EC applications. For example, it can be used to share storage space in edge caches to different service providers. We can also utilize the proposed framework to share resources (e.g., communica- tion, wireless channels) to different users or groups of users (instead of services and service providers). Furthermore, the proposed model can extend to the multi-resource scenario where each buyer needs a combination of different resource types (e.g., storage, bandwidth, and compute) to run its service. We will formally report these cases (e.g., network slicing, NFV chaining applications) in our future work.
The proposed framework could serve as a first step to understand new business models and unlock the enormous potential of the future EC ecosystem. There are several future research directions. For example, we will investigate the ME concept in the case when several edge networks cooperate with each other to form an edge/fog federation. Investigating the impacts of the strategic behavior on the efficiency of the ME is another interesting topic. Note that N. Chen et. al. [24] have shown that the gains of buyers for strategic behavior in Fisher markets are small. Additionally, in this work, we implicitly assume the demand of every service is unlimited. It can be verified that we can add the maximum number of requests constraints to the EG pro- gram to capture the limited demand case, and the solution of this modified problem is indeed an ME. However, although the optimal utilities of the services in this case are unique, there can have infinite number of equilibrium prices. We are investigating this problem in our ongoing work. Also, integrating the operation cost of ENs into the proposed ME framework is a subject of our future work. Finally, how to compute market equilibria with more complex utility functions that capture practical aspects such as task moving expenses among ENs and data privacy is an interesting future research direction.
’
REFERENCES
[1] M. Chiang and T. Zhang, “Fog and IoT: an overview of research opportunities,” IEEE Internet Things J., vol. 3, no. 6, pp. 854–864, Dec. 2016.
[2] M. Satyanarayanan, “The emergence of edge computing,” Com- puter, vol. 50, no. 1, pp. 30–39, Jan. 2017.
[3] W. Shi, J. Cao, Q. Zhang, Y. Li, and L. Xu, “Edge computing: vision and challenges,” IEEE Internet Things J., vol. 3, no. 5, pp. 637–646, Oct. 2016.
[4] K.J. Arrow and G. Debreu, “Existence of equilibrium for a com- petitive economy,” Econometrica, vol. 22, no. 3, pp. 265–290, 1954.
15
0 0.3 0.6 0.9 1.2 1.5 Budget Scale
0
0.01
0.02
0.03
0.04
0.05
0.06
0.07
Pr ice
EN1 EN3 EN5 EN7
(a) Price
0 0.3 0.6 0.9 1.2 1.5
Budget Scale
0
0.1
0.2
0.3
0.4
Ut ilit
y
Buyer 1 Buyer 2 Buyer 3 Buyer 4
(b) Utility
0 0.3 0.6 0.9 1.2 1.5
Budget Scale
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Su rpl
us R
ati o
Buyer 1 Buyer 2 Buyer 3 Buyer 4
(c) Surplus Ratio (surplus/budget)
Fig. 17: ME in the net profit maximization model
1 2 3 4 5 6 7 8 EN
0
0.05
0.1
0.15
0.2
P ric
e
Scale = 0.05 Scale = 0.30 Scale = 1.00 Scale = 1.50 Rev.max
(a) Prices
1 2 3 4 Buyer
0
0.1
0.2
0.3
0.4
U til
ity Scale = 0.05 Scale = 0.30 Scale = 1.00 Scale = 1.50 Rev.max
(b) Utilities
Fig. 18: Impact of budget on equilibrium prices and utilities
[5] W.C. Brainard and H.E. Scarf, “How to compute equilibrium prices in 1891,” Cowles Foundation, Discussion Paper, no. 1272, 2000.
[6] A. Mas-Colell, M. D. Whinston, and J. R. Green, “Microeconomic Theory”, 1st ed. New York: Oxford Univ. Press, 1995.
[7] H. Moulin, “Fair division and collective welfare,” MIT Press, 2004. [8] N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani, “Algo-
rithmic Game Theory”, Cambridge, U.K.: Cambridge Univ. Press, 2007.
[9] E. Eisenberg and D. Gale, “Consensus of subjective probabilities: The pari-mutual method,” Annals of Mathematical Statistics, vol. 30, pp. 165–168, 1959.
[10] E. Eisenberg, “Aggregation of utility functions,” Manage. Sci. 7, PP. 337–350, 1961.
[11] Y. Lin and H. Shen, “CloudFog: leveraging fog to extend cloud gaming for thin-client MMOG with high quality of service,” IEEE Trans. Parallel Distrib. Syst., vol. 28, no. 2, pp. 431–445, Feb. 2017.
[12] L. Gu, D. Zeng, S. Guo, A. Barnawi, and Y. Xiang, “Cost efficient resource management in fog computing supported medical cyber- physical system,” IEEE Trans. Emerg. Topics Comput., vol. 5, no. 1, pp. 108-119, Jan.-Mar. 2017.
[13] A. Mukherjee, D. De, and D.G. Roy, “A power and latency aware cloudlet selection strategy for multi-cloudlet environment,” IEEE Trans. Cloud Comput. , to appear.
[14] R. Deng, R. Lu, C. Lai, T. H. Luan, and H. Liang, “Optimal workload allocation in fog-cloud computing toward balanced delay and power consumption,” IEEE Internet Things J., vol. 3, no. 6, pp. 1171–1181, Dec. 2016.
[15] X. Sun and N. Ansari, “Latency aware workload offloading in the cloudlet network,” IEEE Commun. Lett., vol. 21, no. 7, pp. 1481– 1484, Jul. 2017.
[16] M. Jia, J. Cao, and W. Liang, “Optimal cloudlet placement and user to cloudlet allocation in wireless metropolitan area networks,” IEEE Trans. Cloud Comput., to appear.
[17] L. Yang, J. Cao, G. Liang, and X. Han, “Cost aware service placement and load dispatching in mobile cloud systems,” IEEE Trans. Comput., vol. 65, no. 5, pp. 1440–1452, May 2016.
[18] H. Zhang, Y. Xiao, S. Bu, D. Niyato, F.R. Yu, and Z. Han, “Computing resource allocation in three-Tier IoT fog networks: a joint optimization approach combining stackelberg game and matching,” IEEE Internet Things J., to appear.
[19] S. Sardellitti, G. Scutari, and S. Barbarossa, “Joint optimization of radio and computational resources for multicell mobile-edge computing,” IEEE Trans. Signal Inf. Process. Netw., vol. 1, no. 2, pp. 89–103, Jun. 2015.
[20] X. Lyu, H. Tian, C. Sengul, and P. Zhang, “Multiuser joint task offloading and resource optimization in proximate clouds,” IEEE Trans. Veh. Technol., vol. 66, no. 4, pp. 3435–3447, Apr. 2017.
[21] X. Chen, “Decentralized computation offloading game for mobile
cloud computing,” IEEE Trans. Parallel Distrib. Syst., vol. 26, no. 4, pp. 974–983, Apr. 2015.
[22] N.R. Devanur, C.H. Papadimitriou, A. Saberi, and V.V. Vazirani, “Market equilibrium via a primal–dual algorithm for a convex program,” J. ACM vol. 55, no. 5, article 22, Nov. 2008.
[23] V.V. Vazirani and M. Yannakakis, “Market equilibrium under separable, piecewise-linear, concave utilities,” J. ACM, vol. 58, no. 3, article. 10, May 2011.
[24] N. Chen, X. Deng, B. Tang, and H. Zhang, “Incentives for strategic behavior in Fisher market games”, in Proc. Conf. Artificial Intelli- gence (AAAI), pp. 453–459, Phoenix, Arizona, USA, Feb. 2016.
[25] X. Chen, D. Paparas, and M. Yannakakis, “The complexity of non- monotone markets” J. ACM, vol. 64, no. 3, Article 20, Jun. 2017.
[26] J. Garg, R. Mehta, M. Sohoni, and V.V. Vazirani, “A comple- mentary pivot algorithm for market equilibrium under separable, piecewise-linear concave utilities”, SIAM J. Comput., vol. 44, no. 6, pp. 1820–1847, 2015.
[27] Z. Liu, M. Lin, A. Wierman, S. Low, and L. L. H. Andrew, “Greening geographical load balancing,”, IEEE/ACM Trans. Netw., vol. 23, no. 2, pp. 657–671, Apr. 2015.
[28] L. Tang and H. Chen, “Joint pricing and capacity planning in the IaaS cloud market,” IEEE Trans. Cloud Comput., vol. 5, no. 1, pp. 57–70, Jan.-Mar. 2017.
[29] F. Wu and L. Zhang, “Proportional response dynamics leads to market equilibrium,” in Proc. the thirty-ninth annual ACM sympo- sium on Theory of Computing (STOC), pp. 354–363, New York, NY, USA, 2007.
[30] M. Feldman, K. Lai, and L. Zhang, “The proportional-share allo- cation market for computational resources,” IEEE Trans. Parallel Distrib. Syst., vol. 20, no. 8, pp. 1075–1088, Aug. 2009.
[31] J. F. Nash, “The bargaining problem”, Econometrica 28, pp. 155–162, 1950.
[32] S. Boyd and L. Vandenberghe, “Convex Optimization”, Cam- bridge, U.K.: Cambridge Univ. Press, 2004.
[33] D.P. Palomar and M. Chiang, “A tutorial on decomposition meth- ods for network utility maximization,” IEEE J. Sel. Areas Commun., vol. 24, no. 8, pp. 1439–1451, Aug. 2006.
[34] N.C. Luong, P. Wang, D. Niyato, Y. Wen, and Z. Han, “Resource management in cloud networking using economic analysis and pricing models: a survey,” IEEE Commun. Surv. Tut., vol. 19, no. 2, pp. 954–1001, Secondquarter 2017.
[35] H. Xu and B. Li, “Dynamic cloud pricing for revenue maximiza- tion,” IEEE Trans. Cloud Comput., vol. 1, no. 2, pp. 158–171, Jul.– Dec. 2013.
[36] A.N. Toosi, K. Vanmechelen, K. Ramamohanarao, and R. Buyya, “Revenue maximization with optimal capacity control in infras- tructure as a service cloud markets,” IEEE Trans. Cloud Comput., vol. 3, no. 3, pp. 261–274, Jul.–Sept. 2015.
[37] L. Mashayekhy, M. M. Nejad, and D. Grosu, “Cloud federations in the sky: formation game and mechanism,” IEEE Trans. Cloud Comput., vol. 3, no. 1, pp. 14–27, Jan.-Mar. 2015.
[38] M. Hadji and D. Zeghlache, “Mathematical programming ap- proach for revenue maximization in cloud federations,” IEEE Trans. Cloud Comput., vol. 5, no. 1, pp. 99–111, Jan.-Mar. 2017.
[39] I. Petri, J. Diaz-Montes, M. Zou, T. Beach, O. Rana, and M. Parashar, “Market models for federated clouds,” IEEE Trans. Cloud Comput., vol. 3, no. 3, pp. 398–410, Jul.—Sept. 2015.
[40] A. Prasad and S. Rao, “A mechanism design approach to resource procurement in cloud computing,” IEEE Trans. Comput., vol. 63, no. 1, pp. 17–30, Jan. 2014.
[41] D. Ardagna, B. Panicucci, and M. Passacantando, “Generalized Nash equilibria for the service provisioning problem in cloud systems,” IEEE Trans. Serv. Comput., vol. 6, no. 4, pp. 429–442, Oct.- Dec. 2013.
16
[42] D. Ardagna, M. Ciavotta, and M. Passacantando, “Generalized Nash equilibria for the service provisioning problem in multi- cloud systems,” IEEE Trans. Serv. Comput., vol. 10, no. 3, pp. 381– 395, May-Jun. 2017.
[43] V. Cardellini, V. Di Valerio, and F. Lo Presti, “Game-theoretic resource pricing and provisioning strategies in cloud systems,” IEEE Trans. Serv. Comput., to appear.
[44] L. Mashayekhy, M.M. Nejad, and D. Grosu, “Physical machine resource management in clouds: a mechanism design approach,” IEEE Trans. Cloud Comput., vol. 3, no. 3, pp. 247–260, Jul.–Sep. 2015.
[45] X. Wang, X. Wang, H. Che, K. Li, M. Huang, and C. Gao, “An intelligent economic approach for dynamic resource allocation in cloud services,” IEEE Trans. Cloud Comput., vol. 3, no. 3, pp. 275– 289, Jul.–Sept. 2015.
[46] S. Chichin, Q.B. Vo, and R. Kowalczyk, “Towards efficient and truthful market mechanisms for double-sided cloud markets,” IEEE Trans. Serv. Comput., vol. 10, no. 1, pp. 37–51, Jan.-Feb. 2017.
[47] Technical report. Available [Online]: https://www.dropbox.com/s/l1hmnsog35m5z8n/FogIoT.pdf?dl=0.
APPENDIX A
PROOF OF PROPOSITION 6.1
Consider two following problems
(P1) maximize xi≥0
ui(xi) (36)
subject to ∑
j
pjxi,j ≤ Bi (37)
(P2) maximize xi≥0
Bi ln ui(xi) − ∑
j
pjxi,j (38)
where ui(xi) = ∑
j
(
ai,jxi,j )ρ
. We will show that the given a positive price vector p, each service i can solve either (P1) or (P2), which have the same optimal solution.
xi,j = (a
ρ i,j
pj
) 1
1−ρ Bi ∑M
j=1
(
ai,j pj
)
ρ 1−ρ
, ∀i, j. (39)
Consider (P1). Let λi is the dual variable associated with constraint (37). The Lagrangian is
Li(xi, λi) = ∑
j
(
ai,jxi,j )ρ
+ λi (
Bi − ∑
j
pjxi,j )
(40)
Take the first derivative and set it equal to zero, we have
∂Li ∂xi,j
= ρai,j (
ai,jxi,j )ρ−1
− λipj = 0, ∀j. (41)
⇒ ρa ρ i,jx
ρ−1 i,j = λipj, ∀j. (42)
If λi = 0 ⇒ ai,jxi,j = 0, ∀j ⇒ ui(xi) = 0. Clearly, optimal value of ui(xi) > 0. Hence, λi > 0. Also, as mentioned in the report, pj > 0, ∀j. Thus, xi,j > 0, ∀j. From (42), we have
ρa ρ i,kx
ρ−1 i,k = λipk, ∀k ∈ M. (43)
Since at least one element of vector ai is positive, we assume ai,j > 0. From (42) and (43), we have
ρa ρ i,kx
ρ−1 i,k
ρa ρ i,jx
ρ−1 i,j
= pk pj
, ∀k ∈ M (44)
Hence, xi,k = (pk pj
) 1
ρ−1 (ai,k ai,j
)
ρ 1−ρ
xi,j, ∀k ∈ M. (45)
At the optimality, λi > 0, hence, ∑
k pkxi,k = Bi. Substitut- ing value of every xi,k from (45), we can compute the value of xi,j and infer the value of every xi,k, ∀k ∈ M. We obtain
the optimal solution as shown in (39). Note that this optimal solution is positive.
Next, consider (P2), which is the sub-problem to be solved by every service i. Define fi(xi) = Bi ln ui(xi) − ∑
j pjxi,j , where ui(xi) = ∑
j
(
ai,jxi,j )ρ . Take the first
derivative and set it to be equal to zero, we have
∂fi(xi)
∂xi,j = Biρai,j
(
ai,jxi,j )ρ−1
ui(xi) − pj = 0, ∀j (46)
⇒ Biρa ρ i,jx
ρ−1 i,j = pjui(xi), ∀j. (47)
Following similar steps as for (P1) above, we obtain the closed form expression of the optimal solution of (P2).
APPENDIX B
PROOF OF PROPOSITION 7.1
The EG convex program is
maximize X ,u
N ∑
i=1
Bi ln ui (48)
subject to ui =
M ∑
j=1
ai,jxi,j, ∀i (49)
N ∑
i=1
xi,j ≤ 1, ∀j (50)
xi,j ≥ 0, ∀i, j. (51)
Let ηi, pj , and νi,j be the dual variables associated with (49), (50), and (51), respectively. The Lagrangian function of the EG program (48)-(51) is
L(u, X , η, p, ν) = ∑
i
Bi ln ui + ∑
j
pj(1 − ∑
i
xi,j) (52)
+ ∑
i
ηi (
∑
j
ai,jxi,j − ui )
+ ∑
i
∑
j
νi,jxi,j.
Define fi(ui) = −Bi ln ui, we have
L(u, X , η, p, ν) = ∑
i
(
− ηiui − fi(ui) )
+ ∑
j
pj (53)
+ ∑
i
∑
j
(
− pj + ηiai,j + νi,j )
xi,j.
The dual function is
g(η, p, ν) = maximize u,X
L(u, X , η, p, ν). (54)
The dual problem is
minimize η≥0,p≥0,ν≥0
g(η, p, ν). (55)
According to the KKT conditions, we have
∂L(u, X , η, p, ν)
∂xi,j = −pj + ηiai,j + νi,j = 0, ∀i, j (56)
17
which gives us −pj + ηiai,j = −νi,j ≤ 0, ∀i, j. Thus, ηiai,j ≤ pj, ∀i, j. Furthermore, the dual objective is equiv- alent to
min η,p,ν
(
max u
∑
i
(
− ηiui − fi(ui) )
+ ∑
j
pj )
(57)
= min η,p,ν
(
∑
j
pj + ∑
i
max u
(
− ηiui − fi(ui) )
)
= min η,p,ν
(
∑
j
pj + ∑
i
f∗i (−ηi) )
)
.
Note that the (Fenchel) conjugate function of a function h : R n → R is defined as follows [32].
h∗(µ) := sup x
{
µT x − h(x) }
. (58)
We need to compute the conjugate of fi(ui) = −Bi ln ui. Consider function h(x) = −A ln x where A is a constant. First, we have the conjugate of h1(x) = − ln x is h
∗ 1(µ) =
−1 − ln(−µ). Also, the conjugate function has the following property [32]: if h2(x) = Ah1(x) for some constant A, then h∗2(µ) = Ah
∗ 1(
µ A ). Thus, the conjugate of h(x) = −A ln x
is h∗(µ) = −A − A ln (
−µ A
)
= −A + A ln A − A ln(−µ). Therefore, the conjugate of fi(ui) is
f∗i (µi) = −Bi + Bi ln Bi − Bi ln(−µi). (59)
By ignoring the constant terms (−Bi + Bi ln Bi), the dual objective is equivalent to
min η,p,ν
(
∑
j
pj − ∑
i
Bi ln ηi )
. (60)
We have shown that the convex program (61) can be inferred directly from the EG convex program (48)-(51).
minimize p,η
M ∑
j=1
pj − N ∑
i=1
Bi ln(ηi) (61)
subject to pj ≥ ai,jηi, ∀i, j; pj ≥ 0, ∀j.
Note that it can be verified that the KKT conditions of prob- lems (61) and (48)-(51) are equivalent, where xi,j is the dual variable corresponding to the first constraint of problem (61). Hence, problem (61) captures the market clearing prices (i.e. equilibrium prices).
APPENDIX C
PROOF OF THEOREM 7.2
Consider problems (P3) and (P4) as follows
(P3) minimize p,η
M ∑
j=1
pj − N ∑
i=1
Bi ln(ηi) (62)
subject to
pj ≥ ai,jηi, ∀i, j; ηi ≤ 1, ∀i; ηi ≥ 0, ∀i; pj ≥ 0, ∀j.
(P4) maximize X ,u,s
N ∑
i=1
(
Bi ln ui − si )
(63)
subject to
ui ≤ M ∑
j=1
ai,jxi,j + si, ∀i
N ∑
i=1
xi,j ≤ 1, ∀j; xi,j ≥ 0, ∀i, j; si ≥ 0, ∀i.
- Dual program construction: First we show that the convex program (P4) is the dual program of (P3). This can be shown in a similar way to proof of Proposition 7.1 as follows. Let λi,j , θi, γi, and υj be the dual variables associated with constraints the first, second, third, and last constraints in problem (P3), respectively. The Lagrangian of problem (62) is
L(p, η, λ, θ, γ, υ) = ∑
j
pj − ∑
i
Bi ln ηi − ∑
i
γiηi (64)
+ ∑
i
∑
j
λi,j (
ai,jηi − pj )
+ ∑
i
θi(ηi − 1) − ∑
j
υjpj.
Define fi(ηi) = Bi ln ηi, we have
L(p, η, λ, θ, γ, υ) = ∑
j
(1 − ∑
i
λi,j − υj)pj (65)
+ ∑
i
(
( ∑
j
λi,jai,j + θi − γi)ηi − fi(ηi) )
− ∑
i
θi.
The dual function is
g(λ, θ, γ, υ) = minimize p,η
L(p, η, λ, θ, γ, υ). (66)
The dual problem is
maximize λ≥0,θ≥0,γ≥0,υ≥0
g(λ, θ, γ, υ). (67)
The rest of this construction is similar to Proposition 7.1. By setting xi,j = λi,j , si = θi, and ui =
∑
j λi,jai,j + θi − γi, we can obtain problem (P4).
- Main proof of of theorem 7.2. We need to show that the solution of (P4) is an exact ME. At the equilibrium, total money spent and surplus money of every service equals to its budget, i.e.,
∑
j pjxi,j + si = Bi, ∀i. Additionally, the optimal utility of every service is unique. Clearly, (P4) can be written in the following form.
maximize X
N ∑
i=1
(
Bi ln (
si + M ∑
j=1
ai,jxi,j )
− si )
(68)
subject to N ∑
i=1
xi,j ≤ 1, ∀j (69)
xi,j ≥ 0, ∀i, j (70)
si ≥ 0, ∀i. (71)
Let pj , νi,j , and βi be the dual variables corresponding to (69), (70), and (71), respectively. The Lagrangian is
L(X , s, p, ν, β) = ∑
i
(
Bi ln (
si + M ∑
j=1
ai,jxi,j )
− si )
(72)
+ ∑
j
pj(1 − ∑
i
xi,j) + ∑
i
∑
j
νi,jxi,j + ∑
i
siβi.
Since the feasible region of (68)-(70) is closed, compact, and convex, Slater’s condition holds and the KKT conditions are
18
necessary and sufficient for optimality. The KKT conditions render
∂L
∂si = Bi
1
ui(xi, si) − 1 + βi = 0, ∀i (73)
∂L
∂xi,j = Bi
ai,j ui(xi, si)
− pj + νi,j = 0, ∀i, j (74)
pj(1 − ∑
i
xi,j) = 0, ∀j; νi,jxi,j = 0, ∀i, j (75)
siβi = 0, ∀i; pj ≥ 0, ∀j; βi ≥ 0, ∀i; νi,j ≥ 0, ∀i, j. (76)
where ui(xi, si) = si + ∑
j ai,jxi,j, ∀i. For simplicity, we will write ui(xi, si) as ui. It can be inferred from (73)-(76) the following
∀i, j : ui Bi
≤ ai,j pj
(77)
∀i, j : if xi,j > 0 ⇒ νi,j = 0 ⇒ ui Bi
= ai,j pj
(78)
∀j : pj > 0 ⇒ ∑
i
xi,j = 1; ∑
i
xi,j < 1 ⇒ pj = 0. (79)
Similar to the analysis of the EG program, conditions (77) and (87) imply that xi,j > 0 if and only if j ∈ Di(p), i.e., each service buys resources only from ENs giving it the MBB. This also maximizes ui. Next, we show that total money spent and surplus money of every service equals to its budget. From (73), we have
Bi si ui
− si + siβi = 0, ∀i (80)
Since siβi = 0, ∀i, we have
Bi si ui
= si, ∀i (81)
Similarly, since νi,jxi,j = 0, by multiplying both sides of (74) by xi,j , we have
Bi ai,jxi,j
ui = pjxi,j, ∀i (82)
From (81) and (82), we have
Bi si ui
+ ∑
j
Bi ai,jxi,j
ui = si +
∑
j
pjxi,j, ∀i, j (83)
Hence, Bi = si + ∑
j pjxi,j, ∀i, j. From (73) and (76), if si > 0 ⇒ βi = 0, ∀i ⇒ ui = Bi, ∀i. Therefore, if a buyer has surplus, her utility is equal to her budget. It means buying resources or not does not change her utility since she can keep her money and buy nothing and still has a utility which equals to her budget. This happens when there is no ENs with prices strictly lower than the buyer’s utilities gained from the ENs (i.e., pj ≥ ai,j, ∀j). Finally, the utility of a buyer with no surplus money is always greater or equal to the her budget, i.e., ui ≥ Bi, which can be inferred from (73) and βi ≥ 0.
APPENDIX D
CONCAVE HOMOGENEOUS UTILITY FUNCTIONS
Indeed, the EG program not only captures the Fisher market with linear utilities [9] but also applies to a wider class of concave homogeneous (degree one) utility functions [10].
The proof can be found in [8]. We present the proof here for completeness. The EG program can be written as follows.
maximize X ,u
N ∑
i=1
Bi ln ui(xi) (84)
subject to N ∑
i=1
xi,j ≤ 1, ∀j; xi,j ≥ 0, ∀i, j. (85)
Define x∗i as the optimal solution to the EG program. Let pj and νi,j be dual variables. The KKT conditions give us
pj (
1 − ∑
i
x∗i,j )
= 0, ∀ j (86)
x∗i,jνi,j = 0, ∀i, j (87)
Bi ui(x
∗ i )
∂ui(x ∗ i )
∂xi,j = pj − νi,j, ∀ i, j. (88)
For every service i, multiply both sides of (88) by x∗i,j and sum up the resulting equalities, we have
Bi ui(x
∗ i )
∑
j
x∗i,j ∂ui(x
∗ i )
∂xi,j =
∑
j
(pj − νi,j)x ∗ i,j. (89)
From the Euler’s theorem for homogeneous functions, we have ui(xi) =
∑
j xi,j ∂ui ∂xi,j
for homogeneous function ui. Also, combined with (87), we have
Bi = ∑
j
pjx ∗ i,j. (90)
Thus, x∗i exhausts the budget of buyer i at price p. We now show that x∗i maximizes ui(xi). Let x
′ i ∈ R
M + be
any allocation to buyer i satisfying ∑
j pjx ′ i,j ≤ Bi. From
the concavity of ui, we have.
ui(x ′ i) − ui(x
∗ i ) ≤ ∇ui(x
∗ i )(x
′ i − x
∗ i ) (91)
= ui(x
∗ i )
Bi
∑
j
(pj − νi,j)(x ′ i,j − x
∗ i,j)
= ui(x
∗ i )
Bi
(
∑
j
(pjx ′ i,j − νi,jx
′ i,j) − Bi
)
≤ ui(x
∗ i )
Bi
(
∑
j
pjx ′ i,j − Bi
)
≤ 0.
Therefore, x∗i is an optimal demand bundle of buyer i at price vector p. Hence, every buyer is allocated its optimal resource bundle at the equilibrium prices. The market clear- ing condition proof is similar to that of the linear utility case in the manuscript. We have shown that all the requirements of an ME are satisfied.
APPENDIX E
OTHER DISCUSSIONS
- Net profit maximization and concave homogeneous revenue functions: Instead of linear revenue function ui(xi) as con- sidered throughout this work, here, we consider the case where ui(xi) is concave and homogeneous of degree one. Then, let gi(xi, si) = uixi + si. For any constant d > 0:
gi(dxi, dsi) = uidxi + dsi = dui(xi) + dsi (92)
= d (
∑
j
ai,jxi,j + si )
= dui(xi, si), ∀ i.
19
Thus, gi(xi, si) is a concave homogeneous (of degree one) function. By following similar the proof above in Appendix D for the EG program, we can verify that our new convex optimization problem (as shown below) for the net profit maximization model also applies to the wider class of con- cave homogeneous functions.
maximize X ,u,s
N ∑
i=1
(
Bi ln(ui(xi) + si) − si )
(93)
subject to
N ∑
i=1
xi,j ≤ 1, ∀j; xi,j ≥ 0, ∀i, j; si ≥ 0, ∀i.
- Multiple resource types: Consider an example of the model with multiple resource types. For example, a service may need a combination of bandwidth, computing, and memory. Let di = (di,1, ..., di,K) be the base demand vector giving service i, in which di,k is the amount of resource k in the base demand vector of service i. The utility of service i is commonly defined as follows: ui(xi) = mink{
xi,k di,k
}.
It is easy to see that ui(xi) is concave and homogeneous
of degree one. If there are multiple ENs, we will take sum utility over all the ENs. Therefore, the proposed framework can apply to the multi-resource case.
- Another decentralized implementation of the basic model (revenue maximization): By carefully analyzing the central- ized combinatorial algorithm proposed for the linear Fisher market in the remarkable piece of work of by N.R. Devanur et. al. [22], we observe that it can be modified to work in a distributed fashion as follows. In each round, given new prices, instead of reporting its optimal bundle(s), each service will report its maximum bang-per-buck (MBB) value and the ENs in its demand set Di. The platform will collect these information to construct and compute a new equality graph as defined in [22], and compute a balance flow (maxflow with minimum surplus). By this small mod- ification, the combinatorial algorithm in [22] can be imple- mented in decentralized manner. The algorithm terminates when the max-flow is equal to the total budget of the buyers. Note that before the prices converge to equilibrium prices, the total budget of the buyers and the total prices of the ENs are different, which means the intermediate solution does not satisfy the market clearing condition. Interested readers can refer to [22] for more details.
- 1 Introduction
- 2 Related Work
- 3 System Model
- 4 Problem Formulation
- 4.1 EC Resource Allocation Problem
- 4.2 Service Utility Model
- 5 Centralized Solution
- 6 Decentralized Solution
- 6.1 Dual Decomposition with Function Approximation
- 6.2 Proportional Response Dynamics Strategy
- 7 Net Profit Maximization
- 8 Numerical Results
- 8.1 Simulation Settings
- 8.2 Performance Comparison
- 8.3 Sensitivity Analysis
- 8.4 Analysis of Distributed Algorithms
- 8.4.1 Proportional Dynamics Allocation
- 8.4.2 Function Approximation Algorithm
- 8.5 Net Profit Maximization Model
- 9 Conclusion and Future Works
- References
- Appendix A: Proof of Proposition 6.1
- Appendix B: Proof of Proposition 7.1
- Appendix C: Proof of Theorem 7.2
- Appendix D: Concave Homogeneous Utility Functions
- Appendix E: Other Discussions
