Fair Scheduling for Time-dependent Resources
Authors: Bo Li
Minming Li
Ruilong Zhang
Venue: NeurIPS 2021 Poster (2021)
Keywords: Fairness
Time-dependent resource
Maximin share
Envy-freeness

Abstract: We study a fair resource scheduling problem, where a set of interval jobs are to be allocated to heterogeneous machines controlled by intellectual agents.
Each job is associated with release time, deadline, and processing time such that it can be processed if its complete processing period is between its release time and deadline. 
The machines gain possibly different utilities by processing different jobs, and all jobs assigned to the same machine should be processed without overlap.
We consider two widely studied solution concepts, namely, maximin share fairness and envy-freeness.
For both criteria, we discuss the extent to which fair allocations exist and present constant approximation algorithms for various settings. 

Fair Scheduling for Time-dependent Resources
Bo Li
Minming Li
Department of Computing
Department of Computer Science
The Hong Kong Polytechnic University Hung Hom, Hong Kong comp-bo.
City University of Hong Kong
Kowloon Tang, Hong Kong minming. .wainngglieee li@ciiyyui edu hk
Ruilong Zhang +t
Department of Computer Science
City University of Hong Kong Kowloon Tang, Hong Kong
rui muilzhhng4-ccaa ccemy.
edu. .k
Abstract
We study a fair resource scheduling problem,nye mobee nwhere a set of interval jobs are to be allocated to heterogeneous machines controlled by intellectual agents. Each job is associated with release time. deadline and processing time such that it can be processed if its complete processing period is between its release time and deadline. The machines gain possibly different utilities by processing different jobs, and all jobs assigned to the same machine should be processed without overlap. We consider two widely studied solution concepts, namely, maximin share fairness and envy-freeness. For both criteria, we discuss the extent to which fair allocations exist and present constant approximation algorithms for various settings.
1 Introduction
With the rapid progress of AI technologies, Al algorithms are widely deployed in many societal settings such as the distribution of job and education opportunities where complex social effects may significantly diminish the performance of the algorithms. To motivate our study, let us consider a problem faced by the Students Affairs Office (SAO). An SAO clerk is assigning multiple part-time jobs to the students who submitted job applications. Each part-time job occupies a consecutive time period within possibly flexible interval. For example, an one-hour math tutorial needs be given between 8:00am and 11:00am on June 26th. A feasible assignment requires that the jobs assigned to an applicant can be scheduled without mutual overlap. The students students may hold different job preferences. It is important that the students are treated equally in terms of getting job opportunities, and thus the clerk's 's task is to make the assignment fair.
heterogeneous, i.e., different
The SAO problem falls under the umbrella of the research on job scheduling, which has been studied in numerous fields, including operations research Gentner al. [2004], machine learning Paleja et al. [2020], parallel computing Drozdowski [2009], cloud computing Al-Arasi and Saif [2020], etc. Following the convention of job scheduling research, each part-time job, job for short, is associated with release time, deadline, and processing time. The students are modeled as machines, who have different utility gains for completing jobs. Traditionally, the objective of designing scheduling algorithms is solely focused on efficiency or profit. However, motivated by various real-world AI driven deployments where the data points the algorithms are real human beings who should be
"Equal contribution CCorreppondigg author
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

treated unbiasedly, addressing the individual faimess becomes important. Accordingly, the past several years has seen considerable efforts in developing fair AI algorithms Chierichetti et al. [2017]. where combinatorial structures are incorporated into the design, such as vertex cover Rahmattalabi et al. [2019], facility location Chen et al. [2019] and knapsack Amanatidis el al. [2020].
It is noted that people have different criteria on evaluating fairesss, and in this work, we consider two of the most widely accepted definitions. The first is motivated by the max-min objective, i.e., maximizing the worst-case utility, which has received observable attention for various learning scenarios Rahmattalabi et al. [2019]. However, for heterogeneous agents, optimizing the worst case is not enough, as different people have different perspectives and may not agree on the output. Accordingly, one popular research agenda is centered around computing an assignment such that everyone believes that it (approximately) maximizes the worst case utility. This criterion is named maximin share (MMS) fairness in Budish [2010]. The second one envy-freeness (EF), which has been very widely studied in social sciences and economics but arguably less explored in machine learning. Informally, an assignment is called EF if everyone believes she has obtained the best resource compared with any other agent's 's assignment. We note that, due to the scheduling-feasibee constraint, some jobs may not be allocated. Thus EF alone is not able to satisfy the agents as keeping all resources unallocated does not incur any envy among them, but the agents envy the charity where umallocated//issegaadde items are assumed to be donated to a charity. To resolve this issue, in this work, want to understand how we can compute allocations that are simultancously EF and Pareto efficient (PO), where an allocation is called PO if there does not exist another allocation that makes nobody worse off but somebody strietly better off.
Recently, Chiarelli et al. [2020] and Hummel and Hetland [2021] studied the fair allocation of conflicting items, where the items are connected via graphs. An edge between two items means they are in conflict and should be allocated to different agents. However, in our model, the conflict among items cannot be described as the edges in graph. For example, two one-hour tutorials between 9:00am and 1 11:00m can be feasibly scheduled, but three such tutorials are not feasible any more. For comprehensive introduction to the various constraints, including conflict constraints, studied in fair division, we refer the interested reader to the recent survey of Suksompong [2021].
1.1 Main Results
We study the fair interval scheduling problem (FISP), where fairness is captured by MMS and EF. For each of them, we design approximation algorithms to compute MMS or EFI schedules.
Maximin Share. Informally, machine's 's MMS is defined to be her optimal worst-case utility in an imaginary experiment: she partitions the items into mn bundles but was the last to select one, where m is the number of agents. It is noted that as the machines are heterogeneous, they may not have the same MMS value. Our task is to investigate the extent to which everyone agrees on the final allocation. A job assignment is called a- a-approximate MMS fair if every machine's utility is no less than a fraction of her MMS value. Our main result in this part is an algorithmic framework which ensures //3-approximate MMS schedule, and thus improves the best known approximation of I/5 which is proved for a broader class of valuation functions - XOS Ghodsi et al. [2018]. Interestingly, in the independent and parallel work Hummel and Hetland [2021]. the authors also show the existence of 1/3 1/3-approximate MMS for graphically conflicting items. With XOS valuation oracles, Ghodsi algorithm to compute
et al. [2018] also designed a polynomial-ting allocation. As comparison, by slightly modifying our algorithm, it returns a 0.24-approximate MMS allocation in polynomial time, without valuation oracles. When all jobs are rigid, i.e., processing time = deadline release time, our problem degenerates to finding a partition of an interval graph such that the minimum weight of the independent set for each subgraph is maximized. Recently, a poludoooolynmiall time algorithm is given in Chiarelli et al. [2020] for constant number of agents. In this sense, we generalize this problem to flexible jobs and design approximation algorithms for arbitrary number of agents.
MMS
Main Result 1. For arbitrary FISP instance, there exists a 1/3 aprroxiie MMS schedule, and (0.24 - <) approximae MMS schedule can be found in polynomial time, for any constant é >> 0.
EFI+PO. EF is actually demanding fairness notion, in the sense that any approximation of BF is not compatible with PO. Instead, initiated by Lipton et al. [2004], most research is focused on its relaxation, eny--freenes up to one item (EF1), which means the envy between two agents may exist

