Envy-Free Makespan Approximation

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 $\Omega(\log m / \log\log m)$. This improves the recent result of Hartline et al. 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.

Introduction

The tension between fairness and efficiency is a central theme in algorithmic mechanism design. In task scheduling on unrelated machines, the goal is typically to minimize the makespan—the time when the last task is completed. However, when machines are controlled by self-interested agents, fairness becomes a critical requirement.

A standard fairness criterion is envy-freeness: an allocation where no agent would prefer another's assigned tasks and payments over their own. While payments can compensate agents for harder tasks, enforcing envy-freeness often leads to a "price of fairness"—an increase in the makespan compared to the social optimum. Previous work suggested this price could be as high as $O(m)$, where $m$ is the number of machines. This paper investigates whether a more efficient balance can be struck.

Characterizing Envy-Freeness

A fundamental insight utilized in this work is the characterization of envy-free implementability through local efficiency. An allocation is envy-free implementable if and only if it minimizes the total cost across all possible permutations of the assigned task bundles. This geometric property allows the problem of finding an envy-free schedule to be reframed as finding a locally efficient assignment with a small makespan.

Indivisible Tasks: The FIND-APPROX Algorithm

For indivisible tasks, the authors propose the FIND-APPROX algorithm, which achieves an $O(\log m)$ approximation. The algorithm operates in iterative phases:

  1. Bundling: It begins with an optimal (though potentially unfair) allocation, treating tasks assigned to each machine as a single bundle.
  2. Iterative Filtering: In each phase, it identifies a locally efficient assignment of the remaining bundles. If a machine's load exceeds twice the optimal makespan ($2 \times OPT$), those bundles are discarded and deferred to the next phase.
  3. Union: The final schedule is the union of assignments from all phases.

The logarithmic approximation factor arises because at most half the bundles are discarded in each phase. Since there are $m$ bundles, the process terminates in $O(\log m)$ phases, with each phase contributing at most $2 \times OPT$ to the total makespan.

Divisible Tasks and Optimal Efficiency

A significant result of this research is that for divisible tasks, the price of fairness vanishes. The authors prove that a lexicographically minimal assignment—one that minimizes the maximum load, then the second-highest, and so on—is inherently locally efficient. Consequently, there always exists a polynomial-time envy-free mechanism that achieves the optimal makespan (a 1-approximation).

Lower Bounds and the Price of Fairness

The paper significantly tightens the lower bounds for indivisible tasks. While previous knowledge suggested a lower bound of $2 - 1/m$, this work proves a much stronger bound of $\Omega(\log m / \log \log m)$. This suggests that a logarithmic gap between the optimal makespan and an envy-free one is likely unavoidable.

The complex cost matrix used to establish the lower bound for indivisible tasks.

The proof of this lower bound relies on the construction of a specific, intricate cost matrix (shown above) that forces any locally efficient assignment to have a large makespan relative to the optimum.

Summary of Results

The following table summarizes the improvements made over previous bounds:

Task Type Previous Upper Bound New Upper Bound New Lower Bound
Divisible $1 + (m-1)/2$ 1 (Optimal) 1
Indivisible $(m+1)/2$ $O(\log m)$ $\Omega(\frac{\log m}{\log \log m})$

Conclusion and Future Work

This work narrows the efficiency gap for envy-free scheduling from $O(m)$ to $O(\log m)$. However, a small gap remains between the $O(\log m)$ upper bound and the $\Omega(\log m / \log \log m)$ lower bound. Future research may focus on closing this gap or exploring the intersection of envy-freeness with truthfulness (incentive compatibility). While envy-freeness ensures fairness given reported costs, ensuring agents report their costs truthfully is a significantly harder problem with known lower bounds of $\Omega(m)$. Additionally, the magnitude of payments required to maintain envy-freeness remains an open area for investigation.

Summary updated

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