acceptodds
Under review as a conference paper at ICLR 2027

Fair Interval Scheduling for Multi-Agent Resource Allocation

Abstract

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 groups and integer-endpoint intervals with lengths between and , we give an efficient randomized algorithm that guarantees every group at least a fraction of its standalone optimum in expectation and achieves an approximation ratio of for every . 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.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
combinatorial optimization, fair resource allocation, interval scheduling, approximation algorithms, price of fairness

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_NWFYOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies 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. This paper characterizes the optimal worst-case trade-off between fairness and throughput and establishes a matching lower bound, proving that this trade-off is optimal. This paper also develops deterministic algorithms that guarantee each group a proportional share of its standalone optimum, rounded down to an integer, and algorithms were evaluated on workload-derived instances.

Critical strengths

The motivation is clear, the theoretical results are strong, and the empirical evaluation is good.

Critical weaknesses
  • This is a classical scheduling/operations-research paper. It does not study representation learning, deep learning, or core machine learning. While ICLR accepts theory, the topic and techniques are far from the typical ICLR audience.

  • For ex post result, although the bound is tight for k=2k=2, there exist a gap for general number of groups.

  • The claim on the difference with Bhore et al. (2021) is unclear. They study the independent set in interval graphs, with color, which is the same as the setting in this paper. The main difference should be the fairness concept, however, the paper does not clarify this well in related work.

Monor:
The conclusion section is missing.

Questions for authors

How is this paper related to representation learning, deep learning, or core machine learning?

3 comments
AuthorsOpenReview ↗

Response to Reviewer NWFY on Relevance to ICLR, Deterministic Guarantees, and Relation to Bhore et al.

Thank you for the careful review and for highlighting the motivation, theoretical results, and empirical evaluation. We appreciate the opportunity to clarify the connection to ICLR and to explain how our fairness criterion relates to prior work.

W1/Q1. Relevance to ICLR. Our connection to deep learning is through the shared infrastructure used to train models. When several teams request fixed windows on a shared GPU server, the scheduler must decide which reservations to admit and how much access to guarantee each team. Systems such as Themis and Gavel motivate this question by studying fairness and efficiency in scheduling ML workloads (Section 1). Our paper isolates the fixed-reservation admission problem and gives a tight bound on how much throughput can be retained while guaranteeing each group an expected share of its standalone service (in a randomized setting). This connects to fairness, optimization, and infrastructure, all listed in the ICLR 2027 Call for Papers. Section 2 also discusses related fair-scheduling work at ICLR (Zhao et al., 2025) and NeurIPS (Li et al., 2021).

W2. Deterministic guarantees for more than two groups. We agree that the optimal guarantee for rounded quotas remains open for general kk. Theorem 5.1 gives the tight result for two groups. For k≥3k\ge3 and α=k\alpha=k, BPA achieves an approximation ratio of at most min⁡(Δ,(3k−3)/2)\min(\Delta,(3k-3)/2), and Appendix A.5 gives lower bounds that can leave a gap. In our workload experiments at k=10k=10, BPA's and GPSA's mean approximation ratios are within 0.01 under each of the three original assignments (Table 7). For fairness in expectation, Theorem 4.1 gives matching worst-case bounds for every kk.

W3. Relation to Bhore et al. (2021). We agree that the two papers share the same interval-selection structure and that the distinction is in the fairness criterion. Bhore et al. ask whether an independent set can contain a prescribed, equal number of intervals from each color. The main difference is that we set each group's target using its standalone optimum, OPTg\mathrm{OPT}_g. The target is OPTg/α\mathrm{OPT}_g/\alpha in expectation or ⌊OPTg/α⌋\lfloor\mathrm{OPT}_g/\alpha\rfloor in every output. This formulation lets us ask how much of the unrestricted throughput can be retained while meeting those targets (Sections 2, 4, and 5). Appendix A.7 adapts their dynamic program to maximize throughput subject to unequal quotas.

The missing Conclusion section. Thank you for pointing out the missing conclusion. We added Section 7 to summarize the main results and identify the remaining open questions.

