The VCG mechanism for Bayesian scheduling

Giannakopoulos Y, Kyropoulou M (2017)

Publication Type: Journal article

Publication year: 2017

Journal

ACM Transactions on Economics and Computation Association for Computing Machinery (ACM)

Book Volume: 5

Pages Range: 19:1--19:16

Article Number: 19

Journal Issue: 4

DOI: 10.1145/3105968

Open Access Link: http://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, in which 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(mn ) for prior-independent mechanisms, given by Chawla et al. [7] under the additional assumption of Monotone Hazard Rate (MHR) distributions. Although we demonstrate that this is tight in general, if we do maintain the MHR assumption, then we get improved, (small) constant bounds form = n lnn i.i.d. tasks. 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

Ioannis Giannakopoulos

Involved external institutions

The University of Liverpool GB United Kingdom (GB) University of Oxford GB United Kingdom (GB)

How to cite

APA:

Giannakopoulos, Y., & Kyropoulou, M. (2017). The VCG mechanism for Bayesian scheduling. ACM Transactions on Economics and Computation, 5(4), 19:1--19:16. https://dx.doi.org/10.1145/3105968

MLA:

Giannakopoulos, Yiannis, and Maria Kyropoulou. "The VCG mechanism for Bayesian scheduling." ACM Transactions on Economics and Computation 5.4 (2017): 19:1--19:16.

BibTeX: Download