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