(Almost) optimal coordination mechanisms for unrelated machine scheduling

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 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 [16], and Davis and Jaffe [10]. 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 non-decreasing 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² m) policy for which we can prove fast convergence of best responses to pure Nash equilibria.

REFERENCES

• 1: James Aspnes , Yossi Azar , Amos Fiat , Serge Plotkin , Orli Waarts, On-line routing of virtual circuits with applications to load balancing and machine scheduling, Journal of the ACM (JACM), v.44 n.3, p.486-504, May 1997 [doi>10.1145/258128.258201]
• 2: B. Awerbuch, Y. Azar, Y. Richter, and Dekel Tsur. Tradeoffs in worst-case equilibria. In WAOA, 2003.
• 3: Yossi Azar , Joseph Seffi Naor , Raphael Rom, The competitiveness of on-line assignments, Journal of Algorithms, v.18 n.2, p.221-237, March 1995 [doi>10.1006/jagm.1995.1008]
• 4: A. Bagchi. Stackelberg differential games in economic models. Springer-Verlag, 1984.
• 5: M. Beckman, C. B. McGuire, and C. B. Winsten. Studies in the Economics of Transportation. Yale University Press, 1956.
• 6: Allan Borodin , Morten N. Nielsen , Charles Rackoff, (Incremental) priority algorithms, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.752-761, January 06-08, 2002, San Francisco, California
• 7: G. Christodoulou, E. Koutsoupias, and A. Nanavati. Coordination mechanisms. In ICALP, pages 345--357, Turku, Finland, 12--16 July 2004.
• 8: Richard Cole , Yevgeniy Dodis , Tim Roughgarden, How much can taxes help selfish routing?, Proceedings of the 4th ACM conference on Electronic commerce, p.98-107, June 09-12, 2003, San Diego, CA, USA [doi>10.1145/779928.779941]
• 9: Artur Czumaj , Berthold Vöcking, Tight bounds for worst-case equilibria, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.413-420, January 06-08, 2002, San Francisco, California
• 10: Ernest Davis , Jeffrey M. Jaffe, Algorithms for Scheduling Tasks on Unrelated Processors, Journal of the ACM (JACM), v.28 n.4, p.721-736, Oct. 1981 [doi>10.1145/322276.322284]
• 11: E. Even-dar, A. Kesselman, and Y. Mansour. Convergence time to nash equilibria. In ICALP, pages 502--513, 2003.
• 12: G. Finn and E. Horowitz. A linear time approximation algorithm for multiprocessor scheduling. BIT, 19:312--320, 1979.
• 13: Lisa Fleischer , Kamal Jain , Mohammad Mahdian, Tolls for Heterogeneous Selfish Users in Multicommodity Networks and Generalized Congestion Games, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.277-285, October 17-19, 2004 [doi>10.1109/FOCS.2004.69]
• 14: Martin Gairing , Thomas Lücking , Marios Mavronicolas , Burkhard Monien, Computing Nash equilibria for scheduling on restricted parallel links, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007446]
• 15: Michel Goemans , Vahab Mirrokni , Adrian Vetta, Sink Equilibria and Convergence, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.142-154, October 23-25, 2005 [doi>10.1109/SFCS.2005.68]
• 16: Oscar H. Ibarra , Chul E. Kim, Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical Processors, Journal of the ACM (JACM), v.24 n.2, p.280-289, April 1977 [doi>10.1145/322003.322011]
• 17: N. Immorlica, L. Li, V. Mirrokni, and A. Schulz. Coordination mechanisms for selfish scheduling. In Workshop of Internet and Economics, 2005.
• 18: Yannis A. Korilis , Aurel A. Lazar , Ariel Orda, Achieving network optima using Stackelberg routing strategies, IEEE/ACM Transactions on Networking (TON), v.5 n.1, p.161-173, Feb. 1997 [doi>10.1109/90.554730]
• 19: E. Koutsoupias and C. Papadimitriou. Worst-case equilibria. In STACS, pages 404--413, 1999.
• 20: J. K. Lenstra , D. B. Shmoys , É. Tardos, Approximation algorithms for scheduling unrelated parallel machines, Mathematical Programming: Series A and B, v.46 n.3, p.259-271, January 1990 [doi>10.1007/BF01585745]
• 21: V. S. Mirrokni and A. Vetta. Convergence issues in competitive games. In APPROX, pages 183--194, 2004.
• 22: Tim Roughgarden, Stackelberg scheduling strategies, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.104-113, July 2001, Hersonissos, Greece [doi>10.1145/380752.380783]
• 23: S. Sahni and Y. Cho. Bounds for list schedules on uniform processors. Siam J. of Computing, 9:91--103, 1980.
• 24: Petra Schuurman , Tjark Vredeveld, Performance Guarantees of Local Search for Multiprocessor Scheduling, Proceedings of the 8th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.370-382, June 13-15, 2001
• 25: H. von Stackelberg. Marktform und Gleichgewicht. Springer-Verlag, 1934. English translation entitled The Theory of the Market Economy.
• 26: T. Vredeveld. Combinatorial approximation algorithms. Guaranteed versus experimental performance. 2002. Ph.D. thesis.
• 27: Wikipedia. http://en.wikipedia.org/wiki/ Independence_of_irrelevant_alternatives.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
        G.1.10 Applications
      G.1.2 Approximation

General Terms:
Algorithms, Design, Theory