Optimal Coordination Mechanisms for Unrelated Machine Scheduling

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.