Envy-Free Makespan Approximation

2009/09/06 by Edith Cohen, Michal Feldman, Cohen, Edith +7
Computer Science · #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #cs.GT

paper · pdf · doi:10.48550/arxiv.0909.1072

arxiv created 2009/09/06 · arxiv updated 2009/12/01

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(log m), where m is the number of machines. We also show a lower bound of Ω(log m / loglog m). This improves the recent result of Hartline \sl et al. \citeAhuva: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.

Related

• Tight Lower Bounds on Envy-Free Makespan Approximation
• Lower Bound for Envy-Free and Truthful Makespan Approximation on Related Machines
• Proportionally Fair Makespan Approximation
• A New Lower Bound for Deterministic Truthful Scheduling
• Prior-Independent Mechanisms for Scheduling