{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,10]],"date-time":"2025-09-10T21:33:38Z","timestamp":1757540018721,"version":"3.41.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2014,8,11]],"date-time":"2014-08-11T00:00:00Z","timestamp":1407715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Cluster of Excellence MMCI at Saarland University"},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["Ho 3831\/3-1"],"award-info":[{"award-number":["Ho 3831\/3-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","award":["CNS-0435060, CCR-0325197, and EN-CS-0329609"],"award-info":[{"award-number":["CNS-0435060, CCR-0325197, and EN-CS-0329609"]}],"id":[{"id":"10.13039\/100000144","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-0435060, CCR-0325197, and EN-CS-0329609"],"award-info":[{"award-number":["CNS-0435060, CCR-0325197, and EN-CS-0329609"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2014,10,28]]},"abstract":"<jats:p>\n            We study distributed load balancing in networks with selfish agents. In the simplest model considered here, there are\n            <jats:italic>n<\/jats:italic>\n            identical machines represented by vertices in a network and\n            <jats:italic>m<\/jats:italic>\n            &gt;\n            <jats:italic>n<\/jats:italic>\n            selfish agents that unilaterally decide to move from one vertex to another if this improves their experienced load. We present several protocols for concurrent migration that satisfy desirable properties such as being based only on local information and computation and the absence of global coordination or cooperation of agents. Our main contribution is to show rapid convergence of the resulting migration process to states that satisfy different stability or balance criteria. In particular, the convergence time to a Nash equilibrium is only logarithmic in\n            <jats:italic>m<\/jats:italic>\n            and polynomial in\n            <jats:italic>n<\/jats:italic>\n            , where the polynomial depends on the graph structure. In addition, we show reduced convergence times to approximate Nash equilibria. Finally, we extend our results to networks of machines with different speeds or to agents that have different weights and show similar results for convergence to approximate and exact Nash equilibria.\n          <\/jats:p>","DOI":"10.1145\/2629671","type":"journal-article","created":{"date-parts":[[2014,8,12]],"date-time":"2014-08-12T13:53:48Z","timestamp":1407851628000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Distributed Selfish Load Balancing on Networks"],"prefix":"10.1145","volume":"11","author":[{"given":"Petra","family":"Berenbrink","sequence":"first","affiliation":[{"name":"Simon Fraser University, Burnaby, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Hoefer","sequence":"additional","affiliation":[{"name":"Max-Planck-Institute for Informatics and Saarland University, Saarbr\u00fccken, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Sauerwald","sequence":"additional","affiliation":[{"name":"University of Cambridge, Cambridge, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,8,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1582716.1582732"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0363012993249195"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1455248.1455249"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 19th Symposium on Discrete Algorithms (SODA\u201908)","author":"Awerbuch Baruch","year":"2008","unstructured":"Baruch Awerbuch , Yossi Azar , and Rohit Khandekar . 2008 . Fast load balancing via bounded best response . In Proceedings of the 19th Symposium on Discrete Algorithms (SODA\u201908) . 314--322. Baruch Awerbuch, Yossi Azar, and Rohit Khandekar. 2008. Fast load balancing via bounded best response. In Proceedings of the 19th Symposium on Discrete Algorithms (SODA\u201908). 314--322."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/060660345"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9482-1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2008.05.005"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133152"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.4330020403"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2009.05.004"},{"volume-title":"Spectral Graph Theory. Number 92 in CBMS Regional Conference Series in Mathematics","author":"Chung Fan","key":"e_1_2_1_11_1","unstructured":"Fan Chung . 1997. Spectral Graph Theory. Number 92 in CBMS Regional Conference Series in Mathematics . American Mathematical Society . Fan Chung. 1997. Spectral Graph Theory. Number 92 in CBMS Regional Conference Series in Mathematics. American Mathematical Society."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(89)90021-X"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704446475"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1273340.1273348"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 16th Symposium on Discrete Algorithms (SODA\u201905)","author":"Even-Dar Eyal","year":"2005","unstructured":"Eyal Even-Dar and Yishay Mansour . 2005 . Fast convergence of selfish rerouting . In Proceedings of the 16th Symposium on Discrete Algorithms (SODA\u201905) . 772--781. Eyal Even-Dar and Yishay Mansour. 2005. Fast convergence of selfish rerouting. In Proceedings of the 16th Symposium on Discrete Algorithms (SODA\u201905). 772--781."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/1759210.1759262"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.12.016"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/090746720"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.01.055"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-009-9198-2"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536433"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0075"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2542174.2542177"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536487"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-011-0129-5"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1329125.1329175"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/070680199"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002240000092"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/795664.796463"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01737559"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374428"},{"volume-title":"Algorithmic Game Theory, Noam Nisan, \u00c9va Tardos","author":"V\u00f6cking Berthold","key":"e_1_2_1_32_1","unstructured":"Berthold V\u00f6cking . 2007. Selfish load balancing . In Algorithmic Game Theory, Noam Nisan, \u00c9va Tardos , Tim Roughgarden, and Vijay Vazirani (Eds.). Cambridge University Press , Chapter 20. Berthold V\u00f6cking. 2007. Selfish load balancing. In Algorithmic Game Theory, Noam Nisan, \u00c9va Tardos, Tim Roughgarden, and Vijay Vazirani (Eds.). Cambridge University Press, Chapter 20."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629671","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2629671","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:13:30Z","timestamp":1750227210000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629671"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,8,11]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,10,28]]}},"alternative-id":["10.1145\/2629671"],"URL":"https:\/\/doi.org\/10.1145\/2629671","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2014,8,11]]},"assertion":[{"value":"2012-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-08-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}