On the price of anarchy of two-stage machine scheduling games

Deshi Ye, Lin Chen, Guochuan Zhang

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

We consider a scheduling game, in which both the machines and the jobs are players. Machines are controlled by different selfish agents and attempt to maximize their workloads by choosing a scheduling policy among the given set of policies, while each job is controlled by a selfish agent that attempts to minimize its completion time by selecting a machine. Namely, this game was done in two-stage. In the first stage, every machine simultaneously chooses a policy from some given set of policies, and in the second stage, every job simultaneously chooses a machine. In this work, we use the price of anarchy to measure the efficiency of such equilibria where each machine is allowed to use one of the at most two policies. We provide nearly tight bounds for every combination of two deterministic scheduling policies with respect to two social objectives: minimizing the maximum job completion, and maximizing the minimum machine completion time.

Original languageEnglish
JournalJournal of Combinatorial Optimization
DOIs
StateAccepted/In press - 2019

Keywords

  • Coordination mechanisms
  • Price of anarchy
  • Scheduling

Fingerprint Dive into the research topics of 'On the price of anarchy of two-stage machine scheduling games'. Together they form a unique fingerprint.

Cite this