Thank you for the response. I am raising my score, even though I am not sure whether this paper is within the scope of ICLR.

Dear Reviewer,

Thank you for reconsidering your evaluation in light of our response. We are pleased that our clarifications have been helpful and appreciate your willingness to increase your score.

Thank you again for your constructive feedback and positive assessment of our work.

Reviewer_uJnTOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies group fairness in offline interval scheduling on a single resource, measuring each group's service relative to its standalone optimum. The authors propose GPSA, which mixes a throughput-optimal schedule with group-protecting schedules, and prove matching upper and lower bounds on the worst-case fairness–throughput trade-off under expected fairness. They also develop deterministic algorithms for rounded-down quotas, with tight guarantees for two groups. Experiments on four workload-derived interval sets show favorable empirical fairness–throughput trade-offs.

Critical strengths
  1. Matching upper and lower bounds characterize the optimal worst-case fairness–throughput trade-off under the paper's expected fairness criterion.

  2. Experiments on workload-derived instances with tens of thousands to over a hundred thousand requests show a favorable trade-off between group fairness and throughput.

Critical weaknesses
  1. The limited baseline comparison and lack of ablations leave the sources of GPSA’s empirical gains unclear.
Questions for authors
  1. How does GPSA compare with processing groups in a uniformly random order and applying earliest-finish-time greedy within each group, accepting only requests compatible with those already selected? At α=k\alpha=k, this baseline provides the same expected fairness guarantee while also admitting compatible requests from other groups.

  2. Could the authors isolate the contribution of greedy completion by keeping GPSA’s sampling probabilities fixed and omitting completion from the protection schedules? This variant preserves the expected fairness guarantee and would help quantify how much of the throughput improvement comes from completion.

  3. Could the authors clarify which algorithmic or analytical ideas are new relative to prior fair interval scheduling work, and how these ideas enable the tight fairness–throughput bounds?

2 comments
AuthorsOpenReview ↗

Response to Reviewer uJnT on the Random-Order Baseline, Completion Ablation, and Novelty

Thank you for the careful review and for suggesting two concrete ways to clarify the source of GPSA's empirical gains. We implemented both experiments in the revision.

Q1. Comparison with random-order greedy.

We added the baseline you suggested in Appendix B.7. It processes groups in a uniformly random order and applies earliest-finish-time greedy within each group to requests compatible with the current schedule. As you noted, each group is processed first with probability 1/k1/k, so both algorithms guarantee at least OPTg/k\mathrm{OPT}_g/k requests for every group in expectation.

At k=α=10k=\alpha=10, GPSA lowers the mean approximation ratio by 21.99%, 13.13%, and 17.34% under containment-, length-, and log-length-based assignments, respectively. The table below (Table 4 in the revised paper) reports the mean approximation ratio / mean fairness ratio for each algorithm, averaged over four workload traces.

AlgorithmContainment-basedLength-basedLog-length-based
Random-order greedy1.5158 / 4.76071.3533 / 5.21241.3971 / 6.7367
GPSA1.1824 / 10.14131.1756 / 7.11391.1549 / 10.0509
Adaptive GPSA (θ=0.90\theta=0.90)1.3367 / 5.80031.3284 / 5.04021.3133 / 5.7970

We also examine how lowering the instance-dependent parameter αθ\alpha_\theta strengthens the expected-fairness guarantee. Across the tested settings, this improves empirical fairness at the cost of a higher mean approximation ratio. At θ=0.90\theta=0.90, the adaptive variant improves both ratios over random-order greedy for length-based groups (1.84% and 3.30%) and log-length-based groups (6.00% and 13.95%), respectively.

Q2. Contribution of greedy completion.

We added the ablation you suggested in Appendix B.6. GPSA without completion holds GPSA's sampling probabilities fixed and returns the standalone optimum whenever it selects a protection schedule. As you anticipated, this preserves the expected-fairness guarantee. Table 3 in the paper gives the following mean ratios at k=α=10k=\alpha=10.

