We investigate load balancing games in the context of unrelated machines
scheduling. In such a game, there are a 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 selfish 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 time of his job.
It is known that in an equilibrium, the performance of the system can
be far from optimal. The degradation of the system performance in Nash
equilibrium is defined 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 reduce 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 mechanisms use preemption". In this thesis we prove a lower
bound of ( logm log logm) for all symmetric preemptive coordination mechanisms.
Moreover we study the lower bound for the unusual case when the coordination
mechanisms are asymmetric and we get the same bound
under the weak assumption that machines have no IDs. On the positive side we
prove that the inefficiency-based mechanism can achieve a constant PoA when the
maximum inefficiency of the jobs is bounded by a constant.