Copula-based randomized mechanisms for truthful scheduling on two unrelated machines

DOI10.1007/978-3-642-41392-6_20zbMATH Open1319.91053arXiv1306.3909OpenAlexW2563330249MaRDI QIDQ2856147FDOQ2856147

Authors: Luis Fernando Zuluaga, Xujin Chen, Donglei Du 

Publication date: 23 October 2013

Published in: Algorithmic Game Theory (Search for Journal in Brave)

Abstract: We design a Copula-based generic randomized truthful mechanism for scheduling on two unrelated machines with approximation ratio within $[1.5852,1.58606]$, offering an improved upper bound for the two-machine case. Moreover, we provide an upper bound 1.5067711 for the two-machine two-task case, which is almost tight in view of the lower bound of 1.506 for the scale-free truthful mechanisms [4]. Of independent interest is the explicit incorporation of the concept of Copula in the design and analysis of the proposed approximation algorithm. We hope that techniques like this one will also prove useful in solving other problems in the future.

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

Recommendations

• Copula-based randomized mechanisms for truthful scheduling on two unrelated machines
• An improved randomized truthful mechanism for scheduling unrelated machines
• Truthful mechanisms for two-range-values variant of unrelated scheduling
• New bounds for truthful scheduling on two unrelated selfish machines
• A Characterization of 2-Player Mechanisms for Scheduling

zbMATH Keywords

copulaalgorithmic mechanism designrandom mechanismtruthful scheduling

Mathematics Subject Classification ID

Characterization and structure theory for multivariate probability distributions; copulas (62H05) Deterministic scheduling theory in operations research (90B35) Applications of game theory (91A80) Auctions, bargaining, bidding and selling, and other market models (91B26)

Cited In (3)

• An improved randomized truthful mechanism for scheduling unrelated machines
• Truthful mechanisms for two-range-values variant of unrelated scheduling
• Copula-based randomized mechanisms for truthful scheduling on two unrelated machines

This page was built for publication: Copula-based randomized mechanisms for truthful scheduling on two unrelated machines

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