AlgorithmContainment approx. / fair.Length approx. / fair.Log-length approx. / fair.
Uniform group sampling (UGS)7.0729 / 10.15337.0000 / 10.15337.3186 / 10.1533
GPSA without completion1.6702 / 10.14131.5480 / 7.49381.6362 / 10.0623
GPSA1.1824 / 10.14131.1756 / 7.11391.1549 / 10.0509

With the sampling probabilities fixed, completion lowers the mean approximation ratio by 29.2%, 24.1%, and 29.4%, respectively. For length-based groups, it also lowers the mean fairness ratio from 7.4938 to 7.1139. With completion disabled, switching from UGS to GPSA's sampling rule lowers the mean approximation ratio by 76.4%, 77.9%, and 77.6%, respectively. These are successive comparisons, since the benefit of completion depends on the schedule selected. Fairness ratios slightly above 10 reflect finite-sample variation.

Q3. Novelty and why the bounds match. In this paper, we characterize how much unrestricted throughput can be guaranteed when each group must receive a fraction of its standalone optimum in expectation. Section 2 relates this fairness objective to prior work. We added a note at the end of Section 2 explaining the main novelty of GPSA: its sampling rule. GPSA gives more weight to protection schedules for groups that receive a smaller share of their standalone optimum in the unrestricted schedule. The sampling rule still selects the unrestricted optimum with probability at least (α−k+1)/α(\alpha-k+1)/\alpha, and standard greedy completion ensures that each protection schedule serves at least OPT/Δ\mathrm{OPT}/\Delta requests. The matching lower bound shows that the same fairness requirement can force any randomized algorithm to accept long requests that displace multiple short ones (Theorems 4.4 and 4.5).

Dear Reviewer,

As the discussion period is approaching its end, we wanted to kindly follow up and ask whether our rebuttal and the additional experiments have addressed your questions.

In particular, we have included the random-order greedy baseline you suggested, isolated the contribution of greedy completion, and clarified the novelty of our theoretical results relative to previous work.

We would appreciate any further feedback and would be grateful if you could revisit your evaluation in light of these additions.

Thank you again for your time and constructive suggestions.

Reviewer_geHZOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper is well written and well organized, with solid theoretical analysis. It studies the trade-off between fairness and throughput in offline interval scheduling and proposes a randomized algorithm called GPSA. The authors prove its optimal worst-case approximation ratio with a matching lower bound. The paper also presents deterministic fair scheduling algorithms and evaluates their performance using workload-derived instances.

Critical strengths

1.Theorems 4.4 and 4.5 establish matching upper and lower bounds, showing the optimal trade-off between fairness and throughput. GPSA also achieves an efficient running time of . 2.The paper is well organized and provides detailed proofs. It considers both randomized and deterministic fairness. For example, Theorem 5.1 gives a tight approximation bound for two groups, and experiments on four workload traces provide useful supporting results.

Critical weaknesses

1.The paper assumes offline scheduling with fixed intervals and a single resource, which may not fully reflect real scheduling systems. In Section 6, groups are created based on interval features rather than actual user identities, making the practical value of the results less clear. 2.Figure 1 shows that GPSA achieves higher throughput than Uniform Group Sampling (UGS). However, UGS does not use the greedy completion step included in GPSA. An ablation study would help clarify the contributions of adaptive sampling and greedy completion. In addition, the experiments mainly report average fairness without analyzing how often individual schedules fall below the fairness targets.

Questions for authors

1.The paper measures fairness by the number of accepted requests. When groups have very different request durations, would measuring fairness by resource usage time lead to different theoretical or practical results? 2.How much of GPSA's improvement comes from adaptive sampling rather than greedy completion? Could the authors compare GPSA with uniformly sampled, greedily completed group schedules at ? 3.GPSA guarantees fairness in expectation, but individual schedules may fall below the fairness targets. Could the authors report how often these shortfalls occur? Also, how should GPSA and BPA be compared given their different fairness guarantees?

2 comments
AuthorsOpenReview ↗

Response to Reviewer geHZ on Group Construction, Duration-Based Fairness, Ablation, and Per-Schedule Shortfalls

