Abstract
In load balancing problems there is a set of clients, each wishing to select a resource from a set of permissible ones, in order to execute a certain task. Each resource has a latency function, which depends on its workload, and a client’s cost is the completion time of her chosen resource. Two fundamental variants of load balancing problems are selfish load balancing (aka. load balancing games), where clients are non-cooperative selfish players aimed at minimizing their own cost solely, and online load balancing, where clients appear online and have to be irrevocably assigned to a resource without any knowledge about future requests. We revisit both selfish and online load balancing under the objective of minimizing the Nash Social Welfare, i.e., the geometric mean of the clients’ 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.
This work was partially supported by the Italian MIUR PRIN 2017 Project ALGADIMAR “Algorithms, Games, and Digital Markets”.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
In fact, on the one hand, using this idea for bounding a performance ratio (e.g., the price of anarchy or the competitive ratio), one obtains a bound on the ratio between two logarithms (each one having the product of the players’ costs as argument). On the other hand, we are interested in bounding the ratio between the argument of these logarithms, and there is no direct correlation between these two ratios (notice that logarithm of the latter ratio is equal to the difference between the corresponding utilitarian social costs, and therefore it is not related to the former one).
References
Aland, S., Dumrauf, D., Gairing, M., Monien, B., Schoppmann, F.: Exact price of anarchy for polynomial congestion games. SIAM J. Comput. 40(5), 1211–1233 (2011)
Aspnes, J., Azar, Y., Fiat, A., Plotkin, S.A., Waarts, O.: On-line routing of virtual circuits with applications to load balancing and machine scheduling. J. ACM 44(3), 486–504 (1997)
Awerbuch, B., Yossi, A., Grove, E.F., Kao, M., Krishnan, P., Vitter, J.S.: Load balancing in the l\({}_{\text{p}}\) norm. In: Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS), pp. 383–391 (1995)
Azar, Y., Naor, J., Rom, R.: The competitiveness of on-line assignments. In: Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms (SODA), pp. 203–210 (1992)
Beckmann, M.J., McGuire, C.B., Winsten, C.B.: Studies in the Economics of Transportation. Yale University Press, New Haven (1956)
Bei, X., Garg, J., Hoefer, M., Mehlhorn, K.: Earning and utility limits in fisher markets. ACM Trans. Econ. Comput. 7(2), 10:1–10:35 (2019)
Bhawalkar, K., Gairing, M., Roughgarden, T.: Weighted congestion games: price of anarchy, universal worst-case examples, and tightness. ACM Trans. Econ. Comput. 2(4), 1–23 (2014)
Bilò, V.: A unifying tool for bounding the quality of non-cooperative solutions in weighted congestion games. Theory Comput. Syst. 62(5), 1288–1317 (2018). https://doi.org/10.1007/s00224-017-9826-1
Bilò, V., Fanelli, A., Flammini, M., Moscardelli, L.: Performances of one-round walks in linear congestion games. Theory Comput. Syst. 49(1), 24–45 (2011). https://doi.org/10.1007/s00224-010-9309-0
Bilò, V., Vinci, C.: On the impact of singleton strategies in congestion games. In: Proceedings of the 25th Annual European Symposium on Algorithms, (ESA), pp. 17:1–17:14 (2017)
Bilò, V., Vinci, C.: Dynamic taxes for polynomial congestion games. ACM Trans. Econ. Comput. 7(3), 15:1–15:36 (2019)
Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, Cambridge (1998)
Brainard, W.C., Scarf, H.E.: How to compute equilibrium prices in 1891. CowlesFoundation Discussion Paper 1270 (2000)
Caragiannis, I.: Better bounds for online load balancing on unrelated machines. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 972–981 (2008)
Caragiannis, I., Flammini, M., Kaklamanis, C., Kanellopoulos, P., Moscardelli, L.: Tight bounds for selfish and greedy load balancing. Algorithmica 61(3), 606–637 (2011). https://doi.org/10.1007/s00453-010-9427-8
Caragiannis, I., Kurokawa, D., Moulin, H., Procaccia, A.D., Shah, N., Wang, J.: The unreasonable fairness of maximum Nash welfare. In: Proceedings of the 2016 ACM Conference on Economics and Computation (EC), pp. 305–322 (2016)
Chakrabarty, D., Mehta, A., Nagarajan, V., Vazirani, V.: Fairness and optimality in congestion games. In: Proceedings of the 6th ACM Conference on Electronic Commerce (EC), pp. 52–57 (2005)
Chekuri, C., Khanna, S.: Handbook of Scheduling: Algorithms, Models, and Performance Analysis, Chap. Approximation Algorithms for Minimizing Average Weighted Completion Time. Chapman & Hall/CRC, London (2004)
Christodoulou, G., Mirrokni, V.S., Sidiropoulos, A.: Convergence and approximation in potential games. Theor. Comput. Sci. 438, 13–27 (2012)
Cole, R., Gkatzelis, V.: Approximating the Nash social welfare with indivisible items. SIAM J. Comput. 47(3), 1211–1236 (2018)
Czumaj, A., Vöcking, B.: Tight bounds for worst-case equilibria. ACM Trans. Algorithms 3(1), 4:1–4:17 (2007)
Fleming, P.J., Wallace, J.: How not to lie with statistics: the correct way to summarize benchmark results. Commun. ACM 29(3), 218–221 (1986)
Gairing, M., Schoppmann, F.: Total latency in singleton congestion games. In: Deng, X., Graham, F.C. (eds.) WINE 2007. LNCS, vol. 4858, pp. 381–387. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-77105-0_42
Graham, R.L.: Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. 45(9), 1563–1581 (1966)
Hochbaum, D.S., Shmoys, D.B.: Using dual approximation algorithms for scheduling problems: theoretical and practical results. J. ACM 34, 144–162 (1987)
Horowitz, E., Sahni, S.K.: Exact and approximate algorithms for scheduling nonidentical processors. J. ACM 23, 317–327 (1976)
Ieong, S., McGrew, R., Nudelman, E., Shoham, Y., Sun, Q.: Fast and compact: a simple class of congestion games. In: Proceedings of the 20th AAAI Conference on Artificial Intelligence (AAAI), pp. 489–494 (2005)
Klimm, M., Schmand, D., Tönnis, A.: The online best reply algorithm for resource allocation problems. In: Fotakis, D., Markakis, E. (eds.) SAGT 2019. LNCS, vol. 11801, pp. 200–215. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-30473-7_14
Koutsoupias, E., Papadimitriou, C.: Worst-case equilibria. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol. 1563, pp. 404–413. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-49116-3_38
Lenstra, J.K., Shmoys, D.B., Tardos, E.: Approximation algorithms for scheduling unrelated parallel machines. Math. Program. 46, 259–271 (1990). https://doi.org/10.1007/BF01585745
Meyers, C.A., Schulz, A.S.: The complexity of welfare maximization in congestion games. Networks 59(2), 252–260 (2012)
Nash, J.: The bargaining problem. Econometrica 18(2), 155–162 (1950)
Pigou, A.C.: The Economics of Welfare. Macmillan and Co., London (1938)
Rosenthal, R.W.: A class of games possessing pure-strategy Nash equilibria. Int. J. Game Theory 2, 65–67 (1973). https://doi.org/10.1007/BF01737559
Roughgarden, T.: The price of anarchy is independent of the network topology. J. Comput. Syst. Sci. 67(2), 341–364 (2003)
Roughgarden, T., Tardos, E.: How bad is selfish routing? J. ACM 49(2), 236–259 (2002)
Roughgarden, T., Tardos, E.: Bounding the inefficiency of equilibria in nonatomic congestion games. Games Econ. Behav. 47(2), 389–403 (2004)
Suri, S., Tóth, C., Zhou, Y.: Selfish load balancing and atomic congestion games. Algorithmica 47(1), 79–96 (2007). https://doi.org/10.1007/s00453-006-1211-4
Vinci, C.: Non-atomic one-round walks in congestion games. Theor. Comput. Sci. 764, 61–79 (2019)
Vöcking, B.: Algorithmic Game Theory, chap. Selfish Load Balancing, Cambridge (2007)
Wardrop, J.G.: Some theoretical aspects of road traffic research. Proc. Inst. Civ. Eng. Part II 1(36), 352–362 (1952)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Bilò, V., Monaco, G., Moscardelli, L., Vinci, C. (2020). Nash Social Welfare in Selfish and Online Load Balancing. In: Chen, X., Gravin, N., Hoefer, M., Mehta, R. (eds) Web and Internet Economics. WINE 2020. Lecture Notes in Computer Science(), vol 12495. Springer, Cham. https://doi.org/10.1007/978-3-030-64946-3_23
Download citation
DOI: https://doi.org/10.1007/978-3-030-64946-3_23
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-64945-6
Online ISBN: 978-3-030-64946-3
eBook Packages: Computer ScienceComputer Science (R0)