EFX Feasible Scheduling for Time-dependent Resources

1 Introduction

The fair division problem aims to address how to allocate limited resources among multiple agents with individual preferences in a manner that is both fair and efficient. Classical literature on fair division primarily focuses on divisible resources [Deng et al., 2012; Aziz and Mackenzie, 2016]. Recently, the fair division of indivisible resources has gained significant attention, where resources must be integrally allocated to agents. This has become an important research area in economics, operations research, and computer science [Brams and Taylor, 1996; Brandt et al., 2016; Moulin, 2019]. It has numerous real-world applications, such as the fair division of courses [Budish et al., 2017], public housing [Benabbou et al., 2020], food donations [Aleksandrov et al., 2015], and inheritance [Goldman and Procaccia, 2015].

An important fairness concept in fair division is envyfreeness (EF) [Varian, 1974], which requires that no agent prefers another agent's bundle over their own. However, EF allocation does not always exist for indivisible resources. For example, if there is only one resource and two agents, an EF allocation cannot be achieved. A significant relaxation of EF is the concept of envy-freeness up to one item (EF1) [Richard et al., 2004], which allows for envy between two agents as long as there exists an item in the envied agent's bundle that, when removed, can eliminate the envy. [Caragiannis et al., 2019b] proposed another notable fairness concept, envy-freeness up to any good (EFX), which balances between the stronger concept of EF and the weaker concept of EF1. EFX assumes that removing any positive value item from the envied agent's bundle can eliminate the envy. Unlike the universal existence of EF1, the existence of EFX allocations remains uncertain. Indeed, establishing the existence of EFX allocations is widely regarded as one of the core open problems in the fair division of indivisible resources.

∗Corresponding Authors.

In addition to fairness requirements, resource allocators also seek efficient allocations. A commonly used efficiency criterion is Pareto optimality (PO), where an allocation is Pareto optimal if no other allocation can make someone better off without making someone else worse off. [Caragiannis et al., 2019b] analyzed the properties of allocations that maximize Nash social welfare (MaxNSW) and demonstrated that for additive valuation functions, there exist MaxNSW allocations that satisfy both EF1 and PO, where Nash social welfare is defined as the geometric mean of all agents' valuations [Kaneko and Nakamura, 1979]. However, since computing a MaxNSW allocation is NP-hard, this result only establishes the existence of EF1+PO allocations. Consequently, extensive research has aimed to design algorithms that can simultaneously optimize both fairness and efficiency [Barman et al., 2018a; Barman and Krishnamurthy, 2019; Garg and Murhekar, 2023].

In most of the literature on fair division, any subset of items can be feasibly allocated to any agent. However, this assumption is not applicable in many scenarios. For example, in the Student Affairs Office (SAO) problem, SAO staff needs to allocate jobs to students applying for work, where each job has a release time, a deadline, and a consecutive processing time and students earn compensation by getting jobs. A feasible job allocation requires that the jobs assigned to a student can be scheduled without overlapping in time. Motivated by this scenario, [Li et al., 2021] introduced the fair interval scheduling problem (FISP) where a set of interval jobs is allocated to heterogeneous machines controlled by agents. Each job is associated with a release time, a deadline, and a processing time, and it can be processed if its processing period falls between its release time and deadline. Each machine can only process one job at any given time, and different machines may derive different utilities from processing the same job.

Additionally, all jobs assigned to the same machine must be processed without overlapping in time. They investigated the existence and computability of approximate maximin share fairness (MMS) and EF1 schedules.

However, the fairness guarantee of EF1, limited to the most valuable item, is often too weak. This paper continues the study of FISP and explores a stronger fairness concept, EFX. It aims to investigate the computability of schedules that satisfy EFX and various efficiency concepts.

1.1 Our Contribution

We study the fair interval scheduling problem (FISP), where fairness is captured by EFX. We also consider several efficiency concepts: MaxNSW, PO, and Weakly Individual Optimal (WIO).

Our main contributions are summarized as follows.

EFX +MaxNSW+ PO. We first consider binary valuation functions, where agents' valuations for jobs are restricted to 1 or 0. We explore the characteristics of MaxNSW schedules, focusing on fairness guarantees (approximate EFX) and efficiency guarantees (PO).

Main Result 1: For any instance of FISP with binary valuations, there exists a MaxNSW schedule that is 12 -EFX and PO. Additionally, there exist instances where no MaxNSW schedule can guarantee ( 12 + ε)-EFX for any ε > 0.

Main Result 2: For any instance of FISP with binary valuations and jobs with unit processing times, there exists a MaxNSW schedule that is EFX and PO, and it can be computed in polynomial time.

