Envy-free makespan approximation: extended abstract

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

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 / log log m). 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.
BibTeX
@inproceedings{cohen2010envy,
  author = {Edith Cohen and Michal Feldman and Amos Fiat and Haim Kaplan and Svetlana Olonetsky},
  title = {{Envy-free makespan approximation: extended abstract}},
  booktitle = {EC},
  year = {2010},
  url = {https://openreview.net/forum?id=26h1o90ud2w},
}
Figure