Thank you for the careful review and for identifying where the experimental comparisons needed to be clearer. Your question about resource usage also led us to extend the tight fairness–throughput trade-off to total accepted duration.

W1. Model scope and group construction. In response to your concern about group construction, we added three assignments in Appendix B.8. Uniform and Zipf draw group labels independently of interval features, with equal and unequal expected request volumes, respectively. Request-count uses the actual trace user IDs: it sorts users by submission count, divides them into groups with roughly equal numbers of users, and keeps all requests from each user in the same group.

At k=α=10k=\alpha=10, Global Greedy already meets every group's fairness target on all 12 instances, so GPSA returns the same schedule and attains an approximation ratio of 1 on every instance. Under Uniform, Request-count, and Zipf, GPSA's mean fairness ratios are 1.6301, 1.6307, and 1.8787, compared with 10.1533 for UGS under each assignment. The corresponding UGS mean approximation ratios are 6.3817, 8.0338, and 6.7150 (Table 5). At the same fairness target, GPSA's mean approximation ratios range from 1.1549 to 1.1824 under the three original interval-based assignments (Table 3). In summary, GPSA outperforms UGS on both mean approximation and fairness ratios under all three alternative assignments, including the one built from actual trace user IDs.

We agree that the offline model in this paper captures a specific scheduling decision: which fixed reservations to admit to a single shared resource. The experiments use real submission times and job durations to study this decision, and Theorem 4.1 gives the tight worst-case fairness–throughput trade-off within this model.

Q1. Fairness measured by accepted duration. We evaluated your suggestion by implementing GPSA-D and UGS-D, which use total accepted duration both as the throughput objective and as the measure of service to each group.

Under containment-, length-, and log-length-based assignments, GPSA-D's mean approximation ratios are 1.0905, 1.2309, and 1.1735, compared with 4.5401, 5.1585, and 4.9959 for UGS-D. GPSA-D’s mean fairness ratios are 4.6153, 4.7902, and 5.0516, compared with 10.1533 for UGS-D under each assignment (Table 6). The exact expected fairness ratio for UGS-D is 10, and the difference reflects finite-sample variation.

Theoretical result. For every α≥k\alpha\ge k, we prove that the optimal worst-case approximation ratio for total accepted duration on the unit grid is αΔ/((α−k+1)Δ+k−1)\alpha\Delta/((\alpha-k+1)\Delta+k-1) among randomized algorithms that are α\alpha-fair in expectation. GPSA-D attains this ratio, and a matching lower bound applies to every randomized algorithm with the same fairness guarantee (Appendix B.9).

W2/Q2. Adaptive sampling and greedy completion. We added an ablation in Appendix B.6 that compares uniform group sampling (UGS), GPSA without completion, and full GPSA. The table below reports mean approximation ratios at k=α=10k=\alpha=10, averaged over four workload traces for each group assignment. The first two columns compare sampling rules with completion disabled. The last two show the effect of adding greedy completion with GPSA's sampling probabilities fixed.

Group assignmentUGSGPSA without completionFull GPSA
Containment-based7.07291.67021.1824
Length-based7.00001.54801.1756
Log-length-based7.31861.63621.1549

Changing the sampling rule lowers the mean approximation ratio by 76.4–77.9%, and adding greedy completion lowers it by a further 24.1–29.4% (Table 3). All three variants satisfy the same expected-fairness guarantee. We also added random-order greedy as a separate baseline. GPSA achieves a lower mean approximation ratio under all three original assignments, while random-order greedy achieves a lower mean fairness ratio (Appendix B.7, Table 4).

W2/Q3. Shortfalls in individual schedules and comparison with BPA. We added per-schedule shortfall measurements at k=α=10k=\alpha=10 (Appendix B.10, Table 7). For containment-, length-, and log-length-based assignments, the mean percentage of groups below their unrounded target was 34.53%, 15.91%, and 20.23% for GPSA and 17.50%, 2.50%, and 2.50% for BPA, respectively. The corresponding mean shortfalls, measured as percentages of the target averaged over all groups, were 32.01%, 10.19%, and 15.99% for GPSA and 0.07%, 0.02%, and 2.50% for BPA.

