In game theory, a job scheduling game is a game that models a scenario in which multiple selfish users wish to utilize multiple processing machines. Each user has a single job, and he needs to choose a single machine to process it. The incentive of each user is to have his job run as fast as possible.
Contents
Definition
Job scheduling games are the following set of problems: given
For example: given game with 2 machines M1 and M2 and 2 jobs J1 and J2. The rows represent the strategies job J1 can choose and the columns represent the strategies job J2 can choose.
Motivation
The problem of dividing several jobs among several machines in a way that optimizes some global objective function is well known and has been widely studied in computer science. In this type of problems there is a central designer that determines the allocation of jobs into machines and all the participating entities are assumed to obey the protocol. However, since the emergence of the Internet, problems in distributed settings has been studied as well. In this type of problems, different machines and jobs may be owned by different strategic entities, who will typically attempt to optimize their own objective rather than the global objective.
Main Properties
The price of stability is used to measure inefficiency. It differentiates between games in which all equlibria are inefficient and those in which there exists an equilibrium that is inefficient
For every job scheduling game price of stability is equal to 1
proof: Price of stability is equal to best Nash equilibrium divided by OPTimum. Therefore, in order to prove that Price of stability = 1 it is sufficient to prove that the optimum is equal to the best Nash equilibrium. In order to prove that, it is sufficient to prove that there is an OPTimum solution which is in Nash equilibrium, since if the OPTimum is also Nash equilibrium it is especially best Nash equilibrium.
The optimum state is when the most loaded machine is the less loaded it can be. Assuming each job which was scheduled to the most loaded machine will not aspire to move to another machine. In addition, each job that was scheduled to a machine which is not the most loaded one, will not aspire to move to the most loaded machine. Given a game with in the optimum state with
The price of anarchy is a concept from game theory that describes the difference in maximum social utility and the utility of an equilibrium point of the game.
There exist job scheduling game where Price of anarchy is not bounded
claim: Price of anarchy =
proof: Given a game with 2 machines