Random coordination mechanism for scheduling games with machine modification

This paper studies the Random coordination mechanism for scheduling games with machine modification. A set of jobs is to be processed on a set of identical machines. An initial schedule before the modification of machines is given as a prior. Subsequently, some machines are removed and some new machines are added. Each job has the right either to stay on its original machine if the machine is not removed, or to move to another machine. If a job changes its machine, it will be behind all the jobs previously scheduled on the target machine. For two jobs moving to the same machine or remaining on the same machine, each has an equal probability of being ahead of the other. The individual cost of each job is its completion time, while the social cost is defined as the maximal load of all the machines. We present properties of Nash Equilibrium and establish Price of Anarchy of the game. The bounds are tight for each combination of the number of final machines, added machines and removed machines.