Next, we find that under general valuation functions, the approximation guarantee of EFX is related to the non-zero range parameter γ, defined as the ratio of the maximum valuation to the minimum non-zero valuation among all agents.

Main Result 3: For any instance of FISP, there exists a MaxNSW schedule that is 1 γ 2 -EFX and PO. When all jobs have unit processing times, there exists a MaxNSW schedule that is 1 γ+1 -EFX and PO. Additionally, in both settings, there exist instances where no MaxNSW schedule can guarantee ( 1 γ + ε)-EFX for any ε > 0.

EFX + WIO. [Li et al., 2021] proved the incompatibility between Individual Optimal (IO) (no one envies the union of their assigned jobs and the unassigned jobs) and EF1, even for FISP with identical valuation functions. This implies that IO is also incompatible with the stronger fairness concept, EFX. Therefore, we consider the relaxed version of IO, known as WIO, which means that no one envies the unassigned jobs. We first provide an algorithm framework demonstrating the compatibility between WIO and EFX for all instances of FISP. Then, we show that finding a WIO schedule is NP-hard. Finally, we present a polynomial-time algorithm that approximates both EFX and WIO.

Main Result 4: There exists an algorithm that can return a feasible schedule that is both EFX and WIO for all FISP instances.

Main Result 5: For any 0 < ε < 1, there exists a polynomial-time algorithm that can return a feasible schedule that is both 0.644(1 - ε)-EFX and 0.644-WIO for all FISP instances. The running time is polynomial in |J|, |A|, and

1ε , where |J| is the number of jobs and |A| is the number of agents.

1.2 RelatedWork

