# efx_feasible_scheduling_for_timedependent_resources__bbee6756.pdf EFX Feasible Scheduling for Time-dependent Resources Jiazhu Fang1 , Qizhi Fang1,2 , Minming Li3 and Wenjing Liu1,2 1 School of Mathematical Sciences, Ocean University of China, Qingdao, Shandong, China. 2 Laboratory of Marine Mathematics, Ocean University of China, Qingdao, Shandong, China. 3 Department of Computer Science, City University of Hong Kong, Kowloon Tong, Hong Kong, China. fjz@stu.ouc.edu.cn, qfang@ouc.edu.cn, minming.li@cityu.edu.hk, liuwj@ouc.edu.cn In this paper, we study a fair resource scheduling problem involving the assignment of a set of interval jobs among a group of heterogeneous machines. Each job is associated with a release time, a deadline, and a processing time. A machine can process a job if the entire processing period falls within the release time and deadline of the job. Each machine can process at most one job at any given time, and different jobs yield different utilities for the machine. The goal is to find a fair and efficient schedule of the jobs. We discuss the compatibility between envy-freeness up to any item (EFX) and various efficiency concepts. Additionally, we present polynomial-time algorithms for various settings. 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 Corresponding Authors. 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. 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 (Max NSW) and demonstrated that for additive valuation functions, there exist Max NSW 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 Max NSW 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. Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-25) 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: Max NSW, PO, and Weakly Individual Optimal (WIO). Our main contributions are summarized as follows. EFX + Max NSW + PO. We first consider binary valuation functions, where agents valuations for jobs are restricted to 1 or 0. We explore the characteristics of Max NSW 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 Max NSW schedule that is 1 2-EFX and PO. Additionally, there exist instances where no Max NSW schedule can guarantee ( 1 2 + ε)-EFX for any ε > 0. Main Result 2: For any instance of FISP with binary valuations and jobs with unit processing times, there exists a Max NSW 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 Max NSW schedule that is 1 γ2 -EFX and PO. When all jobs have unit processing times, there exists a Max NSW schedule that is 1 γ+1-EFX and PO. Additionally, in both settings, there exist instances where no Max NSW 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 Related Work 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 Das Gupta, 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 + Max NSW/PO. We primarily review the literature on the compatibility of EFX with various efficiency concepts. For binary additive valuations, any Max NSW 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 Max NSW allocation is EFX. [Caragiannis et al., 2019a] proved that under additive valuation functions, there exist partial allocations that are EFX and 1 2-Max NSW (where some items may remain unallocated). [Garg et al., 2023] showed that even under subadditive valuation functions, there exist complete allocations that are 1 2-EFX and 1 2-Max NSW. [Feldman et al., 2024] provided optimal trade-offs between EFX and Max NSW for additive and subadditive valuation functions. [Dai et al., 2024] investigated the relationship between EFX and Max NSW under budget constraints, proving that for binary valuation functions, Max NSW can guarantee 1 4-EFX and PO. However, even under unconstrained additive valuations, computing a Max NSW allocation is NP-hard [Ramezani and Endriss, 2010]. [Barman et al., 2018b] showed that for binary additive valuations, a Max NSW allocation that is both EFX and PO can be found in polynomial time. [Benabbou et al., 2021] proved that for matroid rank functions, Max NSW 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 Max NSW schedule is 1 4-EF1 and PO, and for jobs with unit processing times, it is 1 2-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 Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-25) 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, u A), 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 u A = {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) = P 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., ui(S) = max S S:S is feasible jk S ui(jk). 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, u A), the non-zero range parameter is defined as γ := maxai A,jk J ui(jk) minjk J,ai:ui(jk)>0 ui(jk). 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\ S 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 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 ui(Xi) α ui(Xk\{j}) for some j Xk. 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 ui(Xi) α ui(Xk\{j}) for any j Xk. 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 ui(Xi) < α ui(Xk\{j}) for some j Xk. Efficiency Concepts Definition 4 (Max NSW Schedule). A feasible schedule X = (X1, , Xm) is called Max NSW schedule if and only if X arg max X F ( i=1 ui(X i)) 1 m 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\ S 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 . 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\ S 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. Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-25) 3 Approximately EFX and Max NSW Scheduling In this section, we establish interesting connections between EFX and Max NSW schedules by analyzing the performance of the non-wasteful Max NSW 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 Max NSW 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 Max NSW schedules must exist. 3.1 We first consider the relationship between EFX and the nonwasteful Max NSW schedules in binary valuation instances. Our main result shows that for any binary valuation instance I, there exists a Max NSW schedule that is both 1 2-EFX and PO. Moreover, the 1 2-approximation is the best EFX guarantee achievable among all Max NSW schedules. The following results provide the worst-case EFX approximation guaranteed by the non-wasteful Max NSW schedules on any instance I with Max NSW(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 , if Max NSW(I) > 0, then any nonwasteful Max NSW schedule is 1 4-EFX and PO. However, for an instance I with Max NSW(I) = 0, it is possible for a non-wasteful Max NSW schedule to have an unbounded EFX approximation. We now consider the best possible EFX approximation guarantee achievable by the nonwasteful Max NSW 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 Max NSW(I) > 0 when analyzing the relationship between EFX and Max NSW schedules. Lemma 1. For any FISP with , if for all instances I with Max NSW(I) > 0, there exists a non-wasteful Max NSW schedule that is α-EFX and PO, then for any instance I with Max NSW(I ) = 0, there must exist a non-wasteful Max NSW 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 1 2EFX envy between agents for any binary valuation instance. Lemma 2. For an arbitrary instance I with Max NSW(I) > 0 of FISP with and any non-wasteful Max NSW schedule X = (X1, . . . , Xm), if there exist i, k [m] such that ai 1 2-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 , there exists a non-wasteful Max NSW 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 Max NSW(I) > 0. Theorem 1 has already proven that any non-wasteful Max NSW schedule is PO. Below, we present the procedure to find a non-wasteful Max NSW schedule that satisfies 1 2-EFX. For any non-wasteful Max NSW schedule X = (X1, . . . , Xm) with X0 = J\ i [m] Xi, if X is 1 2EFX, then the proof is complete. Otherwise, there must exist i, k [m] such that ai 1 2-EFX envies ak, i.e., 2 ui(Xk \ {jp}), jp Xk. (1) 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 \ S 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, since uk(Xk) = uk(Xk \ {jp}) + 1 ui(Xk \ {jp}) + 1 2 ui(Xi) + 2, 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 ui(X i) uk(X k) = (ui(Xi) + 1) (uk(Xk) 2) = ui(Xi) uk(Xk) + uk(Xk) (2 ui(Xi) + 2) ui(Xi) uk(Xk). Thus, by iterating this process, we can eliminate the 1 2EFX 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 Max NSW schedule that satisfies 1 Remark 1. In fact, Theorem 2 provides a conversion procedure from any Max NSW schedule to a 1 2-EFX Max NSW schedule. Each step that eliminates 1 2-EFX envy results in an increase in the number of jobs allocated to charity, implying that a non-wasteful Max NSW with the maximum number of charity jobs must be 1 2-EFX. However, finding a Max NSW schedule is NP-hard, and thus, we cannot implement this procedure efficiently. We now provide an example to show that the 1 2approximation of EFX is optimal. Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-25) Theorem 3. There exists an instance I of FISP with such that no Max NSW schedule of I is ( 1 2 + ε)-EFX, where ε > 0. 3.2 [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 . Fortunately, we find that for any instance of FISP with , there exists a non-wasteful Max NSW 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 , if Max NSW(I) > 0, then any non-wasteful Max NSW schedule is EFX and PO; if Max NSW(I) = 0, then there exists a non-wasteful Max NSW schedule that is EFX and PO. For any instance I of FISP with , we present below a polynomial-time algorithm to find a Max NSW 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 Max NSW(I ) > 0. According to the proof of Lemma 1 and Theorem 4, it suffices to find a nonwasteful Max NSW 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 Max NSW 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, u AM ) with Max NSW(I ) > 0. Finally, find a non-wasteful Max NSW 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 Max NSW 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: Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-25) Algorithm 1 Greedy Algorithm Input: An arbitrary instance I = (J, A, u A) of FISP with . Output: A non-wasteful Max NSW 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 ) arg max (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 (1) If a directed path P ends at some agent vertex, then the schedule after updating along P is feasible. (2) 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. (3) 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 Max NSW, 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) < Max NSW(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 ln(Max NSW(I )) ln(NSW(Xt 1(P))) n)(ln(Max NSW(I )) ln(NSW(Xt 1))). Theorem 5. Given an arbitrary instance I of FISP with , a non-wasteful Max NSW 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 Max NSW schedules is related to the non-zero range parameter γ. Theorem 6. Given an arbitrary instance I of FISP, when γ 6, if Max NSW(I) > 0, then any non-wasteful Max NSW schedule is 1 γ2 -EFX and PO; if Max NSW(I) = 0, then there exists a non-wasteful Max NSW schedule that is 1 γ2 -EFX and PO. The results show that the EFX approximation guarantee achievable by the non-wasteful Max NSW 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 Max NSW schedules. Theorem 7. Given an arbitrary instance I of FISP, when γ < 6, if Max NSW(I) > 0, then any non-wasteful Max NSW schedule is 1 6-EFX and PO; if Max NSW(I) = 0, then there exists a non-wasteful Max NSW schedule that is a 1 6-EFX and PO. Theorem 8. There exists an instance I of FISP with such that no Max NSW 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 , if Max NSW(I) > 0, then any non-wasteful Max NSW schedule is 1 γ+1-EFX and PO; if Max NSW(I) = 0, then there exists a non-wasteful Max NSW schedule that is 1 γ+1-EFX and PO. 4 Approximately EFX and WIO Scheduling [Li et al., 2021] proved the incompatibility between IO and EF1 even for FISP with . 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. Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-25) Algorithm 2 Envy-Bundle Elimination Input: An arbitrary FISP instance I = (J, A, u A). Output: An 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) < 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 P 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 and WIO 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 P 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 = (Xl 1, . . . , Xl m) and Xl 0 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 = (Xl 1, . . . , Xl m) is feasible and EFX. Theorem 10. EFX + WIO are 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, u A); β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 P 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 Future Work This paper studied the fair scheduling problem with timedependent resources, considering the compatibility between the concepts of fairness, mainly EFX, and efficiency, mainly Max NSW, 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 Max NSW and approximate EFX can be made tight. An interesting direction is to consider the relationship between approximate Max NSW and approximate EFX. Can we design polynomial-time algorithms that provide strong approximation guarantees for both EF and Max NSW? Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-25) 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). [Ajtai et al., 1998] Miklos Ajtai, James Aspnes, Moni Naor, Yuval Rabani, Leonard J Schulman, and Orli Waarts. Fairness in scheduling. Journal of Algorithms, 29(2):306 357, 1998. [Aleksandrov et al., 2015] Martin Aleksandrov, Haris Aziz, Serge Gaspers, and Toby Walsh. Online fair division: analysing a food bank problem. In Proceedings of the 24th International Conference on Artificial Intelligence, IJCAI 15, page 2540 2546, Buenos Aires, Argentina, 2015. AAAI Press. [Amanatidis et al., 2021] Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas, Alexandros Hollender, and Alexandros A Voudouris. Maximum nash welfare and other stories about efx. Theoretical Computer Science, 863:69 85, 2021. [Aziz and Mackenzie, 2016] Haris Aziz and Simon Mackenzie. A discrete and bounded envy-free cake cutting protocol for any number of agents. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 416 427, Los Alamitos, CA, USA, 2016. IEEE Computer Society. [Babaioff et al., 2021] Moshe Babaioff, Tomer Ezra, and Uriel Feige. Fair and truthful mechanisms for dichotomous valuations. Proceedings of the AAAI Conference on Artificial Intelligence, 35(6):5119 5126, 2021. [Barman and Krishnamurthy, 2019] Siddharth Barman and Sanath Kumar Krishnamurthy. On the proximity of markets with integral equilibria. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01):1748 1755, 2019. [Barman et al., 2018a] Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish. Finding fair and efficient allocations. In Proceedings of the 2018 ACM Conference on Economics and Computation, page 557 574, Ithaca, NY, USA, 2018. Association for Computing Machinery. [Barman et al., 2018b] Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish. Greedy algorithms for maximizing nash social welfare. In Proceedings of the 17th International Conference on Autonomous Agents and Multi Agent Systems, page 7 13, Stockholm, Sweden, 2018. International Foundation for Autonomous Agents and Multiagent Systems. [Barman et al., 2023] Siddharth Barman, Arindam Khan, Sudarshan Shyam, and K. V. N. Sreenivas. Guaranteeing envy-freeness under generalized assignment constraints. In Proceedings of the 24th ACM Conference on Economics and Computation, page 242 269, , London, United Kingdom,, 2023. Association for Computing Machinery. [Benabbou et al., 2020] Nawal Benabbou, Mithun Chakraborty, Xuan-Vinh Ho, Jakub Sliwinski, and Yair Zick. The price of quota-based diversity in assignment problems. ACM Trans. Econ. Comput., 8(3), 2020. [Benabbou et al., 2021] Nawal Benabbou, Mithun Chakraborty, Ayumi Igarashi, and Yair Zick. Finding fair and efficient allocations for matroid rank valuations. ACM Trans. Econ. Comput., 9(4), 2021. [Berman and Das Gupta, 2000] Piotr Berman and Bhaskar Das Gupta. Multi-phase algorithms for throughput maximization for real-time scheduling. Journal of Combinatorial Optimization, 4:307 323, 2000. [Bil o et al., 2016] Vittorio Bil o, Angelo Fanelli, Michele Flammini, Gianpiero Monaco, and Luca Moscardelli. The price of envy-freeness in machine scheduling. Theoretical Computer Science, 613:65 78, 2016. [Brams and Taylor, 1996] Steven J Brams and Alan D Taylor. Fair Division: From cake-cutting to dispute resolution. Cambridge University Press, Cambridge, UK, 1996. [Brandt et al., 2016] Felix Brandt, Vincent Conitzer, Ulle Endriss, J erˆome Lang, and Ariel D Procaccia. Handbook of computational social choice. Cambridge University Press, Cambridge, UK, 2016. [Budish et al., 2017] Eric Budish, G erard P Cachon, Judd B Kessler, and Abraham Othman. Course match: A largescale implementation of approximate competitive equilibrium from equal incomes for combinatorial allocation. Operations Research, 65(2):314 336, 2017. [Caragiannis et al., 2019a] Ioannis Caragiannis, Nick Gravin, and Xin Huang. Envy-freeness up to any item with high nash welfare: The virtue of donating items. In Proceedings of the 2019 ACM Conference on Economics and Computation, page 527 545, Phoenix, AZ, USA, 2019. Association for Computing Machinery. [Caragiannis et al., 2019b] Ioannis Caragiannis, David Kurokawa, Herv e Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang. The unreasonable fairness of maximum nash welfare. ACM Trans. Econ. Comput., 7(3), 2019. [Chuzhoy et al., 2006] Julia Chuzhoy, Rafail Ostrovsky, and Yuval Rabani. Approximation algorithms for the job interval selection problem and related scheduling problems. Mathematics of Operations Research, 31(4):730 738, 2006. [Dai et al., 2024] Sijia Dai, Guichen Gao, Shengxin Liu, Boon Han Lim, Li Ning, Yicheng Xu, and Yong Zhang. Maximum nash social welfare under budget-feasible efx. IEEE Transactions on Network Science and Engineering, 11(2):1810 1820, 2024. Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-25) [Deng et al., 2012] Xiaotie Deng, Qi Qi, and Amin Saberi. Algorithmic solutions for envy-free cake cutting. Operations Research, 60(6):1461 1476, 2012. [Feldman et al., 2024] Michal Feldman, Simon Mauras, and Tomasz Ponitka. On optimal tradeoffs between efx and nash welfare. Proceedings of the AAAI Conference on Artificial Intelligence, 38(9):9688 9695, 2024. [Garg and Murhekar, 2023] Jugal Garg and Aniket Murhekar. Computing fair and efficient allocations with few utility values. Theoretical Computer Science, 962:113932, 2023. [Garg et al., 2023] Jugal Garg, Edin Husi c, Wenzheng Li, L aszl o A. V egh, and Jan Vondr ak. Approximating nash social welfare by matching and local search. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, page 1298 1310, Orlando, FL, USA, 2023. Association for Computing Machinery. [Goldman and Procaccia, 2015] Jonathan Goldman and Ariel D. Procaccia. Spliddit: unleashing fair division algorithms. SIGecom Exch., 13(2):41 46, 2015. [Im et al., 2020] Sungjin Im, Shi Li, and Benjamin Moseley. Breaking 1 - 1/e barrier for nonpreemptive throughput maximization. SIAM Journal on Discrete Mathematics, 34(3):1649 1669, 2020. [Johnson and Garey, 1979] David S Johnson and Michael R Garey. Computers and intractability: A guide to the theory of NP-completeness. WH Freeman, New York, NY, USA, 1979. [Kaneko and Nakamura, 1979] Mamoru Kaneko and Kenjiro Nakamura. The nash social welfare function. Econometrica, 47(2):423 435, 1979. [Kumar et al., 2024] Yatharth Kumar, Sarfaraz Equbal, Rohit Gurjar, Swaprava Nath, and Rohit Vaish. Fair scheduling of indivisible chores. In Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems, page 2345 2347, , Auckland, New Zealand, 2024. International Foundation for Autonomous Agents and Multiagent Systems. [Li et al., 2021] Bo Li, Minming Li, and Ruilong Zhang. Fair scheduling for time-dependent resources. In Advances in Neural Information Processing Systems, volume 34, pages 21744 21756, , NY, USA, 2021. Curran Associates, Inc. [Moulin, 2019] Herv e Moulin. Fair division in the internet age. Annual Review of Economics, 11:407 441, 2019. [Ramezani and Endriss, 2010] Sara Ramezani and Ulle Endriss. Nash social welfare in multiagent resource allocation. In Agent-Mediated Electronic Commerce. Designing Trading Strategies and Mechanisms for Electronic Markets, pages 117 131, Berlin, Heidelberg, Germany, 2010. Springer Berlin Heidelberg. [Richard et al., 2004] Lipton Richard, Markakis Evangelos, Mossel Elchanan, and Saberi Amin. On approximately fair allocations of indivisible goods. In Proceedings of the 5th ACM Conference on Electronic Commerce, page 125 131, New York, NY, USA, 2004. Association for Computing Machinery. [Schrijver, 1998] Alexander Schrijver. Theory of linear and integer programming. John Wiley & Sons, Hoboken, NJ, USA, 1998. [Varian, 1974] Hal R. Varian. Equity, envy, and efficiency. Journal of Economic Theory, 9(1):63 91, 1974. Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-25)