Fair Scheduling for Time-dependent Resources

Abstract:
We study a fair resource scheduling problem,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.

heading: 1 Introduction
text: With the rapid progress of AI technologies, AI 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 a possibly flexible interval. For example, an one-hour math tutorial needs to 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 are heterogeneous, i.e., different 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 task is to make the assignment fair.
The SAO problem falls under the umbrella of the research on job scheduling, which has been studied in numerous fields, including operations research Gentner et 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, or 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 of the algorithms are real human beings who should be ∗Equal contribution †Corresponding author
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
treated unbiasedly, addressing the individual fairness 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 et al. [2020].
It is noted that people have different criteria on evaluating fairness, 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 is 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 assignment. We note that, due to the scheduling-feasible 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 unallocated/disregarded items are assumed to be donated to a charity. To resolve this issue, in this work, we want to understand how we can compute allocations that are simultaneously 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 strictly 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 a graph. For example, two one-hour tutorials between 9:00am and 11:00am can be feasibly scheduled, but three such tutorials are not feasible any more. For a 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].

heading: 1.1 Main Results
text: 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 EF1 schedules.
Maximin Share. Informally, a machine’s MMS is defined to be her optimal worst-case utility in an imaginary experiment: she partitions the items into m 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 α-approximate MMS fair if every machine’s utility is no less than α fraction of her MMS value. Our main result in this part is an algorithmic framework which ensures a 1/3-approximate MMS schedule, and thus improves the best known approximation of 1/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-approximate MMS for graphically conflicting items. With XOS valuation oracles, Ghodsi et al. [2018] also designed a polynomial-time algorithm to compute a 0.125-approximate MMS allocation. As a 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 pseudo-polynomial-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.
Main Result 1. For an arbitrary FISP instance, there exists a 1/3-approximate MMS schedule, and a (0.24− )-approximate MMS schedule can be found in polynomial time, for any constant > 0. EF1+PO. EF is actually a demanding fairness notion, in the sense that any approximation of EF is not compatible with PO. Instead, initiated by Lipton et al. [2004], most research is focused on its relaxation, envy-freeness up to one item (EF1), which means the envy between two agents may exist
but will disappear if some item is removed. Unfortunately, EF1 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 EF1 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] 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.
Main Result 2. No algorithm can return an EF1 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 EF1 and PO schedule can be computed in polynomial time.
Although exact EF1 and PO are not compatible, we 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]. If all jobs have unit processing time, a 1/2-approximate EF1 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 EF1 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/4-approximate EF1. If all jobs have unit processing time, it is 1/2-approximate EF1.
EF1+IO By above results, we observe that PO is too demanding to measure efficiency in our model. One milder requirement is 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 EF1 is still not compatible with IO in the general case. But for unary valuations, we obtain positive results and design polynomial time algorithms for (1) computing an EF1 and IO schedule for rigid jobs, and (2) computing an EF1 and 1/2-approximate IO schedule for flexible jobs. To prove these results, we utilize two classic algorithms Earliest Deadline First and Round-Robin. We defer this part completely to the full version Li et al. [2021].

heading: 1.2 Other Related Works
text: 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-time solvable Schrijver [1999]. Recently, scheduling has been studied from the perspective of machine learning, including developing learning algorithms to empirically solve NP-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 et al. [1998]; Baruah and Lin [1998]; Baruah [1995]. Most of these works aim at finding a fair schedule for the jobs, such as balancing the waiting and completion time Bilò et al. [2016]; Im and Moseley [2020].
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 et 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-rank 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 EF1, in the unconstrained setting, an allocation that is both EF1 and PO is guaranteed to exist Caragiannis et al. [2016]; Barman et al. [2018]. 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. [2021]; Dror et al. [2021].

heading: 2 Preliminaries

