The price of anarchy for utilitarian scheduling games on related machines

Ruben Pieter Hoeksma*, Marc Uetz

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)
2 Downloads (Pure)

Abstract

We present bounds on the efficiency of Nash equilibria in a scheduling game where jobs are players who choose a machine out of a set of machines to be processed on. Machines may have different speeds, and sequence the jobs in shortest processing time first order. When players selfishly choose a machine to minimize their own completion time, we analyze the price of anarchy for the sum of the completion times of the jobs. We show that it is bounded from below by e∕(e−1)≈1.58 and from above by 2.

Original languageEnglish
Pages (from-to)29-39
Number of pages11
JournalDiscrete optimization
Volume31
DOIs
Publication statusPublished - 1 Feb 2019

Keywords

  • Price of anarchy
  • Related machines
  • Scheduling
  • Utilitarian

Fingerprint Dive into the research topics of 'The price of anarchy for utilitarian scheduling games on related machines'. Together they form a unique fingerprint.

Cite this