Journal article
The VCG mechanism for Bayesian scheduling
- Abstract:
- We study the problem of scheduling m tasks to n selfish, unrelated machines in order to minimize the makespan, where the execution times are independent random variables, identical across machines. We show that the VCG mechanism, which myopically allocates each task to its best machine, achieves an approximation ratio of O(ln n/ln ln n). This improves significantly on the previously best known bound of O (m/n) for prior-independent mechanisms, give by Chawla et al. [STOC'13] under the additional assumption of Monotone Hazard Rate (MHR) distributions. Although we demonstrate that this is in general tight, if we do maintain the MHR assumption, then we get improved, (small) constant bounds for m ≥ n ln n i.i.d. tasks, while we also identify a sufficient condition on the distribution that yields a constant approximation ratio regardless of the number of tasks.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, pdf, 373.7KB, Terms of use)
-
- Publisher copy:
- 10.1145/3105968
Authors
- Publisher:
- Association for Computing Machinery
- Journal:
- ACM Transactions on Economics and Computation More from this journal
- Volume:
- 5
- Issue:
- 4
- Pages:
- 19
- Publication date:
- 2017-12-01
- Acceptance date:
- 2017-03-21
- DOI:
- ISSN:
-
2167-8375 and 2167-8383
- Pubs id:
-
pubs:687157
- UUID:
-
uuid:f0b283b1-dc61-40f8-83b6-5eabab91c4ca
- Local pid:
-
pubs:687157
- Source identifiers:
-
687157
- Deposit date:
-
2017-03-25
Terms of use
- Copyright holder:
- Association for Computing Machinery
- Copyright date:
- 2017
- Notes:
- © 2017 ACM. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
If you are the owner of this record, you can report an update to it here: Report update to this record