heading: 2.1 Fair Interval Scheduling Problem
text: In a fair interval scheduling problem (FISP), we are given a job-machine system, which is denoted by tuple (J ,A,uA). J = { j1, · · · , jn } represents a set of n jobs (also called resources or items) and A = { a1, · · · , am } is a set of m > 2 machines controlled by agents. In this work, machines and agents are used interchangeably. We consider discrete time, and for t ∈ N+, let [t, t+ 1) denote the t-th time slot. Each ji ∈ J is associated with release time ri ∈ N+, deadline di ∈ N+, and processing time pj ∈ N+ such that pi 6 di − ri + 1. The [ri, di] is called a job interval, which can also be viewed as a set of consecutive time slots, { ri, ri + 1, · · · , di }. Job ji can be processed successfully if it is offered pi consecutive time slots within [ri, di]. Each machine can process at most one job at each time slot and a set of jobs J ′ ⊆ J is called feasible if all jobs in J ′ can be processed without overlap on a single machine. For a job jk ∈ J , agent ai ∈ A gains utility ui({ jk }) > 0 if jk is successfully processed by ai. We slightly abuse the notation and assume that ui(jk) = ui({ jk }). We use ui to denote ai’s utility function, and define uA = (ui)i∈A. For a feasible set of jobs S, the agent’s utility is additive, i.e., ui(S) = ∑ jk∈S ui(jk). 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.,
ui(S) = max S′⊆S: S′ is feasible ∑ jk∈S′ ui(jk).
It is noted that ui(·)’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 ui(·)’s interval scheduling (IS) functions.
A schedule or allocation X = (X1, · · · ,Xm) is defined as an ordered partial partition of J , where Xi is the jobs assigned to agent ai, such that Xi ∩Xj = ∅ for i 6= j and X1 ∪ · · · ∪Xm ⊆ J . Let X0 = J \ ⋃ i∈[m]Xi denote all unscheduled jobs, which is regarded as the donation to a charity. A schedule X is called feasible if Xi is feasible for all ai ∈ A, i.e., all jobs in Xi can be successfully processed by ai. Note that since jobs in X0 are not scheduled, X0 is not necessarily feasible. Observe that any infeasible schedule X is equivalent to a feasible schedule X′ by setting each X ′i to be the feasible subset of Xi that maximizes ai’s utility and X ′0 = J \ ⋃ i∈[m]X ′ i . We call an instance rigid if pi = di − ri + 1, for all ji ∈ J , i.e., the jobs need to occupy the entire job intervals. For rigid instances, the feasibility constraints can be described via interval graphs and the computation of ui(S) for any S ⊆ J can be done in polynomial time Kleinberg and Tardos [2006].

heading: 2.2 Solution Concepts
text: We first define the maximin value for any utility function u, item set S and the number of agents k. Let F(S, k) be the set of all k-partial-partitions of S and
MMSu(S, k) = max (S1,··· ,Sk)∈F(S,k) min i∈[k] u(Xi).
For any FISP instance (J ,A,uA) with m = |A|, agent ai ∈ A’s maximin share (MMS) is given by MMSi(J ,m) = MMS ui(J ,m).
When the parameters are clear in the context, we write MMSi = MMSi(J ,m) for simplicity. If a schedule X achieves MMSi, i.e., mink∈[m] ui(Xk) = MMSi, it is called an MMS schedule for ai. Definition 1 (α-MMS Schedule). For 0 < α 6 1, a schedule X = (X1, · · · ,Xm) is called α-approximate MMS (α-MMS) if ui(Xi) > α ·MMSi. When α = 1, X is called an MMS schedule.
We next introduce envy freeness (EF). An EF schedule X = (X1, · · · ,Xm) requires everybody’s utility to be no less than her utility for any other agent’s bundle, i.e., ui(Xi) > ui(Xk) for any ai, ak ∈ A. Since EF is over demanding for indivisible items, following the convention of fair division literature, in this work, we mainly consider EF1. Definition 2 (α-EF1 Schedule). For 0 < α 6 1, a schedule X = (X1, · · · ,Xm) is called αapproximate envy-free up to one item (α-EF1) if for any two agents ai, ak ∈ A,
ui(Xi) > α · ui(Xk \ {j}) for some j ∈ Xk. When α = 1, X is called an EF1 schedule.
We observe that an empty schedule is trivially EF and EF1, i.e., X0 = J and Xi = ∅ for all ai ∈ A. However, this is 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) if there does not exist an alternative schedule X′ = (X ′1, · · · ,X ′m) such that ui(X ′i) > ui(Xi) for all ai ∈ A, and uk(X ′k) > uk(Xk) for some ak ∈ A.
We note that any approximation of EF is not compatible with PO, even in the very simple setting with two machines and a 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 EF1 and IO.

