# fair_scheduling_for_timedependent_resources__64f8f3d1.pdf

Fair Scheduling for Time-dependent Resources

Bo Li Department of Computing The Hong Kong Polytechnic University Hung Hom, Hong Kong comp-bo.li@polyu.edu.hk

Minming Li Department of Computer Science City University of Hong Kong Kowloon Tang, Hong Kong minming.li@cityu.edu.hk

Ruilong Zhang Department of Computer Science City University of Hong Kong Kowloon Tang, Hong Kong ruilzhang4-c@my.cityu.edu.hk

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.

1 Introduction

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 (Neur IPS 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].

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

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 Das Gupta [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].

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, A, u A). 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 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 u A = (ui)i A. For a feasible set of jobs S, the agent s utility is additive, i.e., ui(S) = P

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 = j and X1 Xm J. Let X0 = J \ S 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 \ S

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

2.2 Solution Concepts

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, u A) with m = |A|, agent ai A s maximin share (MMS) is given by MMSi(J, m) = MMSui(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 < α 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 < α 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.

3 Approximately MMS Scheduling

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.

3.1 Algorithmic Framework

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

3.1.1 Pre-processing

As we will see, the above bag-filling algorithm works well only if the jobs are small, i.e., ui(jk) β β+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, u A) 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, u A); Thresholds (γ1, , γm). Output: (1) Sub-instance I = (J , A , u A ) such that ui(jk) β β+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, u A) with (γ1, , γm), the partial schedule (Xr)ar A\A and the reduced instance I = (J , A , u A ) 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 .

3.1.2 Bag-Filling Procedure

Let I = (J, A, u A) be an instance such that |A| = m and ui(jk) β β+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 P

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

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. Bag Filling Procedure

Input: An FISP instance I = (J, A, u A) such that ui(jk) β β+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 = and J = do 3: Set B = . 4: while u i(B) < β β+2 γi for all ai A and J = 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 P

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 X

k [m] ui(X k) m γi. (1)

Denote by (Xr)ar A\A the assignments that are allocated to A\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 }) 1 β+2 γi as u i is β-approximation of ui.

By the assumption that all jobs are small, i.e., ui(jlr) β β+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) = X

ui(X k J ) + X

ar A\A ui(X k Xr)

k [m] ui(X k J ) + X

k [m] ui(X k Xr)

k [m] ui(X k J ) + X

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

3.1.3 Main Existential Theorem

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-Bag Filling

Input: An arbitrary FISP instance I = (J, A, u A); β-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 , u A ) 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.

3.2 Polynomial-time Implementation

Note that, in general, Algorithm 3 is not efficient, because if P = 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 MMSi for some ai, no matter what values are set for γj, j = i, Algorithm 3 always assigns a bag to ai such that ui(Xi) β β+2γi.

Lemma 4. For any ai, if γi 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-Bag Filling

Input: An arbitrary FISP instance I = (J, A, u A); β-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.

4 Approximately EF1 and PO Scheduling

4.1 Compatibility of EF1 and PO

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, u A), 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-matching M . 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 = 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 = S

1 i n 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)| 1 for all ji J and |M(tl)| 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-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|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].

4.2 Approximate EF1 and PO

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.

5 Experiment

Finally, we evaluate the performance of Matching-Bag Filling 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-Bag Filling 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-Bag Filling+: (1) Run Matching-Bag Filling; (2) Run Round-Robin on the remaining unscheduled jobs. We formally describe Round-Robin and Matching-Bag Filling+ in the full version Li et al. [2021]. Note that Matching-Bag Filling+ does not have better theoretical performance than Matching-Bag Filling.

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-Bag Filling+ (short for BAG+), Matching-Bag Filling (short for BAG), and Round Robin (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-Bag Filling+ clearly outperforms Round-Robin, i.e., every agent gets higher utility in Matching-Bag Filling+. Compared with the number of agents, if the number of jobs is small (e.g.

|A| = 15 and |J| = 100, 500, 1000), Matching-Bag Filling has decent performance. However, as the number of jobs gets larger (e.g., |A| = 5 and |J| = 100, 500, 1000), Matching-Bag Filling 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].

U.1 U.2 U.3 P .1 P .2 P .3 N.1 N.2 N.3

U.1 U.2 U.3 P .1 P .2 P .3 N.1 N.2 N.3

U.1 U.2 U.3 P .1 P .2 P .3 N.1 N.2 N.3

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, 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. City U 11200518 from Research Grants Council of HKSAR.

Miklós Ajtai, James Aspnes, Moni Naor, Yuval Rabani, Leonard J. Schulman, and Orli Waarts. Fairness in scheduling. J. Algorithms, 29(2):306 357, 1998.

Rasha A. Al-Arasi and Anwar Saif. Task scheduling in 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. Algorithms, 13(4):52:1 52: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 Neur IPS, 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., 31(2):331 352, 2001.

Siddharth Barman and Sanath Kumar Krishnamurthy. Approximation algorithms for maximin fair division. ACM Trans. Economics and Comput., 8(1):5:1 5:28, 2020.

Siddharth Barman and Paritosh Verma. Existence and computation of maximin fair allocations under matroid-rank valuations. In AAMAS, pages 169 177. 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 816, 1998.

Sanjoy K. Baruah. Fairness in periodic real-time scheduling. In RTSS, pages 200 209. IEEE Computer Society, 1995.

Piotr Berman and Bhaskar Das Gupta. 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. ijcai.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 Krnc, Martin Milanic, Ulrich Pferschy, Nevena Pivac, and Joachim Schauer. Fair packing of independent sets. In IWOCA, 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-Halevi. On fair division under heterogeneous matroid constraints. Co RR, abs/2010.07280, 2020.

Amitay Dror, Michal Feldman, and Erel Segal-Halevi. 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. Co RR, abs/2104.04977, 2021.

Jiarui Gan, Bo Li, and Xiaowei Wu. Approximately envy-free budget-feasible allocation. Co RR, abs/2106.14446, 2021.

M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. 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 conflicting items. Co RR, abs/2104.06280, 2021.

Sungjin Im and Benjamin Moseley. Fair scheduling via iterative quasi-uniform sampling. SIAM J. Comput., 49(3):658 680, 2020.

Sungjin Im, Shi Li, and Benjamin Moseley. Breaking 1 - 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. Co RR, abs/2107.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 personalized apprenticeship scheduling: Learning interpretable scheduling policies from heterogeneous user demonstrations. In Neur IPS, 2020.

Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ML predictions. In Neur IPS, 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. In Neur IPS, pages 15750 15761, 2019.

Alexander Schrijver. Theory of linear and integer programming. Wiley-Interscience series in discrete mathematics and optimization. Wiley, 1999.

Warut Suksompong. Constraints in fair division. SIGecom Exch., 19(2):46 61, 2021.

Xiaowei Wu, Bo Li, and Jiarui Gan. Budget-feasible maximum nash social welfare allocation is almost envy-free. In IJCAI. ijcai.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 Neur IPS, 2020.