The scheduling problem. [Johnson and Garey, 1979] showed that computing the maximum feasible set of jobs is NP-hard. Subsequently, various approximation algorithms have been proposed [Chuzhoy et al., 2006; Berman and DasGupta, 2000], with the currently best-known approximation ratio being 0.644 [Im et al., 2020]. For instances with rigid jobs, [Schrijver, 1998] provided a polynomial-time algorithm to solve the problem. Various fairness criteria have also been proposed, including minimizing the maximum deviation from a desired load [Ajtai et al., 1998], minimizing the ℓp norm of flow time [Im et al., 2020], and analyzing the welfare degradation resulting from the imposition of fairness constraints [Bil`o et al., 2016].

EFX + MaxNSW/PO. We primarily review the literature on the compatibility of EFX with various efficiency concepts. For binary additive valuations, any MaxNSW allocation is EFX [Amanatidis et al., 2021]. [Garg and Murhekar, 2023] showed that for instances with binary additive valuations, EFX and PO allocations can be computed in polynomial time, but for instances with three distinct values, EFX and PO are incompatible. [Babaioff et al., 2021] proved that under submodular and dichotomous valuations, any MaxNSW allocation is EFX. [Caragiannis et al., 2019a] proved that under additive valuation functions, there exist partial allocations that are EFX and 12 -MaxNSW (where some items may remain unallocated). [Garg et al., 2023] showed that even under subadditive valuation functions, there exist complete allocations that are 12 -EFX and 12 -MaxNSW. [Feldman et al., 2024] provided optimal trade-offs between EFX and MaxNSW for additive and subadditive valuation functions. [Dai et al., 2024] investigated the relationship between EFX and MaxNSW under budget constraints, proving that for binary valuation functions, MaxNSW can guarantee 14 -EFX and PO. However, even under unconstrained additive valuations, computing a MaxNSW allocation is NP-hard [Ramezani and Endriss, 2010]. [Barman et al., 2018b] showed that for binary additive valuations, a MaxNSW allocation that is both EFX and PO can be found in polynomial time. [Benabbou et al., 2021] proved that for matroid rank functions, MaxNSW can be found in polynomial time.

The most relevant works to ours are [Li et al., 2021] and [Kumar et al., 2024]. [Li et al., 2021] proposed the fair interval scheduling problem, and investigated fairness concepts of MMS and EF1. They showed that any MaxNSW schedule is 14 -EF1 and PO, and for jobs with unit processing times, it is 12 -EF1 and PO. They also introduced the efficiency concept of individual optimality (IO), and considered the compatibility of EF1 and IO. When switching EF1 to EFX, IO is difficult to achieve. Therefore, we consider a relaxed version of IO, known as weakly individual optimality (WIO), which is referred to as bounded charity in some literature [Barman et al., 2023]. [Kumar et al., 2024] considered the fair interval scheduling problem for indivisible chores by constructing interval graphs and studying the existence and computability of schedules that are both EF1 and maximal.

2 Preliminaries

2.1 Fair Interval Scheduling Problem

Problem instance. We follow the notation used by [Li et al., 2021]. An instance I of the fair interval scheduling problem (FISP) is given by a tuple (J,A, uA), where J = {j1, . . . , jn} represents a set of n indivisible jobs and A = {a1, . . . , am} is a set of m agents (machines). The timeline consists of disjoint unit time slots [0, 1), [1, 2), [2, 3), and so on. For any 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 pi ∈ N+ such that pi ≤ di - ri + 1. We refer to [ri, di] as a job interval, which can be viewed as a set of contiguous time slots from ri to di, denoted as {ri, . . . , di}. If pi contiguous time slots within [ri, di] are allocated to job ji, then job ji can be successfully processed. An agent can process at most one job in any given time slot. A set of jobs J ′ ⊆ J is called feasible if all jobs in J ′ can be processed on a single machine without overlapping. Define ui : 2J → R≥0 as the valuation function of agent ai ∈ A, and uA = {u1, . . . , um} as the valuation profile of the m agents. We call these ui(·) interval scheduling (IS) functions. For a job jk ∈ J, if jk is successfully processed by agent ai, then agent ai receives a utility ui({jk}) ≥ 0. For simplicity, denote ui({jk}) as ui(jk). For a feasible job set S, the utility of agent ai is additive, i.e., ui(S) = ∑jk∈S ui(jk). For any infeasible job set S, the utility of agent ai is the maximum value obtainable by processing a feasible subset of S, i.e.,

Non-zero range parameter. Part of our approximation guarantees for the fairness concept is related to the nonzero range parameter γ ≥ 1, which depends on the range of non-zero valuations. Formally, for any given instance I = (J, A, uA), the non-zero range parameter is defined as

Schedule (Allocation). A schedule X = (X1, · · · ,Xm) is defined as an ordered m-partition of a subset of J, where Xi is the set of jobs (or bundle) assigned to agent ai. Thus, we have X1 ∪ · · · ∪ Xm ⊆ J and Xi ∩ Xj = ∅ for every pair of agents ai, aj ∈ A. Let X0 = J\ ⋃i∈[m] Xi denote all unscheduled jobs, which can be considered as donated 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. A schedule X is called non-wasteful if jk ∈ Xi implies ui(jk) > 0 for all jk ∈ J, ai ∈ A, and wasteful otherwise.

Special instance class. Regarding agents' valuations, we consider (1) Binary: ui(jk) ∈ {0, 1} for all ai ∈ A, jk ∈ J; (2) Identical: ui(jk) = ur(jk) for all ai, ar ∈ A, jk ∈ J; (3) General: ui(jk) ≥ 0 without any restrictions. Regarding jobs, we consider (1) Unit: pi = 1, for all ji ∈ J, i.e., all jobs have unit processing time; (2) Rigid: ri + pi - 1 =

di, for all ji ∈ J, i.e., each job needs to occupy the entire time interval between release time and deadline; (3) Flexible: ri + pi - 1 ≤ di, for all ji ∈ J. Note that unit jobs may not be rigid and rigid jobs may not be unit either. We use "FISP with <valuation type, job type>" to denote a special instance class of FISP.

2.2 Solution Concepts

We define the fairness and efficiency concepts considered in this paper as follows.

Fairness Concepts

Definition 1 (α-EF1 Schedule). For 0 < α ≤ 1, a feasible schedule X = (X1, · · · ,Xm) is called α-approximate envyfree up to one item (α-EF1) if for any two agents ai, ak ∈ A, we have

Definition 2 (α-EFX Schedule). For 0 < α ≤ 1, a feasible schedule X = (X1, · · · ,Xm) is called α-approximate envyfree up to any item (α-EFX) if for any two agents ai, ak ∈ A, we have

Definition 3 (α-EFX Envy). Given a feasible schedule X = (X1, · · · ,Xm), for any two agents ai, ak ∈ A and 0 < α ≤ 1, we say ai α-EFX envies ak if

Efficiency Concepts

Definition 4 (MaxNSW Schedule). A feasible schedule X = (X1, · · · ,Xm) is called MaxNSW schedule if and only if

where F is the set of all feasible schedules and X′ = (X′1 , · · · ,X′m).

Definition 5 (PO Schedule). A feasible schedule X = (X1, · · · ,Xm) is called Pareto optimal (PO) if there does not exist an alternative feasible 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.

Definition 6 (α-IO Schedule [Li et al., 2021]). For 0 < α ≤ 1, a feasible schedule X = (X1, · · · ,Xm) with X0 = J\ ⋃i∈[m] Xi is called α-approximate individual optimal (αIO) if ui(Xi) ≥ α · ui(X0 ∪ Xi) for all ai ∈ A. When α = 1, X is called an IO schedule.

[Li et al., 2021] proved the incompatibility between EF1 and IO even for FISP with <Identical, Rigid>. Therefore, we consider the relaxed version of IO, called WIO.

Definition 7 (α-WIO Schedule). For 0 < α ≤ 1, a feasible schedule X = (X1, · · · ,Xm) with X0 = J\ ⋃i∈[m] Xi is called α-approximate weakly individual optimal (α-WIO) if ui(Xi) ≥ α · ui(X0) for all ai ∈ A. When α = 1, X is called a WIO schedule.

3 Approximately EFX andMaxNSW Scheduling

In this section, we establish interesting connections between EFX and MaxNSW schedules by analyzing the performance of the non-wasteful MaxNSW schedules. We also explore the conditions under which a schedule can be both EFX and PO.

Clearly, if an agent's valuation for a job is 0, a natural idea is not to assign that job to him, as doing so would not only waste machine resources but also fail to generate any social welfare. Therefore, we primarily concentrate on the non-wasteful MaxNSW schedules. It is noteworthy that for an arbitrarily wasteful schedule, we can always transfer the 0-valued jobs assigned to agents to the charity, resulting in a non-wasteful schedule with the same Nash social welfare. This also implies that the non-wasteful MaxNSW schedules must exist.

3.1 <Binary, Flexible>

We first consider the relationship between EFX and the nonwasteful MaxNSW schedules in binary valuation instances. Our main result shows that for any binary valuation instance I, there exists a MaxNSW schedule that is both 12 -EFX and PO. Moreover, the 12 -approximation is the best EFX guarantee achievable among all MaxNSW schedules.

The following results provide the worst-case EFX approximation guaranteed by the non-wasteful MaxNSW schedules on any instance I with MaxNSW(I) > 0. All the omitted proofs are presented in the full version of our paper.

Theorem 1. Given an arbitrary instance I of FISP with <Binary, Flexible>, if MaxNSW(I) > 0, then any nonwasteful MaxNSW schedule is 14 -EFX and PO.

However, for an instance I with MaxNSW(I) = 0, it is possible for a non-wasteful MaxNSW schedule to have an unbounded EFX approximation. We now consider the best possible EFX approximation guarantee achievable by the nonwasteful MaxNSW schedules.

We first establish the relationship between instances where the maximum Nash social welfare is greater than 0 and those where the maximum Nash social welfare equals 0, allowing us to focus solely on instances where MaxNSW(I) > 0 when analyzing the relationship between EFX and MaxNSW schedules.

Lemma 1. For any FISP with <valuation type, job type>, if for all instances I with MaxNSW(I) > 0, there exists a non-wasteful MaxNSW schedule that is α-EFX and PO, then for any instance I ′ with MaxNSW(I ′ ) = 0, there must exist a non-wasteful MaxNSW schedule that is α-EFX and PO, where 0 < α ≤ 1.

Then, before presenting the main results of this subsection, we provide a key lemma that guarantees the elimination of 12 - EFX envy between agents for any binary valuation instance.

Lemma 2. For an arbitrary instance I with MaxNSW(I) > 0 of FISP with <Binary, Flexible> and any non-wasteful MaxNSW schedule X = (X1, . . . ,Xm), if there exist i, k ∈ [m] such that ai 12 -EFX envies ak, then there exist a set T ⊂ Xi containing |Xi| - 1 jobs and a set S ⊂ Xk containing 2 jobs that ai values non-zero, such that T ∪ S is feasible.

Theorem 2. Given an arbitrary instance I of FISP with <Binary, Flexible>, there exists a non-wasteful MaxNSW schedule which is 1 2 -EFX and PO.

Proof. By Lemma 1, we only need to show that the conclusion holds for all instances I with MaxNSW(I) > 0. Theorem 1 has already proven that any non-wasteful MaxNSW schedule is PO. Below, we present the procedure to find a non-wasteful MaxNSW schedule that satisfies 12 -EFX.

For any non-wasteful MaxNSW schedule X = (X1, . . . ,Xm) with X0 = J\ ∪i∈[m] Xi, if X is 12 - EFX, then the proof is complete. Otherwise, there must exist i, k ∈ [m] such that ai 12 -EFX envies ak, i.e.,

By Lemma 2, there exist a set T ⊂ Xi containing |Xi| - 1 jobs and a set S ⊂ Xk containing 2 jobs that ai values nonzero, such that T ∪ S is feasible for ai.

Now we construct a new schedule X′ = (X′1 , . . . ,X ′m), where X′r = Xr, ∀r ∈ [m], r ̸= i, k; X′ i = T ∪ S; X′k = Xk \ S; and X′0 = J \ ⋃i∈[m] X′ i . We can observe that in the new schedule X′ , the utility of ai increases by 1, the utility of ak decreases by 2, and the utilities of other agents remain unchanged. Specifically, ui(X′ i ) = ui(Xi) + 1, uk(X′k ) = uk(Xk) - 2, ur(X′r ) = ur(Xr), ∀r ∈ [m], r ̸= i, k. Also,

where the first equality and the first inequality hold due to X being non-wasteful, and the last inequality holds due to inequality (1) and the fact that ui(Xi \{jp}) is an integer, we have

Thus, by iterating this process, we can eliminate the 1 2 - EFX envy between ai and ak without losing Nash social welfare. In the same manner, we can eliminate 1 2 -EFX envy between any pair of agents, thereby obtaining a non-wasteful MaxNSW schedule that satisfies 12 -EFX.

Remark 1. In fact, Theorem 2 provides a conversion procedure from any MaxNSW schedule to a 1 2 -EFX MaxNSW schedule. Each step that eliminates 12 -EFX envy results in an increase in the number of jobs allocated to charity, implying that a non-wasteful MaxNSW with the maximum number of charity jobs must be 12 -EFX. However, finding a MaxNSW schedule is NP-hard, and thus, we cannot implement this procedure efficiently.

We now provide an example to show that the 1 2 - approximation of EFX is optimal.

Theorem 3. There exists an instance I of FISP with <Binary, Rigid> such that no MaxNSW schedule of I is ( 1 2 + ε)-EFX, where ε > 0.

3.2 <Binary, Unit>

[Li et al., 2021] showed that EF1 and PO are incompatible even if jobs are rigid and valuations are unary, i.e., ui(jk) = 1, ∀ai ∈ A, ∀jk ∈ J. This implies that no algorithm can return a feasible schedule that is both EFX and PO for all instances of FISP with <Binary, Rigid>. Fortunately, we find that for any instance of FISP with <Binary, Unit>, there exists a non-wasteful MaxNSW schedule that is both EFX and PO and it can be found in polynomial time.

Theorem 4. Given an arbitrary instance I of FISP with <Binary, Unit>, if MaxNSW(I) > 0, then any non-wasteful MaxNSW schedule is EFX and PO; if MaxNSW(I) = 0, then there exists a non-wasteful MaxNSW schedule that is EFX and PO.

For any instance I of FISP with <Binary, Unit>, we present below a polynomial-time algorithm to find a MaxNSW schedule that is both EFX and PO. Algorithm 1 is based on the proof of Lemma 1. Specifically, it first maximizes the number of agents with non-zero utility by finding the maximum matching. Subsequently, agents not matched in the maximum matching are assigned empty bundles. For the sub-instance I ′ formed by removing the unmatched agents from I, it is clear that MaxNSW(I ′ ) > 0. According to the proof of Lemma 1 and Theorem 4, it suffices to find a nonwasteful MaxNSW schedule for I ′ in polynomial time.

For I ′ , starting with any feasible schedule, the algorithm adopts the simplest schedule update method, where in each update, each agent can add at most one job and remove at most one job, represented by constructing a directed graph. At each update step, the algorithm selects the update that maximizes the Nash social welfare increment among all feasible updates following this method. Lemma 4 quantifies the Nash social welfare increment achieved by each such schedule update. Theorem 5 proves that by performing at most (2m - 1) · n · ln 4n2 m scheduling updates, we can obtain a MaxNSW schedule that satisfies both EFX and PO. Lemma 3 guarantees that our algorithm can be completed in polynomial time.

A polynomial-time algorithm. The detailed description of the algorithm is as follows: Firstly, construct a bipartite graph G(A ∪ J,E), where an edge (ai, jk) exists if and only if ui(jk) = 1. Then, compute a maximum matching M = AM ∪ JM of G. If agent ai is not matched, an empty bundle is assigned, i.e., Xi = ∅. Thus, we obtain a sub-instance I ′ = (J,AM, uAM ) with MaxNSW(I ′ ) > 0. Finally, find a non-wasteful MaxNSW schedule for instance I ′ . To simplify notation, in the following, we still let AM = A.

For the sub-instance I ′ , each agent initially receives the job in the maximum matching M. In each subsequent iteration, the algorithm greedily finds a feasible schedule update that increases Nash social welfare (NSW). Specifically, for any iteration t, the algorithm construct a directed graph G′ (Xt-1 ) based on the current schedule Xt-1 and Xt-1 0 = J\ ∪i∈[m] Xt-1 i , where the vertex set is V = V1 ∪ V2.

Here, V1 = {v0, v1, . . . , vm} represents charity and all agents, and vertices in V1 are referred to as agent vertices. V2 = {j0,1 . . . j0,d0 , j1,1 . . . j1,d1 . . . jm,1 . . . jm,dm }, where ∀jk,i ∈ V2 represents the i-th job in bundle Xt-1 k of agent ak (job indices in Xt-1 k are arbitrary). Specifically, j0,i represents the i-th job in charity bundle Xt-1 0 . Vertices in V2 are referred to as job vertices.

• A directed edge (jk,i, ad), where d ̸= 0, k ̸= d exists if and only if ud(jk,i) = 1 and Xt-1 d ∪ {jk,i} is feasible.
• A directed edge (jk,i, a0) exists if and only if jk,i /∈ Xt-1 0 , i.e. k ̸= 0.
• A directed edge (ad, jk,i) exists if and only if jk,i ∈ Xt-1 d , i.e. k = d.
• A directed edge (jk,i, jk′ ,i′), where k′ ̸= 0 exists if and only if uk′(jk,i) = 1 and Xt-1 k′ ∪ {jk,i} is not feasible and Xt-1 k′ \{jk′ ,i′} ∪ {jk,i} is feasible.

Remark 2. Note that in determining the feasibility of a job set, we utilize the definition of the condensed instance [Li et al., 2021] to improve the running time.

Lemma 3. For any iteration 1 ≤ t ≤ (2m-1)·n· ln 4n2 m , the directed graph G′ (Xt-1 ) can be constructed in polynomial time.

Below, we define a feasible schedule update method for each type of directed edge:

• A directed edge (jk,i, ad) represents moving job jk,i from bundle Xt-1 k to bundle Xt-1 d . i.e., Xt-1 k = Xt-1 k \{jk,i} and Xt-1 d =Xt-1 d ∪ {jk,i}.
• A directed edge (ad, jk,i) represents no change in scheduling. i.e., Xt-1 k =Xt-1 k and Xt-1 d =Xt-1 d .
• A directed edge (jk,i, jk′ ,i′) represents moving job jk,i from bundle Xt-1 k to bundle Xt-1 k′ . i.e., Xt-1 k = Xt-1 k \{jk,i} and Xt-1 k′ =Xt-1 k′ \{jk′ ,i′} ∪ {jk,i}.

For the directed graph G′ (Xt-1 ), we can find all feasible pairs (Definition 8) in polynomial time, and denote the set of these pairs as S. For any feasible pair (ak, ad) ∈ S, it is not difficult to compute the Nash social welfare after updating the schedule according to the paths between them (Observation 1). Therefore, the algorithm greedily find the feasible pair (ak∗, ad∗) that maximizes the Nash social welfare after updating the schedule. If the Nash social welfare does not increase after the update, we determine that the current schedule is a MaxNSW schedule, and output the schedule Xt-1 . Otherwise, we update the schedule along any directed path from ak∗ to ad∗, obtaining a new schedule Xt , and continue the iteration. It turns out that the algorithm terminates after running at most (2m- 1) · n · ln 4n2 m iterations.

Definition 8. A pair of agent vertices (ak, ad) is called a feasible pair if it is reachable from ak to ad, that is, there exists at least one directed path from ak to ad.

Observation 1. For directed graph G′ (Xt-1 ), we have the following results:

Algorithm 1 Greedy Algorithm

Input: An arbitrary instance I = (J,A, uA) of FISP with <Binary, Unit>.

Output: A non-wasteful MaxNSW schedule X = (X1, . . . ,Xm) that is both EFX and PO.

• 1: Initialize X1 = . . . =Xm = ∅, X0 = J.
• 2: Constructing the bipartite graph G(A ∪ J,E) and compute a maximum (weighted) matching M = AM ∪ JM .
• 3: for each (ai, jk) ∈M do
• 4: Xi =Xi ∪ {jk}
• 5: end for
• 6: Let Xc = (Xi)ai∈A\AM , X0 = (Xi)ai∈AM .
• 7: for t = 1 to (2m-1) · n · ln 4n2 m do
• 8: Constructing the directed graph G′ (Xt-1 ) corresponding to the current schedule Xt-1 .
• 9: Let S = {(ak, ad) ∈ AM ∪ {a0}×AM ∪ {a0} : (ak, ad) is a feasible pair}.
• 10: for each (ak, ad) ∈ S do
• 11: NSW(Xt-1 ((ak, ad))) ← Calculate the updated NSW according to (ak, ad).
• 12: end for
• 13: if max(ak,ad)∈S NSW(Xt-1 (ak, ad)) > NSW(Xt-1 ) then
• 14: Let (ak∗, ad∗) ∈ argmax (ak,ad)∈S NSW(Xt-1 (ak, ad))
• 15: Find a path P = {ak∗ , . . . ad∗}.
• 16: Update Xt = Xt-1 (P), where Xt-1 (P) is the schedule update according to path P .
• 17: else
• 18: return X = (Xc , Xt-1 )
• 19: end if
• 20: end for
• If a directed path P ends at some agent vertex, then the schedule after updating along P is feasible.
• If (ak, ad) is a feasible pair and there exist multiple paths from ak to ad, updating the schedule along different paths results in different schedules with the same Nash social welfare.
• If C is a directed cycle, the NSW of the schedule remains unchanged after updating along it.

We prove below that in each iteration before reaching MaxNSW, there must exist a feasible pair such that updating along any path between them guarantees a lower bound on the increase of NSW.

Lemma 4. For any iteration 1 ≤ t ≤ (2m-1) · n · ln 4n2 m , if NSW(Xt-1 ) < MaxNSW(I ′ ), then there must exist a feasible pair (ak, ad) in the directed graph G′ (Xt-1 ), and adjusting along any directed path P from ak to ad results in a schedule Xt-1 (P) that satisfies

Theorem 5. Given an arbitrary instance I of FISP with <Binary, Unit>, a non-wasteful MaxNSW schedule which is both EFX and PO can be found in polynomial time.

3.3 General Valuation

We consider the general instances of FISP and find that the EFX approximation guarantee achieved by the non-wasteful MaxNSW schedules is related to the non-zero range parameter γ.

Theorem 6. Given an arbitrary instance I of FISP, when γ ≥ √6, if MaxNSW(I) > 0, then any non-wasteful MaxNSW schedule is 1 γ 2 -EFX and PO; if MaxNSW(I) = 0, then there exists a non-wasteful MaxNSW schedule that is 1 γ 2 -EFX and PO.

The results show that the EFX approximation guarantee achievable by the non-wasteful MaxNSW schedules is inversely related to the non-zero range parameter γ. This implies that the larger the disparity in agents' valuations of items, the worse the fairness guarantee provided by the MaxNSW schedules.

Theorem 7. Given an arbitrary instance I of FISP, when γ < √6, if MaxNSW(I) > 0, then any non-wasteful MaxNSW schedule is 16 -EFX and PO; if MaxNSW(I) = 0, then there exists a non-wasteful MaxNSW schedule that is a 16 -EFX and PO.

Theorem 8. There exists an instance I of FISP with <Identical, Unit> such that no MaxNSW schedule of I is ( 1 γ + ε)-EFX, where ε > 0.

If we restrict the job types to unit jobs, we can obtain a nearly tight EFX approximation guarantee.

Theorem 9. Given an arbitrary instance I of FISP with <General, Unit>, if MaxNSW(I) > 0, then any non-wasteful MaxNSW schedule is 1 γ+1 -EFX and PO; if MaxNSW(I) = 0, then there exists a non-wasteful MaxNSW schedule that is 1 γ+1 -EFX and PO.

4 Approximately EFX andWIO Scheduling

[Li et al., 2021] proved the incompatibility between IO and EF1 even for FISP with <Identical, Rigid>. This implies that the stronger fairness concept EFX is also incompatible with IO. Therefore, we consider a relaxed concept WIO. [Barman et al., 2023] proved the existence of EFX with bounded charity under generalized assignment constraints. Utilizing their idea framework, we first provide an algorithm demonstrating compatibility between WIO and EFX for all instances of FISP. The high-level idea of the algorithm is as follows: if there exist agents who envy the charity, we identify "the most envious" agent among them and find a bundle in the charity that this agent envies but no other agent EFX envies. Then "the most envious" agent selects the most valuable feasible subset from this bundle, and the remaining jobs, along with the bundle previously owned by the agent, are returned to the charity. This process is repeated until no agent envies the charity.

Algorithm 2 Envy-Bundle Elimination

Input: An arbitrary FISP instance I = (J, A, uA). Output: An EFX andWIO schedule.

• 1: Initialize: Schedule X = (X1, · · · ,Xm) = (∅, · · · , ∅) and charity X0 = J.
• 2: while there is an agent ai ∈ A with ui(Xi) < ui(X0) do
• 3: Set B =X0 and s = i.
• 4: while there exists an agent ak ∈ A and a job jt ∈ B such that uk(Xk) < uk(B\{jt}) do
• 5: Set B = B\{jt} and s = k.
• 6: end while
• 7: Let C ⊆ B be a feasible subset such that ∑jl∈C us(jl) = us(B).
• 8: Set Xs = C and X0 = J\ ∪i∈[m] Xi.
• 9: end while
• 10: return X= (X1, · · · ,Xm) and X0 = J\ ∪i∈[m] Xi

Then, we show that computing a WIO schedule is NP-hard. Finally, we present a polynomial-time algorithm that approximates both EFX and WIO.

4.1 Compatibility of EFX andWIO

In the following, we present the specific algorithm: the initialization of the algorithm begins by assigning an empty bundle X = (∅, · · · , ∅) to each agent, while the charity holds all the jobs, i.e., X0 = J. Whenever there exists an agent who envies the charity, we perform the following operations on the charity's bundle X0: continuously remove jobs jt from X0 that still leave some agent envious after their removal, until we find a bundle B such that only one agent as envies B, and no other agents EFX envies B. Then as gets a feasible subset C ⊆ B with ∑jl∈C us(jl) = us(B), and the bundle previously owned by as, and the jobs removed from the charity and B\C are returned to the charity. The algorithm continues until no agents envy the charity, as illustrated by Algorithm 2.

Note that we update the schedule only after each iteration of the outer while loop. We denote by Xl = (Xl1 , . . . ,X lm) and Xl0 the schedule and charity updated after the l-th iteration of the outer while loop in Algorithm 2, respectively. Let X0 = {∅, . . . , ∅} and X0 0 = J.

Lemma 5. After any l-th (l ≥ 0) iteration of the outer while loop in Algorithm 2, Xl = (Xl1 , . . . ,X lm) is feasible and EFX.

Theorem10. EFX+WIOare compatible for FISP, i.e., there exists an algorithm that can return a feasible schedule that is simultaneously EFX and WIO for all FISP instances.

4.2 Computational Hardness of the Problem

We now provide a proof showing that computing WIO schedule alone is NP-hard.

Theorem 11. Given an arbitrary instance I of FISP, computing a WIO schedule is NP-hard.

Algorithm 3 Efficient Implementation

Input: An arbitrary FISP instance I = (J,A, uA); βapproximation polynomial-time algorithm for IS functions, a parameter ε ∈ (0, 1).

Output: An β(1- ε)-EFX and β-WIO schedule.

• 1: Initialize: Schedule X = (X1, · · · ,Xm) = (∅, · · · , ∅) and charity X0 = J.
• 2: while there is an agent ai ∈ A with ui(Xi) < u′i (X0) do
• 3: Set B =X0 and s = i.
• 4: while there exists an agent ak ∈ A and a job jt ∈ B such that uk(Xk) < (1 - ε)u′k (B\{jt}) do
• 5: Set B = B\{jt} and s = k.
• 6: end while
• 7: Let C ⊆ B be a feasible subset such that ∑jl∈C us(jl) = u′s (B).
• 8: Set Xs = C and X0 = J\ ∪i∈[m] Xi.
• 9: end while
• 10: return X= (X1, · · · ,Xm) and X0 = J\ ∪i∈[m] Xi

4.3 Polynomial-time Implementation

Note that Algorithm 2 is inefficient, because if P ̸= NP, the exact value of the IS function cannot be computed in polynomial time. For special case of rigid or unit jobs, the IS function can be computed in polynomial time. Therefore, in this subsection, we present a polynomial-time algorithm for computing approximate EFX and WIO schedule. For the IS function, we can directly use a β-approximation algorithm, with the most well-known approximation ratio being 0.644 [Im et al., 2020]. For each ai ∈ A, we use u′i : 2J → R+ to denote the approximate valuation, and thus u′i (S) ≥ β ·ui(S) for any S ⊆ J. Thus, we directly obtain Algorithm 3 and the following theorem.

Theorem 12. For any 0 < ε < 1, Algorithm 3 returns a β(1 - ε)-EFX and β-WIO schedule for arbitrary FISP instance with a β-approximation algorithm for IS functions. The running time is polynomial with |J|, |A| and 1ε .

Corollary 1. For any 0 < ε < 1, given a instance I of FISP, an 0.644(1 - ε)-EFX and 0.644-WIO schedule can be found in polynomial time; when jobs are either rigid or unit, an (1 - ε)-EFX and WIO schedule can be found in polynomial time.

5 Conclusion and FutureWork

This paper studied the fair scheduling problem with timedependent resources, considering the compatibility between the concepts of fairness, mainly EFX, and efficiency, mainly MaxNSW, WIO and PO. Moreover, we designed polynomialtime algorithms that satisfy various fairness and efficiency concepts. Despite some progress, several important issues remain unresolved. A direct question is whether the relationship between MaxNSW and approximate EFX can be made tight. An interesting direction is to consider the relationship between approximate MaxNSW and approximate EFX. Can we design polynomial-time algorithms that provide strong approximation guarantees for both EF and MaxNSW?

Ethical Statement

There are no ethical issues.

Acknowledgments

This research was supported in part by the National Natural Science Foundation of China (12201590, 12171444) and Natural Science Foundation of Shandong Province (ZR2024MA031).