Price of Anarchy for Maximizing the Minimum Machine Load

Main Article Content

Yulia Vasil'evna Chirkova

Abstract

The maximizing the minimum machine delay game (or cover 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. the chosen machine’s completion time. The social payoff is
the minimal delay over all machines. For the general case of N machines we found the lower
bound for Price of Anarchy (PoA), and for the case of 3 machines we found its exact value. We
proved that the PoA does not change 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.

Downloads

Download data is not yet available.

Article Details

How to Cite
Chirkova, Y. (2017). Price of Anarchy for Maximizing the Minimum Machine Load. Advances in Systems Science and Applications, 17(4), 61-77. https://doi.org/10.25728/assa.2017.17.4.518
Section
Translated articles