The price of anarchy for utilitarian scheduling games on related machines

Ruben Pieter Hoeksma; Marc Uetz

doi:10.1016/j.disopt.2018.08.001

The price of anarchy for utilitarian scheduling games on related machines

Ruben Pieter Hoeksma^*, Marc Uetz

^*Corresponding author for this work

Discrete Mathematics and Mathematical Programming

Research output: Contribution to journal › Article › Academic › peer-review

8 Citations (Scopus)

168 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 language	English
Pages (from-to)	29-39
Number of pages	11
Journal	Discrete optimization
Volume	31
DOIs	https://doi.org/10.1016/j.disopt.2018.08.001
Publication status	Published - 1 Feb 2019

Keywords

Price of anarchy
Related machines
Scheduling
Utilitarian

Access to Document

10.1016/j.disopt.2018.08.001

ORL_HU_finalAccepted author version, 255 KBLicence: CC BY-NC-ND

Cite this

@article{63ab6160c4df4206885a1a9730efb2c0,

title = "The price of anarchy for utilitarian scheduling games on related machines",

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.",

keywords = "Price of anarchy, Related machines, Scheduling, Utilitarian",

author = "Hoeksma, {Ruben Pieter} and Marc Uetz",

year = "2019",

month = feb,

day = "1",

doi = "10.1016/j.disopt.2018.08.001",

language = "English",

volume = "31",

pages = "29--39",

journal = "Discrete optimization",

issn = "1572-5286",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - The price of anarchy for utilitarian scheduling games on related machines

AU - Hoeksma, Ruben Pieter

AU - Uetz, Marc

PY - 2019/2/1

Y1 - 2019/2/1

N2 - 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.

AB - 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.

KW - Price of anarchy

KW - Related machines

KW - Scheduling

KW - Utilitarian

UR - http://www.scopus.com/inward/record.url?scp=85052758405&partnerID=8YFLogxK

U2 - 10.1016/j.disopt.2018.08.001

DO - 10.1016/j.disopt.2018.08.001

M3 - Article

AN - SCOPUS:85052758405

SN - 1572-5286

VL - 31

SP - 29

EP - 39

JO - Discrete optimization

JF - Discrete optimization

ER -

The price of anarchy for utilitarian scheduling games on related machines

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this