Help Privacy Policy Disclaimer
  Advanced SearchBrowse




Journal Article

Coordinating Oligopolistic Players in Unrelated Machine Scheduling


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


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

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available

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: https://hdl.handle.net/11858/00-001M-0000-0025-7584-A
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.