Geodesic
Price of anarchy for machine load balancing game with 3 machines
Matematičeskaâ teoriâ igr i eë priloženiâ, Tome 6 (2014) no. 4, pp. 85-96.

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

The Machine Load Balancing Game with 3 machines is considered. A set of n jobs is to be assigned to a set of 3 machines with different speeds. Jobs choose machines to minimize their own delays. The social cost of a schedule is the maximum delay among all machines, i.e. makespan. For this model the upper bound estimation of the Price of Anarchy is obtained. This upper bound estimation is an exact estimation of the Price of Anarchy for the case when the speed of the fastest machine is enough large. Conditions of PoA increasing with addition a machine in the system of 2 machines are found.
Keywords: machine load balancing game, Nash equilibrium, price of anarchy. 
@article{MGTA_2014_6_4_a3,
     author = {Julia V. Chirkova},
     title = {Price of anarchy for machine load balancing game with 3 machines},
     journal = {Matemati\v{c}eska\^a teori\^a igr i e\"e prilo\v{z}eni\^a},
     pages = {85--96},
     publisher = {mathdoc},
     volume = {6},
     number = {4},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MGTA_2014_6_4_a3/}
}
TY  - JOUR
AU  - Julia V. Chirkova
TI  - Price of anarchy for machine load balancing game with 3 machines
JO  - Matematičeskaâ teoriâ igr i eë priloženiâ
PY  - 2014
SP  - 85
EP  - 96
VL  - 6
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MGTA_2014_6_4_a3/
LA  - ru
ID  - MGTA_2014_6_4_a3
ER  - 
%0 Journal Article
%A Julia V. Chirkova
%T Price of anarchy for machine load balancing game with 3 machines
%J Matematičeskaâ teoriâ igr i eë priloženiâ
%D 2014
%P 85-96
%V 6
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MGTA_2014_6_4_a3/
%G ru
%F MGTA_2014_6_4_a3
Julia V. Chirkova. Price of anarchy for machine load balancing game with 3 machines. Matematičeskaâ teoriâ igr i eë priloženiâ, Tome 6 (2014) no. 4, pp. 85-96. http://geodesic.mathdoc.fr/item/MGTA_2014_6_4_a3/

[1] Mazalov V. V., Matematicheskaya teoriya igr i prilozheniya, Lan, SPb.–M.–Krasnodar, 2010

[2] Chirkova Yu. V., “Tsena anarkhii v igre balansa zagruzki sistemy obsluzhivaniya”, Matematicheskaya teoriya igr i ee prilozheniya, 4:4 (2012), 93–113 | Zbl

[3] Czumaj A., Vöcking B., “Tight bounds for worst-case equilibria”, Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'02 (2002), 413–420 | Zbl

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

[5] Even-Dar E., Kesselman A., Mansour Y., “Convergence time to Nash equilibria”, Proc. of the 30th International Colloquium on Automata, Languages and Programming, ICALP'2003 (2003), 502–513 | MR | Zbl

[6] Feldmann R., Gairing M., Lücking T., Monien B., Rode M., “Nashification and the coordination ratio for a selfish routing game”, Proc. of the 30th International Colloquium on Automata, Languages and Programming, ICALP'2003 (2003), 514–526 | MR | Zbl

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

[8] Korilis Y. A., Lazar A. A., Orda A., “Avoiding the Braess paradox in non-cooperative networks”, J. Appl. Prob., 36 (1999), 211–222 | DOI | MR | Zbl

[9] Murchland J. D., “Braess's paradox of traffic flow”, Transportation Research, 4 (1970), 391–394 | DOI

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