Envy-free makespan approximation

DOI10.1137/100801597zbMATH Open1238.91013arXiv0909.1072OpenAlexW2081331628MaRDI QIDQ2884571FDOQ2884571

Haim Kaplan, Edith Cohen, Svetlana Olonetsky, Michal Feldman, Amos Fiat

Publication date: 30 May 2012

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Abstract: We study envy-free mechanisms for scheduling tasks on unrelated machines (agents) that approximately minimize the makespan. For indivisible tasks, we put forward an envy-free poly-time mechanism that approximates the minimal makespan to within a factor of $O(logm)$, where $m$ is the number of machines. We also show a lower bound of $Omega(logm/loglogm)$. This improves the recent result of Hartline {sl et al.} cite{Ahuva:2008} who give an upper bound of $(m+1)/2$, and a lower bound of $2-1/m$. For divisible tasks, we show that there always exists an envy-free poly-time mechanism with optimal makespan.

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

Recommendations

• Fair by design: multidimensional envy-free mechanisms
• Lower bound for envy-free and truthful makespan approximation on related machines
• The price of envy-freeness in machine scheduling
• The price of envy-freeness in machine scheduling
• On Multi-dimensional Envy-Free Mechanisms

zbMATH Keywords

schedulingenvy-freealgorithmic mechanism design

Mathematics Subject Classification ID

(n)-person games, (n>2) (91A06) Computational methods for problems pertaining to game theory, economics, and finance (91-08)

Cited In (5)

• On Multi-dimensional Envy-Free Mechanisms
• A lower bound of \(1+\varphi \) for truthful scheduling mechanisms
• Combinatorial Walrasian Equilibrium
• The price of envy-freeness in machine scheduling
• Fair by design: multidimensional envy-free mechanisms

This page was built for publication: Envy-free makespan approximation

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