Geodesic
Computing the price of anarchy in processor load balancing game with linear delays
Contributions to game theory and management, Tome 14 (2021), pp. 72-81.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{CGTM_2021_14_a6,
     author = {Julia V. Chirkova},
     title = {Computing the price of anarchy in processor load balancing game with linear delays},
     journal = {Contributions to game theory and management},
     pages = {72--81},
     publisher = {mathdoc},
     volume = {14},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CGTM_2021_14_a6/}
}
TY  - JOUR
AU  - Julia V. Chirkova
TI  - Computing the price of anarchy in processor load balancing game with linear delays
JO  - Contributions to game theory and management
PY  - 2021
SP  - 72
EP  - 81
VL  - 14
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/CGTM_2021_14_a6/
LA  - en
ID  - CGTM_2021_14_a6
ER  - 
%0 Journal Article
%A Julia V. Chirkova
%T Computing the price of anarchy in processor load balancing game with linear delays
%J Contributions to game theory and management
%D 2021
%P 72-81
%V 14
%I mathdoc
%U http://geodesic.mathdoc.fr/item/CGTM_2021_14_a6/
%G en
%F CGTM_2021_14_a6
Julia V. Chirkova. Computing the price of anarchy in processor load balancing game with linear delays. Contributions to game theory and management, Tome 14 (2021), pp. 72-81. http://geodesic.mathdoc.fr/item/CGTM_2021_14_a6/

[1] Chirkova J. V., “Load Balancing Game with Linear Externalities”, Mathematical Game Theory and its Applications, 13:2 (2021), 62–79 (in Russian) | MR | Zbl

[2] Chirkova J. V., “Maximizing the Minimum Processor Load with Linear Externalities”, Mathematical Optimization Theory and Operations Research: Recent Trends, MOTOR 2021, Communications in Computer and Information Science, 1476, eds. Strekalovsky A., Kochetov Y., Gruzdeva T., Orlov A., Springer, Cham, 2021, 147–162 | MR

[3] Chirkova Yu. V., “Price of anarchy in machine load balancing game”, Automation and Remote Control, 76:10 (2015), 1849–1864 | MR

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

[5] Fotakis D., Kontogiannis S. C., Koutsoupias E., Mavronicolas M., Spirakis P. G., “The structure and complexity of Nash equilibria for a selfish routing game”, Proc. of the 29th International Colloquium on Automata, Languages and Programming, ICALP 2002, 123–134 | MR | Zbl

[6] Epstein L., “Equilibria for Two Parallel Links: The Strong Price of Anarchy Versus the Price of Anarchy”, Acta Inform., 47:7–8 (2010), 375–389 | MR | Zbl

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

[8] Koutsoupias E., Papadimitriou C. H., “Worst-Case Equilibria”, Proc. STACS, 1563 (1999), 404–413 | MR | Zbl

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