Algorithmic Game Theory and Scheduling

Éric Angel, Evripidis Bampis, Fanny PascualOpenalex Unknown 2007 · DOI · OpenAlex

Abstract International audience. This paper surveys the intersection of scheduling and game theory, focusing on quantifying the efficiency loss caused by selfish agents—the "Price of Anarchy"—and designing mechanisms to mitigate it. It provides rigorous bounds for various scheduling models and demonstrates how local policies or "truthful" algorithms can nudge selfish behavior toward better global outcomes.

Introduction

In classical computer science, scheduling problems often assume a central, omniscient controller that optimizes for a global objective. However, modern decentralized systems like the Internet are populated by rational, selfish agents. These agents—whether they are users submitting tasks or resource owners providing hardware—prioritize their own utility over system-wide efficiency. This paper, "Algorithmic Game Theory and Scheduling" by Eric Angel, Evripidis Bampis, and Fanny Pascual, explores the mathematical consequences of this selfishness and strategies for managing it.

Problem Models

The authors categorize the interaction between agents and systems into three primary models:

  1. The KP Model: Selfish tasks choose machines to minimize their own contribution to the total load (makespan).
  2. The CKN Model: Tasks choose machines based on specific local scheduling policies to minimize their individual completion times.
  3. The AT Model: Selfish machines may misreport their processing speeds to maximize their own payments or minimize their workload.

The central challenge in these models is the lack of coordination. Standard optimization fails because it lacks "incentive compatibility"—if a global optimum requires an agent to accept a suboptimal personal result, a selfish agent will deviate.

Methodology and Metrics

To quantify the impact of selfishness, the authors utilize two key metrics:

  • Price of Anarchy (PoA): The ratio between the performance of the worst-case Nash Equilibrium and the social optimum.
  • Price of Stability (PoS): The ratio between the best-case Nash Equilibrium and the social optimum.

Beyond measurement, the paper discusses Mechanism Design. This involves creating "truthful" payment schemes or financial incentives that ensure an agent's best strategy is to act honestly (e.g., reporting true machine speeds). They also explore Coordination Mechanisms, which are local rules (like "Shortest Processing Time first") that machines follow to naturally guide selfish agents toward more efficient global states.

Key Insights and Results

The survey highlights several critical theoretical bounds and algorithmic properties:

  • The 3/2 Barrier: In the KP model with two identical machines, the PoA is exactly $3/2$, meaning selfishness results in at most a 50% efficiency loss.
  • Local Policy Optimization: In the CKN model, using a combination of "Longest Processing Time" (LPT) and "Shortest Processing Time" (SPT) policies on two machines can reduce the coordination ratio to $4/3$.
  • Truthfulness and Monotonicity: For an algorithm to be "truthful" in the AT model, it must be monotone; if a machine's speed increases, the algorithm should not assign it less work.
  • Randomized Efficiency: The authors introduce $LS_\delta$, a randomized algorithm that is both truthful and provides a better expected approximation ratio than deterministic alternatives.

Limitations and Future Research

While the paper provides a robust foundation, it identifies several open frontiers:

  • Scaling to $m$ Machines: Many tight bounds are currently limited to two-machine scenarios. Generalizing these to $m$ machines remains a significant challenge.
  • Computational Complexity: Finding a Nash Equilibrium remains a significant challenge in polynomial-time computation.
  • Unrelated Machines: Systems where machine performance varies per specific task (rather than a global speed factor) present much higher complexity and remain an active area of study.

Conclusion

Building efficient systems from selfish components is a defining challenge of modern digital infrastructure. By bridging game theory and scheduling, this work provides the tools necessary to design robust, incentive-compatible environments that minimize the "cost of selfishness."

Summary updated

Abstract

International audience
BibTeX
@inproceedings{angel2007algorithmic,
  author = {Éric Angel and Evripidis Bampis and Fanny Pascual},
  title = {{Algorithmic Game Theory and Scheduling}},
  booktitle = {Openalex Unknown},
  year = {2007},
  doi = {10.1201/9781420010749-92},
}
Figure