Envy-free makespan approximation

DOI10.1137/100801597MaRDI QIDQ2884571zbMATH OpenOpenAlexFDO

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

Publication date 30 May 2012

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

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

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)

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.

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

Cited in

(7)

• Fair by design: multidimensional envy-free mechanisms
• Lower bound for envy-free and truthful makespan approximation on related machines
• A lower bound of \(1+\varphi \) for truthful scheduling mechanisms
• Combinatorial Walrasian equilibrium
• The price of envy-freeness in machine scheduling
• The price of envy-freeness in machine scheduling
• On Multi-dimensional 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)