The price of anarchy in two-stage scheduling games

Deshi Ye, Lin Chen, Guochuan Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

We consider a scheduling game, in which both the machines and the jobs are players. A job attempts to minimize its completion time by switching machines, while each machine would like to maximize its workload by choosing a scheduling policy from the given set of policies. We consider a two-stage game. 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 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
Title of host publicationCombinatorial Optimization and Applications - 11th International Conference, COCOA 2017, Proceedings
EditorsXiaofeng Gao, Hongwei Du, Meng Han
PublisherSpringer-Verlag
Pages214-225
Number of pages12
ISBN (Print)9783319711461
DOIs
StatePublished - 2017
Event11th International Conference on Combinatorial Optimization and Applications, COCOA 2017 - Shanghai, China
Duration: Dec 16 2017Dec 18 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10628 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference11th International Conference on Combinatorial Optimization and Applications, COCOA 2017
CountryChina
CityShanghai
Period12/16/1712/18/17

Keywords

  • Coordination mechanisms
  • Price of anarchy
  • Scheduling

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

Cite this