Efficient coordination mechanisms for unrelated machine scheduling

ABSTRACT

We present three new coordination mechanisms for scheduling n selfish jobs on m unrelated machines. A coordination mechanism aims to mitigate the impact of selfishness of jobs on the efficiency of schedules by defining a local scheduling policy on each machine. The scheduling policies induce a game among the jobs and each job prefers to be scheduled on a machine so that its completion time is minimum given the assignments of the other jobs. We consider the maximum completion time among all jobs as the measure of the efficiency of schedules. The approximation ratio of a coordination mechanism quantifies the efficiency of pure Nash equilibria (price of anarchy) of the induced game. Our mechanisms are deterministic, local, and preemptive in the sense that the scheduling policy does not necessarily process the jobs in an uninterrupted way and may introduce some idle time. Our first coordination mechanism has approximation ratio O(log m) and always guarantees that the induced game has pure Nash equilibria to which the system converges in at most n rounds. This result improves a recent bound of O(log² m) due to Azar, Jain, and Mirrokni and, similarly to their mechanism, our mechanism uses a global ordering of the jobs according to their distinct IDs. Next we study the intriguing scenario where jobs are anonymous, i.e., they have no IDs. In this case, coordination mechanisms can only distinguish between jobs that have different load characteristics. Our second mechanism handles anonymous jobs and has approximation ratio O (log m/log log m) although the game induced is not a potential game and, hence, the existence of pure Nash equilibria is not guaranteed by potential function arguments. However, it provides evidence that the known lower bounds for non-preemptive coordination mechanisms could be beaten using preemptive scheduling policies. Our third coordination mechanism also handles anonymous jobs and has a nice "cost-revealing" potential function. Besides in proving the existence of equilibria, we use this potential function in order to upper-bound the price of stability of the induced game by O(log m), the price of anarchy by O(log² m), and the convergence time to O(log² m)-approximate assignments by a polynomial number of best-response moves. Our third coordination mechanism is the first that handles anonymous jobs and simultaneously guarantees that the induced game is a potential game and has bounded price of anarchy.

REFERENCES

