de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Journal Article

Coordinating Oligopolistic Players in Unrelated Machine Scheduling

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons43960

Abed,  Fidaa
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44648

Huang,  Chien-Chung
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

Abed, F., & Huang, C.-C. (2015). Coordinating Oligopolistic Players in Unrelated Machine Scheduling. Theoretical Computer Science, 570, 40-54. doi:10.1016/j.tcs.2014.12.022.


Cite as: http://hdl.handle.net/11858/00-001M-0000-0025-7584-A
Abstract
We consider the following machine scheduling game. Jobs, controlled by selfish players, are to be assigned to unrelated machines. A player cares only about the finishing time of his job(s), while disregarding the welfare of other players. The outcome of such games is measured by the makespan. Our goal is to design coordination mechanisms to schedule the jobs so as to minimize the price of anarchy. We introduce oligopolistic players. Each such player controls a set of jobs, with the aim of minimizing the sum of the completion times of his jobs. Our model of oligopolistic players is a natural generalization of the conventional model, where each player controls only a single job. In our setting, previous mechanisms designed for players with single jobs are inadequate, e.g., having large price of anarchy, or not guaranteeing pure Nash equilibria. To meet this challenge, we design three mechanisms that are adapted/generalized from Caragiannis' ACOORD. All our mechanisms induce pure Nash equilibria while guaranteeing relatively small price of anarchy. (C) 2015 Elsevier B.V. All rights reserved.