Abstract:
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.
Fulltext:
PDF file (742 kB)
