{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,16]],"date-time":"2026-01-16T10:19:45Z","timestamp":1768558785105,"version":"3.49.0"},"reference-count":93,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2022,6,30]],"date-time":"2022-06-30T00:00:00Z","timestamp":1656547200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Italian MIUR PRIN 2017 Project ALGADIMAR \u201cAlgorithms, Games, and Digital Markets.\u201d"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2022,6,30]]},"abstract":"<jats:p>\n            In load-balancing problems there is a set of clients, each wishing to select a resource from a set of permissible ones to execute a certain task. Each resource has a latency function, which depends on its workload, and a client\u2019s cost is the completion time of her chosen resource. Two fundamental variants of load-balancing problems are\n            <jats:italic>selfish load balancing<\/jats:italic>\n            (a.k.a.\n            <jats:italic>load-balancing games<\/jats:italic>\n            ), where clients are non-cooperative selfish players aimed at minimizing their own cost solely, and\n            <jats:italic>online load balancing<\/jats:italic>\n            , where clients appear online and have to be irrevocably assigned to a resource without any knowledge about future requests. We revisit both problems under the objective of minimizing the\n            <jats:italic>Nash Social Welfare<\/jats:italic>\n            , i.e., the geometric mean of the clients\u2019 costs. To the best of our knowledge, despite being a celebrated welfare estimator in many social contexts, the Nash Social Welfare has not been considered so far as a benchmarking quality measure in load-balancing problems. We provide tight bounds on the price of anarchy of pure Nash equilibria and on the competitive ratio of the greedy algorithm under very general latency functions, including polynomial ones. For this particular class, we also prove that the greedy strategy is optimal, as it matches the performance of any possible online algorithm.\n          <\/jats:p>\n          <jats:p\/>","DOI":"10.1145\/3544978","type":"journal-article","created":{"date-parts":[[2022,8,4]],"date-time":"2022-08-04T11:58:50Z","timestamp":1659614330000},"page":"1-41","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Nash Social Welfare in Selfish and Online Load Balancing"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7848-4904","authenticated-orcid":false,"given":"Vittorio","family":"Bil\u00f2","sequence":"first","affiliation":[{"name":"University of Salento Lecce, Lecce, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0998-5649","authenticated-orcid":false,"given":"Gianpiero","family":"Monaco","sequence":"additional","affiliation":[{"name":"University of L\u2019Aquila, L\u2019Aquila, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9256-481X","authenticated-orcid":false,"given":"Luca","family":"Moscardelli","sequence":"additional","affiliation":[{"name":"University of Chieti-Pescara Pescara, Pescara, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7741-9342","authenticated-orcid":false,"given":"Cosimo","family":"Vinci","sequence":"additional","affiliation":[{"name":"University of Salerno and Gran Sasso Science Institute, L\u2019Aquila, Italy"}]}],"member":"320","published-online":{"date-parts":[[2022,10,7]]},"reference":[{"key":"e_1_3_4_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/1455248.1455249"},{"key":"e_1_3_4_3_2","doi-asserted-by":"publisher","DOI":"10.1137\/090748986"},{"key":"e_1_3_4_4_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797324874"},{"key":"e_1_3_4_5_2","article-title":"Greedy algorithms for fair division of mixed manna","volume":"1911","author":"Aleksandrov M.","year":"2019","unstructured":"M. Aleksandrov and T. Walsh. 2019. Greedy algorithms for fair division of mixed manna. CoRR abs\/1911.11005 (2019).","journal-title":"CoRR"},{"key":"e_1_3_4_6_2","doi-asserted-by":"publisher","DOI":"10.1137\/070680096"},{"key":"e_1_3_4_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/258128.258201"},{"key":"e_1_3_4_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060599"},{"key":"e_1_3_4_9_2","first-page":"383","volume-title":"Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS)","author":"Awerbuch B.","year":"1995","unstructured":"B. Awerbuch, A. Yossi, E. F. Grove, M.-Y. Kao, P. Krishnan, and J. S. Vitter. 1995. Load balancing in the L \\( {}_{\\mbox{p}} \\) norm. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS). 383\u2013391."},{"key":"e_1_3_4_10_2","first-page":"203","volume-title":"Proceedings of the 3rd Annual ACM\/SIGACT-SIAM Symposium on Discrete Algorithms (SODA)","author":"Azar Y.","year":"1992","unstructured":"Y. Azar, J. Naor, and R. Rom. 1992. The competitiveness of on-line assignments. In Proceedings of the 3rd Annual ACM\/SIGACT-SIAM Symposium on Discrete Algorithms (SODA). 203\u2013210."},{"key":"e_1_3_4_11_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1074"},{"key":"e_1_3_4_12_2","volume-title":"Studies in the Economics of Transportation","author":"Beckmann M. J.","year":"1956","unstructured":"M. J. Beckmann, C. B. McGuire, and C. B. Winsten. 1956. Studies in the Economics of Transportation. Yale University Press."},{"key":"e_1_3_4_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3340234"},{"key":"e_1_3_4_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-64946-3_18"},{"key":"e_1_3_4_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/2629666"},{"key":"e_1_3_4_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-017-9826-1"},{"key":"e_1_3_4_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-012-9411-6"},{"key":"e_1_3_4_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9417-x"},{"key":"e_1_3_4_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-010-9309-0"},{"key":"e_1_3_4_20_2","doi-asserted-by":"publisher","DOI":"10.3390\/a13100261"},{"key":"e_1_3_4_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2014.09.010"},{"key":"e_1_3_4_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-64946-3_23"},{"key":"e_1_3_4_23_2","first-page":"146:1\u2013146:14","volume-title":"Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP)","author":"Bil\u00f2 V.","year":"2018","unstructured":"V. Bil\u00f2, L. Moscardelli, and C. Vinci. 2018. Uniform mixed equilibria in network congestion games with link failures. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP). 146:1\u2013146:14."},{"key":"e_1_3_4_24_2","first-page":"17:1\u201317:14","volume-title":"Proceedings of the 25th Annual European Symposium on Algorithms, (ESA)","author":"Bil\u00f2 V.","year":"2017","unstructured":"V. Bil\u00f2 and C. Vinci. 2017. On the impact of singleton strategies in congestion games. In Proceedings of the 25th Annual European Symposium on Algorithms, (ESA). 17:1\u201317:14."},{"key":"e_1_3_4_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/3355946"},{"key":"e_1_3_4_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-018-9902-1"},{"key":"e_1_3_4_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-57980-7_5"},{"key":"e_1_3_4_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2019.10.012"},{"key":"e_1_3_4_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00355-018-1157-x"},{"key":"e_1_3_4_30_2","doi-asserted-by":"publisher","DOI":"10.5555\/290169"},{"key":"e_1_3_4_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/3033274.3085143"},{"key":"e_1_3_4_32_2","first-page":"972","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Caragiannis I.","year":"2008","unstructured":"I. Caragiannis. 2008. Better bounds for online load balancing on unrelated machines. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). 972\u2013981."},{"key":"e_1_3_4_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9650-6"},{"key":"e_1_3_4_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9427-8"},{"key":"e_1_3_4_35_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-71924-5_6"},{"key":"e_1_3_4_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/3328526.3329574"},{"issue":"1","key":"e_1_3_4_37_2","article-title":"Taxes for linear atomic congestion games","volume":"7","author":"Caragiannis I.","year":"2010","unstructured":"I. Caragiannis, C. Kaklamanis, and P. Kanellopoulos. 2010. Taxes for linear atomic congestion games. ACM Trans. Algor. 7, 1 (2010).","journal-title":"ACM Trans. Algor."},{"key":"e_1_3_4_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/2940716.2940726"},{"key":"e_1_3_4_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/1064009.1064015"},{"key":"e_1_3_4_40_2","volume-title":"Handbook of Scheduling: Algorithms, Models, and Performance Analysis","author":"Chekuri C.","year":"2004","unstructured":"C. Chekuri and S. Khanna. 2004. Approximation algorithms for minimizing average weighted completion time. In Handbook of Scheduling: Algorithms, Models, and Performance Analysis. Chapman & Hall\/CRC."},{"key":"e_1_3_4_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/2841229"},{"key":"e_1_3_4_42_2","doi-asserted-by":"publisher","DOI":"10.1137\/18M1207880"},{"key":"e_1_3_4_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060600"},{"key":"e_1_3_4_44_2","doi-asserted-by":"publisher","DOI":"10.5555\/2040572.2040586"},{"key":"e_1_3_4_45_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.02.033"},{"key":"e_1_3_4_46_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2013.03.011"},{"key":"e_1_3_4_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/3033274.3085109"},{"key":"e_1_3_4_48_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.09.010"},{"key":"e_1_3_4_49_2","doi-asserted-by":"publisher","DOI":"10.1137\/15M1053682"},{"key":"e_1_3_4_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/3328526.3329579"},{"issue":"1","key":"e_1_3_4_51_2","first-page":"4:1\u20134:17","article-title":"Tight bounds for worst-case equilibria","volume":"3","author":"Czumaj A.","year":"2007","unstructured":"A. Czumaj and B. V\u00f6cking. 2007. Tight bounds for worst-case equilibria. ACM Trans. Algor. 3, 1 (2007), 4:1\u20134:17.","journal-title":"ACM Trans. Algor."},{"key":"e_1_3_4_52_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53354-3_9"},{"key":"e_1_3_4_53_2","doi-asserted-by":"publisher","DOI":"10.1145\/1273340.1273348"},{"key":"e_1_3_4_54_2","doi-asserted-by":"publisher","DOI":"10.5555\/71777.71779"},{"key":"e_1_3_4_55_2","doi-asserted-by":"publisher","DOI":"10.5555\/1940179.1940198"},{"key":"e_1_3_4_56_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.09.035"},{"key":"e_1_3_4_57_2","doi-asserted-by":"publisher","DOI":"10.5555\/647910.740462"},{"key":"e_1_3_4_58_2","doi-asserted-by":"publisher","DOI":"10.1145\/5666.5673"},{"key":"e_1_3_4_59_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-008-9152-8"},{"key":"e_1_3_4_60_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10841-9_29"},{"key":"e_1_3_4_61_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.024"},{"key":"e_1_3_4_62_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626406002514"},{"key":"e_1_3_4_63_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77105-0_42"},{"key":"e_1_3_4_64_2","doi-asserted-by":"publisher","DOI":"10.1137\/0222026"},{"key":"e_1_3_4_65_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.150"},{"key":"e_1_3_4_66_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2016.1512"},{"key":"e_1_3_4_67_2","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1966.tb01709.x"},{"key":"e_1_3_4_68_2","doi-asserted-by":"publisher","DOI":"10.1145\/7531.7535"},{"key":"e_1_3_4_69_2","doi-asserted-by":"publisher","DOI":"10.1145\/321941.321951"},{"key":"e_1_3_4_70_2","first-page":"489","volume-title":"Proceedings of the 20th AAAI Conference on Artificial Intelligence (AAAI)","author":"Ieong S.","year":"2005","unstructured":"S. Ieong, R. McGrew, E. Nudelman, Y. Shoham, and Q. Sun. 2005. Fast and compact: A simple class of congestion games. In Proceedings of the 20th AAAI Conference on Artificial Intelligence (AAAI). 489\u2013494."},{"key":"e_1_3_4_71_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.12.032"},{"key":"e_1_3_4_72_2","doi-asserted-by":"publisher","DOI":"10.2307\/1914191"},{"key":"e_1_3_4_73_2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0019"},{"key":"e_1_3_4_74_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-30473-7_14"},{"key":"e_1_3_4_75_2","doi-asserted-by":"publisher","DOI":"10.5555\/1764891.1764944"},{"key":"e_1_3_4_76_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585745"},{"key":"e_1_3_4_77_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.06.045"},{"key":"e_1_3_4_78_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.20439"},{"key":"e_1_3_4_79_2","doi-asserted-by":"publisher","DOI":"10.1017\/CCOL0521360552"},{"key":"e_1_3_4_80_2","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/2954.001.0001"},{"key":"e_1_3_4_81_2","doi-asserted-by":"publisher","DOI":"10.2307\/1907266"},{"key":"e_1_3_4_82_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2014.09.010"},{"key":"e_1_3_4_83_2","volume-title":"The Economics of Welfare","author":"Pigou A. C.","year":"1938","unstructured":"A. C. Pigou. 1938. The Economics of Welfare. Macmillan and Co., London."},{"key":"e_1_3_4_84_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01737559"},{"key":"e_1_3_4_85_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00044-8"},{"key":"e_1_3_4_86_2","first-page":"980","volume-title":"Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Roughgarden T.","year":"2004","unstructured":"T. Roughgarden. 2004. The maximum latency of selfish routing. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 980\u2013981."},{"key":"e_1_3_4_87_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701397059"},{"key":"e_1_3_4_88_2","doi-asserted-by":"publisher","DOI":"10.1145\/506147.506153"},{"key":"e_1_3_4_89_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2003.06.004"},{"key":"e_1_3_4_90_2","volume-title":"Improved Bounds for the On-line Scheduling Problem","author":"III J. F. Rudin","year":"2001","unstructured":"J. F. Rudin III. 2001. Improved Bounds for the On-line Scheduling Problem. The University of Texas at Dallas."},{"key":"e_1_3_4_91_2","doi-asserted-by":"publisher","DOI":"10.5555\/3118733.3118816"},{"key":"e_1_3_4_92_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2018.06.038"},{"key":"e_1_3_4_93_2","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1017\/CBO9780511800481.022","volume-title":"Algorithmic Game Theory","author":"V\u00f6cking B.","year":"2007","unstructured":"B. V\u00f6cking. 2007. Selfish load balancing. In Algorithmic Game Theory. Cambridge, 517\u2013542."},{"issue":"36","key":"e_1_3_4_94_2","first-page":"352","article-title":"Some theoretical aspects of road traffic research","volume":"1","author":"Wardrop J. G.","year":"1952","unstructured":"J. G. Wardrop. 1952. Some theoretical aspects of road traffic research. Proc. Instit. Civil Eng. Part II 1, 36 (1952), 352\u2013362.","journal-title":"Proc. Instit. Civil Eng. Part II"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3544978","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3544978","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:00:01Z","timestamp":1750186801000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3544978"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,30]]},"references-count":93,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,6,30]]}},"alternative-id":["10.1145\/3544978"],"URL":"https:\/\/doi.org\/10.1145\/3544978","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"value":"2167-8375","type":"print"},{"value":"2167-8383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,6,30]]},"assertion":[{"value":"2021-01-31","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-06-21","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-10-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}