Coordination mechanisms from (almost) all scheduling policies

Conference Paper

We study the price of anarchy of coordination mechanisms for a scheduling problem where each job j has a weight wj, processing time p ij, assignment cost hij, and communication delay (or release date) rij on machine i. Each machine is free to declare its own scheduling policy. Each job is a selfish agent and selects a machine that minimizes its own disutility, which is equal to its weighted completion time plus its assignment cost. The goal is to minimize the total disutility incurred by all the jobs. Our model is general enough to capture scheduling jobs in a distributed environment with heterogeneous machines (or data centers) that are situated across different locations. Our main result is a characterization of scheduling policies that give a small (robust) Price of Anarchy. More precisely, we show that whenever each machine independently declares any scheduling policy that satisfies a certain bounded stretch condition introduced in this paper, the game induced between the jobs has a small Price of Anarchy. Our characterization is powerful enough to test almost all popular scheduling policies. On the technical side, to derive our results, we use a potential function whose derivative leads to an instantaneous smoothness condition, and linear programming and dual fitting. To the best of our knowledge, this is a novel application of these techniques in the context of coordination mechanisms, and we believe these tools will find more applications in analyzing PoA of games. We also ex-tend our results to the lk-norms and l ∞ norm (makespan) objectives. Copyright 2014 ACM.

Full Text

Duke Authors

Cited Authors

  • Bhattacharya, S; Im, S; Kulkarni, J; Munagala, K

Published Date

  • January 1, 2014

Published In

  • Itcs 2014 Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science

Start / End Page

  • 121 - 133

International Standard Book Number 13 (ISBN-13)

  • 9781450322430

Digital Object Identifier (DOI)

  • 10.1145/2554797.2554811

Citation Source

  • Scopus