Ruben Hoeksma — Price of Anarchy for Utilitarian Scheduling Games with Related Machines
| Time: | Wednesday, January 26, 2011 |
| Location: | Room 101, Citadel |
The price of anarchy measures by how much the performance of a system deteriorates due to the lack of central coordination. We address the classical uniformly related machine scheduling problem, assuming that jobs may choose the machine on which they are processed. When jobs seek to minimize their own completion time, the utilitarian social choice function is to minimize the average job completion time. In this setting we analyze the price of anarchy for the natural coordination mechanism where jobs are sequenced shortest first per machine. We show that the price of anarchy is bounded from below by e/(e-1) > 1.58 and from above by 2. This complements recent results on the price of anarchy for the more general unrelated machine scheduling problem by Cole et al. and Correa et al. Moreover, as Nash equilibria correspond one-to-one to SPT schedules, the same bounds hold for the SPT heuristic on uniformly related machines. Thereby, our work also fills a gap in the literature.