paper on price based product allocation for edge computing: market equilibrim approach

Problem formulation:

here resources are products, service providers will assign different priced products to different edge nodes(EN) so the highly demanded products are high priced and low demanded are low. Service means user, he comes with the budget to buy bundle of products from service

Please start changing from here:

The basic idea behind our approach is to assign different 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 heterogeneous 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 different 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 fairness and efficiency. Thus, conventional schemes such as social welfare maximization, maxmin fairness, and auction models may not be suitable. In particular, a welfare maximization 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 effective 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 quantity. 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 constraints (i.e., the capacity constraints of the ENs) are often interpreted as the resource prices [32] and common approaches 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 consideration. 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 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.

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: PN 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: PN 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 P 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;P j p ∗ j xi,j≤Bi Ui(xi , p∗ ) (1) • Condition 2: All the resources are fully allocated, i.e. , we have: P i xi,j = 1, ∀j. The first condition can be interpreted as the user satisfaction 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 models. 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)− P j pjxi,j , ∀i. We focus on the first model throughout the report. The second model is examined.

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) = P 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 consider 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 d UE−PoA i between the user and a PoA of the service, the round-trip network delay d n i,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, d UE−PoA i 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 max i 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 λ max i,j that EN j can process is zero if d n i,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 max i − d n i,j (4) ⇒ λi,j ≤ xi,j µi,j − 1 T max i − di,j . Therefore, if d n i,j < T max i , the maximum number of requests that service i can process at EN j is λ max i,j = max n xi,j µi,j − 1 T max i − di,j , 0 o (5) = xi,j qi,j , ∀i, j where qi,j = max nµi,j − 1 T max i −di,j , 0 o . Define a successful 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) = X M j=1 ui,j = X 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 platform 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 delaysensitive services to illustrate one way to model the service utility function. It can be justified by the fact that nondelay-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) = P j ai,jxi,j subject to the budget constraint P 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 X N i=1 Bi ln ui (8) subject to ui = X M j=1 ai,jxi,j , ∀i (9) X 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 sufficiently 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, ν) = X i Bi ln ui + X j pj (1 − X i xi,j ) (12) + X i ηi X j ai,jxi,j − ui + X i X 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 = X j ai,jxi,j , ∀i; pj(1 − X 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 ⇒ X i xi,j = 1; X 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 interpreted 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 program (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 program. 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 resulting equalities, we get Bi u ∗ i X j ai,jx ∗ i,j = X j (p ∗ j − ν ∗ i,j )x ∗ i,j , ∀i, j. (21) Since ν ∗ i,jx ∗ i,j = 0, ∀i, j, and ui∗ = P j ai,jx ∗ i,j , ∀i, equation (21) implies P 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 optimality, 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 concave 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 allocation. 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 allocation 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 allocation is efficient and non-wasteful because the remaining resources (if any) cannot improve utility of any service. Envyfreeness 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 = P Bi ′ i Bi ′ , ∀i, j. Sharing-incentive property implies ui(xi) ≥ ui(ˆxi), ∀i. Indeed, xˆ is an intuitive resourcefair 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. Sharingincentive 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) ≥ P 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 proportionality 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, Paretooptimality 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. Assume 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) = P j ai,jxi,j . Consider any feasible allocation X′ . Recall the MBB of buyer i is αi = maxj ai,j pj . We have X j x ′ i,jpj ≥ X j x ′ i,j ai,j αi ≥ X j x ∗ i,jai,j 1 αi = X j x ∗ i,jpj. (22) The second inequality is due to ui(x ′ i ) ≥ ui(x ∗ i X ), ∀i. Thus j x ′ i,jpj ≥ Bi , ∀i. (23) Since ui(x ′ i ) > ui(x ∗ i ) for some i, P j x ′ i,jpj ≥ Bi for some i. Adding both sides of (23) over all buyers renders X i Bi < X i X j x ′ i,jpj = X i xi,j X j pj ≤ X j pj (24) because P 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 ′ X j ai,jx ∗ i,j = Bi ′ X j ai,j b ∗ i,j pj (25) = Bi ′ X j ai,j pj b ∗ i,j = B ′ iαi X j b ∗ i,j = B ′ iαiBi = Biαi X j b ∗ i ′ ,j ≥ Bi X j ai,j pj b ∗ i ′ ,j = Bi X j ai,j b ∗ i ′ ,j pj = Bi X 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, P i x ∗ i,j = 1, ∀j. Thus, for linear utilities and the envy-free property, we have ui(C) = ui X i x ∗ i = ui x ∗ i + X i ′6=i ui x ∗ i ′ (26) ≤ ui x ∗ i + X i ′6=i Bi ′ Bi ui x ∗ i = P i ′ Bi ′ Bi ui x ∗ i . Hence, ui(x ∗ i ) ≥ P Bi i ′ Bi ′ ui(C), ∀i. - Sharing-incentive: At the ME (X∗ , p∗ ), no service spends more than its budget. We have X i X j x ∗ i,jp ∗ j ≤ X i Bi ⇒ X j p ∗ j X i x ∗ i,j ≤ X i Bi (27) Thus, P j p ∗ j ≤ P i Bi . Consequently, resource bundle xˆi costs service i: P j xˆi,jp ∗ j = P j P 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(ˆxi), ∀i. 6 DECENTRALIZED SOLUTION A common approach for implementing distributed algorithm 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 program. The value associated with each edge between a service 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 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 X N i=1 Bi ln ui(xi) (28) subject to X N i=1 xi,j ≤ 1, ∀j; xi,j ≥ 0, ∀i, j. Relaxing the coupling constraints, the partial Lagrangian is L(X, p) = X i Bi ln ui(xi) +X j pj 1 − X i xi,j (29) = X i Bi ln ui(xi) − X j pjxi,j + X j pj . Thus, given a price vector p, each service solves maximize xi≥0 Bi ln ui(xi) − X 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: u CES i (xi) = PM 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, u CES i → 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) = P 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 X 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 PM 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 following distributed algorithm with CES function approximation (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 n pj (t) + α(t) 1 − PN i=1 xi,j (t) , 0 o , ∀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 Dynamics (PropDyn) algorithm proposed by the P2P community. This distributed algorithm is very simple to implement 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) = P 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) = P 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 bundl 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 P b−i,ik k j=1 q ai,ij b−i,ij Bi + Pk 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,i P l k j=1 q ai,ij b−i,ij Bi + Pk j=1 b−i,ij − b−i,il To illustrate the effectiveness of the PropDyn mechanism 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 algorithm 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) = P 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: P j xi,jpj ≤ Bi , ∀i and xi,j ≥ 0, ∀i, j. Indeed, maximizing the net profit vi(xi) is equivalent to maximizing P j (ai,j −pj)xi,j +Bi = P j ai,jxi,j +si , where si = Bi − P 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 gametheoretic 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 decomposition 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,η X M j=1 pj − X 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 Lagrangian 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) = P 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,η X M j=1 pj − X 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 X N i=1 Bi ln ui − si (35) subject to ui ≤ X M j=1 ai,jxi,j + si , ∀i X 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. Additionally, 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 revenue 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.