• 1: Heiner Ackermann , Heiko Roglin , Berthold Vocking, On the Impact of Combinatorial Structure on Congestion Games, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.613-622, October 21-24, 2006 [doi>10.1109/FOCS.2006.55]
• 2: S. Aland, D. Dumrauf, M. Gairing, B. Monien, and F. Schoppmann. Exact price of anarchy for polynomial congestion games. 23rd STACS, LNCS 3884, pp. 218--229, 2006.
• 3: Elliot Anshelevich , Anirban Dasgupta , Jon Kleinberg , Eva Tardos , Tom Wexler , Tim Roughgarden, The Price of Stability for Network Design with Fair Cost Allocation, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.295-304, October 17-19, 2004 [doi>10.1109/FOCS.2004.68]
• 4: 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]
• 5: Baruch Awerbuch , Yossi Azar , Amir Epstein, Large the price of routing unsplittable flow, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060599]
• 6: Baruch Awerbuch , Yossi Azar , Amir Epstein , Vahab Seyed Mirrokni , Alexander Skopalik, Fast convergence to nearly optimal solutions in potential games, Proceedings of the 9th ACM conference on Electronic commerce, July 08-12, 2008, Chicago, Il, USA [doi>10.1145/1386790.1386832]
• 7: B. Awerbuch , Y. Azar , E. F. Grove , Ming-Yang Kao , P. Krishnan , J. S. Vitter, Load balancing in the L/sub p/ norm, Proceedings of the 36th Annual Symposium on Foundations of Computer Science, p.383, October 23-25, 1995
• 8: Yossi Azar , Kamal Jain , Vahab Mirrokni, (Almost) optimal coordination mechanisms for unrelated machine scheduling, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.323-332, January 20-22, 2008, San Francisco, California
• 9: 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]
• 10: Ioannis Caragiannis, Better bounds for online load balancing on unrelated machines, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.972-981, January 20-22, 2008, San Francisco, California
• 11: Ioannis Caragiannis , Christos Kaklamanis , Panagiotis Kanellopoulos, Taxes for linear atomic congestion games, Proceedings of the 14th conference on Annual European Symposium, p.184-195, September 11-13, 2006, Zurich, Switzerland [doi>10.1007/11841036_19]
• 12: Ho-Lin Chen , Tim Roughgarden , Gregory Valiant, Designing networks with good equilibria, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.854-863, January 20-22, 2008, San Francisco, California
• 13: George Christodoulou , Elias Koutsoupias, The price of anarchy of finite congestion games, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060600]
• 14: G. Christodoulou, E. Koutsoupias, and A. Nanavati. Coordination mechanisms. 31st ICALP, LNCS 3142, pp. 345--357, 2004.
• 15: G. Christodoulou, V. S. Mirrokni, and A. Sidiropoulos. Convergence and approximation in potential games. 23rd STACS, LNCS 3884, pp. 349--360, 2006.
• 16: Richard Cole , Yevgeniy Dodis , Tim Roughgarden, How much can taxes help selfish routing?, Journal of Computer and System Sciences, v.72 n.3, p.444-467, May 2006 [doi>10.1016/j.jcss.2005.09.010]
• 17: E. Even-Dar, A. Kesselman, and Y. Mansour. Convergence time to Nash equilibria. 30th ICALP, LNCS 2719, pp. 502--513, 2003.
• 18: Alex Fabrikant , Christos Papadimitriou , Kunal Talwar, The complexity of pure Nash equilibria, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007445]
• 19: Angelo Fanelli , Michele Flammini , Luca Moscardelli, The Speed of Convergence in Congestion Games under Best-Response Dynamics, Proceedings of the 35th international colloquium on Automata, Languages and Programming, Part I, July 07-11, 2008, Reykjavik, Iceland [doi>10.1007/978-3-540-70575-8_65]
• 20: 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]
• 21: D. Fotakis, S. Kontogiannis, and P. Spirakis. Selfish unsplittable flows. Theoretical Computer Science, 340(3): 514--538, 2005.
• 22: 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]
• 23: N. Immorlica, L. Li, V. S. Mirrokni, and A. Schulz. Coordination mechanisms for selfish scheduling. 1st WINE, LNCS 3828, pp. 55--69, 2005.
• 24: David S. Johnson , Christos H. Papadimtriou , Mihalis Yannakakis, How easy is local search?, Journal of Computer and System Sciences, v.37 n.1, p.79-100, August 1988 [doi>10.1016/0022-0000(88)90046-3]
• 25: A.C. Kaporis , P.G. Spirakis, The price of optimum in Stackelberg games on arbitrary single commodity networks and latency functions, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA [doi>10.1145/1148109.1148113]
• 26: George Karakostas , Stavros G. Kolliopoulos, Edge Pricing of Multicommodity Networks for Heterogeneous Selfish Users, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.268-276, October 17-19, 2004 [doi>10.1109/FOCS.2004.26]
• 27: Y. A. Korilis, A. A. Lazar, and A. Orda. Architecting noncooperative networks. IEEE Journal on Selected Areas in Communications, 13(7): 1241--1251, 1995.
• 28: 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]
• 29: E. Koutsoupias and C. Papadimitriou. Worst-case equilibria. 16th STACS, LNCS 1563, pp. 404--413, 1999.
• 30: V. S. Anil Kumar , Madhav V. Marathe, Improved Results for Stackelberg Scheduling Strategies, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.776-787, July 08-13, 2002
• 31: 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, February 1990 [doi>10.1007/BF01585745]
• 32: I. Milchtaich. Congestion games with player-specific payoff functions. Games and Economic Behavior, 13: 111--124, 1996.
• 33: V. S. Mirrokni and A. Vetta. Convergence issues in competitive games. APPROX-RANDOM, LNCS 3122, pp. 183--194, 2004.
• 34: D. Monderer and L. S. Shapley. Potential games. Games and Economic Behavior, 14: 124--143, 1996.
• 35: Noam Nisan , Tim Roughgarden , Eva Tardos , Vijay V. Vazirani, Algorithmic Game Theory, Cambridge University Press, New York, NY, 2007
• 36: Christos Papadimitriou, Algorithms, games, and the internet, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.749-753, July 2001, Hersonissos, Greece [doi>10.1145/380752.380883]
• 37: R. Rosenthal. A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory, 2: 65--67, 1973.
• 38: Tim Roughgarden, Stackelberg Scheduling Strategies, SIAM Journal on Computing, v.33 n.2, p.332-350, 2004 [doi>10.1137/S0097539701397059]
• 39: Tim Roughgarden, On the severity of Braess's paradox: designing networks for selfish users is hard, Journal of Computer and System Sciences, v.72 n.5, p.922-953, August 2006 [doi>10.1016/j.jcss.2005.05.009]
• 40: T. Roughgarden. Routing games. In {35}, Chapter 18, pp. 461--486, 2007.
• 41: 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
• 42: Alexander Skopalik , Berthold Vöcking, Inapproximability of pure nash equilibria, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374428]
• 43: Subhash Suri , Csaba D. Toth , Yunhong Zhou, Selfish Load Balancing and Atomic Congestion Games, Algorithmica, v.47 n.1, p.79-96, January 2007 [doi>10.1007/s00453-006-1211-4]
• 44: Chaitanya Swamy, The effectiveness of Stackelberg strategies and tolls for network congestion games, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.1133-1142, January 07-09, 2007, New Orleans, Louisiana
• 45: B. Vöcking. Selfish load balancing. In {35}, Chapter 20, pp. 517--542, 2007.

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:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms