PaperlayerView exact revision on arXiv

Source-linked AI summary

Price-based Resource Allocation for Edge Computing: A Market Equilibrium Approach

Duong Tung Nguyen, Long Bao Le, Vijay Bhargava

arXiv:1805.02982v1cs.GT

TL;DR

The paper addresses fair and efficient allocation of scarce edge resources among competing, budget-constrained services. It prices edge nodes through market equilibrium, using an Eisenberg-Gale program, distributed algorithms, and a new convex formulation for net-profit objectives. The resulting allocations maximize utilization and satisfy Pareto-optimality and fairness properties, while the framework assumes unlimited service demand and faces coupled budgets in conventional welfare decomposition.

  • Problem

    Edge resources are geographically distributed and capacity-limited, so services need fair and efficient allocation under budget constraints.

  • Method

    The framework prices edge nodes to compute market equilibria, using an Eisenberg-Gale program, distributed algorithms, and a new convex program for buyers who value money.

  • Results

    The equilibrium fully allocates resources, maximizes service utility under budgets, and is Pareto-optimal and envy-free with sharing incentive and proportionality.

  • Takeaways & Limitations

    Market equilibrium provides a fair and efficient coordination mechanism for allocating edge resources among competing services.

  • Takeaways & Limitations

    The framework assumes unlimited service demand, although maximum-request constraints can be added to the Eisenberg-Gale program.

Abstract

from arXiv · show

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.

1 INTRODUCTION

The paper frames edge computing as a response to cloud limitations and proposes market-based pricing to allocate scarce, heterogeneous edge resources among budget-constrained services fairly and efficiently.

  • Cloud computing faces growing latency, reliability, security, mobility, and localization limitations, motivating edge computing near end-users.
  • Edge nodes reduce network traffic and improve user experience by enabling local caching, location-aware processing, and real-time analysis.
  • Capacity limits, heterogeneous service preferences, and uneven demand make fair allocation across geographically distributed edge nodes a fundamental problem.
  • The framework prices highly demanded edge resources higher and lets each budget-constrained service choose its preferred affordable bundle until the market clears.
  • The first model uses an Eisenberg-Gale convex program for the market equilibrium and establishes Pareto-optimality, envy-freeness, sharing incentive, and proportionality.
  • Distributed algorithms address non-unique linear-utility demands, while a new convex program exactly captures the model in which buyers value money.

2 RELATED WORK

Related work spans edge resource allocation, cloud economics, auctions, and game-theoretic mechanisms; this paper instead targets fair and efficient allocation among budget-constrained services across multiple edge nodes.

  • Existing edge studies address cloudlet selection, placement, service dispatch, and latency-load tradeoffs, but not the paper’s market-design objective.
  • Prior MEC work studies joint communication-computation allocation, where simultaneous offloading can create interference and small allocations.
  • The paper applies General Equilibrium and Fisher markets to edge allocation, combining market clearing with utility maximization under budgets.
  • Cloud resource research also includes provider profit maximization, federation sharing, procurement, generalized Nash games, and Stackelberg pricing.
  • Auction-based cloud allocation typically selects winning bids and calculates payments, whereas this work seeks fair and efficient allocations for all budget-constrained agents.

3 SYSTEM MODEL

The system consists of heterogeneous, capacity-limited edge nodes and competing services with procurement budgets, with equilibrium prices coordinating utility-maximizing allocation and full resource utilization.

  • The environment contains geographically distributed edge nodes with different configurations and limited computing capacities, plus services with resource-procurement budgets.
  • A platform collects node capacities and service preferences, then computes prices and allocations that maximize service satisfaction while fully allocating edge resources.
  • Services seek to offload as many requests as possible, while their values for edge nodes may differ because of location, capacity, or service preferences.
  • The framework distinguishes revenue maximization under virtual or real budgets from net-profit maximization when remaining money has intrinsic value.

4 PROBLEM FORMULATION

The formulation models services competing for divisible capacities at priced edge nodes, defines equilibrium through optimal affordable bundles and market clearing, and derives linear utilities from delay-sensitive request processing.

  • 4.1 EC Resource Allocation Problem: Each edge node has homogeneous computing units and a capacity constraint, while the allocation matrix records each service’s resource share and budgets limit procurement.
  • 4.1 EC Resource Allocation Problem: A market equilibrium requires every service to receive an optimal affordable bundle at equilibrium prices and all edge-node resources to be fully allocated.
  • 4.1 EC Resource Allocation Problem: In the basic model, services maximize revenue under budgets; in the second model, they maximize revenue minus payments, with the report focusing first on the basic model.
  • 4.2 Service Utility Model: With linear utilities, each service values one unit of node j by a coefficient a_i,j, and its utility is the sum of value-weighted allocated resources.
  • 4.2 Service Utility Model: Request delay combines user-to-aggregation, network, and processing components, with queue stability requiring arrival rates below service rates.
  • 4.2 Service Utility Model: Revenue is based on successfully served requests whose total delay stays within each service’s maximum tolerance, assuming an unlimited request pool.
  • 4.2 Service Utility Model: The resulting utility is linear and homogeneous of degree 1, while node values can incorporate flexible weights such as population or reliability.

