Research Repository

The VCG mechanism for Bayesian scheduling

Giannakopoulos, Yiannis and Kyropoulou, Maria (2015) The VCG mechanism for Bayesian scheduling. In: Web and Internet Economics 11th International Conference, WINE 2015, 2015-12-09 - 2015-12-12, Amsterdam.

1509.07455v3.pdf - Accepted Version

Download (572kB) | Preview


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.

Item Type: Conference or Workshop Item (Paper)
Additional Information: Published proceedings: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Uncontrolled Keywords: cs.GT
Divisions: Faculty of Science and Health
Faculty of Science and Health > Computer Science and Electronic Engineering, School of
SWORD Depositor: Elements
Depositing User: Elements
Date Deposited: 24 Mar 2022 18:47
Last Modified: 24 Mar 2022 18:47

Actions (login required)

View Item View Item