NDLI: Efficient Coordination Mechanisms for Unrelated Machine Scheduling

Content Provider	Springer Nature Link
Author	Caragiannis, Ioannis
Copyright Year	2012
Abstract	We present three new coordination mechanisms for scheduling n selfish jobs on m unrelated machines. A coordination mechanism aims to mitigate the impact of selfishness of jobs on the efficiency of schedules by defining a local scheduling policy on each machine. The scheduling policies induce a game among the jobs and each job prefers to be scheduled on a machine so that its completion time is minimum given the assignments of the other jobs. We consider the maximum completion time among all jobs as the measure of the efficiency of schedules. The approximation ratio of a coordination mechanism quantifies the efficiency of pure Nash equilibria (price of anarchy) of the induced game.Our mechanisms are deterministic, local, and preemptive in the sense that the scheduling policy does not necessarily process the jobs in an uninterrupted way and may introduce some idle time. Our first coordination mechanism has approximation ratio Θ(logm) and always guarantees that the induced game has pure Nash equilibria to which the system converges in at most n rounds. This result improves a bound of O(log2 m) due to Azar, Jain, and Mirrokni and, similarly to their mechanism, our mechanism uses a global ordering of the jobs according to their distinct IDs. Next we study the intriguing scenario where jobs are anonymous, i.e., they have no IDs. In this case, coordination mechanisms can only distinguish between jobs that have different load characteristics. Our second mechanism handles anonymous jobs and has approximation ratio $O(\frac{\log m}{\log\log m})$ although the game induced is not a potential game and, hence, the existence of pure Nash equilibria is not guaranteed by potential function arguments. However, it provides evidence that the known lower bounds for non-preemptive coordination mechanisms could be beaten using preemptive scheduling policies. Our third coordination mechanism also handles anonymous jobs and has a nice “cost-revealing” potential function. We use this potential function in order, not only to prove the existence of equilibria, but also to upper-bound the price of stability of the induced game by O(logm) and the price of anarchy by O(log2 m). Our third coordination mechanism is the first that handles anonymous jobs and simultaneously guarantees that the induced game is a potential game and has bounded price of anarchy. In order to obtain the above bounds, our coordination mechanisms use m as a parameter. Slight variations of these mechanisms in which this information is not necessary achieve approximation ratios of O(m ϵ ), for any constant ϵ>0.
Starting Page	512
Ending Page	540
Page Count	29
File Format	PDF
ISSN	01784617
Journal	Algorithmica
Volume Number	66
Issue Number	3
e-ISSN	14320541
Language	English
Publisher	Springer-Verlag
Publisher Date	2012-04-25
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Algorithmic game theory Price of anarchy Coordination mechanisms Scheduling Unrelated machines Algorithm Analysis and Problem Complexity Theory of Computation Mathematics of Computing Algorithms Computer Systems Organization and Communication Networks Data Structures, Cryptology and Information Theory
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Improving the Price of Anarchy for Selfish Routing via Coordination Mechanisms

A Lower Bound for Scheduling Mechanisms

A Lower Bound of 1+φ for Truthful Scheduling Mechanisms

Graphical Congestion Games

The Price of Optimum: Complexity and Approximation for a Matching Game

Graph Balancing: A Special Case of Scheduling Unrelated Parallel Machines

On the Performance of Approximate Equilibria in Congestion Games

Parametric Packing of Selfish Items and the Subset Sum Algorithm

Scheduling on Unrelated Machines under Tree-Like Precedence Constraints

Efficient Coordination Mechanisms for Unrelated Machine Scheduling

Similar Documents

Improving the Price of Anarchy for Selfish Routing via Coordination Mechanisms

A Lower Bound for Scheduling Mechanisms

A Lower Bound of 1+φ for Truthful Scheduling Mechanisms

Graphical Congestion Games

The Price of Optimum: Complexity and Approximation for a Matching Game

Graph Balancing: A Special Case of Scheduling Unrelated Parallel Machines

On the Performance of Approximate Equilibria in Congestion Games

Parametric Packing of Selfish Items and the Subset Sum Algorithm

Scheduling on Unrelated Machines under Tree-Like Precedence Constraints

Efficient Coordination Mechanisms for Unrelated Machine Scheduling