Fair Division Meets Scheduling: Approximately Envy-Free Interval Scheduling

Abstract

We study interval scheduling from the perspective of fair allocation. There are $m$ identical machines and a set of intervals, each specified by a start time, an end time, and a nonnegative weight. A schedule assigns a subset of the intervals to the machines so that no two intervals on the same machine overlap, and the goal is to maximize the total weight of scheduled intervals. Viewing machines as agents and intervals as goods, we require the schedule to be envy-free up to one item (EF1), and we measure efficiency against the offline optimum without fairness. In the offline setting, we give an algorithm that computes an EF1 schedule whose loss is at most a factor of $3/2$ in the unweighted regime, and we prove lower bounds of $\frac{3m-2}{2m-1}$, approaching $3/2$, in both the unweighted and the unit-length weighted regimes, so the price of fairness is $3/2$ in the limit. In the online setting, intervals arrive in nondecreasing order of start times; an arriving interval must be accepted or rejected, rejections are irrevocable, and an accepted interval may be revoked, and lost, at any time before it ends. For the unweighted regime we present Greedy-Balanced, a simple algorithm that maintains EF1 at every point in time and is $(2-\frac{1}{m})$-competitive against the offline optimum without fairness, and we prove a matching lower bound for every deterministic algorithm; the optimal deterministic fair competitive ratio is thus exactly $2-\frac{1}{m}$. Experiments on real-world benchmark instances show that Greedy-Balanced performs well beyond its worst-case guarantee, with an observed ratio never exceeding $1.306$.