Equilibria of Online Scheduling Algorithms

Authors

  • Itai Ashlagi Massachusetts Institute of Technology
  • Brendan Lucier Microsoft Research New England
  • Moshe Tennenholtz Microsoft Research, Herzlyia, Israel

DOI:

https://doi.org/10.1609/aaai.v27i1.8631

Keywords:

Online Games, Equilibrium Analysis, Scheduling Algorithms, Competitive Queues, Non-Bayesian Equilibria

Abstract

We describe a model for competitive online scheduling algorithms. Two servers, each with a single observable queue, compete for customers. Upon arrival, each customer strategically chooses the queue with minimal expected wait time. Each scheduler wishes to maximize its number of customers, and can strategically select which scheduling algorithm, such as First-Come-First-Served (FCFS), to use for its queue. This induces a game played by the servers and the customers. We consider a non-Bayesian setting, where servers and customers play to maximize worst-case payoffs. We show that there is a unique subgame perfect safety-level equilibrium and we describe the associated scheduling algorithm (which is not FCFS). The uniqueness result holds for both randomized and deterministic algorithms, with a different equilibrium algorithm in each case. When the goal of the servers is to minimize competitive ratio, we prove that it is an equilibrium for each server to apply FCFS: each server obtains the optimal competitive ratio of 2.

Downloads

Published

2013-06-30

How to Cite

Ashlagi, I., Lucier, B., & Tennenholtz, M. (2013). Equilibria of Online Scheduling Algorithms. Proceedings of the AAAI Conference on Artificial Intelligence, 27(1), 67-73. https://doi.org/10.1609/aaai.v27i1.8631