Maximizing the Minimum Processor Load with Linear Externalities
// Mathematical Optimization Theory and Operations Research: Recent Trends. MOTOR 2021. Communications in Computer and Information Science, vol 1476. Springer, Cham. Strekalovsky A., Kochetov Y., Gruzdeva T., Orlov A. (eds), 2021. Pp. 147-162
Keywords: Nash equilibrium, Cover, Maximizing the minimum load, Price of anarchy, Linear externalities
We consider the maximizing the minimum processor delay game on uniformly related processors with linear externalities. Externalities allow taking into account the influence of all loaded processors on each processor performance, unlike the model without externalities this problem has not been considered before. A set of jobs is to be assigned to a set of processors with different delay functions depending on their own loads and also loads on other processors. Jobs choose processors to minimize their own delays, while the system the social payoff of a schedule is the minimum delay among all processors, i.e. cover. For the case of two processors in this model the Nash equilibrium existence is proven and the expression for the Price of Anarchy is obtained. Also we show that the Price of Anarchy is limited in contrast to the initial model without externalities.
Indexed at Scopus
Last modified: September 30, 2022