Skip to main content

Coordination mechanisms from (almost) all scheduling policies

Publication ,  Conference
Bhattacharya, S; Im, S; Kulkarni, J; Munagala, K
Published in: ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science
January 1, 2014

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.

Duke Scholars

Published In

ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science

DOI

Publication Date

January 1, 2014

Start / End Page

121 / 133
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Bhattacharya, S., Im, S., Kulkarni, J., & Munagala, K. (2014). Coordination mechanisms from (almost) all scheduling policies. In ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science (pp. 121–133). https://doi.org/10.1145/2554797.2554811
Bhattacharya, S., S. Im, J. Kulkarni, and K. Munagala. “Coordination mechanisms from (almost) all scheduling policies.” In ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science, 121–33, 2014. https://doi.org/10.1145/2554797.2554811.
Bhattacharya S, Im S, Kulkarni J, Munagala K. Coordination mechanisms from (almost) all scheduling policies. In: ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science. 2014. p. 121–33.
Bhattacharya, S., et al. “Coordination mechanisms from (almost) all scheduling policies.” ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science, 2014, pp. 121–33. Scopus, doi:10.1145/2554797.2554811.
Bhattacharya S, Im S, Kulkarni J, Munagala K. Coordination mechanisms from (almost) all scheduling policies. ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science. 2014. p. 121–133.

Published In

ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science

DOI

Publication Date

January 1, 2014

Start / End Page

121 / 133