A Game-Theoretic Approach to Multi-Objective Resource Sharing and Allocation in Mobile Edge

Faheem Zafari, Jian Li, Kin K. Leung, Don Towsley, Ananthram Swami

TL;DR

This paper tackles the challenge of efficiently allocating limited resources in mobile edge computing by proposing a cooperative game theory framework. It enables multiple edge providers to share resources, leading to improved utility for all, and introduces an efficient O(N) algorithm that guarantees stable and optimal resource allocation.

What Problem Does This Paper Address?

Mobile edge computing (MEC) offers a promising solution for delay-sensitive applications by bringing computation closer to users. However, a key limitation is the scarcity of resources on edge clouds. When multiple edge service providers operate in the same geographical area, they face the challenge of allocating these limited resources not only to their own "native" applications but also potentially to applications from other providers. This becomes a complex multi-objective optimization problem, especially since each provider has its own unique utility function to maximize (e.g., latency, throughput, security). The paper addresses the need for a mechanism that allows these providers to cooperate, share resources effectively, and achieve Pareto optimal allocations that are stable and beneficial for everyone involved.

Methods

The authors propose a Cooperative Game Theory (CGT) framework to model the resource sharing and allocation problem. Here's a breakdown of their approach:

  • Coalition Formation: Edge clouds are treated as "players" who can form coalitions. The core idea is that providers first satisfy their own applications and then share any surplus resources.
  • Multi-Objective Optimization: The problem is framed as a multi-objective optimization problem because each provider has its own utility function.
  • Canonical Game Model: They model this as a Canonical Game with Transferable Utility (TU), meaning the total utility of a coalition can be divided among its members. The game is also shown to be superadditive (forming larger coalitions is always beneficial) and convex.
  • Core and Shapley Value: For convex games, the core (a set of stable and Pareto-optimal allocations) is guaranteed to exist and contain the Shapley value (a fair allocation method). The paper aims to find an allocation within the core.
  • O(N) Algorithm: Recognizing the high computational complexity of calculating the Shapley value (which involves solving 2<sup>N</sup>-1 optimization problems), they introduce an efficient O(N) algorithm. This algorithm provides an allocation from the core but sacrifices some of the fairness guarantees of the Shapley value.

Datasets

Not discussed in the paper. The experiments were conducted using randomly generated request matrices and capacity vectors for the edge clouds.

Key Insights and Ideas

  • Cooperation is Key: The most significant insight is that by cooperating and sharing resources, individual edge providers can achieve higher utilities than they could by operating in isolation. This highlights the economic and performance benefits of forming a shared resource pool.
  • Game Theory as a Solution: Framing resource allocation as a cooperative game provides a robust mathematical framework to ensure stability and optimality, especially in a multi-provider environment with diverse objectives.
  • The Core Guarantees Stability: The concept of the "core" in game theory is crucial here. Allocations within the core ensure that no provider has an incentive to leave the grand coalition and form a smaller one, guaranteeing the stability of the shared resource pool.
  • Efficiency Matters: The development of an O(N) algorithm is a critical practical contribution. It makes the proposed game-theoretic solution scalable to larger numbers of edge providers, which is essential for real-world deployment.

Key Results

  • Improved Utility: Experimental results demonstrate that the proposed resource sharing and allocation framework significantly improves the utility of all service providers compared to a scenario where they operate independently.
  • Pareto Optimality and Stability: The proposed framework, particularly through the O(N) algorithm, provides allocations that are Pareto optimal and ensure the stability of the grand coalition.
  • Significant Speedup: The O(N) algorithm reduces the time complexity of obtaining a solution from the core by as much as 71.67% compared to the Shapley value, with an average improvement of around 49.75%. This makes the approach practical for real-time resource management.
  • Coalition Value Increases with Players: The value of a coalition (total utility) increases as more players (edge providers) join, confirming the superadditive nature of the game and the benefits of cooperation.

Limitations and Future Work

  • Shapley Value Fairness vs. O(N) Efficiency: While the O(N) algorithm provides an efficient allocation from the core, it doesn't offer the same level of fairness as the Shapley value. The paper acknowledges this trade-off.
  • Computational Complexity of Shapley Value: The high computational complexity of the Shapley value limits its applicability to scenarios with a small number of players.
  • Future Work: The authors suggest extending the model to include other types of resources and parameters, and potentially exploring more advanced game-theoretic concepts for finer-grained control or different fairness criteria. The paper also implies that further research could focus on dynamic resource allocation in more complex and evolving edge environments.

Summary updated

Abstract

Mobile edge computing seeks to provide resources to different delay-sensitive applications. However, allocating the limited edge resources to a number of applications is a challenging problem. To alleviate the resource scarcity problem, we propose sharing of resources among multiple edge computing service providers where each service provider has a particular utility to optimize. We model the resource allocation and sharing problem as a multi-objective optimization problem and present a Cooperative Game Theory (CGT) based framework, where each edge service provider first satisfies its native applications and then shares its remaining resources (if available) with users of other providers. Furthermore, we propose an ~O (N) algorithm that provides allocation decisions from the core, hence the obtained allocations are Pareto optimal and the grand coalition of all the service providers is stable. Experimental results show that our proposed resource allocation and sharing framework improves the utility of all the service providers compared with the case where the service providers are working alone (no resource sharing). Our ~O (N) algorithm reduces the time complexity of obtaining a solution from the core by as much as 71.67% when compared with the Shapley value.
BibTeX
@inproceedings{zafari2018game,
  author = {Faheem Zafari and Jian Li and Kin K. Leung and Don Towsley and Ananthram Swami},
  title = {{A Game-Theoretic Approach to Multi-Objective Resource Sharing and Allocation in Mobile Edge}},
  booktitle = {EdgeTech@MobiCom},
  year = {2018},
  url = {https://openreview.net/forum?id=22K0UngfrB},
}
Figure