Datensatz

Zusammenfassung

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.