Inefficiency of the Nash equilibrium for selfish machine covering on two hierarchical uniform machines

Yong Wu, Edwin Tai Chiu Cheng, Min Ji

Research output: Journal article publicationJournal articleAcademic researchpeer-review

1 Citation (Scopus)

Abstract

Abstract This paper studies the selfish scheduling game on two hierarchical uniform machines where the jobs are correspondingly classified into two hierarchical classes. The cost of a job is defined as the completion time of the machine to which it is assigned. Each selfish job is interested in minimizing its own cost, while the game seeks to meet the social objective of maximizing the machine cover. We obtain the (strong) price of anarchy and the (strong) price of stability as functions of the ratio between the speeds of the two machines s. We show that all the derived bounds are tight for any value of s, thus completely solving the problem of measuring the inefficiency of the Nash equilibrium on two hierarchical uniform machines.
Original languageEnglish
Article number5290
Pages (from-to)838-844
Number of pages7
JournalInformation Processing Letters
Volume115
Issue number11
DOIs
Publication statusPublished - 1 Jul 2015

Keywords

  • Hierarchy
  • Nash equilibrium
  • Price of anarchy
  • Price of stability
  • Scheduling

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Cite this