Lower bound for envy-free and truthful makespan approximation on related machines

DOI10.1007/978-3-642-24829-0_16zbMATH Open1233.90154arXiv1107.2957OpenAlexW1573323211MaRDI QIDQ3095271FDOQ3095271

Authors: Lisa Fleischer, Zhenghui Wang 

Publication date: 28 October 2011

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

Abstract: We study problems of scheduling jobs on related machines so as to minimize the makespan in the setting where machines are strategic agents. In this problem, each job $j$ has a length $l_j$ and each machine $i$ has a private speed $t_i$. The running time of job $j$ on machine $i$ is $t_i{l}_j$. We seek a mechanism that obtains speed bids of machines and then assign jobs and payments to machines so that the machines have incentive to report true speeds and the allocation and payments are also envy-free. We show that 1. A deterministic envy-free, truthful, individually rational, and anonymous mechanism cannot approximate the makespan strictly better than $2-1/m$, where $m$ is the number of machines. This result contrasts with prior work giving a deterministic PTAS for envy-free anonymous assignment and a distinct deterministic PTAS for truthful anonymous mechanism. 2. For two machines of different speeds, the unique deterministic scalable allocation of any envy-free, truthful, individually rational, and anonymous mechanism is to allocate all jobs to the quickest machine. This allocation is the same as that of the VCG mechanism, yielding a 2-approximation to the minimum makespan. 3. No payments can make any of the prior published monotone and locally efficient allocations that yield better than an $m$-approximation for $qcmax$ cite{aas, at,ck10, dddr, kovacs} a truthful, envy-free, individually rational, and anonymous mechanism.

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

Recommendations

• STACS 2004
• Truthful approximation mechanisms for scheduling selfish related machines
• A unified approach to truthful scheduling on related machines
• Fair by design: multidimensional envy-free mechanisms
• Envy-free makespan approximation

zbMATH Keywords

envy-freemechanism designincentive compatiblemakespan approximation

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Applications of game theory (91A80)

Cited In (4)

• Envy-free makespan approximation
• The price of envy-freeness in machine scheduling
• The price of envy-freeness in machine scheduling
• Bayesian truthful mechanisms for job scheduling from bi-criterion approximation algorithms

This page was built for publication: Lower bound for envy-free and truthful makespan approximation on related machines

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