Optimal Coordination Mechanisms for Unrelated Machine Scheduling

Yossi Azar (), Lisa Fleischer (), Kamal Jain (), Vahab Mirrokni () and Zoya Svitkina ()
Additional contact information
Yossi Azar: School of Computer Science, Tel-Aviv University, Tel-Aviv 69978, Israel
Lisa Fleischer: Department of Computer Science, Dartmouth, Hanover, New Hampshire 03755
Kamal Jain: Ebay Research, Bellevue, Washington 98004
Vahab Mirrokni: Google Research, New York, New York 10011
Zoya Svitkina: Google, Mountain View, California 94043

Operations Research, 2015, vol. 63, issue 3, 489-500

Abstract: We investigate the influence of different algorithmic choices on the approximation ratio in selfish scheduling. Our goal is to design local policies that minimize the inefficiency of resulting equilibria. In particular, we design optimal coordination mechanisms for unrelated machine scheduling, and improve the known approximation ratio from Θ( m ) to Θ(log m ), where m is the number of machines.A local policy for each machine orders the set of jobs assigned to it only based on parameters of those jobs. A strongly local policy only uses the processing time of jobs on the same machine. We prove that the approximation ratio of any set of strongly local ordering policies in equilibria is at least Ω( m ). In particular, it implies that the approximation ratio of a greedy shortest-first algorithm for machine scheduling is at least Ω( m ). This closes the gap between the known lower and upper bounds for this problem and answers an open question raised by Ibarra and Kim (1977) [Ibarra OH, Kim CE (1977) Heuristic algorithms for scheduling independent tasks on nonidentical processors. J. ACM 24(2):280–289.], and Davis and Jaffe (1981) [Davis E, Jaffe JM (1981) Algorithms for scheduling tasks on unrelated processors. J. ACM 28(4):721–736.]. We then design a local ordering policy with the approximation ratio of Θ(log m ) in equilibria, and prove that this policy is optimal among all local ordering policies. This policy orders the jobs in the nondecreasing order of their inefficiency, i.e., the ratio between the processing time on that machine over the minimum processing time. Finally, we show that best responses of players for the inefficiency-based policy may not converge to a pure Nash equilibrium, and present a Θ(log 2 m ) policy for which we can prove fast convergence of best responses to pure Nash equilibria.

Keywords: analysis of algorithms; approximations/heuristic; production/scheduling (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2015.1363 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:63:y:2015:i:3:p:489-500

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().