The VCG Mechanism for Bayesian Scheduling

DOI10.1007/978-3-662-48995-6_25MaRDI QIDQ3460800zbMATH OpenOpenAlexFDO

Authors Yiannis Giannakopoulos, Maria Kyropoulou

Publication date 8 January 2016

Published in Web and Internet Economics (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial 4.0 International

Full work available at URL https://arxiv.org/abs/1509.07455

zbMATH Keywords

Bayesian schedulingmonotone hazard rate distributionsVCG mechanism

Mathematics Subject Classification ID

Bayesian problems; characterization of Bayes procedures (62C10) Deterministic scheduling theory in operations research (90B35)

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 $Oleft(fraclnnlnlnnight)$. This improves significantly on the previously best known bound of $Oleft(fracmnight)$ 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 $mgeqnlnn$ 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.

Recommendations

• scientific article; zbMATH DE number 1941939
• Euro-Par 2004 Parallel Processing
• A Bayesian Approach to Batch Process Scheduling
• A BAYESIAN SEQUENTIAL SINGLE MACHINE BATCHING AND SCHEDULING PROBLEM WITH RANDOM SETUP TIME
• Prior-independent mechanisms for scheduling
• Bayesian truthful mechanisms for job scheduling from bi-criterion approximation algorithms
• Sensitivity analysis for bayesian models in stochastic scheduling
• Stochastic scheduling and forwards induction
• A theoretic and practical framework for scheduling in a stochastic environment

Cites work

• A deterministic truthful PTAS for scheduling related machines
• A lower bound for scheduling mechanisms
• A lower bound of \(1+\varphi \) for truthful scheduling mechanisms
• Algorithmic mechanism design
• An improved randomized truthful mechanism for scheduling unrelated machines
• Approximation algorithms for scheduling unrelated parallel machines
• Bayesian truthful mechanisms for job scheduling from bi-criterion approximation algorithms
• Computationally feasible VCG mechanisms
• scientific article; zbMATH DE number 1301967 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• Incentives in Teams
• On the limits of black-box reductions in mechanism design
• On weighted balls-into-bins games
• Optimal lower bounds for anonymous scheduling mechanisms
• Prior-independent mechanisms for scheduling
• Properties of Probability Distributions with Monotone Hazard Rate
• Revenue maximization with a single sample
• Revenue submodularity
• The VCG Mechanism for Bayesian Scheduling
• Truthful approximation schemes for single-parameter agents
• Truthful mechanism design for multidimensional scheduling via cycle monotonicity
• Truthful mechanisms for two-range-values variant of unrelated scheduling
• Upper (lower) bounds on the mean of the maximum (minimum) of a number of random variables

Cited in

(7)

• Setting lower bounds on truthfulness
• No truthful mechanism can be better than n approximate for two natural problems
• Optimal pricing for MHR distributions
• The VCG Mechanism for Bayesian Scheduling
• Trust-based mechanisms for robust and efficient task allocation in the presence of execution uncertainty
• A new lower bound for deterministic truthful scheduling
• A proof of the Nisan-Ronen conjecture

This page was built for publication: The VCG Mechanism for Bayesian Scheduling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3460800)