heading: 3 Approximately MMS Scheduling
text: Before introducing our algorithmic framework, we first recall the best known existential and computation results for MMS scheduling problems. Observation 1 (Ghodsi et al. [2018]). For an 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.

heading: 3.1 Algorithmic Framework
text: In this section, we present our algorithmic framework and prove that it ensures a 1/3-MMS schedule. The algorithm has two parameters, a threshold vector (γ1, · · · , γm) with γi > 0 and a βapproximation algorithm for IS functions, where 0 6 β 6 1. In this section, we set γi = MMSi for each ai ∈ A. We can pretend that β = 1 to understand the existential result easily. Note that the computations of each MMSi and exact value for IS functions are NP-hard, and in Section 3.2, we show how to gradually adjust the parameters to make it run in polynomial time. The high-level idea of the algorithm is to repeatedly fill a bag with unscheduled jobs (which may not 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 at least ββ+2 of her MMS.

heading: 3.1.1 Pre-processing
text: As we will see, the above bag-filling algorithm works well only if the jobs are small, i.e., ui(jk) 6 β β+2 · γi for all ai ∈ A and jk ∈ J . We first introduce the following property, which is used to deal with large jobs. Intuitively, Lemma 1 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 I = (J ,A,uA) with |A| = m, the following inequality holds for any ai ∈ A and any jk ∈ J ,
MMSi(J \ { jk } ,m− 1) > MMSi(J ,m).
We use Lemma 1 to design Algorithm 1 which repeatedly allocates a large job to some agent and removes them from the instance until there is no large job.
Algorithm 1. Matching Procedure Input: Arbitrary FISP instance I = (J ,A,uA); Thresholds (γ1, · · · , γm). Output: (1) Sub-instance I ′ = (J ′,A′,uA′) such that ui(jk) 6 ββ+2 ·γi for all ai ∈ A
′ and jk ∈ J ′; (2) Partial Schedule (Xr)ar∈A\A′ .
1: Initialize A′ = A and J ′ = J . 2: while there is an agent ai ∈ A′ and a job jk ∈ J ′ with ui(jk) > ββ+2 · γi do 3: Set Xi = { jk }, A′ = A′ \ { ai }, and J ′ = J ′ \ { jk }. 4: end while
By Lemma 1, it is straightforward to have the following lemma.
Lemma 2. For any instance I = (J ,A,uA) with (γ1, · · · , γm), the partial schedule (Xr)ar∈A\A′ and the reduced instance I ′ = (J ′,A′,uA′) returned by Algorithm 1 satisfy ur(Xr) > ββ+2 · γr for all ar ∈ A \A′ and MMSi(J ′, |A′|) > MMSi(J , |A|) for all ai ∈ A′.

heading: 3.1.2 Bag-Filling Procedure
text: Let I = (J ,A,uA) be an instance such that |A| = m and ui(jk) 6 ββ+2 · γi for all ai ∈ A and jk ∈ J . We show the Bag-Filling Procedure in Algorithm 2, with parameters (γ1, · · · , γm) and β-approximation algorithm for IS functions. For each ai ∈ A, we use u′i : 2J → R+ to denote the approximate utility, and thus u′i(S) > β · ui(S) for any S ⊆ J . Intuitively, it keeps a bag B and repeatedly adds an unscheduled job into it until some agent ai first values this bag (under the approximate utility function u′i) for at least β β+2 ·γi. If there are more than one such agents, arbitrarily
select one of them. Then ai gets assigned a feasible subset Xi ⊆ B with ∑ jl∈Xi ui(jl) = u ′ i(B), and returns B \Xi to the algorithm. This step is crucial, otherwise the other remaining agents may not obtain enough jobs. It is obvious that if agent ai gets assigned a bag, then her true utility satisfies
ui(Xi) = ∑ jl∈Xi ui(jl) = u ′ i(Xi) > β β + 2 · γi.
The major technical difficulty of our algorithm is to prove that everyone can obtain a bag.
Algorithm 2. BagFilling Procedure
Input: An FISP instance I = (J ,A,uA) such that ui(jk) 6 ββ+2 · γi for all ai ∈ A and jk ∈ J ; β-approximation algorithm for IS functions; Thresholds (γ1, · · · , γm). Output: ββ+2 -MMS schedule X = (X1, · · · ,Xm). 1: Initialize A′ = A, J ′ = J , and obtain approximate utility functions u′i for all ai ∈ A. 2: while A′ 6= ∅ and J ′ 6= ∅ do 3: Set B = ∅. 4: while u′i(B) < β β+2 · γi for all ai ∈ A
′ and J ′ 6= ∅ do 5: Let jk be an arbitrary job in J ′. Set B = B ∪ { jk } and J ′ = J ′ \ { jk }. 6: end while 7: Let ai be an arbitrary agent such that u′i(B) > β β+2 · γi.
8: Let Xi ⊆ B be a feasible subset such that ∑ jl∈Xi ui(jl) = u ′ i(B).
9: Set J ′ = J ′ ∪ (B \Xi) and A′ = A′ \ { ai }. 10: end while
Lemma 3. Setting γi = MMSi for all ai ∈ A, Algorithm 2 returns a ββ+2 -MMS schedule.
Proof. As we have discussed, it suffices to prove that at 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.,
u′i(J ′) >
β
β + 2 γi, for any ai ∈ A′.
To prove the above inequality, in the following, we actually prove a stronger argument.
Claim 1. For any ai ∈ A′, let X′ = (X ′1, · · · ,X ′m) be a feasible MMS schedule for ai. Then there exists k ∈ [m], such that ui(X ′k ∩ J ′) > 1β+2 · γi.
Given Claim 1 and the β-approximation of u′i, u ′ i(X ′ k ∩J ′) > β β+2 ·γi and thus the lemma holds. We prove by contradiction and assume Claim 1 does not hold for agent ai. Since X′ = (X ′1, · · · ,X ′m) is a feasible MMS schedule for ai, ui(X ′k) > MMSi = γi for all k ∈ [m] and thus∑
k∈[m]
ui(X ′ k) > m · γi. (1)
Denote by (Xr)ar∈A\A′ the assignments that are allocated toA\A′ in previous rounds by Algorithm 2, and for each ar, let jlr be the last item added to the bag B. Note that jlr ∈ Xr otherwise ar will stop the inner while loop (Step 4) before jlr was added. Moreover, since ai did not break the while loop either, u′i(Xr \ { jlr }) < β β+2 · γi. Thus ui(Xr \ { jlr }) 6 1 β+2 · γi as u ′ i is β-approximation of ui. By the assumption that all jobs are small, i.e., ui(jlr ) 6 β β+2 · γi, we have the following
ui(Xr) = ui(Xr \ { jlr }) + ui(jlr ) < β + 1
β + 2 · γi. (2)
If ui(X ′k ∩ J ′) < 1β+2 · γi for all k ∈ [m], then∑ k∈[m] ui(X ′ k) = ∑ k∈[m] ui(X ′k ∩ J ′) + ∑ ar∈A\A′ ui(X ′ k ∩Xr)  = ∑ k∈[m] ui(X ′ k ∩ J ′) + ∑ ar∈A\A′ ∑ k∈[m] ui(X ′ k ∩Xr)
6 ∑ k∈[m] ui(X ′ k ∩ J ′) + ∑ ar∈A\A′ ui(Xr)
< m · 1 β + 2 · γi + (m− |A′|) · β + 1 β + 2 · γi < m · γi,
where the first inequality is because the X ′k’s are disjoint and the second inequality is because of Equation (2). Thus we obtain a contradiction with Equation (1).

heading: 3.1.3 Main Existential Theorem
text: Combining Lemma 2 and Lemma 3, it is not hard to 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-BagFilling Input: An arbitrary FISP instance I = (J ,A,uA); β-approximation algorithm for IS functions;
Thresholds (γ1, · · · , γm). Output: ββ+2 -MMS schedule X = (X1, · · · ,Xm).
1: Run Algorithm 1 on I with (γ1, · · · , γm). Obtain I ′ = (J ′,A′,uA′) and (Xr)ar∈A\A′ . 2: Run Algorithm 2 on I ′ with (γ1, · · · , γm) and the β-approximation algorithm. Obtain (Xi)ai∈A′ .
Theorem 1. Algorithm 3 with the optimal algorithm for IS functions (i.e., β = 1) and γi = MMSi for all ai ∈ 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 bagfilling algorithm, the authors prove the existence of 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.

heading: 3.2 Polynomial-time Implementation
text: Note that, in general, Algorithm 3 is not efficient, because if P 6= 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 pseudo-polynomial time Chiarelli et al. [2020]. Thus, in this section, we deal with the general case. Of course, for IS functions, we can directly use the β-approximation 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.
First, an important corollary of Lemma 2 and Lemma 3 is that if γi 6 MMSi for some ai, no matter what values are set for γj , j 6= i, Algorithm 3 always assigns a bag to ai such that ui(Xi) > ββ+2γi.
Lemma 4. For any ai, if γi 6 MMSi, Algorithm 3 ensures that ui(Xi) > ββ+2γi, regardless of γ−i.
We prove Lemma 4 in the full version Li et al. [2021]. Now, we are ready to introduce the trick. First, we set each γi to be sufficiently large such that γi > MMSi for all ai. Then we run Algorithm 3. If we found some agent ai with ui(Xi) < ββ+2γi, it means γi is higher than MMSi and we can decrease γi by 0 < 1− < 1 fraction and keep the other MMS values unchanged. We repeat the above procedure until everyone is satisfied ui(Xi) > ββ+2γi. By Lemma 4, it must be that γi > (1− )MMSi for all ai. We summarize this in Algorithm 4, and it is straightforward to have the following theorem.
Algorithm 4. Efficient Implementation: Matching-BagFilling Input: An arbitrary FISP instance I = (J ,A,uA); β-approximation polynomial-time algorithm for
IS functions; Thresholds (γ1 = u′1(J) β , · · · , γm = u′m(J) β ); 0 < < 1.
Output: β(β+2) (1− )-MMS schedule X = (X1, · · · ,Xm). 1: Run Algorithm 3 on I with (γ1, · · · , γm). Obtain X = (X1, · · · ,Xm). 2: while there exist ai ∈ A such that u′i(Xi) < β β+2γi do
3: Set γi = (1− )γi. 4: Run Algorithm 3 on I with (γ1, · · · , γm) and update X = (X1, · · · ,Xm). 5: end while
Theorem 2. For any 0 < < 1, Algorithm 4 returns a ββ+2 (1 − )-MMS schedule for arbitrary FISP instance with an β-approximation algorithm for IS functions. The running time is polynomial with |J |, |A| and 1/ . Particularly, using the 0.64-approximation algorithm in Im et al. [2020], we have 0.24(1− )-approximation polynomial-time algorithm.

heading: 4 Approximately EF1 and PO Scheduling

heading: 4.1 Compatibility of EF1 and PO
text: In this section, we investigate the extent to which there is a schedule that is both EF1 and PO. We first show that EF1 and PO are not compatible even if jobs are rigid and valuations are unary, i.e., ui(jk) = 1 for all ai ∈ A and jk ∈ J . That is no algorithm can return an EF1 and PO schedule for all instances. Fortunately, if the jobs have unit processing time, an EF1 and PO schedule exists and can be computed in polynomial time. This result continues to hold if the agents have weighted but identical utilities, i.e., ui(jk) = ur(jk) for any job jk and any two agents ai and ar. We sometimes ignore the subscript and use u(·) to denote the identical valuation.
Algorithm 5. m-Matching + Inner-Greedy Input: An FISP instance I = (J ,A,uA), where all jobs have unit processing time and all agents
have identical valuation. Output: EF1 and PO schedule X = (X1, · · · ,Xm).
1: Construct graph G(J ∪ T ,E), and compute a maximum weighted m-matchingM∗. 2: Define Jt = { j ∈ J | (j, t) ∈M∗ } for each t ∈ T . 3: Set X1 = X2 = · · · = Xm = ∅. 4: for p = 1 to |T | do 5: if Jp 6= ∅ then 6: Sort A in non-decreasing order of ui(Xi)’s, and Jp in non-increasing order of u(jk)’s. 7: for i = 1 to |Jp| do 8: Set Xi = Xi ∪ { ji }. 9: end for
10: end if 11: end for
Theorem 3. EF1 and PO are not compatible even if all jobs are rigid and all valuations are unary. If all jobs have unit processing time, Algorithm 5 returns an EF1 and PO schedule in polynomial time, as long as the valuations are identical.
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 EF1.
To solve the first task, we use bipartite matchings. Let Ti = [ri, di] = { ri, ri + 1, · · · , di } be the job interval for each ji ∈ J , and T = ⋃ 16i6n Ti. We first construct a weighted bipartite graph G(J ∪ T ,E), where each job ji ∈ J is a node on the left side, and a time slot tl ∈ T is a node on the right side. There is an edge (ji, tl) ∈ E with weight u(ji) if and only if tl ∈ Ti. For any set B ⊆ E and v ∈ J ∪ T , let B(v) ⊆ E be the set of edges in B that intersects v. Next we define m-matching M ⊆ E, which requires that |M(ji)| 6 1 for all ji ∈ J and |M(tl)| 6 m for all tl ∈ 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-matchingM∗, 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|T |}, and each group Jt contains the jobs that are matched to time slot t by M∗. To maintain feasibility, each agent can get at most one job from each Jt. We process {J1, · · · , J|T |} one by one, and to satisfy EF1, the agent with low cumulative utility should obtain a better job in the next group. By induction, we can prove that eventually, the assignment is indeed EF1.
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].

