Online Learning for Load Balancing of Unknown Monotone Resource Allocation Games

Ilai Bistritz, Nicholas BambosICML 2021 · OpenReview

Introduction

In large-scale distributed networks, managing shared resources—such as electricity across a smart grid or bandwidth across wireless channels—is a delicate balancing act. If too many users flock to a single resource, the system suffers from congestion, delays, or outright failure.

Traditionally, a central manager might solve this by collecting everyone's preferences and calculating an optimal, system-wide allocation. However, this centralized approach suffers from two major flaws:

  1. Privacy: Users are often reluctant to share their private reward functions or usage patterns.
  2. Complexity: In a massive network, solving a central optimization problem becomes computationally impossible in real-time.

Game theory offers an alternative: allow users to act selfishly, and they will eventually reach a Nash Equilibrium (NE). The drawback is that a natural, unguided NE is often inefficient and "unbalanced." This paper asks a critical question: Can a manager steer this selfish behavior toward a load-balanced state using only minimal, privacy-preserving feedback, such as the total load on each resource?

To solve this, the authors introduce a simple online pricing algorithm that balances loads in distributed resource allocation games without the manager ever knowing the users' private preferences. By adjusting prices based solely on observed total resource usage, the system provably converges to a balanced Nash Equilibrium, even while users simultaneously learn their own optimal strategies.

The Model and Methodology

The authors model the interaction as a Strongly Monotone Resource Allocation Game. In this environment, a central manager controls linear pricing coefficients ($\alpha$) for each resource to influence user behavior.

System architecture showing the manager adjusting pricing coefficients based on total load feedback to steer players toward a balanced equilibrium.

The core contribution is a dual-scale online learning approach:

  • The Players: Each user runs a "proper" Stochastic Gradient Descent (SGD) to maximize their own utility. They do not need to know the global state of the system; they simply react to the current prices set by the manager.
  • The Manager: The manager acts similarly to a "game bandit." At each step, they observe the total load per resource and update the prices. If a resource is over-utilized compared to a target capacity $l^*$, the price goes up. If it is under-utilized, the price goes down (bounded at zero).

The mathematical heavy lifting of the paper involves proving convergence despite "equilibrium noise." Because the manager changes prices every turn, the Nash Equilibrium itself is a moving target. The authors prove that by making the manager's updates significantly slower than the players' updates (a two-scale learning approach), the system eventually stabilizes at the desired balanced state.

Key Insights

  • Privacy-Preserving Control: The manager never sees individual actions or reward functions. They only require the sum of actions, which is often naturally available (e.g., the total power draw on a neighborhood transformer).
  • Handling Resource Coupling: In these games, resources are interconnected. Raising the price of Resource A might unexpectedly increase the load on Resource B. The proposed algorithm is robust enough to handle these cross-resource effects without needing an explicit model of the game's underlying structure.
  • Two-Scale Learning: A critical insight is the tuning of step sizes. For the system to converge, the manager must learn at a different "speed" than the players. This ensures the players don't "lose track" of the shifting equilibrium.
  • Complementary Slackness: The algorithm naturally satisfies "complementary slackness"—it only leaves a resource under-utilized if the price of that resource has already dropped to zero.

Real-World Applications and Results

The paper evaluates the algorithm using two simulated, high-impact applications, comparing the results against uncontrolled systems and existing state-of-the-art methods:

  1. Demand-Side Management (DSM) in Electricity Grids:
    • Setup: A simulation with 1,000 players and 24 resources (representing hours of the day), aiming to shift demand away from peak hours.
  2. Result: The algorithm significantly increased "social welfare" (total user satisfaction minus costs) compared to standard baseline pricing models, scoring 744.7 versus the baseline's 208.9.
  3. Power Control in Wireless Networks:
    • Setup: A simulation with 300 communication links and 3 frequency channels, aiming to minimize interference and power consumption while maintaining throughput.
  4. Result: The algorithm achieved 15% higher total throughput than an uncontrolled system, while simultaneously reducing average transmission power and interference.

Crucially, the authors provide a rigorous theoretical guarantee that the algorithm converges in $L_2$ to a load-balanced Nash Equilibrium. Furthermore, the approach performed as well as methods that require full information (like knowing the exact mathematical relationship between users), proving that "blind" aggregate feedback is sufficient for effective control.

Limitations and Future Work

While highly effective, the approach has a few limitations that pave the way for future research:

  • Monotonicity Assumption: The mathematical proofs rely on the game being "strongly monotone." While many physical systems fit this description, it does not cover every possible type of strategic interaction.
  • Strategic Manipulation: The model assumes players are "myopic" (simply using SGD to optimize their immediate utility). Future work could explore system vulnerabilities if a large group of players attempts to intentionally manipulate the manager's pricing algorithm.
  • Convergence Rates: While the paper proves the system will converge, it does not provide a specific "regret bound" or a formula for exactly how many iterations it takes to reach equilibrium. Establishing these bounds is a promising avenue for future theoretical work.

Summary updated

BibTeX
@inproceedings{bistritz2021online,
  author = {Ilai Bistritz and Nicholas Bambos},
  title = {{Online Learning for Load Balancing of Unknown Monotone Resource Allocation Games}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=ljp2wLsm8f},
}
Figure