Job-Scheduling Games with Time-Dependent Processing Times
New paper shows Nash equilibria may not exist when job lengths change over time...
A new paper on arXiv by Ido Borenstein and Tami Tamir tackles job-scheduling games with time-dependent processing times—a significant departure from traditional models that assume fixed job durations. In realistic environments like cyber-security response or high-frequency trading, a task's length grows or shrinks based on when it starts (positive or negative deterioration). The authors introduce the concept of delay-averse agents to analyze equilibrium existence. For delay-averse jobs, they show pure Nash equilibria (NE) can be computed efficiently, preserving stability. But for non-delay-averse jobs, NE may not exist, and deciding existence is NP-complete even on identical machines—a fundamental break from classical results.
To mitigate inefficiency, the paper proposes three coordination mechanisms: SBPT (Shortest Basic Processing Time) reduces Price of Anarchy (PoA) to a constant for positive deterioration. For negative deterioration, SDR (Smallest Deterioration Rate) achieves tight PoA of 2, and LBDR (Largest Basic-Deterioration Ratio) achieves PoA of max{e/(e-1), 2-1/m}. These results bridge centralized time-dependent scheduling and decentralized game theory, offering practical insights for designing scheduling policies in dynamic environments like cloud computing or automated trading systems.
- Job lengths are linear functions of start times, modeling real-world dynamic environments like cyber-security and HFT.
- For delay-averse agents, pure Nash equilibria exist and are efficiently computable; for others, existence is NP-complete.
- Coordination mechanisms SBPT, SDR, and LBDR bound Price of Anarchy to constants (e.g., 2 or e/(e-1)).
Why It Matters
This work provides foundational theory for designing scheduling algorithms in dynamic, decentralized systems like cloud computing and trading.