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/