Geodesic
Price of anarchy for machine load balancing game
Matematičeskaâ teoriâ igr i eë priloženiâ, Tome 4 (2012) no. 4, pp. 93-113.

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

The Machine Load Balancing Game with $N$ machines is considered. A set of $n$ jobs is to be assigned to a set of $N$ 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. Conditions, when this upper bound estimation is an exact estimation of the Price of Anarchy, are found. Conditions of Braess's Paradox appearing in the system are found. For the case of 3 machines the exact value of Price of Anarchy is obtained numerically with the algorithm that was developed.
Keywords: machine load balancing game, Nash equilibrium, price of anarchy. 
@article{MGTA_2012_4_4_a5,
     author = {Julia V. Chirkova},
     title = {Price of anarchy for machine load balancing game},
     journal = {Matemati\v{c}eska\^a teori\^a igr i e\"e prilo\v{z}eni\^a},
     pages = {93--113},
     publisher = {mathdoc},
     volume = {4},
     number = {4},
     year = {2012},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MGTA_2012_4_4_a5/}
}
TY  - JOUR
AU  - Julia V. Chirkova
TI  - Price of anarchy for machine load balancing game
JO  - Matematičeskaâ teoriâ igr i eë priloženiâ
PY  - 2012
SP  - 93
EP  - 113
VL  - 4
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MGTA_2012_4_4_a5/
LA  - ru
ID  - MGTA_2012_4_4_a5
ER  - 
%0 Journal Article
%A Julia V. Chirkova
%T Price of anarchy for machine load balancing game
%J Matematičeskaâ teoriâ igr i eë priloženiâ
%D 2012
%P 93-113
%V 4
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MGTA_2012_4_4_a5/
%G ru
%F MGTA_2012_4_4_a5
Julia V. Chirkova. Price of anarchy for machine load balancing game. Matematičeskaâ teoriâ igr i eë priloženiâ, Tome 4 (2012) no. 4, pp. 93-113. http://geodesic.mathdoc.fr/item/MGTA_2012_4_4_a5/

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

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

[3] 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 (ICALP2003), 2003, 514–526 | DOI | MR | Zbl

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

[5] Mazalov V., Monien B., Schoppmann F., Tiemann R., “Wardrop equilibria and price of stability for bottleneck games with splittable traffic”, Lecture Notes in Computer Science, 4286, 2006, 331–342 | DOI

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

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