---

but will disappear if some item is removed. Unfortumately, EFI and PO are still not compatible even if all jobs are rigid and agents have unary valuations. However, the good news is, if all jobs have unit processing time, an EFI and PO schedule is guaranteed to exist and can be found in polynomial time. This result continues to hold when agent valuations are weighted but identical. It is shown in Biswas and Barman [2018 8] that under laminar matroid constraint an EF1 and PO allocation exists when agents have identical utilities, but finding it may need exponential time. We improve this result in two perspectives. First, our feasibility constraints, even for unit jobs, are not necessarily laminar matroid. Second, our algorithm runs in polynomial time.
No algorithm can return an EFI and PO schedule for all FISP instances, even if all jobs are rigid and valuations are unary. When all jobs have unit processing time and valuations are (weighted) identical, an EFI and PO schedule can be computed in polynomial time.
Main Result 2.
Although exact EF1 and PO are not compatible, prove that for an arbitrary FISP instance, there always exists a 1/ /4-approximate EF1 and PO schedule, which coincides with Wu et al. [2021]. J. If all jobs have unit processing time, a 1/2-approximate EFI and PO schedule exists. To prove this result, we consider Nash social welfare - the geometric mean of all machines' utilities. We show that a Nash social welfare maximizing schedule satisfies the desired approximation ratio. This result is in contrast to the corresponding one in Caragiannis et al. [2016], which shows that without any feasibility constraints, such an allocation is EFI and PO. We also show that both approximations are tight.
Main Result 3. For any FISP instance, the schedule maximizing Nash social welfare is PO and 1 144-approximate EFI. If all jobs have unit processing time, it is 1 1/2-approximate EFI.
By above results, we observe that PO is too demanding to measure efficiency in our model. One milder requirement individual optimality (IO). Intuitively, an allocation is called IO if every agent gets the best feasible subset of jobs from the union of her current jobs and unscheduled jobs. We show that EFI is still not compatible with I0 in the general case. But for unary valuations, we obtain positive results and design polynomial time algorithms for (1) computing an EFI and IO schedule for rigid jobs, and (2) computing an EFI and 1/2-approximate 10 schedule for flexible jobs. To prove these results, utilize two classic algorithms Earliest Deadline First and Round Robin. We defer this part completely to the full version Li et al. [2021].
EF1+IO
1.2 Other Related Works
Since computing feasible job sets to maximize the total weight is NP-hard Garey and Johnson [1979]. various approximation algorithms have been proposed Bar-Noy et al. [2001]; Berman and DasGupta [2000]: Chuzhoy et al. [2006], and the best known approximation ratio is 0.644 Im et al. [2020]. For rigid instances, the problem is polynomial been studied from the perspective of machine learning, including developing learning algorithms to empirically solve ha-hard scheduling problem Zhang et al. [2020]: Paleja et al. [2020], and predicting uncertain data in order to optimize the performance in the online setting Purohit et al. [2018]. Fairness has been concerned in the scheduling community in past decades Ajtai el al. [1998]; Baruah and Lin [1998]; Baruah [1995]. Most of these works aim at finding fair schedule for the jobs, such as balancing the waiting and completion time Bilò et al. [2016]; Im and Moseley [2020].
solvable Schrijver [1999]. Recently, scheduling has
MMS allocation for indivisible resources has been widely studied since Budish [2010]. Unfortunately, it is shown in Kurokawa et al. [2018]; Ghodsi et al. [2018]; Feige al. [2021] that an exact MMS fair allocation may not exist. Thereafter, a string of approximation algorithms for various valuation types are proposed, such as additive Garg and Taki [2020], matroid-rant function Babaioff et al. [2021]; Barman and Verma [2021]. submodular Barman and Krishnamurthy [2020]; Ghodsi et al. [2018].
XOS and subadditive Ghodsi et al. [2018]. Regarding EFI, in the unconstrained setting, an allocation that is both EFI and PO is guaranteed to exist Caragiannis el al. [2016]; Barman et al. [201 8). However, when there are constraints, such as cardinality and knapsack, the general compatibility is still open Biswas and Barman [2018, 2019]; Wu et al. [2021]] Gan et al. 10:21; Dror et al. [2021].
3

---