heading: 4.2 Approximate EF1 and PO
text: Although EF1 and PO are only compatible in special cases, in this section we show that approximate EF1 and PO can be always satisfied. Theorem 4 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/4-EF1 and PO. If all jobs have unit processing time, there is a feasible schedule that is 1/2-EF1 and PO.

heading: 5 Experiment
text: Finally, we evaluate the performance of Matching-BagFilling on randomly generated data sets, and compare it with the extensively adopted heuristic algorithm Round-Robin: 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 Matching-BagFilling has good theoretical guarantee, for many concrete instances, it can be significantly improved. Since each agent only selects a bag with 1/3MMSi, there might be lots of unscheduled jobs that can be feasibly processed. Therefore, we first refine our algorithm as Matching-BagFilling+: (1) Run Matching-BagFilling; (2) Run Round-Robin on the remaining unscheduled jobs. We formally describe Round-Robin and Matching-BagFilling+ in the full version Li et al. [2021]. Note that Matching-BagFilling+ does not have better theoretical performance than Matching-BagFilling.
In our experiment, as shown in Figure 1, we randomly generate a set of rigid jobs J (|J | = 100, 500, 1000) and a set of agents A following some distribution, where for i = 1, 2, 3, U/P/N .i means there are |A| = 5 × i 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-BagFilling+ (short for BAG+), Matching-BagFilling (short for BAG), and RoundRobin (short for RR) and record every agent ai’s average utilities ui(BAG+),ui(BAG),ui(RR). Then we compute the ratios ui(BAG+)/ui(RR) and ui(BAG)/ui(RR). Of course, if these ratios are greater than 1, it 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-BagFilling+. Compared with the number of agents, if the number of jobs is small (e.g.
|A| = 15 and |J | = 100, 500, 1000), Matching-BagFilling has decent performance. However, as the number of jobs gets larger (e.g., |A| = 5 and |J | = 100, 500, 1000), Matching-BagFilling is clearly worse than Round-Robin, which is because too many jobs are left unscheduled. We defer a detailed description of our experiments and the discussion of results to the full version Li et al. [2021].

heading: 6 Conclusion and Future Directions
text: In this work, we studied the fair scheduling problem for time-dependent resources, and designed constant approximation algorithms for MMS, EF1&PO and EF1&IO schedules. There are 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. It is also interesting to impose other efficiency criteria on EF1 schedules, such as computing an EF1 schedule that maximizes social welfare. In this work, we have assumed the jobs are resources that bring utility to agents, and leave the case when jobs are chores for future study. Finally, it is of both theoretical interest and practical importance to 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 Li was partially supported by NSFC under Grant No. 11771365, and by Project No. CityU 11200518 from Research Grants Council of HKSAR.

Review summaries:
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.

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.   The paper obtains novel approximation algorithms for various problems arising in this setting, improving upon the existing best results for some of them. 

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.  Two 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. 

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:  - 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.  With 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.  -  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.  The 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.)