Optimal Coordination Mechanisms for Unrelated Machine Scheduling

• 成果类型: Article
• 署名作者: Azar, Yossi; Fleischer, Lisa; Jain, Kamal; Mirrokni, Vahab; Svitkina, Zoya
• 署名单位: Tel Aviv University; Dartmouth College; Alphabet Inc.; Google Incorporated; Alphabet Inc.; Google Incorporated
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2015.1363
• 发表日期: 2015
• 页码: 489-500
• 关键词: worst-case equilibria; algorithms; CONVERGENCE; processors; tasks; time

摘要

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 Theta(m) to Theta(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 Omega(m). In particular, it implies that the approximation ratio of a greedy shortest-first algorithm for machine scheduling is at least Omega(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 Theta(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 Theta(log(2) m) policy for which we can prove fast convergence of best responses to pure Nash equilibria.