AG 1, AG 2, AG 3, AG 4, AG 5, SWS, RG1, MMCI   Info

Public Audience

English

30 Minutes

Saarbrücken

We investigate load balancing games in the context of unrelated machines. In such games, 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 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 equilibria 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 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 first two cases and we show our progress in the third case.

Jennifer Gerling

225

--email hidden

passcode not visible

logged in users only