{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T16:49:09Z","timestamp":1761929349161,"version":"3.41.0"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2007,8,1]],"date-time":"2007-08-01T00:00:00Z","timestamp":1185926400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2007,8]]},"abstract":"<jats:p>\n            We study the number of steps required to reach a pure Nash equilibrium in a load balancing scenario where each job behaves selfishly and attempts to migrate to a machine which will minimize its cost. We consider a variety of load balancing models, including identical, restricted, related, and unrelated machines. Our results have a crucial dependence on the weights assigned to jobs. We consider arbitrary weights, integer weights,\n            <jats:italic>k<\/jats:italic>\n            distinct weights, and identical (unit) weights. We look both at an arbitrary schedule (where the only restriction is that a job migrates to a machine which lowers its cost) and specific efficient schedulers (e.g., allowing the largest weight job to move first). A by-product of our results is establishing a connection between various scheduling models and the game-theoretic notion of potential games. We show that load balancing in unrelated machines is a generalized ordinal potential game, load balancing in related machines is a weighted potential game, and load balancing in related machines and unit weight jobs is an exact potential game.\n          <\/jats:p>","DOI":"10.1145\/1273340.1273348","type":"journal-article","created":{"date-parts":[[2007,9,14]],"date-time":"2007-09-14T13:44:55Z","timestamp":1189777495000},"page":"32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":88,"title":["Convergence time to Nash equilibrium in load balancing"],"prefix":"10.1145","volume":"3","author":[{"given":"Eyal","family":"Even-Dar","sequence":"first","affiliation":[{"name":"University of Pennsylvania, Philadelphia, PA"}]},{"given":"Alex","family":"Kesselman","sequence":"additional","affiliation":[{"name":"Max-Planck Institut fur Informatik, Saarbrucken, Germany"}]},{"given":"Yishay","family":"Mansour","sequence":"additional","affiliation":[{"name":"Tel-Aviv University, Tel-Aviv, Israel"}]}],"member":"320","published-online":{"date-parts":[[2007,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.2001.1754"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060599"},{"key":"e_1_2_1_3_1","first-page":"178","article-title":"On-Line load balancing. Online Algorithms In: The State of the Art. Springer","volume":"8","author":"Azar Y.","year":"1998","unstructured":"Azar , Y. 1998 . On-Line load balancing. Online Algorithms In: The State of the Art. Springer , Chap. 8 , 178 -- 195 . Azar, Y. 1998. On-Line load balancing. Online Algorithms In: The State of the Art. Springer, Chap. 8, 178--195.","journal-title":"Chap."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1016312521369"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(96)00036-4"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(95)00030-U"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509952"},{"volume-title":"Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 413--420","author":"Czumaj A.","key":"e_1_2_1_8_1","unstructured":"Czumaj , A. , and Vocking , B . 2002. Tight bounds on worse case equilibria . In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 413--420 . Czumaj, A., and Vocking, B. 2002. Tight bounds on worse case equilibria. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 413--420."},{"volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 772--781","author":"Even-Dar E.","key":"e_1_2_1_9_1","unstructured":"Even-Dar , E. , and Mansour , Y . 2005. Fast convergence of selfish rerouting . In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 772--781 . Even-Dar, E., and Mansour, Y. 2005. Fast convergence of selfish rerouting. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 772--781."},{"volume-title":"Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP). 514--526","author":"Feldmann R.","key":"e_1_2_1_10_1","unstructured":"Feldmann , R. , Gairing , M. , Lcking , T. , and B. Monien , M. R. 2003. Nashification and the coordination ratio for a selfish routing game . In Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP). 514--526 . Feldmann, R., Gairing, M., Lcking, T., and B. Monien, M. R. 2003. Nashification and the coordination ratio for a selfish routing game. In Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP). 514--526."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01930985"},{"volume-title":"Proceedings of the 31th International Colloquium on Automata, Languages and Programming (ICALP). 593--605","author":"Fotakis D.","key":"e_1_2_1_12_1","unstructured":"Fotakis , D. , Kontogiannis , S. , and Spirakis , P . 2004. Selfish unsplittable flows . In Proceedings of the 31th International Colloquium on Automata, Languages and Programming (ICALP). 593--605 . Fotakis, D., Kontogiannis, S., and Spirakis, P. 2004. Selfish unsplittable flows. In Proceedings of the 31th International Colloquium on Automata, Languages and Programming (ICALP). 593--605."},{"volume-title":"Proceedings of the 29th International Colloquium on Automatia, Languages and Programming (ICALP). 123--134","author":"Fotakis D.","key":"e_1_2_1_13_1","unstructured":"Fotakis , D. , Kontogiannis , S. , Koutsoupias , E. , Mavronicolas , M. , and Spirakis , P . 2002. The structure and complexity of Nash equilibria for a selfish routing game . In Proceedings of the 29th International Colloquium on Automatia, Languages and Programming (ICALP). 123--134 . Fotakis, D., Kontogiannis, S., Koutsoupias, E., Mavronicolas, M., and Spirakis, P. 2002. The structure and complexity of Nash equilibria for a selfish routing game. In Proceedings of the 29th International Colloquium on Automatia, Languages and Programming (ICALP). 123--134."},{"key":"e_1_2_1_14_1","unstructured":"Fudenberg D. and Levine D. 1998. The Theory of Learning in Games. MIT Press Cambridge MA.  Fudenberg D. and Levine D. 1998. The Theory of Learning in Games. MIT Press Cambridge MA."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1011767.1011787"},{"key":"e_1_2_1_16_1","unstructured":"Hopcroft J. and Ullman J. 1979. Introduction to Automata Theory Languages and Computation. Addison-Wesley.   Hopcroft J. and Ullman J. 1979. Introduction to Automata Theory Languages and Computation. Addison-Wesley."},{"volume-title":"Proceedings of the 18th Conference on Uncertainty in Artificial Intelligence (UAI).","author":"Kearns M.","key":"e_1_2_1_17_1","unstructured":"Kearns , M. , and Mansour , Y . 2002. Efficient nash computation in large population games with bounded influence . In Proceedings of the 18th Conference on Uncertainty in Artificial Intelligence (UAI). Kearns, M., and Mansour, Y. 2002. Efficient nash computation in large population games with bounded influence. In Proceedings of the 18th Conference on Uncertainty in Artificial Intelligence (UAI)."},{"volume-title":"Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science (STACS). 404--413","author":"Koutsoupias E.","key":"e_1_2_1_18_1","unstructured":"Koutsoupias , E. , and Papadimitriou , C. H . 1999. Worst-Case equilibria . In Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science (STACS). 404--413 . Koutsoupias, E., and Papadimitriou, C. H. 1999. Worst-Case equilibria. In Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science (STACS). 404--413."},{"volume-title":"Proceedings of the Conference on Advances in Neural Information Processing Systems (NIPS).","author":"Littman M.","key":"e_1_2_1_19_1","unstructured":"Littman , M. , Kearns , M. , and Singh , S . 2002. An efficient exact algorithm for singly connected graphical games . In Proceedings of the Conference on Advances in Neural Information Processing Systems (NIPS). Littman, M., Kearns, M., and Singh, S. 2002. An efficient exact algorithm for singly connected graphical games. In Proceedings of the Conference on Advances in Neural Information Processing Systems (NIPS)."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380846"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1996.0027"},{"volume-title":"Proceedings of the 7th International Workshop on Approximation Algorithms for Combinatorial Optimization.","author":"Mirrokni V.","key":"e_1_2_1_22_1","unstructured":"Mirrokni , V. , and Vetta , A . 2004. Convergence issues in competitive games . In Proceedings of the 7th International Workshop on Approximation Algorithms for Combinatorial Optimization. Mirrokni, V., and Vetta, A. 2004. Convergence issues in competitive games. In Proceedings of the 7th International Workshop on Approximation Algorithms for Combinatorial Optimization."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1996.0044"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.2307\/1969529"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.251910"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380883"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01737559"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/506147.506153"},{"volume-title":"Proceedings of the Conference on Integer Programming and Combinatorial Optimization (IPCO). 370--382","author":"Schuurman P.","key":"e_1_2_1_29_1","unstructured":"Schuurman , P. , and Vredeveld , T . 2001. Performance guarantees of local search for multiprocessor scheduling . In Proceedings of the Conference on Integer Programming and Combinatorial Optimization (IPCO). 370--382 . Schuurman, P., and Vredeveld, T. 2001. Performance guarantees of local search for multiprocessor scheduling. In Proceedings of the Conference on Integer Programming and Combinatorial Optimization (IPCO). 370--382."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1273340.1273348","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1273340.1273348","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:57:55Z","timestamp":1750258675000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1273340.1273348"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,8]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2007,8]]}},"alternative-id":["10.1145\/1273340.1273348"],"URL":"https:\/\/doi.org\/10.1145\/1273340.1273348","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2007,8]]},"assertion":[{"value":"2007-08-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}