Fair Interval Scheduling for Multi-Agent Resource Allocation

Fair scheduling of shared computing resources aims to provide equitable access to competing groups while maintaining high throughput. We model this problem as offline interval scheduling, where each request belongs to a group, occupies a fixed time window, and competes with overlapping requests for exclusive access to a resource. To account for heterogeneous demand and conflicts within groups, we measure each group’s allocation against its standalone optimum, defined as the maximum number of its requests that can be scheduled in isolation. Our main result characterizes the optimal worst-case trade-off between fairness and throughput. For $k$ groups and integer-endpoint intervals with lengths between $1$ and $\Delta$, we give an efficient randomized algorithm that guarantees every group at least a $1/\alpha$ fraction of its standalone optimum in expectation and achieves an approximation ratio of $\frac{\alpha \Delta }{(\alpha -k+1)\Delta +k-1}$ for every $\alpha \ge k$. We establish a matching lower bound, proving that this trade-off is optimal. The algorithm randomly selects between a maximum-throughput schedule and schedules that guarantee individual groups their standalone optima, with carefully chosen probabilities that meet the fairness requirements. We also develop deterministic algorithms that guarantee each group a proportional share of its standalone optimum, rounded down to an integer. In particular, for two groups, we establish a tight throughput guarantee. We also evaluate the algorithms on workload-derived instances to examine how the relationship between group membership and request structure affects fairness and throughput.