5 CENTRALIZED SOLUTION

The centralized solution formulates the edge-resource market as an Eisenberg–Gale convex program whose optimum is a market equilibrium with utility-maximizing, budget-exhausting allocations. The resulting allocation is Pareto-optimal and satisfies several fairness properties.

  • At equilibrium, each service buys resources only from ENs maximizing its utility per unit price, defined by its maximum bang-per-buck demand set.The demand set contains ENs attaining max_j{a_i,j/p_j}.
  • The optimal solution to the EG convex program is a market equilibrium: services exhaust their budgets, buy only maximum-bang-per-buck resources, and the market clears.Equilibrium prices are dual variables for EN capacity constraints, and optimal utilities and prices are unique.
  • The equilibrium allocation is scale-free: scaling a service’s utility coefficients or splitting its budget across identical services does not change its total allocation.The paper also notes that the result extends beyond linear utilities to a wider class of homogeneous concave utilities.
  • The equilibrium allocation is Pareto-optimal and envy-free, while also satisfying sharing incentive and proportionality.These properties ensure that services prefer their equilibrium bundles to proportional initial contributions and receive utility proportional to their budgets.

6 DECENTRALIZED SOLUTION

The decentralized solution addresses non-unique demand bundles by approximating linear utilities with strictly concave CES utilities and by using distributed bidding dynamics. These methods converge to solutions at or near the centralized equilibrium, while proportional response requires less information than best response.

  • Linear utilities can yield infinitely many optimal demand bundles, so exact equilibrium prices may still produce mismatched reported demand and supply.The paper illustrates this issue with a service that can choose different EN combinations at the same equilibrium prices.
  • 6.1 Dual Decomposition with Function Approximation: The CES function-approximation algorithm converges to an approximately global optimum arbitrarily close to the centralized EG solution with a sufficiently small step size.CES strict concavity makes each service’s optimal demand bundle unique, resolving the non-uniqueness problem of linear utilities.
  • 6.2 Proportional Response Dynamics Strategy: Proportional response updates each service’s bids from its previous utilities and requires only each service’s own information plus received utility feedback.ENs compute prices from total bids and the process stops when price deviations are sufficiently small.
  • 6.2 Proportional Response Dynamics Strategy: Best response usually gives buyers lower utilities than proportional response, while requiring knowledge of other buyers’ total bids and every EN’s capacity.The comparison concerns the proportional-sharing BR and PropDyn mechanisms.

7 NET PROFIT MAXIMIZATION

The paper develops a convex optimization formulation for market equilibrium when services maximize net profit rather than revenue. Reverse-engineering the basic model yields a program whose solution is exactly an equilibrium, with utility incorporating revenue and surplus money.

  • Net-profit model: Net-profit maximization is formulated by subtracting resource costs from revenue, so services buy resources only when their value exceeds the price.The service objective is expressed using value minus price for each purchased resource.
  • Net-profit model: A direct welfare-maximization and dual-decomposition approach fails under budgets because the budget constraints couple the services.Without budgets, decomposition produces independent service subproblems; budget coupling prevents that strategy here.
  • Extended Fisher market: The proposed convex program has a solution that is exactly a market equilibrium for the net-profit market model.The construction is obtained by reverse-engineering the basic model's primal and dual structure.
  • Extended Fisher market: At equilibrium, each service's spending plus surplus equals its budget, and any service with surplus has utility equal to its budget.The optimal utility of every service is unique and at least as large as its budget.
  • Extended Fisher market: The convex formulation interprets each service's utility as revenue plus surplus money while subtracting surplus from the aggregate objective.The formulation retains the logarithmic-utility structure of the Eisenberg–Gale program while accounting for money left unspent.

8 NUMERICAL RESULTS

Numerical experiments compare market equilibrium (ME) with alternative allocation schemes, examine budget sensitivity and pricing, and evaluate distributed and approximate algorithms. The results show that ME balances efficiency and fairness, reflects budget-based priorities, and converges effectively in the tested settings.

  • 8.2 Performance Comparison: The ME scheme balances system efficiency and fairness better than the compared schemes, outperforming proportional sharing while avoiding the low total utility of maxmin and zero-utility allocations in SW1 and SW2.These comparisons are reported under both equal-budget and different-budget settings.
  • 8.2 Performance Comparison: The ME scheme significantly outperforms social welfare maximization and maxmin schemes in envy-freeness, while satisfying proportionality for four equal-budget buyers.The proportionality ratio is expected to be at least 1/4 in this setting.
  • 8.3 Sensitivity Analysis: Increasing service 1’s budget increases its allocation and utility while decreasing service 2’s allocation and utility, showing that the algorithm captures budget-based service priority.The allocation and utility changes are reported as the budget ratio between the two services varies.
  • 8.3 Sensitivity Analysis: Equilibrium prices vary with budget ratios and reflect EN valuations: EN7 and EN8 respond strongly to service 1’s budget, while EN5 and EN6 have lower prices and EN2 and EN8 higher prices.The price patterns are linked to delay feasibility and the relative values of ENs to buyers.
  • 8.5 Net Profit Maximization Model: In the net-profit model, equilibrium prices increase and then saturate as budgets grow, while utilities eventually equal budgets when purchasing resources provides no additional benefit.For the same budget scale, net-profit equilibrium prices are smaller than in the revenue-maximization model because services buy only resources with positive gain.