2 Preliminaries
2.1 Fair Interval Scheduling Problem
In a fair interval scheduling problem (FISP), we are given a job-machine system, which is denoted by tuple (J, u4). J = {j1,... Inn } represents set of n. jobs (also called resources items) and A= {i1,... Om } is a set of m 3 2 machines controlled by agents. In this work, machines and agents are used interchangeably. We consider discrete time, and for t E N+, let [t, + 1) denote the t-th time slot. Each J; E J is associated with release time T; E N,+, deadline d; E NN. and processing time Pj N such that pj E d, r; + 1. The [rr, [r..d.] called a job interval, which can also be viewed as set of consecutive time slots. Ti, T; + 1, 1....,,,, de J. Job ji can be processed successfully if it is offered pi consecutive time slots within [r;, de]. Each machine can process most one job each time slot and a set of jobs J' C J is called feasible if all jobs in J' can be processed without overlap on a single machine. For a job ja E J, agent a, E A gains utility uz (1.jj }) > 0 js is successfully processed by a. We slightly abuse the notation and assume that uy (ik)) = (1,(. ji F). We use u, denote a,'s 's utility function. and define UA = (ui)iE For a feasible set of jobs S, the agent's s utility is additive, i.e., (S( Ej.ss Es us (Ja)) For an arbitrary set of jobs that may not be feasible, the agent's utility is the maximum she can obtain by processing a feasible subset, i.e.,
max (S) S' S' is feasihle
Σ
(ix))
ES
is noted that uz(-)'s 's are not additive for infeasible set of jobs and the computation of its value is NP-hard Garey and Johnson [1979]. In the full version Li et al. [2021], we show that they are actually
XOS, which is a special type of subadditive functions. We call these uz(-)'s interval scheduling (IS)
functions.
A schedule or allocation X = (Xi,..., Xm) is defined as an ordered partial partition of J, where X, is the jobs assigned to agent ag such that X, NX = @ for i + and X1 U...U U Xm J. Let = Use(m) X, denote all unscheduled jobs, which is regarded as the donation to a charity, A schedule X is called feasible if X, is feasible for all a, E A. i.c., all jobs X, can be successfully processed by a, Note that since jobs in Xo not scheduled, Xo is not necessarily feasible. Observe that any infeasible schedule X is equivalent to a feasible schedule X' by setting each X to be the feasible subset of X, that maximizes a,'s 's utility and X-- = J Usemm] X- We call instance rigid if ps d; r + for all j: E J, i.e., the jobs need occupy the entire job intervals. For rigid instances, the feasibility constraints can be described via interval graphs and the computation of (S)) for any S S J can be done in polynomial time Kleinberg and Tardos [2006].
2.2 Solution Concepts
We first define the maximin value for any utility function u, item set S and the number of agents Let F(S, k) be the set of all --partall-pariiionns partitions of S and
MSS k)
max min u (X.). (S1.. (L.) (E(K]
For any FISP instance (J,A,u)) with m = |A], agent a, A's maximin share (MMS) is given by MMS,(J, m) MMS (J, m))
When the parameters are clear in the context, we write MMS, = MMS, m) for simplicity. If a schedule X achieves MMS,, i.c., minke[m] 2s (Xxx) = MMS,, it is called an MMS schedule for a,. Definition 1 (a-MMS Schedule). For 0- < & 1, a schedule X = (X1,... Xm) is called a-approximate MMS (a-MMS) if (X.)) > a MMS, When a 1, X called an MMS schedule.
We next introduce envy freeness (EF). An EF schedule X (X,,,... .x,.) requires everybody's 's utility to be no less than her utility for any other agent's bundle, i.e., ux(X.) 2 u, (Xx) for any as (gg A. Since EF is over demanding for indivisible items, following the convention of fair division literature, in this work, we mainly consider EFI.
Definition 2 (o-EF1 Schedule). For < a & 1, a schedule X = (X1, .....,,,)))) Xmm) is called a- approximate envy-free up to one item (a-EF1) for any two agents a; ag E A,
U. (X,) 3 a ux(Xx \ (f)) for some j E Xt- When 1, X is called an EFI schedule.

---

