Citation:
Edith Cohen, Michal Feldman, Amos Fiat Haim Kaplan, and Svetlana Olonetsky. “Envy-Free Makespan Approximation”. Discussion Papers 2010. Web.
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(log m/log logm). This improves the recent result of Mu'alem [22] 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. Finally, we demonstrate how our mechanism for envy free makespan minimization can be interpreted as a market clearing problem.