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

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

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.

Introduction

Mobile Edge Computing (MEC) aims to bring cloud-like capabilities to the network edge—such as cell towers or routers—to reduce latency for demanding applications like AR/VR and autonomous driving. However, edge nodes are physically constrained, possessing limited compute and storage compared to centralized data centers.

A significant gap in current research is the assumption that a single entity owns all hardware. In reality, the edge is a patchwork of diverse service providers (e.g., AWS, local telcos). These providers face a dual challenge: maintaining customer loyalty by prioritizing native applications and maximizing utility by renting out idle resources. This paper addresses the need for a fair, stable system where multiple providers can share resources, even with differing objectives like low latency versus high throughput.

Methodology

The proposed framework utilizes Cooperative Game Theory (CGT), specifically modeling the environment as a Canonical Game with Transferable Utility (TU).

Multi-Objective Optimization and the Grand Coalition

Since providers have varying goals, the system optimizes a weighted sum of utilities. The authors prove that the game is "superadditive," meaning the total utility of a combined group is always greater than or equal to the sum of providers working individually. Consequently, it is mathematically optimal for all providers to join a single "Grand Coalition."

Algorithm 2: An $O(N)$ Solution

Finding fair allocations traditionally involves calculating the Shapley value, which has an exponential time complexity of $O(2^N)$. This paper introduces a linear-time $O(N)$ algorithm (Algorithm 2) that finds solutions within the "Core"—a set of allocations where no provider has an incentive to defect. This breakthrough is justified by proving the game is "convex" due to monotone non-decreasing utility functions.

Experimental Setup

The model was validated using synthetic data, including request matrices for communication and computation, and capacity vectors for resource limits. The authors tested the model using both linear and sigmoidal utility functions to represent different types of application demands.

Key Results

Utility Gains through Sharing

The primary finding is that sharing is mutually beneficial. Every provider achieved higher utility by participating in the sharing framework than by working in isolation. This remains true even when providers prioritize their own "native" applications before sharing surpluses, mimicking real-world business logic.

Utility comparison between no sharing and the grand coalition across ten players.

As shown in the figure above, the utility for each of the ten players is significantly higher under the "Grand Coalition" scenario compared to the "No sharing" baseline, across different values of the parameter $\mu$.

Efficiency and Complexity

The proposed $O(N)$ algorithm demonstrates a massive leap in efficiency. It reduces the time complexity of finding a stable solution by up to 71.67% compared to the traditional Shapley value method.

Computational time comparison between the Shapley Value (S.V.) and the proposed Algorithm 2.

The time comparison highlights that as the number of applications increases (e.g., the 3-100 player-application case), the computational advantage of Algorithm 2 becomes increasingly pronounced, making it suitable for large-scale edge environments.

Conclusion

This research provides a robust mathematical foundation for collaborative resource management in MEC. By proving the stability of the grand coalition and providing a high-efficiency allocation algorithm, the authors offer a path toward more efficient edge networks.

Future work should address the challenges of decentralized control, as the current model assumes a central controller with full knowledge of all players' resources. Additionally, moving from static snapshots to dynamic, real-time environments and validating with real-world edge traffic traces will be crucial for practical implementation.

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 \emph{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 $\mathcal{O}(N)$ algorithm that provides allocation decisions from the \emph{core}, hence the obtained allocations are \emph{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 $\mathcal{O}(N)$ algorithm reduces the time complexity of obtaining a solution from the core by as much as 71.67\% when compared with the \emph{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 Clouds}},
  booktitle = {EdgeTech@MobiCom},
  year = {2018},
  url = {https://openreview.net/forum?id=22K0UngfrB},
}
Figure