Computing the price of anarchy in processor load balancing game with linear delays

Julia V. Chirkova

Institute of Applied Mathematical Research, Karelian Research Centre of RAS, Pushkinskaya str., 11, Petrozavodsk, Karelia, 185910, Russia

Abstract: This paper considers a generalization of the processor load balancing game also known as KP-model. A linear delay of a processor may depend on not only its load but on loads of other processors. Players choose processors of different speeds to run their jobs striving to minimize job's delay, i.e., the job completion time on a chosen processor. The social cost is the maximum delay over all processors. We propose a computing algorithm of the exact PoA value which can be applied to estimate the POA visually if its exact analytical expression is not obtained yet or it is rather complicated to figure out its formula.

Keywords: processor load balancing game, Nash equilibrium, price of anarchy, linear functional, computation.

Language: English

DOI: 10.21638/11701/spbu31.2021.06