An approximation algorithm based on game theory for scheduling simple linear deteriorating jobs

We consider the scheduling of simple linear deteriorating jobs on parallel machines from a new perspective based on game theory. In scheduling, jobs are often controlled by independent and selfish agents, in which each agent tries to select a machine for processing that optimizes its own payoff while ignoring the others. We formalize this situation as a game in which the players are job owners, the strategies are machines, and a player's utility is inversely proportional to the total completion time of the machine selected by the agent. The price of anarchy is the ratio between the worst-case equilibrium makespan and the optimal makespan. In this paper, we design a game theoretic approximation algorithm A and prove that it converges to a pure-strategy Nash equilibrium in a linear number of rounds. We also derive the upper bound on the price of anarchy of A and further show that the ratio obtained by A is tight. Finally, we analyze the time complexity of the proposed algorithm.