Research Repository

The VCG Mechanism for Bayesian Scheduling

Giannakopoulos, Yiannis and Kyropoulou, Maria (2017) 'The VCG Mechanism for Bayesian Scheduling.' ACM Transactions on Economics and Computation, 15 (4). pp. 1-16. ISSN 2167-8375

1509.07455.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, 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&frac; ln ln n). This improves significantly on the previously best known bound of O(m/n) 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 for m ≥ n ln n 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.

Item Type: Article
Uncontrolled Keywords: Scheduling; Bayesian mechanism design; VCG mechanism; balls-in-bins
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
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: 02 Mar 2018 13:48
Last Modified: 24 Mar 2022 18:42

Actions (login required)

View Item View Item