The mean approximation ratios differ by less than 0.01 under each assignment. BPA also has smaller shortfalls in the least fair observed outcomes. BPA guarantees the rounded quota ⌊OPTg/k⌋\lfloor\mathrm{OPT}_g/k\rfloor in every schedule, keeping each group's deficit below one request. GPSA guarantees the target OPTg/k\mathrm{OPT}_g/k in expectation. On one log-length-based instance, BPA leaves a group with a zero rounded quota unserved.

Dear Reviewer,

As the discussion period is approaching its end, we wanted to kindly follow up and ask whether our rebuttal and revised manuscript have adequately addressed your concerns.

In response to your suggestions, we have substantially expanded the evaluation, including group assignments based on actual user identities, an ablation separating the contributions of adaptive sampling and greedy completion, and measurements of fairness shortfalls in individual schedules. We have also extended our tight theoretical characterization to fairness measured by total accepted duration.

We would appreciate it if you could revisit your evaluation in light of these additions. We would also be happy to address any remaining concerns.

Many thanks again for your constructive feedback and consideration.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response: summary of revisions

We thank all three reviewers for carefully reading our paper and for their useful suggestions. The revised paper and updated supplementary materials are now available on OpenReview. In response to the provided feedback, we expanded the experimental evaluation (Appendices B.6–B.10), extended the tight fairness–throughput characterization to total accepted duration (Appendix B.9), and added a conclusion (Section 7).

  • Ablation of sampling and greedy completion (Appendix B.6, Table 3). We added a GPSA variant that keeps the sampling probabilities fixed and omits greedy completion. At k=α=10k=\alpha=10, switching from uniform group sampling (UGS) to GPSA's sampling rule with completion disabled already reduces the mean approximation ratio by 76.4–77.9%. Adding greedy completion then reduces it by a further 24.1–29.4%. All three variants satisfy the same expected-fairness guarantee.

  • Comparison with random-order greedy (Appendix B.7, Table 4). We added the suggested baseline, which processes groups in a uniformly random order and uses a greedy approach to schedule each group's compatible requests. At k=α=10k=\alpha=10, GPSA meets the same expected-fairness target and achieves a 13.13–21.99% lower mean approximation ratio across the tested group assignments. We also investigate how tuning the instance-dependent parameter αθ\alpha_\theta strengthens the fairness target. At θ=0.90\theta=0.90, the adaptive variant achieves lower mean approximation and fairness ratios than random-order greedy for both length- and log-length-based groups.

  • Group assignments independent of interval features (Appendix B.8, Table 5). To study GPSA when requests are grouped using random labels or actual user IDs, we added three assignments: Uniform, Zipf, and Request-count. Request-count keeps all requests from each user in the same group. Under each assignment, GPSA achieves a lower mean approximation ratio than UGS while providing the same fairness guarantee in expectation.

  • Fairness measured by accepted duration (Appendix B.9, Table 6). The paper primarily studies how to maximize the number of accepted intervals under fairness constraints. That said, following the reviewer’s suggestion, we also adapted and evaluated GPSA and UGS using total accepted duration as both the throughput objective and the measure of service to each group. We prove that GPSA-D (the duration variant of GPSA) attains the same tight worst-case approximation ratio as in the request-count setting, with a matching lower bound. In the experiments, GPSA-D lowers the mean approximation ratio by 75.98–76.51% and the mean fairness ratio by 50.25–54.54% relative to UGS-D.

  • Shortfalls in individual schedules and comparison with BPA (Appendix B.10, Table 7). In the revised version, we now report the share of groups below target, the mean shortfall, and the least fair observed schedule. GPSA and BPA differ by less than 0.01 in mean approximation ratio under each assignment. BPA has smaller realized shortfalls and guarantees rounded quotas per schedule. GPSA guarantees unrounded targets in expectation, including for a group with a zero rounded quota that BPA leaves unserved.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.