Coordination Mechanisms for Unrelated Machine Scheduling

number of jobs and a number of machines, and each job needs to be scheduled on one machine. A collection
of values pij are given, where pij indicates the processing time of job i on machine j. Moreover, each job is
controlled by a selsh player who only wants to minimize the completion time of his job while disregarding
other players' welfare. The outcome schedule is a Nash equilibrium if no player can unilaterally change his
machine and reduce the completion of his job. It can be expected that in an equilibrium, the performance
of the system can be far from optimal. The degradation of the system performance in Nash equilibrium is
dened as the price of anarchy (PoA): the ratio of the cost of the worst Nash equilibrium to the cost of the
optimal scheduling. Clever scheduling policies can be designed to minimize PoA. These scheduling policies
are called coordination mechanisms.
It has been posed as an open question: what is the best possible lower bound when coordination mecha-
nisms use preemption. In this thesis we consider three cases: when the jobs have IDs, when coordination
mechanisms order the jobs randomly, and when the jobs are anonymous. We prove a tight lower bound for
the rst two cases and we show our progress in the third case.