Systems Analysis

Price of anarchy for maximizing the minimum machine load

Yu. V. Chirkova

Institute of Applied Mathematical Research of Karelian Research Centre of RAS

Abstract: The maximizing the minimum machine delay game with uniformly related machines is considered. Players choose machines with different speeds to run their jobs trying to minimize job’s delay, i.e. chosen machine’s completion time. The social payoff is the minimal delay over all machines. For the general case of N machines we find the lower bound for Price of Anarchy (PoA), and for the case of 3 machines we find its exact value. We prove that the PoA either remains the same or increases when an additional third machine is included into the system with two machines. Also we propose a method of computation the PoA value and illustrate it for 3 machines.

Keywords: Nash equilibrium, cover, maximizing the minimum load, price of anarchy, selfish load balancing.

UDC: 519.711.7
BBK: 22.1

Received: April 17, 2016
Published: July 31, 2016

Bibliographic databases:

•