The VCG mechanism for Bayesian scheduling
Giannakopoulos Y, Kyropoulou M (2015)
Publication Type: Conference contribution, Original article
Publication year: 2015
Journal
Publisher: Springer Verlag
Book Volume: 9470
Pages Range: 343-356
Conference Proceedings Title: Proceedings of the 11th Conference on Web and Internet Economics (WINE)
Event location: Amsterdam
ISBN: 9783662489949
DOI: 10.1007/978-3-662-48995-6_25
Open Access Link: https://arxiv.org/abs/1509.07455
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 (Formula presented). This improves significantly on the previously best known bound of (Formula presented) for prior-independent mechanisms, given 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.
Authors with CRIS profile
Involved external institutions
United Kingdom (GB)How to cite
APA:
Giannakopoulos, Y., & Kyropoulou, M. (2015). The VCG mechanism for Bayesian scheduling. In Guido Schäfer, Evangelos Markakis (Eds.), Proceedings of the 11th Conference on Web and Internet Economics (WINE) (pp. 343-356). Amsterdam, NL: Springer Verlag.
MLA:
Giannakopoulos, Yiannis, and Maria Kyropoulou. "The VCG mechanism for Bayesian scheduling." Proceedings of the 11th International Conference on Web and Internet Economics, WINE 2015, Amsterdam Ed. Guido Schäfer, Evangelos Markakis, Springer Verlag, 2015. 343-356.
BibTeX: Download