game-theory

  We consider the scheduling of simple linear deteriorating jobs on parallel machines a new perspective based on game theory. In scheduling, jobs are often controlled by independent and selfish agents, in which each agent tries to 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 Aand 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 Aand further show that the ratio obtained by Ais tight. Finally, we analyze the time complexity of the proposed algorithm