Abstract
We consider the following dynamic load balancing game: Given an initial assignment of jobs to identical parallel machines, the system is modified; specifically, some machines are added or removed. Each job’s cost is the load on the machine it is assigned to; thus, when machines are added, jobs have an incentive to migrate to the new unloaded machines. When machines are removed, the jobs assigned to them must be reassigned. Consequently, other jobs might also benefit from migrations. In our job-extension penalty model, for a given extension parameter δ ≥ 0, if the machine on which a job is assigned to in the modified schedule is different from its initial machine, then the job’s processing time is extended by δ.
We provide answers to the basic questions arising in this model. Namely, the existence and calculation of a Nash Equilibrium and a Strong Nash Equilibrium, and their inefficiency compared to an optimal schedule. Our results show that the existence of job-migration penalties might lead to poor stable schedules; however, if the modification is a result of a sequence of improvement steps or, better, if the sequence of improvement steps can be supervised in some way (by forcing the jobs to play in a specific order) then any stable modified schedule approximates well an optimal one.
Our work adds two realistic considerations to the study of job scheduling games: the analysis of the common situation in which systems are upgraded or suffer from failures, and the practical fact according to which job migrations are associated with a cost.
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
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Anshelevich, E., Dasgupta, A., Kleinberg, J.M., Tardos, É., Wexler, T., Roughgarden, T.: The price of stability for network design with fair cost allocation. In: FOCS (2004)
Andelman, N., Feldman, M., Mansour, Y.: Strong Price of Anarchy. In: SODA (2007)
Azar, Y., Jain, K., Mirrokni, V.S.: (Almost) optimal coordination mechanisms for unrelated machine scheduling. In: SODA (2008)
Belikovetsky, S., Tamir, T.: Load Rebalancing Games in Dynamic Systems with Migration Costs. Full version, http://www.faculty.idc.ac.il/tami/Papers/Rebalance.pdf
Caragiannis, I., Flammini, M., Kaklamanis, C., Kanellopoulos, P., Moscardelli, L.: Tight Bounds for Selfish and Greedy Load Balancing. Algorithmica 61(3), 606–637 (2011)
Czumaj, A., Vöcking, B.: Tight bounds for worst-case equilibria. ACM Transactions on Algorithms 3(1) (2007)
Even-Dar, E., Kesselman, A., Mansour, Y.: Convergence time to Nash equilibria. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 502–513. Springer, Heidelberg (2003)
Feldman, M., Tamir, T.: Conflicting congestion effects in resource allocation games. Journal of Operation Research 60(3), 529–540 (2012)
Fiat, A., Kaplan, H., Levy, M., Olonetsky, S.: Strong Price of Anarchy for Machine Load Balancing. In: Arge, L., Cachin, C., Jurdziński, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 583–594. Springer, Heidelberg (2007)
Finn, G., Horowitz, E.: A linear time approximation algorithm for multiprocessor scheduling. BIT 19(3), 312–320 (1979)
Fotakis, D., Kontogiannis, S., Koutsoupias, E., Mavronicolas, M., Spirakis, P.: The structure and complexity of Nash equilibria for a selfish routing game. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol. 2380, pp. 123–134. Springer, Heidelberg (2002)
Graham, R.L.: Bounds on Multiprocessing Timing Anomalies. SIAM J. Appl. Math. 17, 263–269 (1969)
Hochbaum, D.S., Shmoys, D.B.: Using dual approximation algorithms for scheduling problems: Practical and theoretical results. Journal of the ACM 34(1), 144–162 (1987)
Koutsoupias, E., Papadimitriou, C.: Worst-case Equilibria. Computer Science Review 3(2), 65–69 (1999)
Papadimitriou, C.: Algorithms, Games, and the Internet. In: STOC (2001)
Paes Leme, R., Syrgkanis, V., Tardos, É.: The curse of simultaneity. In: ITCS (2012)
Vöcking, B.: In: Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V. (eds.) Algorithmic Game Theory: Selfish Load Balancing, ch. 20. Cambridge University Press (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Belikovetsky, S., Tamir, T. (2013). Load Rebalancing Games in Dynamic Systems with Migration Costs. In: Vöcking, B. (eds) Algorithmic Game Theory. SAGT 2013. Lecture Notes in Computer Science, vol 8146. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-41392-6_7
Download citation
DOI: https://doi.org/10.1007/978-3-642-41392-6_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-41391-9
Online ISBN: 978-3-642-41392-6
eBook Packages: Computer ScienceComputer Science (R0)