Geodesic
Machine Load Balancing Game with linear externalities
Matematičeskaâ teoriâ igr i eë priloženiâ, Tome 13 (2021) no. 2, pp. 62-79.

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

The Machine Load Balancing Game with linear externalities is considered. A set of jobs is to be assigned to a set of machines with different latencies depending on their own loads and also loads on other machines. Jobs choose machines to minimize their own latencies. The social cost of a schedule is the maximum delay among all machines, i.e. makespan. For the case of two machines in this model an Nash equilibrium existence is proven and of the expression for the Price of Anarchy is obtained.
Keywords: machine load balancing game, linear externalities, Nash equilibrium, price of anarchy. 
@article{MGTA_2021_13_2_a3,
     author = {Julia V. Chirkova},
     title = {Machine {Load} {Balancing} {Game} with linear externalities},
     journal = {Matemati\v{c}eska\^a teori\^a igr i e\"e prilo\v{z}eni\^a},
     pages = {62--79},
     publisher = {mathdoc},
     volume = {13},
     number = {2},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MGTA_2021_13_2_a3/}
}
TY  - JOUR
AU  - Julia V. Chirkova
TI  - Machine Load Balancing Game with linear externalities
JO  - Matematičeskaâ teoriâ igr i eë priloženiâ
PY  - 2021
SP  - 62
EP  - 79
VL  - 13
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MGTA_2021_13_2_a3/
LA  - ru
ID  - MGTA_2021_13_2_a3
ER  - 
%0 Journal Article
%A Julia V. Chirkova
%T Machine Load Balancing Game with linear externalities
%J Matematičeskaâ teoriâ igr i eë priloženiâ
%D 2021
%P 62-79
%V 13
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MGTA_2021_13_2_a3/
%G ru
%F MGTA_2021_13_2_a3
Julia V. Chirkova. Machine Load Balancing Game with linear externalities. Matematičeskaâ teoriâ igr i eë priloženiâ, Tome 13 (2021) no. 2, pp. 62-79. http://geodesic.mathdoc.fr/item/MGTA_2021_13_2_a3/

[1] Acemoglu D., Ozdaglar A., Flow control, routing, and performance from service provider viewpoint, LIDS report, 2004, 74 pp. | Zbl

[2] Andelman N., Feldman M., Mansour Y., “Strong price of anarchy”, Proc. of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2007, 189–198 | MR | Zbl

[3] Braess D., “Uber ein Paradoxon der Verkehrsplanung”, Unternehmensforschung, 12 (1968), 258–268 | MR | Zbl

[4] Easley D., Kleinberg J., Networks, Crowds, and Markets: Reasoning about Highly Connected World, Cambridge University Press, Cambridge, 2010 | MR | Zbl

[5] Epstein L., “Equilibria for two parallel links: the strong price of anarchy versus the price of anarchy”, Acta Informatica, 47:7–8 (2010), 375–389 | DOI | MR | Zbl

[6] 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, 2002, 123–134 | MR | Zbl

[7] Gao H., Mazalov V. V., Xue J., “Optimal Parameters of Service in a Public Transportation Market with Pricing”, Journal of Advanced Transportation, 2020, Safety, Behavior, and Sustainability under the Mixed Traffic Flow Environment. 2020 (2020)

[8] Holzman R., Monderer D., “Strong equilibrium in network congestion games: Increasing versus decreasing costs”, International Journal of Game Theory, 44 (2015), 647–666 | DOI | MR | Zbl

[9] Jacobs J., The economy of cities, Random House, New York, 1969 | MR

[10] Koutsoupias E., Papadimitriou C. H., “Worst-case Equilibria”, Proc. of STACS, 1563, 1999, 404–413 | MR | Zbl

[11] Kuang Z., Lian Z., Lien J. W., Zheng J., “Serial and parallel duopoly competition in multi-segment transportation routes”, Transportation Research Part E: Logistics and Transportation Review, 133 (2020), 101821 | DOI

[12] Kuang Z., Mazalov V. V., Tang X., Zheng J., “Transportation network with externalities”, Journal of Computational and Applied Mathematics, 382 (2021), 113091 | DOI | MR | Zbl

[13] 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

[14] Mak V., Seale D. A., Gishces E. J. et al., “The Braess Paradox and Coordination Failure in Directed Networks with Mixed Externalities”, Production and Operations Management, 27:4 (2018), 717–733 | DOI | MR

[15] Mazalov V., Chirkova J., Networking Games. Network Forming Games and Games on Networks, Academic Press, 2019 | Zbl

[16] Milchtaich I., “Network topology and the efficiency of equilibrium”, Games and Economic Behavior, 57:2 (2006), 321–346 | DOI | MR | Zbl

[17] Papadimitriou C. H., Koutsoupias E., “Worst-Case Equilibria”, LNSC, 1563, 1999, 404–413 | MR | Zbl

[18] Roughgarden T., Tardos É., How bad is selfish routing?, Journal of the ACM, 49:2 (2002), 236–259 | DOI | MR | Zbl