Motivating Learners in Multi-Orchestrator Mobile Edge Learning: A Stackelberg Game Approach

Mhd Saria Allahham, Sameh Sorour, Amr Mohamed, Aiman Erbad, Mohsen GuizaniarXiv 2021 · arXiv

Abstract

Mobile Edge Learning (MEL) leverages resource-constrained edge devices for distributed machine learning, necessitating robust incentive mechanisms to compensate for energy and computational costs. While existing research often assumes a single-orchestrator model, real-world deployments involve multiple orchestrators competing for the same pool of edge devices. This paper proposes a two-round Stackelberg game approach to address this multi-orchestrator challenge. By employing a Factor-Based Association (FBA) heuristic followed by a rigorous optimization phase, the proposed FBA-OPT framework effectively balances model accuracy requirements with learner utility. Experimental results using the MNIST dataset demonstrate that FBA-OPT consistently outperforms baseline strategies in terms of accuracy, learner revenue, and overall system utility.

Introduction

Mobile Edge Learning (MEL), encompassing paradigms such as Federated Learning, utilizes the distributed computational resources of edge nodes—like smartphones and IoT devices—to train machine learning models. This approach offers significant advantages in terms of data privacy and reduced backbone network traffic. However, the inherent resource constraints of edge devices make learners naturally reluctant to participate due to the high energy consumption associated with local training and communication.

To encourage participation, incentive mechanisms are required. Most current literature focuses on scenarios with a single central orchestrator. In practice, however, multiple orchestrators with distinct tasks and datasets coexist, creating a competitive environment for edge resources. This paper tackles the multi-orchestrator problem: determining how learners should associate with tasks and how orchestrators should set prices to maximize performance without overspending.

Methodology

The interaction between orchestrators and learners is modeled as a static two-round Stackelberg game.

Round 1: Association Phase

Orchestrators initiate the game by broadcasting task parameters and initial price offers. Learners must then select a single orchestrator to join. Because optimal association is an NP-hard knapsack problem, the authors introduce the Factor-Based Association (FBA) heuristic. FBA matches learners to orchestrators based on the ratio of normalized initial payment to physical distance, which serves as a proxy for communication overhead.

Round 2: Optimization Phase

In the second round, orchestrators act as leaders, announcing final service prices and the required number of local training iterations. Learners, acting as followers, decide the volume of data to process to maximize their net profit (revenue minus energy costs). Using backward induction, the authors prove the existence of a Nash equilibrium in this stage, allowing for the derivation of optimal pricing and data-processing strategies.

The framework was evaluated using the MNIST dataset for handwritten digit classification, with Multi-Layer Perceptrons (MLPs) representing the learning models.

Key Insights

A primary challenge identified is the straggler bottleneck. In synchronous updates, the global training cycle is limited by the slowest learner. Orchestrators must account for these delays in their strategic planning. Furthermore, the model assumes strict rationality: learners will only engage if the offered compensation exceeds their operational costs. This creates a threshold price below which participation drops to zero.

Experimental Results

The proposed FBA-OPT framework was compared against a random assignment strategy and a distance-based, energy-efficient heuristic (DBA-EE).

Model Accuracy

FBA-OPT consistently achieved higher learning accuracy than the baselines across various time constraints ($T_{max}$). By optimizing incentives, the framework ensures that learners process an ideal amount of data to minimize learning loss within the allotted time frame.

Figure 1: Accuracy % vs. Time (s) for different association and optimization strategies.

Learner Utility and Revenue

FBA-OPT provided the highest total revenue and normalized utility for the learners. As the available training time increases, the framework allows learners to scale their participation, maximizing their financial returns.

Figure 4: Normalized Utility vs. Time (s) showing the superior performance of FBA-OPT in maximizing learner benefits.

While the DBA-EE baseline prioritizes energy conservation, FBA-OPT is more "opportunistic." It consumes more energy overall, but the resulting financial payouts to the learners more than justify the additional battery drain, leading to higher overall system satisfaction.

Conclusion

This paper presents a novel game-theoretic framework for multi-orchestrator mobile edge learning. By splitting the problem into a heuristic association phase and a mathematically rigorous optimization phase, the FBA-OPT approach successfully navigates the complexities of competitive edge resource allocation. Future research directions include extending the model to support asynchronous learning to eliminate straggler effects and incorporating more dynamic wireless channel models to reflect real-world variability.

Summary updated

Abstract

Mobile Edge Learning (MEL) is a learning paradigm that enables distributed training of Machine Learning models over heterogeneous edge devices (e.g., IoT devices). Multi-orchestrator MEL refers to the coexistence of multiple learning tasks with different datasets, each of which being governed by an orchestrator to facilitate the distributed training process. In MEL, the training performance deteriorates without the availability of sufficient training data or computing resources. Therefore, it is crucial to motivate edge devices to become learners and offer their computing resources, and either offer their private data or receive the needed data from the orchestrator and participate in the training process of a learning task. In this work, we propose an incentive mechanism, where we formulate the orchestrators-learners interactions as a 2-round Stackelberg game to motivate the participation of the learners. In the first round, the learners decide which learning task to get engaged in, and then in the second round, the training parameters and the amount of data for training in case of participation such that their utility is maximized. We then study the training round analytically and derive the learners' optimal strategy. Finally, numerical experiments have been conducted to evaluate the performance of the proposed incentive mechanism.
BibTeX
@misc{allahham2021motivating,
  author = {Mhd Saria Allahham and Sameh Sorour and Amr Mohamed and Aiman Erbad and Mohsen Guizani},
  title = {{Motivating Learners in Multi-Orchestrator Mobile Edge Learning: A Stackelberg Game Approach}},
  year = {2021},
  eprint = {2109.12409},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2109.12409},
}
Figure