9 CONCLUSION AND FUTURE WORKS

The paper applies General Equilibrium theory to edge-computing resource allocation, yielding Pareto-efficient and fair market-equilibrium outcomes. It identifies extensions involving broader resource-sharing scenarios, federated edge networks, strategic behavior, limited demand, and operating costs.

  • The framework applies General Equilibrium theory to edge-computing resource allocation and produces Pareto-efficient solutions with fairness properties.The authors identify applications beyond edge computing, including sharing storage, communication, and wireless resources, and extending to multiple resource types.
  • The framework can support storage sharing, resource sharing among users or groups, and future multi-resource applications such as network slicing and NFV chaining.
  • Future work includes edge/fog federation, strategic behavior, limited-demand equilibria, and incorporating edge-node operating costs.The authors also note ongoing work on equilibrium prices under limited demand and more complex resource settings.

APPENDIX A PROOF OF PROPOSITION 6.1

The appendix derives the optimal solution of each service’s subproblem using first-order conditions and budget constraints. It concludes that the solution has a closed form and is positive.

  • The two service optimization formulations have the same optimal solution for any positive price vector.
  • The service subproblem is solved by forming its Lagrangian, applying first-order conditions, and using the budget constraint to infer each allocation component.
  • The resulting optimal solution has a closed-form expression and is positive.

APPENDIX B PROOF OF PROPOSITION 7.1

The appendix constructs a dual formulation from the Eisenberg–Gale program and shows that their optimality conditions coincide. This establishes that the derived convex program captures equilibrium prices.

  • The appendix derives a dual objective from the Eisenberg–Gale convex program by removing constant terms from its objective.
  • The conjugate of the logarithmic utility-related function is computed to support the dual construction.
  • The derived convex program is inferred directly from the Eisenberg–Gale program.
  • Equivalent KKT conditions show that the derived program captures market-clearing equilibrium prices.The allocation variables in the derived program correspond to dual variables in the Eisenberg–Gale formulation.

APPENDIX C PROOF OF THEOREM 7.2

The appendix derives the dual formulation for the net-profit model and proves that its solution is an exact market equilibrium. The proof uses KKT conditions to characterize demand, spending, surplus, and utility.

  • The dual formulation is constructed by assigning dual variables to the constraints of the primal problem and identifying them with allocation and surplus variables.
  • The proof establishes exact market equilibrium by combining budget exhaustion, unique optimal utilities, and KKT conditions.
  • The KKT conditions characterize nonnegative prices, surplus-related variables, and complementary-slackness relationships.
  • Each service buys only from edge nodes offering its maximum bang-per-buck and therefore maximizes its utility.
  • A service with surplus has utility equal to its budget, while a service without surplus spends its budget and obtains utility above its budget.

APPENDIX D CONCAVE HOMOGENEOUS UTILITY FUNCTIONS

This appendix shows that the Eisenberg–Gale program yields a market equilibrium for concave homogeneous utility functions. The proof establishes budget exhaustion, utility maximization, and market clearing at the equilibrium prices.

  • The EG program applies beyond linear utilities to concave homogeneous utility functions of degree one.This broader applicability is identified as an extension of the Fisher-market formulation.
  • The proof uses KKT conditions and Euler’s theorem for homogeneous functions to connect the EG optimum with buyers’ demand and budget constraints.Dual variables and homogeneity relate the optimization conditions to equilibrium pricing.
  • At equilibrium prices, each buyer exhausts its budget.
  • The EG solution gives every buyer an optimal resource bundle at equilibrium prices and satisfies all market-equilibrium requirements.The argument establishes both optimal demand and market clearing.

APPENDIX E OTHER DISCUSSIONS

The appendix extends the framework to concave homogeneous revenue functions, multiple resource types, and a decentralized implementation. These extensions preserve applicability of the proposed optimization framework and broaden its implementation scope.

  • Net profit maximization and concave homogeneous revenue functions: The net-profit model extends to concave homogeneous revenue functions because the combined utility remains concave and homogeneous of degree one.The appendix states that the new convex optimization problem continues to apply to this wider function class.
  • Multiple resource types: Multiple-resource services can be modeled with a minimum-ratio utility over bandwidth, computing, and memory, and the framework applies to multiple edge nodes.The construction uses a base demand vector and sums utility across edge nodes when needed.
  • Another decentralized implementation of the basic model (revenue maximization): The revenue-maximization model also admits a decentralized implementation in which services report maximum bang-per-buck values and demanded edge nodes.This modifies a centralized combinatorial algorithm for distributed operation.
Loading 1805.02982v1…