We observe that an empry schedule is trivially EF and EFI, i.e. XD = J and X; = 0 for all E A. However, this a highly inefficient schedule, and thus we also want the schedule to be Pareto optimal. Definition 3 (PO schedule). A schedule X (X1.... Xm) ) is called Pareto Optimal (PO) there does not exist an alternative schedule X' = (X1: X such that un( (X)) 2 us ux(X,) for all a, E A, and ug(Xp)) > (xx( for some ag A.
We note that any approximation of EF is not compatible with PO, even in the very simple setting with two machines and single job. In the full version Li et al. [2021], we introduce another efficiency criterion, individual optimality (IO), which is weaker than PO and study the compatibility between EFI and IO.
Approximately MMS Scheduling
Before introducing our algorithmic framework, we first recall the best known existential and compu- tation results for MMS scheduling problems.
Observation 1 (Ghodsi et al. [2018]). For arbitrary FISP instance, there exists a 1/5-MMS schedule and a 1/8-MMS schedule can be computed in polynomial time, given XOS function oracle.
3.1 Algorithmic Framework
In this section, present algorithmic framework and prove that it ensures 1/3-MMS sched- ule. The algorithm has two parameters, a threshold vector (71.... Tm) with % > and a 3- approximation algorithm for IS functions, where 0 & 8 & 1. In this section, set 7/2 MMS; for each O2 E A. We can pretend that , = to understand the existential result easily. Note that the computations of each MMS, and exact value for IS functions show how to gradually adjust the parameters to make run in polynomial time. The high-level idea of the algorithm is repeatedly fill a bag with unscheduled jobs (which may be feasible) until some agent values it for no less than a threshold and takes away the bag. Then this agent reserves her best feasible subset of the bag, and returns the remaining jobs to the algorithm. By carefully designing the thresholds, we show that everybody can obtain least e 3+2
NP-hard, and in Section 3.2,
of her MMS.
3.1.1 Pre-processing
As we will see, the above bag-filling algorithm works well only if the jobs are small, i.e., u ux(is) < 342 " for all a; E and jæ E J. We first introduce the following property, which is used to deal with large jobs. Intuitively, Lemma implies that after allocating an arbitrary job to an arbitrary agent, the remaining agents' MMS values in the reduced sub-instance do not decrease. A similar result for additive valuations is proved in Amanatidis et al. [2017].
Lemma 1. For any instance (J,A, uA) with |A| m, the following inequality holds for any a, E A and any jk E J,
MMS;(J (ik) m 1) MM).
We use Lemma to design Algorithm which repeatedly allocates large job to some agent and removes them from the instance until there no large job.
Algorithm 1. Matching Procedure
Input: Arbitrary FISP instance I (J, A, uA); Thresholds (71.-.. 7m).
Output: (1) Sub-instance I' (J', A', u.) such that (i(x)) & 9+2 tys for all a, E A' and ja E J':
(2) Partial Schedule (Xy)a-EA\,A-- 1: Initialize A' = A and J' = J.
2: while there is an agent 0; A' and job j& E J' with us vi(ie)
a+2 % do
8
3: Set X; = {ix} ). A' A' \ { [a; }. and J' {jx].
4: end while
By Lemma 1, it is straightforward to have the following lemma.
5

---

Lemma 2. For any instance I = (J, UA) with (72,--,, ,mm),, the partial schedule (Xr),,EAM and the reduced instance I' =(J', A',,,'', u,x) returned by Algorithm I satisfy u,(X,) 3 B+2 " for all a, E A A' and MMS > [M))(J, all a, E AA'
3.1.2 Bag-Filling Procedure
Let I = (J,A, us) be an instance such that |A| = m and uz(ik) < ,822 " for all E A and jk J. We show the Bag-Filling Procedure in Algorithm 2, with parameters (n,.... .Tmm and 3-approximation algorithm for IS functions. For each 0₁ E A, we use n/ 2 - R to denote the approximate utility, and thus (S) > 8 (S) for any S E J. Intuitively, keeps bag B and repeatedly adds an unscheduled job into it until some agent ag first values this bag (under the approximate utility function vd) for at least 8
9
3+2 .Y. If there are more than one such agents, arbitrarily select one of them. Then gets assigned feasible subset X; B with Djex, vi(ii (B).. and returns B \ X; to the algorithm. This step is crucial, otherwise the other remaining agents may not obtain enough jobs. It is obvious that if agent 04 gets assigned bag, then her true utility satisfies
u+( = u.(i) = xx,),) > B 2 %
neX,
The major technical difficulty of our algorithm is prove that everyone can obtain bag.
Algorithm 2. BagFilling Procedure
Input: An FISP instance Z = (J, A, uA) such that (i(ik) < 8
342 for all as E A and ju E J; 8-approximation algorithm for IS functions; Thresholds (y1," 7m).
Output: #
342 842 -MMS schedule X (X1,... .x.).
Initialize A' J, = J, and obtain approximate utility functions of for all as E A.
2: while A' * 1 and J + 0 do
3: Set = 0.
4: while (B)
3ーニ ni for all o, A' and J' + 0 do
5: Let ja be arbitrary job in J'. Set B B U {ix } and J' {is
6: end while
7: Let a; be an arbitrary agent such that uB( デー2 T
8: Let X, S be a feasible subset such that EjEx 4z(ii) = (B)
9: Set J'==''=" = J' U (B X₂) and A' = A' A'\ {a
end while
Lemma 3. Setting 7 MMS; all a, E A, Algorithm 2 returns
3 -MS schedule. 3+2
Proof. As we have discussed, it suffices to prove that the beginning of any round of the outer while loop, there are sufficiently many remaining jobs in J' for every remaining agent in A', i.e.
3
(J')
3 2 Yo, for any a, E A'.
To prove the above inequality, in the following, we actually prove a stronger argument.
Claim 1. For any a; E A', ler X' = (X), "', be a feasible MMS schedule for a4. Then there exists is E [m], such that u, (X n J') D-2
Given Claim 1 and the 3-approximation of u/, uf (X nX)) > e
3+2 74 and thus the lemma holds. We
prove by contradiction and assume Claim does not hold for agent feasible MMS schedule for a, u, (X()) MMS; 74 for all A [m]] and thus
a, Since X' = (Xi, .. X m is
Σ ke/ml
un ux((
m 7/-

---

Denote by (N,,), the assignments that are allocated to A\, A' in previous rounds by Algorithm 2, and for each a,, let Jt. be the last item added to the bag B. Note that Jt. E X, otherwise a, will stop the inner while loop (Step 4) before jt. was added. Moreover, since ag did not break the while loop either, (X, \ {tt })
_ 3+2 "i. Thus (X, \ ((..) }) < --2 " as un is 3-approximation of u,
By the assumption that all jobs are small, i.e., u((ht)) &
T/s we have the following
3+2
3 8+1
ug (x,,)) (X, \ (h. }) us (i.))
<
3+2 2 %
(2)
If (X, nJ < 3+2 7/8 for all & E [mm] then
Σ
mi(x²) = Σ
ui ui(xgn))
+
E
ui(Xi n...)
[[(m]]
KE [m]
a.EAYA
Σ
us (x (J)+
Σ
E
u
kE [m]]
or OrEA RE(m)
(x(x + Σ (x,),)
kE[m]
AAAA
8 +
m 3+2 74 + (m - (
7/
<
m 76
3 + 2
where the first inequality is because the X/'s are disjoint and the second inequality is because of Equation (2). Thus we obtain a contradiction with Equation (1).
3.1.3 Main Existential Theorem
Combining Lemma 2 and Lemma 3, it is not hard prove the main existential result. In the full version Li et al. [2021], we will prove that our analysis is asymptotically tight.
Algorithm 3. Main Algorithm: Matching-Bage BagFilling
Input: An arbitrary FISP instance I (J,A, 8 B-approximation algorithm for IS functions; Thresholds (71, "m).
A Output: 342 -MMS schedule X 5== (X(,,, Xm))
1: Run Algorithm 1 on I with (71, 7m). Obtain I' = = AJ,, ux') and (Xy)a,
2: Run Algorithm 2 on I' with (71,". mm) and the B-approximation algorithm. Obtain (Xi)a,EA
Theorem 1. Algorithm with the optimal algorithm for IS functions (i.e., 1) and 74 MMS; for all a; E A returns a 1/3-MMS schedule for arbitrary FISP instance.
Interestingly, in the independent and parallel work Hummel and Hetland [2021]] via a similar bag- filling algorithm, the authors prove the existence of 1 1/3-approximate MMS allocations under the context of graphically conflicting items. However, the two models in our work and theirs are not compatible in general.
3.2 Polynomial-tine Implementation
Note that, in general, Algorithm is not efficient, because if A NP, the computation of exact values for IS functions and MMS values cannot be done in polynomial time. For the special case when jobs are rigid or unit, IS functions can be computed in polynomial time. If the number of machines is constant, MMS values for rigid jobs can be computed in pecudo-polynonen [2020]. Thus, in this section, we deal with the general case. Of course, for IS functions, we can directly the /-aaproximation algorithms, and the best-known approximation ratio is 0.644 Im et al. [2020]. Regarding the MMS barrier, instead of using their approximate values, we utilize a combinatorial trick similar with one used in Barman and Krishnamurthy [2020] such that without knowing their values, we can still execute our algorithm.
time Chiarelli et al.
First, an important corollary of Lemma 2 and Lemma 3 is that if 73 & MMS; for some a, no matter what values are set for Yg. j # Z,, Algorithm 3 always assigns bag a, such that u, (X,) >> 342 74.
7

---

Lemma 4. For any a, i < MMS, Algorithm 3 ensures that (x(),) 3 B
042 regardless of "Y-t-
We prove Lemma 4 in the full version Li et al. [2021]. Now, we ready to introduce the trick. First, we set each ? to be sufficiently large such that Y e MMS; for all a, Then we run Algorithm 3. If we found some agent a, with u, ux())) < 3+2 7h. it means "/ is higher than MMS; and we can decrease "/ by 0 < 1 1-
fraction and keep the other MMS values unchanged. We repeat the above procedure until everyone satisfied ux(X,)) 3 8+2 "/i- By Lemma 4, it must be that % 2 (1 - c)MMS for all ag. We summarize this in Algorithm 4, and is straightforward to have the following theorem.
Algorithm Efficient Implementation: Matching BaaiailBaFFiigg
Input: An arbitrary FISP instance (J, uA); a-approximation polynomial algorithm for (J)
IS functions; Thresholds (?1 [.( ,... 7mm= "m
<<<l.
Output: (842) e)-MMS schedule X (X1,... (Xm))
8
1: Run Algorithm 3 on with (71, .. 7m). Obtain X (XI, Xm).
2: while there exist a; E A such that (X,) $427% do
3: Set % = -1-66) -)-
4: Run Algorithm I with (71, .. 7m) and update X (X1,'.. X.
5: end while
Theorem 2. For any 0 < e 1, Algorithm 4 returns a - c)-MMS schedule for arbitrary FISP instance with an 8-approximation algorithm for IS functions. The running time is polynomial with [J], |A| and 1/e. Particularly, using the 0.64 (44-approximation algorithm in Im et al. [2020], we have 0.24(1 apprpoximmtio polynomial-time algorithm.
4
Approximately EF1 and PO Scheduling
4.1 Compatibility of EFI and PO
In this section, we investigate the extent to which there a schedule that is both EFI and PO. We first show that EFI and PO are not compatible even if jobs are rigid and valuations are unary, i.e., u; (f+) = for all a; E A and ja J. That no algorithm can return an EFI and PO schedule for all instances. Fortunately, if the jobs have unit processing time, EF1 and PO schedule exists and can be computed polynomial time. This result continues to hold if the agents have weighted but identical utilities, i.c., (jk) u, (jk) for any job jk and any two agents a; and a,.. We sometimes ignore the subscript and use u(-) to denote the identical valuation.
Algorithm mo-Maat + Inner- Greedy
Input: An FISP instance = (J, A, uA), where all jobs have unit processing time and all agents have identical valuation.
Output: EFI and PO schedule X = (X1,... Xm).
1: Construct graph GJJUT, E), and compute maximum weighted m-matching M
2: Define Jj = fjj J
M" for each E
3: Set X1 = Xx _...= Xm 0.
4: for p 1o [T] IT|d do
5: if J, / 0 then
6:
Sort A in non-decreasing order of ux()))'s, and Jp in non-increasing order of u(ja)'s for := to Jpl do
7:
Set X, X, }. end for 10: end if
8:
9:
end for
Theorem 3. EFI and PO are not compatible even if all jobs are rigid and all valuations are unary. If all jobs have unit processing time, Algorithm returns an EFI and PO schedule polynomial time, as long the valuations identical.
8

---

Here, we briefly discuss the intuition of Algorithm 5 in the following, At the heart of Algorithm 5, there are two tasks: (1) Find jobs with maximum weight to schedule in order to guarantee PO. (2) Assign these jobs to agents such that the assignment is EFI.
To solve the first task, we use bipartite matchings. Let T; (ri, d.] [ [ri, I,... .d, be the job interval for each ji E J, and T = Uigign Ti We first construct a weighted bipartite graph G(J UT, E), where each job ji E J is node on the left side, and a time slot t E T is node on the right side. There is an edge (Je, ti) E E with weight u(j:) if and only if E T. For any set B C E and e E JUUT, let B(v) S E. be the set of edges in B that intersects U. Next we define m-matching M S F, which requires that (M(j.) ) < 1 for all ji E J and (M4 & m for all 4 E T, where m is the number of machines. m- matching is used to ensure that at each time slot at most m. jobs are processed. Accordingly, by computing a maximum weighted m-matching M we can find the set of jobs by scheduling which we can maximize the social welfare so that the resulting schedule is PO.
However, how shall we assign these jobs to agents? We partition these selected jobs into groups {J1, J J. and each group Jr contains the jobs that are matched to time slot t by MM.. To maintain feasibility, each agent can get at most one job from each J,. We process {Ji, I one by one, and to satisfy EF1, the agent with low cumulative utilityy should obtain better job in the next group. By induction, we can prove that eventually, the assignment is indeed EFI.
A final remark is about the running time. If the graph size is polynomial, by Bernhard and Vygen [2008], finding .M can be done in polynomial time. However, (T) can be exponentially large. Therefore, before running Algorithm 5, we first reduce an arbitrary instance to a condensed one by discarding some time slots which is essentially equivalent to the original one but only contains polynomial number of time slots. We defer this discussion completely to the full version Li et al. [2021].
4.2 Approximate EF1 and PO
Although EFI and PO are only compatible in special cases, in this section we show that approximate EF1 and PO can be always satisfied. Theorem is proved in the full version Li et al. [2021], where we introduce Nash social welfare and show that Nash social welfare maximizing schedule satisfies the desired properties.
Theorem 4. For arbitrary FISP instance, there is a feasible schedule that is 1 1/4-EF1 and PO. If all jobs have unit processing time, there is a feasible schedule that is 1/2-EF1 and PO.
5 Experiment
Finally, we evaluate the performance of Matching-BagFille on randomly generated data sets, and compare with the extensively adopted heuristic algorithm Round- Robbin: Each agent takes turns to select a feasible unscheduled job that maximizes her marginal utility gain until no more jobs can be selected. Before conducting the experiments, we note that although good theoretical guarantee, for many concrete instances, it can be significantly improved. Since each agent only selects a bag with 1 1/3MMS, there might be lots of unscheduled jobs that can be feasibly processed. Therefore, we first refine our algorithm as Matching Filliingg::: (1) Run (2) Run Round-Rotte describe Round-Robin and Matching- Berehhing-BagFiille BigFiliing+ in the full version Li et al. [2021]. Note that Batching-BagFillingg does not have better theoretical performance than Faggiiin...
aatching-BaaFilliing has
on the remaining unscheduled jobs. We formally
In our experiment, as shown in Figure 1, we randomly generate a set of rigid jobs J (J) 100, 500, 1000) and set of agents following some distribution, where for = 1, 2, 3, U/P/Ná means there are |A] = 5 x agents whose values are randomly generated from a(n) Uniform, Poisson, or Normal distribution. For each setting, we generate 1000 instances. For each of them we run Matching- Bagllliiig (short for BAG+), Matching BaghiiigggaFFiligggggg (short for BAG), and Round- Robin (short for RR) and record every agent 0, 's average utilities u, (BAG+)), u, (BAG), u. (RR). Then we compute the ratios u, (BAG+)/u, (RR) and u, (BAG)/ uu (RR). Of course, if these ratios are greater than 1, means our algorithms outperform the Round-Robin. We use two vertical line intervals to represent the range of all agents' ratios. It can be seen that in all experiments, Matching-BagFilling clearly outperforms Round-Robin, i.e., every agent gets higher utility in Matching-BagFillingg BagFillingt. Compared with the number of agents, if the number of jobs is small (c.g.

---

| 15 and |J] 100, 500, 1000), Matching BagFilling has decent performance. However, as the is clearly
number jobs gets larger (e.g. |A| and | 100, 500, 1000), worse than Round-Robin which is because too many jobs are left unscheduled. We defer detailed description of our experiments and the discussion of results to the full version Li et al. [2021].
100
U10
Ul01000
1.4
1.2
1.2
1.2
1.0
1.0
0.8
Figure 1: Experiments
6 Conclusion and Future Directions
In this work, we studied the fair scheduling problem for time-dependent resources, and designed constant approximation algorithms for MMS, EFI&PO and EFI&IO schedules. There many open problems and future directions. An immediate direction is to improve our approximation ratios and investigate the limit of approximation algorithms for different settings. is also interesting impose other efficiency criteria on EFI schedules, such as computing an EF1 schedule that maximizes social welfare. In this work, we have assumed the jobs resources that bring utility agents, and leave the case when jobs are chores for future study. Finally, it is of both theoretical interest and practical importance consider the online setting when jobs arrive dynamically and the strategic setting when agents' valuations are private information.
Acknowledgements and Funding
The authors thanks Warut Suksompong for reading a draft of this paper and for helpful discussions. Bo Li was partially funded by The Hong Kong Polytechnic University under Grant No. P0034420. Minming was partially supported by NSFC under Grant No. 11771365, and by Project No. CityU 1 11200518 8 from Research Grants Council of HKSAR.
10

---

References
Miklós Ajtai, James Aspnes, Moni Naor, Yuval Rabani, Leonard Schulman, and Orli Waarts. Fairness in scheduling. J. Algorithms, 29(2):306-3)) -507 1998.
Rasha A. Al-Arasi and Anwar Saif. Task scheduling cloud computing based on metaheuristic techniques: A review paper. EAI Endorsed Trans. Cloud Syst., 6(17):e4, 2020.
Georgios Amanatidis, Evangelos Markakis, Afshin Nikzad, and Amin Saberi. Approximation algorithms for computing maximin share allocations. ACM Trans. Algoritims, 13(4):52:1152:28, 2017.
Georgios Amanatidis, Federico Fusco, Philip Lazos, Stefano Leonardi, and Rebecca Reiffenhäuser. Fast adaptive non-monotone submodular maximization subject to a knapsack constraint. In NeurIPS, 2020.
Moshe Babaioff, Tomer Ezra, and Uriel Feige. Fair and truthful mechanisms for dichotomous valuations. In AAAI, pages 5119-5126. AAAI Press, 2021.
Amotz Bar-Noy, Sudipto Guha, Joseph Naor, and Baruch Schieber. Approximating the throughput of multiple machines in real-time scheduling. SIAM J. Comput., 312):331-332 2001.
Siddharth Barman and Sanath Kumar Krishnamurthy. Approximation algorithms for maximin fair division. ACM Trans. Economics and Comput., 801):5: 2020.
Siddharth Barman and Paritosh Verma. Existence and computation of maximin fair allocations under matroid-rank valuations. In AAMAS, pages (69-177.00 ACM, 2021.
Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish. Finding fair and efficient allocations. In EC, pages 557-574. ACM, 2018.
Sanjoy K. Baruah and Shun-Shii Lin. Pfair scheduling of generalized pinwheel task systems. IEEE Trans. Computers, 47(7):812-81) 1998.
Sanjoy K. Baruah. Fairness in periodic real-time scheduling. In RTSS, pages 200-209. IERE Computer Society, 1995.
Piotr Berman and Bhaskar DasGupta. Multi-phase algorithms for throughput maximization for real-time scheduling. J. Comb. Optim., 4(3):307-323, 2000.
Korte Bernhard and Jens Vygen. Combinatorial optimization: Theory and algorithms. Springer, Third Edition, 2005., 2008.
Vittorio Bilò, Angelo Fanelli, Michele Flammini, Gianpiero Monaco, and Luca Moscardelli. The price of envy-freeness in machine scheduling. Theor. Comput. Sci., 613:65-78, 2016.
Arpita Biswas and Siddharth Barman. Fair division under cardinality constraints. In IJCAI, pages 91-97. ojgai.org, 2018
Arpita Biswas and Siddharth Barman. Matroid constrained fair allocation problem. In AAAI, pages 9921-9922, AAAI Press, 2019.
Eric Budish. The combinatorial assignment problem: approximate competitive equilibrium from equal incomes. In BQGT, page 74:1. ACM, 2010.
Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang. The unreasonable fairness of maximum nash welfare. In EC, pages 305-322. ACM, 2016.
Xingyu Chen, Brandon Fain, Liang Lyu, and Kamesh Munagala. Proportionally fair clustering. In ICML, volume 97 of Proceedings of Machine Learning Research, pages 1032-1041. PMLR, 2019.
Nina Chiarelli, Matjaz Krne, Martin Milanic, Ulrich Pferschy, Nevena Pivac, and Joachim Schauer. Fair packing of independent sets. /WOCA, volume 12126 of Lecture Notes in Computer Science, pages 154-165. Springer, 2020.

---

Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii. Fair clustering through fairlets. In NIPS, pages 5029-5037, 2017.
Julia Chuzhoy, Rafail Ostrovsky, and Yuval Rabani. Approximation algorithms for the job interval selection problem and related scheduling problems. Math. Oper. Res., 31(4):730-738, 2006.
Amitay Dror, Michal Feldman, and Erel Segal-Halewt On fair division under heterogeneous matroid constraints. CoRR, abs/2010.07280. 2020.
Amitay Dror, Michal Feldman, and Erel Segal-Halewt On fair division under heterogeneous matroid constraints. In AAAI, pages 5312-5320. AAAI Press, 2021.
Maciej Drozdowski. Scheduling for Parallel Processing. Computer Communications and Networks. Springer, 2009.
Uriel Feige, Ariel Sapir, and Laliv Tauber. A tight negative example for MMS fair allocations. CoRR, abs/2104. 04977, 2021.
Jiarui Gan, Bo Li. and Xiaowei Wu. Approximately envy-free budget-feasible allocation. CoRR, abs/2106. 14446, 2021.
M. R. Garey and David S. Johnson. Computers and Intractability: Guide the Theory of NP-C CP--Completeeess. W. H. Freeman, 1979.
Jugal Garg and Setareh Taki. An improved approximation algorithm for maximin shares. In EC, pages 379-380. ACM, 2020.
Karsten Gentner, Klaus Neumann, Christoph Schwindt, and Norbert Trautmann. Batch production scheduling in the process industries. In Handbook of Scheduling. Chapman and Hall/CRC, 2004.
Mohammad Ghodsi, Mohammad Taghi Hajiaghayi, Masoud Seddighin, Saeed Seddighin, and Hadi Yami. Fair allocation of indivisible goods: Improvements and generalizations. In EC, pages 539-556. ACM, 2018.
Halvard Hummel and Magnus Lie Hetland. Fair allocation of confticting items. abs/2104.06280, 2021.
CoRR,
Sungjin Im and Benjamin Moseley. Fair scheduling via iterative quasi-uniform sampling. SIAM J. Comput., 49(3):658-688 -800, 2020.
Sungjin Im, Shi Li, and Benjamin Moseley. Breaking 1/e barrier for nonpreemptive throughput maximization. SIAM J. Discret. Math., 34(3):1649-1669 2020.
Jon M. Kleinberg and Éva Tardos. Algorithm design. Addison-Wesley. 2006.
David Kurokawa, Ariel D. Procaccia, and Junxing Wang. Fair enough: Guaranteeing approximate maximin shares. J. ACM, 65(2):8:1-8:27, 2018.
Bo Li, Minming Li, and Ruilong Zhang. Fair allocation with interval scheduling constraints. CoRR, abs/2107.1 11648, 2021.
Richard J. Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi. On approximately fair allocations of indivisible goods. In EC, pages 125-131. ACM, 2004.
Rohan R. Paleja, Andrew Silva, Letian Chen, and Matthew C. Gombolay. Interpretable and personal- ized apprenticeship scheduling: Learning interpretable scheduling policies from heterogeneous user demonstrations. In NeurIPS, 2020.
Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via MI. predictions. In NewrlPS, pages 9684-9693, 2018.
Aida Rahmattalabi, Phebe Vayanos, Anthony Fulginiti, Eric Rice, Bryan Wilder, Amulya Yadav, and Milind Tambe. Exploring algorithmic fairness in robust graph covering problems. NeurIPS, pages 15750-15761, 2019.
12

---

Alexander Schrijver. Theory of linear and integer programming. Wiley-Interscience series in discrete mathematics and optimization. Wiley, 1999.
Warut Suksompong. Constraints fair division. SIGecom Exch., 19(2):4661, 2021.
Xiaowei Wu, Bo Li, and Jiarui Gan. Budget-feasible maximum nash social welfare allocation is almost envy-free. In IJCAL. ijeai.org, 2021.
Cong Zhang, Wen Song, Zhiguang Cao, Jie Zhang, Puay Siew Tan, and Chi Xu. Learning to dispatch for job shop scheduling via deep reinforcement learning. In NeurlPS, 2020.
13


Reviews:
[{"review_id": "qTlfwRnTF5h", "reviewer": "Reviewer_RGgx", "summary": "The paper considers the scheduling problem of assigning jobs, each with a release time a deadline and a duration, to heterogeneous machines with the objective of *fairness*. More specifically, each machine has a utility for each job and its total utility is defined as the sum of utilities of jobs that were assigned to it and can be feasibly scheduled. With respect to fairness two concepts are considered:\n\n- Maximin Share (MMS): the MMS of a machine can be thought of as the value it would obtain in the worst case by partitioning the jobs into bundles and was the last machine to select a bundle. If every machine obtains a utility that is no less than an $\\alpha$-fraction of its MMS.\n\nWith respect to MMS the paper proves the existence of an $1/3$-approximate MMS schedule and shows that a $(0.24-\\epsilon)$ one can be constructed in polynomial time. These improve upon the best known $1/5$-approximate MMS schedule due Ghodsi et al.\n\n-  Envy freeness up to one item (EF1) + Pareto optimal (PO): EF1 means that although envy between different machines may exist, it disappears after removal of one item, and an allocation is PO if there does not exist another allocation that makes nobody worse off but somebody strictly better off.\n\nThe authors show that no algorithm can return a schedule satisfying EF1 and PO simultaneously for all input instances. When all durations are unit and the valuations are identical then such a schedule can be computed in polynomial time. It is also shown, that the schedule maximising Nash social welfare is PO and simultaneously 1/4-approximate EF1 (and 1/2-approximate EF1 if all jobs have unit processing times.)", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Regarding MMS, the algorithm itself is quite involved and consists 1) so-called large jobs are sequentially assigned to the machines so that when a machine receives a job the MMS values of the other machines do not decrease, and 2) the remaining jobs are put into a bundle until some machine chooses to \"get\" a subset of that bundle. This approach more or less directly gives the existential result but needs to be massaged in order to give the constructive one. I did not check the proofs line by line but they seem to check out.\n\nWith respect to EF1 and PO, it is shown that they are not compatible even in special cases. For the special case of unit processing time and identical valuations a polynomial time algorithm is given based on a maximum weighted $m$-matching on a specific graph. Naturally the algorithm crucially builds upon the fact that the jobs have unit sizes. Although the algorithm is only pseudo-polynomial (all possible time-slots are considered individually) it can be transformed into a polynomial one via standard tricks.\n\nIn the experimental results the algorithm is compared to -- and outperforms -- Round-Robin.\n\nThe paper considers an interesting problem, and at least the result with respect to MMS is interesting since it improves the state of the art, and the algorithm and its analysis are definitely non-trivial (although I cannot say to what extend they build upon previous works and which ideas are new). The results regarding EF1 + PO seem quite specific and not so interesting to me. Overall this is a nice and well written paper and I think it should be accepted, although I am a bit uncertain on whether this is the correct venue for such a result.\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "no limitations and no potential negative societal impact that I can think of.", "review_text": "", "extra_scores": {"ethical_concerns": "no ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}, {"review_id": "S_8tvZLPvX5", "reviewer": "Reviewer_SsyJ", "summary": "Problem considered is the following: Given a m intelligent agents or machines and a set of Jobs (with release times and deadlines, processing time requirement and a utility) the goal is to allocate a maximum utility subset of jobs feasibly under some fairness criteria. They consider two fairness criteria namely: Minimax fairness and envy freeness. \n\nThe paper obtains novel approximation algorithms for various problems arising in this setting, improving upon the existing best results for some of them. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nI like this paper -- well motivated and well written problem. The algorithm for minimax fairness (1/3-approximation guarantee) which improves upon existing state of the art (1/5-approximation) is in particular quite interesting. The algorithm is surprisingly simple (yet, in my opinion non-trivial to prove) : keep filling a subset (\"bag\") of tasks until some agent finds it attractive enough. There are other complementary results -- for example making the above algorithm PTIME runnable and those considering the envy free fairness setting. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Quite theoretical - so this question seems N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "~ 2-3 hours"}, "extra_text": {}}, {"review_id": "QWqCgVnAqRu", "reviewer": "Reviewer_WBBe", "summary": "The paper addresses the following job scheduling problem. There are n jobs and m processors. Job i “arrives” at time r_i, has a processing time p_i, and needs to be executed non-preemptively by time d_i (deadline). It is scheduled on a processor for execution, which can be working on one job at a time and derives utility u_i from execution of a job i. Each processor accumulates the sum of the utilities of the individual jobs it processes.\n\nTwo core solution concepts are used for allocating/scheduling the jobs onto processors. 1) maximizing the minimum utility accumulated by any processor, and 2) having the accumulated utility of each processor be no less than that of any other. The latter is matched with a Pareto optimality concept. Variants of those core concepts are investigated.\n", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is interesting and provides “relaxation bounds” for construction of schedules in general instances. I can see how the proofs go and actually some of the arguments are reminiscent of those used in classical job-shop scheduling theory. It would be useful to discuss a bit or provide pointers to connections to job-shop scheduling.\n\nAlso, it appears from the proofs that if we restrict the classes of “arrival” times r_i, the processing times p_i and deadlines d_i -- so that we reduced the “busrtiness” of the job “flow” – then we can obtain (potentially) much tighter “relaxation bounds” for the performance. That is, it appears that if we control/suppress the “burstiness” of the jobs, we’ll be able to schedule them more efficiently on the same set of processors. I believe the reader would benefit from at least a discussion of that aspect, even if the existing proofs cannot be “massaged” to demonstrate this effect. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4.5"}, "extra_text": {}}, {"review_id": "Ff_MoVAOlAj", "reviewer": "Reviewer_kF3C", "summary": "This paper presents algorithms for fair division of items to agents. Each item is a job that needs to be processed within a given interval for its utility to be extracted by the agent processing it. This adds a layer of complexity since given any set of items, it is NP-hard to find the subset of feasible items that maximizes utility for the agent (utilities are additive but heterogeneous across agents). Two notions of fairness are considered. The first part of the paper focuses on max-min fairness. The main results are to improve the bounds for (a) the best existential max-min fair allocation, and (b) the best approximation to max-min fairness that can be obtained algorithmically in polynomial time. The difference between the two is primarily because of the NP-hardness stated above of finding the optimal subset of feasible jobs in a given set of jobs. The second paper of the paper focuses on variants of envy freeness. Here, the goal is to obtain envy-free solutions that are also Pareto optimal. But, this is impossible, and so are various extensions such as relaxing to EF1. Nevertheless, some positive results are obtained by relaxing EF1 an approximate notion, or relax Pareto optimality to individual optimality and focus on rigid jobs, etc.", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper has some interesting and non-trivial results, and as such, and I appreciate the technical work in the paper. But, my main concern is fit. I do not see a clear connection of this paper to ML. It is basically a set of results in designing fair scheduling algorithms. The authors try to explain the relevance by saying that fairness is important in AI and ML. Of course that is true, but this paper does not give any results for fairness in ML. I think the paper is more suitable for a conference like EC, and possibly AAAI, or even some theoretical computer science conferences, but I don't think it is suitable for NeurIPS.\n\nI have read the authors' response. The main concern remains the suitability of the paper for this particular venue, since the connections to learning are still rather vague. On technical merit alone, the score of the paper would be 6 instead of 4, which I have communicated to the AC.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations are not discussed explicitly, although the section on future work does point out some ways that the results in this paper can be made more general. I think the paper would benefit from a discussion on the limitations of the fairness measures used here to model fairness as an abstract concept, i.e., what are situations where these are the right measures and when are there other measures that fit fairness goals better?", "review_text": "", "extra_scores": {"ethical_concerns": "None that I can think of.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper was well-liked by the reviewers.  The only concern was fit for NeurIPS.  I believe there will be interest in this work and I prefer to error on the side of being inclusive. 
Decision: Accept (Poster)