Computing the Price of Anarchy in Processor Load Balancing Game with Linear Delays

Authors

  • Julia V. Chirkova Institute of Applied Mathematical Research, Karelian Research Centre of RAS, Pushkinskaya str., 11, Petrozavodsk, Karelia, 185910, Russia https://orcid.org/0000-0001-6524-4004

DOI:

https://doi.org/10.21638/11701/spbu31.2021.06

Abstract

This paper considers a generalization of the processor load balancing game also known as KP-model. A linear delay of a processor may depend on not only its load but on loads of other processors. Players choose processors of different speeds to run their jobs striving to minimize job's delay, i.e., the job completion time on a chosen processor. The social cost is the maximum delay over all processors. We propose a computing algorithm of the exact PoA value which can be applied to estimate the POA visually if its exact analytical expression is not obtained yet or it is rather complicated to figure out its formula.

Keywords:

processor load balancing game, Nash equilibrium, price of anarchy, linear functional, computation

Downloads

Download data is not yet available.
 

References

Chirkova, J. V. (2021). Load Balancing Game with Linear Externalities. In: Mathematical Game Theory and its Applications, Vol. 13, Iss. 2, pp. 62–79 (in Russian)

Chirkova, J. V. (2021). Maximizing the Minimum Processor Load with Linear Externalities. In: Mathematical Optimization Theory and Operations Research: Recent Trends. MOTOR 2021. Communications in Computer and Information Science (Strekalovsky, A., Kochetov, Y., Gruzdeva, T., Orlov, A., eds), Vol. 1476, pp. 147–162. Springer, Cham

Chirkova, Yu. V. (2015). Price of anarchy in machine load balancing game. Automation and Remote Control, 76(10), 1849–1864

Chirkova, Yu. V. (2017). Price of Anarchy for Maximizing the Minimum Machine Load. Advances in Systems Science and Applications, 17(4), 61–77

Fotakis, D., Kontogiannis, S. C., Koutsoupias, E., Mavronicolas, M., Spirakis, P. G. (2002). The structure and complexity of Nash equilibria for a selfish routing game. Proc. of the 29th International Colloquium on Automata, Languages and Programming (ICALP2002), 123–134

Epstein, L. (2010). Equilibria for Two Parallel Links: The Strong Price of Anarchy Versus the Price of Anarchy. Acta Inform. 47(7–8), 375–389

Epstein L., Kleiman E., van Stee R. (2009). Maximizing the minimum load: the cost of selfishness. Proceedings of the 5th International Workshop on Internet and Network Economics, LNCS, 5929, 232–243

Koutsoupias, E. and Papadimitriou, C. H. (1999). Worst-Case Equilibria. Proc. STACS, 1563, 404–413

Lücking, T., Mavronicolas, M., Monien, B., Rode, M., Spirakis, P., Vrto, I. (2003). Which is the Worst-case Nash Equilibrium? Proc. of the 26th International Symposium on Mathematical Foundations of Computer Science, LNCS 2747, 551–561

Downloads

Published

2021-10-30

How to Cite

Chirkova, J. V. (2021). Computing the Price of Anarchy in Processor Load Balancing Game with Linear Delays. Contributions to Game Theory and Management, 14, 72–81. https://doi.org/10.21638/11701/spbu31.2021.06

Issue

Vol. 14 (2021)

Section

Articles

License

Articles of "Contributions to Game Theory and Management" are open access distributed under the terms of the License Agreement with Saint Petersburg State University, which permits to the authors unrestricted distribution and self-archiving free of charge.