Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

VCG is the best anonymous scheduling mechanism

VCG is the best anonymous scheduling mechanism VCG is the Best Anonymous Scheduling Mechanism Itai Ashlagi Harvard and Shahar Dobzinski The School of Computer Science and Engineering, The Hebrew University of Jerusalem and Ron Lavi Faculty of Industrial Engineering and Management, The Technion, Israel 1. INTRODUCTION In a mechanism for scheduling on unrelated machines there are n jobs which should be assigned to m machines, where it takes machine i tj time units to process job i j (and this is also the cost machine i incurs to process job j). The processing times are private information of the machines. The load of machine i is the sum of processing times of the jobs i is assigned. The goal is to design a truthful mechanism which allocates the jobs such that the makespan, which is the maximal load over all machines, is minimized. A mechanism is truthful if it is a dominant strategy for every machine to report its true processing times. This problem has been introduced by Nisan and Ronen [1999]. Nisan and Ronen show that the VCG mechanism achieves an approximation ratio of m, and also show that no mechanism, even one with unlimited computational power, can guarantee an approximation ratio better than http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM SIGecom Exchanges Association for Computing Machinery

VCG is the best anonymous scheduling mechanism

Download PDF
2 pages

Loading next page...
 
/lp/association-for-computing-machinery/vcg-is-the-best-anonymous-scheduling-mechanism-5PNuAPQQul
Publisher
Association for Computing Machinery
Copyright
The ACM Portal is published by the Association for Computing Machinery. Copyright © 2010 ACM, Inc.
Subject
Scheduling
ISSN
1551-9031
DOI
10.1145/1598780.1598784
Publisher site
See Article on Publisher Site

Abstract

VCG is the Best Anonymous Scheduling Mechanism Itai Ashlagi Harvard and Shahar Dobzinski The School of Computer Science and Engineering, The Hebrew University of Jerusalem and Ron Lavi Faculty of Industrial Engineering and Management, The Technion, Israel 1. INTRODUCTION In a mechanism for scheduling on unrelated machines there are n jobs which should be assigned to m machines, where it takes machine i tj time units to process job i j (and this is also the cost machine i incurs to process job j). The processing times are private information of the machines. The load of machine i is the sum of processing times of the jobs i is assigned. The goal is to design a truthful mechanism which allocates the jobs such that the makespan, which is the maximal load over all machines, is minimized. A mechanism is truthful if it is a dominant strategy for every machine to report its true processing times. This problem has been introduced by Nisan and Ronen [1999]. Nisan and Ronen show that the VCG mechanism achieves an approximation ratio of m, and also show that no mechanism, even one with unlimited computational power, can guarantee an approximation ratio better than

Journal

ACM SIGecom Exchanges – Association for Computing Machinery

Published: Jul 1, 2009

There are no references for this article.