Paper deep dive
Minimizing Cumulative Envy in Allocating a Sequence of Items
Paul W. Goldberg, Isaac Robinson, Nicholas Teh
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 92%
Last extracted: 10/8/2026, 6:03:05 AM
Summary
This paper investigates temporal fair division with indivisible goods arriving sequentially, assuming full knowledge of valuations and future arrivals. It introduces 'cumulative maximum envy' as an objective function, defined as the sum of maximum pairwise envy over all rounds. The study proves that minimizing this objective is strongly NP-complete with no constant-factor approximation unless P=NP, even under identical or binary valuations. However, it provides pseudopolynomial-time dynamic programming solutions for constant agents, polynomial-time algorithms for specific restricted settings, and an FPTAS for fixed n with identical integer valuations. Additionally, it analyzes a sequencing variant where the arrival order is chosen by the algorithm, offering approximation guarantees via greedy algorithms.
Entities (9)
Relation Signals (8)
Minimizing Cumulative Maximum Envy → hascomplexity → NP-complete
confidence 98% · For a fixed arrival order, we show that the corresponding decision problem is strongly NP-complete
Minimizing Cumulative Maximum Envy → hasapproximationlimit → no constant-factor approximation unless P=NP
confidence 95% · minimizing this objective admits no constant-factor approximation unless P = NP
Cumulative Maximum Envy → isdefinedas → sum of maximum pairwise envy over all rounds
confidence 95% · We introduce \emph{cumulative maximum envy}: the sum, over all rounds, of the maximum pairwise envy at that round.
Greedy Algorithm → achievesapproximation → 3/2-approximation
confidence 90% · a simple greedy algorithm achieves a 3/2-approximation for n=2 agents
Greedy Algorithm → achievesapproximation → n/(n-1)-approximation
confidence 90% · an n/(n-1)-approximation for any number of agents
EFX → isrelaxationof → Envy-freeness
confidence 90% · and envy-freeness up to any good (EFX)
EF1 → isrelaxationof → Envy-freeness
confidence 90% · the two most prominent relaxations are envy-freeness up to one good (EF1)
Dynamic Programming → solves → Minimizing Cumulative Maximum Envy
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We study temporal fair division with indivisible goods that arrive sequentially and must be allocated irrevocably. In contrast to the usual online model, we assume that valuations and future arrivals are known in advance, and ask how unfairness evolves during the process. We introduce \emph{cumulative maximum envy}: the sum, over all rounds, of the maximum pairwise envy at that round. Equivalently, this is the area under the worst-envy curve, and it captures both the magnitude and the duration of envy. For a fixed arrival order, we show that the corresponding decision problem is strongly NP-complete and that minimizing this objective admits no constant-factor approximation unless P = NP, even under identical valuations and even under binary valuations. We complement these hardness results with a dynamic program that gives pseudopolynomial-time solvability for a constant number of agents, polynomial-time algorithms in further restricted settings, and an FPTAS for fixed $n$ under identical integer valuations. We then study a sequencing variant where the algorithm may choose the arrival order. This variant remains NP-complete even for two agents with identical valuations; however, a simple greedy algorithm achieves a $3/2$-approximation for $n=2$ agents, an $n/(n-1)$-approximation for any number of agents, and an additive guarantee depending on the maximum value of any good.
Tags
Links
- Source: https://arxiv.org/abs/2610.09843v1
- Canonical: https://arxiv.org/abs/2610.09843v1
Trouble viewing inline? Open PDF directly →
Full Text
116,283 characters extracted from source content.
Expand or collapse full text
Minimizing Cumulative Envy in Allocating a Sequence of ItemsThanks: A preliminary version of this paper was presented at the 19th International Symposium on Algorithmic Game Theory (SAGT), 2026. Paul W. Goldberg Isaac Robinson Nicholas Teh Affiliation: University of Oxford, UK E-mail paul.goldberg,isaac.robinson,nicholas.teh@cs.ox.ac.uk Abstract We study temporal fair division with indivisible goods that arrive sequentially and must be allocated irrevocably. In contrast to the usual online model, we assume that valuations and future arrivals are known in advance, and ask how unfairness evolves during the process. We introduce cumulative maximum envy: the sum, over all rounds, of the maximum pairwise envy at that round. Equivalently, this is the area under the worst-envy curve, and it captures both the magnitude and the duration of envy. For a fixed arrival order, we show that the corresponding decision problem is strongly NP-complete and that minimizing this objective admits no constant-factor approximation unless P = NP, even under identical valuations and even under binary valuations. We complement these hardness results with a dynamic program that gives pseudopolynomial-time solvability for a constant number of agents, polynomial-time algorithms in further restricted settings, and an FPTAS for fixed n under identical integer valuations. We then study a sequencing variant where the algorithm may choose the arrival order. This variant remains NP-complete even for two agents with identical valuations; however, a simple greedy algorithm achieves a 3/23/2-approximation for n=2n=2 agents, an n/(n−1)n/(n-1)-approximation for any number of agents, and an additive guarantee depending on the maximum value of any good. 1 Introduction Fair division of indivisible goods is a fundamental, well-studied problem at the intersection of computer science and economics [12, 54], with applications ranging from divorce settlements to distributed load balancing. A central fairness notion in this context is envy-freeness, which requires that every agent values their allocated bundle at least as much as any other agent’s bundle. However, this strong requirement is not always achievable; consider, for example, the case of two agents and a single good that both value positively, which must be allocated to one of them. As a result, recent years have seen considerable interest in relaxations of envy-freeness. Arguably, the two most prominent relaxations are envy-freeness up to one good (EF1) [14, 52] and envy-freeness up to any good (EFX) [15, 37]. An allocation is EF1 if, for any pair of agents, any envy can be eliminated by removing one good from the envied agent’s bundle, where goods are compared using the envious agent’s valuation; in particular, removing a most-valued good is sufficient. It is EFX if the envy is eliminated even after removing a least-valued good. The concept of EF1 originates from the seminal work of Lipton et al. [52], which introduced the first algorithmic approach for computing approximately envy-free allocations of indivisible goods. Their envy-cycle elimination algorithm remains a foundational tool and has since been used as a building block in tackling some of the most challenging problems in fair division, including the recent breakthrough on the existence of EFX allocations for three agents [17]. Interestingly, EF1 emerged from an effort to bound envy: if each agent’s maximum envy can be bounded by the largest value of a single good, then a polynomial-time algorithm can achieve this relaxed form of envy-freeness. This same line of reasoning also motivates the optimization problem of minimizing envy, which was considered by Lipton et al. [52] (see also [59]). The optimization perspective has received comparatively less attention than discrete relaxations such as EF1 and EFX. While most prior works study the fair division problem in the offline setting (i.e., all goods are immediately available and are allocated to agents in a single-shot), many real-world systems do not allocate all resources at once. Instead, indivisible goods become available over time and must be assigned as they appear: affordable housing units are completed in phases, public extraction permits are issued across multiple periods, and platforms assign arriving tasks or opportunities to workers. In such settings, stakeholders care not only about the final allocation, but also about the trajectory: large early imbalances can create lasting disadvantages, distort downstream behavior, or erode trust. Several recent works have considered an online model where goods arrive one at a time, and must immediately and irrevocably be allocated to agents. This captures numerous application scenarios where goods need to be allocated in a sequential manner, such as assigning donations to food banks [1], allocating resources in cloud computing environments [9], or allocating impressions in recommendation systems [55]. In the standard online fair division model, it is usually assumed that each good’s valuation is not known until its arrival. Most work on online fair division evaluates fairness only at the end of the process, once all goods have arrived and been allocated. In practice, agents experience the allocation process as it unfolds, and limiting unfairness throughout the process can be important for maintaining balance, participation, and trust, especially in long-term allocation systems. This motivation is central to recently-studied temporal fair division model [25, 29], where the goal is to guarantee fairness not merely at the end, but at every prefix during the allocation process given information about future arrivals and valuations for each good-agent pair. This perspective provides a different lens on sequential fair division. In the standard and commonly-studied online model, agents have limited to no information about future arrivals, and fairness is evaluated only at the end (after all goods have arrived). In contrast to these standard online models with unknown future arrivals, the temporal fair division model assumes complete information about valuations and future arrivals while striving for typically stronger, cumulative fairness guarantees [25, 29].11 1 Note that without this “cumulative fairness” consideration, the problem reduces to the standard offline model. Consider the allocation of pre-built affordable housing units that become available over time: while the housing authority knows when each unit will be ready, ensuring equitable distribution throughout the multi-year process—not just at the end—is essential for maintaining public trust and preventing systematic disadvantage to any group. Similarly, when allocating extraction rights for public natural resources across multiple time periods to private companies, temporal fairness ensures that no firm gains disproportionate early advantages that could distort market competition. To quantify experienced unfairness over time, we take an optimization view rooted in classic envy minimization [52]. For an allocation process, let AitA_i^t denote agent i’s bundle after the first t goods, and define envyi,jt:=max0,vi(Ajt)−vi(Ait)envy_i,j^t:= \0,\,v_i(A_j^t)-v_i(A_i^t)\. Let ct:=maxi,j∈Nenvyi,jtc_t:= _i,j∈ Nenvy_i,j^t be the maximum envy after the first t goods have been allocated. The sequence (c1,…,cm)(c_1,…,c_m) is the worst-envy curve of the process. Our objective is ∑t=1mct _t=1^mc_t, the area under this curve.22 2 In online fair division, the term cumulative envy is sometimes used for the maximum envy after the first t goods have been allocated (see, e.g., [11]), which is ctc_t in our notation. Our objective instead adds up the maximum envy over all rounds. This objective is a simple, parameter-free baseline: it uses the standard maximum-envy measure at each round and aggregates it over time, so it penalizes both large envy and envy that persists for many rounds. We do not claim that this is the only meaningful temporal objective. Rather, it is a natural optimization counterpart to prefix-based temporal fairness notions, and it remains meaningful even when maintaining a strong fairness guarantee at every prefix is impossible. For each agent i, let eit:=maxj∈Nenvyi,jte_i^t:= _j∈ Nenvy_i,j^t and Ei:=∑t=1meitE_i:= _t=1^me_i^t. Since ct=maxi∈Neitc_t= _i∈ Ne_i^t, we have maxi∈NEi≤∑t=1mct≤∑i∈NEi≤nmaxi∈NEi _i∈ NE_i≤ _t=1^mc_t≤ _i∈ NE_i≤ n _i∈ NE_i. Thus, our objective upper-bounds the cumulative envy experienced by every agent and is within a factor n of the largest individual cumulative envy. In either of our two models, an optimal solution for our objective is therefore an n-approximation for directly minimizing maxi∈NEi _i∈ NE_i over the same feasible allocation processes. However, our objective need not distribute envy evenly across agents. Directly minimizing maxi∈NEi _i∈ NE_i, ∑i∈NEi _i∈ NE_i, or weighted versions of these quantities is a natural direction for future work. It would also be useful to study objectives that directly minimize the largest or total individual cumulative envy. We investigate cumulative maximum envy minimization in two related settings. First, we study the standard temporal model where the arrival order is fixed and may be adversarially chosen as part of the input. Second, we study a sequencing variant in which the algorithm may choose the order of the goods before allocating them. This models settings where all goods are known and can be held briefly before release; for example, a food bank may have several donated pallets in storage and choose which pallet to allocate next, or a public agency may choose the order in which approved permits are issued. 1.1 Our Contributions We begin in Section 3 by presenting several intractability results. We show that the fixed-order problem is NP-complete even under identical valuations and even under binary valuations. In both cases, we also prove that no constant-factor approximation is possible unless P=NP P= NP. Motivated by these hardness results, in Section 4 we give a dynamic programming algorithm that computes an optimal allocation sequence in time ((m+1)(Vmaxm2+1)(mVmax+1)n2⋅n3)O((m+1)(V_ m^2+1)(mV_ +1)^n^2· n^3), where n is the number of agents, m is the number of goods, and VmaxV_ is the maximum value of any good to any agent. This gives pseudopolynomial-time solvability when n is constant, and polynomial-time solvability under binary valuations for constant n. If the number of goods is constant, an optimal solution can also be found by direct enumeration. We further show that binary identical valuations admit a simple polynomial-time optimal algorithm, and that identical integer valuations admit an FPTAS for every fixed n. This contrasts with the offline setting, where the minimum maximum envy cannot be approximated within any factor unless P=NP P= NP, even for two agents with identical valuations [52]; the difference is that, under identical valuations, our objective is always at least a (1−1/n)(1-1/n) fraction of the total value of the goods. In Section 5, we explore a natural variant of the model in which the algorithm is allowed to choose the arrival order of goods (while an adversary pre-selects the agents’ valuations over the goods). We show that this variant remains NP-complete even for just two agents and identical valuations. On the positive side, when agents have identical valuations, we design a polynomial-time algorithm that achieves: (i) a 3/23/2-approximation for n=2n=2 agents, (i) a n/(n−1)n/(n-1)-approximation for general n, and (i) a n−1nVmax n-1n\,V_max-additive approximation to the optimal cost. 1.2 Related Work We highlight the works most relevant to our focus on envy minimization in the temporal setting. Offline Fair Division. In the offline fair division model, all goods are available simultaneously and allocated at once. Lipton et al. [52] investigate envy minimization in this setting, aiming to bound the maximum envy between any pair of agents. They introduce the well-known envy cycle elimination algorithm, which runs in polynomial time and guarantees an allocation where the maximum envy is at most the highest value of any good. This result also gives rise to the well-known EF1 concept. They also study the problem of computing an allocation with minimum maximum envy. Since deciding whether this minimum is zero is NP-hard even for two agents with identical valuations, no approximation within any factor is possible unless P=NP P= NP. They therefore also consider the envy-ratio; under identical valuations, they relate it to scheduling on identical machines and give a PTAS, as well as an FPTAS when the number of agents is constant. Nguyen and Rothe [59] show that minimizing the envy-ratio is APX-hard in general, and give an FPTAS for a constant number of agents with additive valuations. Online Fair Division. In the online fair division model, goods arrive sequentially in a fixed order, and the algorithm has no knowledge of future items. Due to this uncertainty, most works on this model focus on ensuring fairness guarantees at the final round, once all goods have arrived and been allocated. Several works look at minimizing the maximum envy in this setting. Benadè et al. [10] (see also [11]) study a fully adversarial setting in which item values are chosen adaptively: an adversary observes the algorithm and all decisions made thus far, and selects the value of each incoming good to maximize envy at the end. They prove that, even with just two agents, any online algorithm must incur a maximum envy of Ω(mr/2) (m^r/2) for every constant r<1r<1, where m is the number of goods, and that allocating each good to a uniformly random agent nearly matches this bound. Recognizing that adaptive adversaries may be unrealistically powerful, Halpern et al. [42] consider an oblivious adversary model, where item values are fixed in advance and chosen to be worst-case with respect to the algorithm, but do not depend on the actual allocation decisions made in previous rounds. In this setting, they show connections to the online multicolor discrepancy problem and, in the special case of two agents, to online vector balancing [64]. Other works give the algorithm partial information about future goods [56], let it see a few goods ahead [4], or let it hold and reorder a bounded number of goods before allocating them [3]; the last two also give guarantees that hold after every allocated good. For approximate proportionality, Choo et al. [21] show that several natural greedy rules cannot guarantee any positive approximation to proportionality up to one good (PROP1) against an adaptive adversary, and Neoh and Teh [58] show that this holds for every online algorithm, and also for proportionality up to k goods with any fixed k; positive guarantees are possible against an oblivious adversary [21, 24] or when each agent’s largest value for a good is known in advance [21, 58]. Online fair division under budget constraints has also been studied [23]. In contrast, our work assumes full information about the values of all goods from the outset, and focuses on cumulative envy minimization, aligning more with the temporal fair division model than with adversarial online models. Temporal Fair Division. In the temporal fair division model (sometimes also referred to as the fully informed online fair division model), the sequence of goods is known in advance, allowing the algorithm to make allocation decisions with full knowledge of future arrivals. This setting enables us to introduce the study of fairness guarantees that are cumulative over time, rather than only at the final round. Cookson et al. [25] introduce temporal fair division and give existence/algorithmic guarantees for achieving EF1-type fairness simultaneously at multiple points in time, with stronger positive results in special cases (e.g., two agents or structured preferences). Elkind et al. [29] formalize temporal EF1 (TEF1) for sequential item arrivals, show that deciding whether a TEF1 allocation exists is NP-hard, and provide polynomial-time algorithms in several structured cases. He et al. [43] maintain EF1 at every round by allowing limited reallocations (or what they call adjustments), and quantify how many such changes are necessary (including separations between informed vs. uninformed settings); in particular, with full information about future goods, no adjustments are needed for two agents, whereas for three or more agents EF1 cannot always be maintained at every round without adjustments, so TEF1 allocations need not exist. Choi and Li [20] study temporal versions of EFX and maximin share fairness, and Choi and Li [19] further allow each good to be delayed by a bounded number of rounds before it is allocated. Choi et al. [18] identify settings with goods and chores in which TEF1 allocations exist and can be computed efficiently. In contrast to this constraint-based line of work (maintaining temporal EF1 at every prefix), we take an optimization view and minimize the cumulative “area under the envy curve”, which remains meaningful even when strong prefix-fairness constraints are infeasible. Fairness over time has also been studied in repeated allocation, where the same set of items is allocated in every round [46, 16]. Micheel and Wilczynski [53] study a related repeated house allocation model in which every round is a complete matching, so each agent receives one object. They focus on envy-based fairness across the repeated assignments, together with Pareto efficiency in each round. Their model differs from ours in two main ways: they make a complete assignment in every round, whereas we allocate one indivisible good irrevocably at each step; and they study fairness conditions across repeated assignments, whereas we minimize cumulative maximum envy. Lim et al. [51] study repeated matchings that maximize the minimum cumulative utility of an agent, either at the end or at every round. Fairness over time has also been studied in other collective decision problems, such as temporal slot assignment [28] and perpetual or temporal voting [50, 30]. 2 Preliminaries For each positive integer z, we denote [z]:=1,…,z[z]:=\1,…,z\. An instance of the fair division problem is a tuple ℐ=(N,G,=(v1,…,vn))I=(N,G,v=(v_1,…,v_n)), where N=[n]N=[n] is the set of (fixed) agents, G is a set of m goods, and for each i∈Ni∈ N, the function vi:2G→ℝ≥0v_i 2^G _≥ 0 is the valuation function of agent i. We write v instead of viv_i when all agents have identical valuation functions. In the temporal fair division problem, goods arrive sequentially according to some order π, and we must allocate each good (to an agent) as it arrives. Let Π denote the space of all such arrival orders. In this work, we consider both the setting where π is chosen by an adversary (i.e., the standard temporal fair division setting) and the setting where π can be chosen by the algorithm. As with most works in the fair division literature, we assume that valuation functions are additive, i.e., for any subset of goods B⊆GB G, vi(B)=∑g∈Bvi(g)v_i(B)= _g∈ Bv_i(\g\). For convenience, we write vi(g)v_i(g) instead of vi(g)v_i(\g\) for a single good g. Every subset of goods in G can also be referred to as a bundle. An allocation =(A1,…,An)A=(A_1,…,A_n) is a partition of the goods into bundles, with agent i∈Ni∈ N receiving bundle AiA_i. For each i∈Ni∈ N and t∈[m]t∈[m], let AitA_i^t denote the partial allocation of agent i after the t-th arriving good is allocated to an agent and let Ai0=∅A_i^0= be the initial empty allocation, and Aim=AiA_i^m=A_i. Equivalently, we can represent an allocation by an allocation sequence S=(s1,…,sm)∈NmS=(s_1,…,s_m)∈ N^m, where for each t∈[m]t∈[m], the t-th entry sts_t specifies the agent that the t-th arriving good is allocated to. Let the space of all such sequences be S. Next, we define envy and the envy minimization objective. Let S be the allocation sequence corresponding to A, given some order π. Then, for any t∈[m]t∈[m], the envy of agent i∈Ni∈ N toward agent j∈N∖ij∈ N \i\ is envyi,jt(S,π):=max0,vi(Ajt)−vi(Ait)envy_i,j^t(S,π):= \0,\,v_i(A_j^t)-v_i(A_i^t)\; in particular, envyi,it(S,π)=0envy_i,i^t(S,π)=0. The per-round cost is ct(S,π):=maxi,j∈Nenvyi,jt(S,π)c_t(S,π):= _i,j∈ Nenvy_i,j^t(S,π), and the cumulative maximum envy is cost(S,π):=∑t=1mct(S,π) cost(S,π):= _t=1^mc_t(S,π), which we seek to minimize. Maximum envy is a standard quantitative objective in both offline envy minimization [52] and online envy minimization [11, 42]. In most online models, fairness is evaluated only after the last item has been allocated. In the fully informed temporal model, however, future arrivals and valuations are known, so it is natural to ask for fairness over the trajectory of the allocation, not just at the end. One stronger requirement would be to optimize every prefix simultaneously (as in the anytime optimality notion of Lim et al. [51] for repeated matching), or to impose a fairness constraint at every prefix as in temporal EF1 [29]. We instead optimize the total area under the worst-envy curve. This permits short-term imbalances when they are compensated later, but penalizes imbalances that are large or long-lasting. This matches settings where temporary disparities are acceptable but prolonged severe unfairness is not. Finally, optimizing only the final maximum envy can be badly misaligned with minimizing cumulative exposure to envy. Example 1 gives a linear separation even under identical valuations; conversely, cumulative maximum envy always controls final envy because cm(S,π)c_m(S,π) is one of the terms in ∑tct(S,π) _tc_t(S,π). Example 1 Consider an instance with n=2n=2 and identical valuation function v. Fix any integer q≥2q≥ 2, let m:=2q+1m:=2q+1 and ε:=992q := 992q. Then m is odd and (m−1)ε=99(m-1) =99. Let π=(g1,…,gm)π=(g_1,…,g_m) be a fixed arrival order where v(gt)=εv(g_t)= for every t≤m−1t≤ m-1 and v(gm)=100v(g_m)=100. For n=2n=2, we have ct(S,π)=|v(A1t)−v(A2t)|c_t(S,π)= |v(A_1^t)-v(A_2^t) | for every t∈[m]t∈[m]. • An allocation minimizing the final round cost. Allocate g1,…,gm−1\g_1,…,g_m-1\ to agent 11 and gmg_m to agent 22. Then v(A1m)=99v(A_1^m)=99 and v(A2m)=100v(A_2^m)=100, so cm(S,π)=1c_m(S,π)=1 (and no allocation can have cm(S,π)<1c_m(S,π)<1 since v(G)=199v(G)=199). Moreover, for each t≤m−1t≤ m-1 we have v(A1t)=tεv(A_1^t)=t and v(A2t)=0v(A_2^t)=0, so ct(S,π)=tεc_t(S,π)=t . Thus, cost(S,π)=∑t=1m−1tε+1=εm(m−1)2+1=99m2+1cost(S,π)= _t=1^m-1t +1= m(m-1)2+1= 99m2+1, which grows linearly in m. • An allocation with much smaller cumulative cost. Alternately allocate the first m−1m-1 goods between the agents. Then for every t≤m−1t≤ m-1, we maintain |v(A1t)−v(A2t)|≤ε|v(A_1^t)-v(A_2^t)|≤ , so ct(S,π)≤εc_t(S,π)≤ ; more precisely, ct(S,π)=εc_t(S,π)= on odd t and ct(S,π)=0c_t(S,π)=0 on even t. Since m−1m-1 is even, ∑t=1m−1ct(S,π)=m−12ε _t=1^m-1c_t(S,π)= m-12 . Allocating gmg_m gives cm(S,π)=100c_m(S,π)=100, so cost(S,π)=m−12ε+100=992+100=2992<99m2+1cost(S,π)= m-12 +100= 992+100= 2992< 99m2+1 for all m>3m>3. 3 Intractability Results We first present several results highlighting the computational intractability of envy minimization as an objective in the temporal fair division setting. We begin by formalizing the decision problem. Temporal-EnvyMin Given an instance ℐ=(N,G,)I=(N,G,v), an order π=(g1,…,gm)π=(g_1,…,g_m) over the goods in G, and an integer γ∈ℤ≥0γ _≥ 0, can we find an allocation sequence S such that cost(S,π)≤γ cost(S,π)≤γ? Then, we show that the problem is computationally intractable even in the restricted setting where agents have identical valuation functions—that is, for any pair of agents i,j∈Ni,j∈ N and good g, we have vi(g)=vj(g)=v(g)v_i(g)=v_j(g)=v(g). Moreover, we go one step further by showing that a constant-factor approximation algorithm is unlikely to exist. Theorem 3.1 Temporal-EnvyMin is strongly NP-complete even when agents have identical valuations. Moreover, in this setting, there exists no constant-factor approximation algorithm, unless P=NP P= NP. Proof We reduce from the 3-Partition problem, which is known to be strongly NP-complete [34]. An instance of 3-Partition is given by a multiset of positive integers X=x1,…,x3kX=\x_1,…,x_3k\ (with ∑j=13kxj=kT _j=1^3kx_j=kT); it is a yes-instance if there exists a partition of X into k subsets X1′,…,Xk′X _1,…,X _k (each containing three integers) such that ∑x∈Xj′x=T _x∈ X _jx=T for all j∈[k]j∈[k], and a no-instance otherwise. Note that for each integer x∈Xx∈ X, we can without loss of generality assume that x<Tx<T (otherwise it is trivially a no-instance). Construct an instance of our problem, where N=[k+2]N=[k+2] and we have m:=9k+7m:=9k+7 goods arriving in the order π=(g1,g2,…,g3k+1,g3k+2,g3k+3,…,g9k+7)π=(g_1,g_2,…,g_3k+1,g_3k+2,g_3k+3,…,g_9k+7), with valuations defined as follows: v(gj)=10T if j=1;xj−1+3T if j∈2,…,3k+1;10T if j=3k+2;0 if j∈3k+3,…,9k+7.v(g_j)= cases10T& if j=1;\\ x_j-1+3T& if j∈\2,…,3k+1\;\\ 10T& if j=3k+2;\\ 0& if j∈\3k+3,…,9k+7\. cases We first show that Temporal-EnvyMin is NP-complete (it is easy to see that the problem is in NP, we thus focus on proving NP-hardness). We do so by proving that there exists a solution X1′,…,Xk′X _1,…,X _k to 3-Partition if and only if there exists an allocation A (and hence corresponding allocation sequence S) such that cost(S,π)≤10T⋅(3k+1) cost(S,π)≤ 10T·(3k+1) for the above constructed instance. (⇒ ) Suppose there exists a solution X1′,…,Xk′X _1,…,X _k to 3-Partition. Consider the sequence S=(s1,…,sm)S=(s_1,…,s_m): sj=1 if j∈1,3k+3,…,9k+7;2 if j=3k+2;ℓ+2 if xj−1∈Xℓ′ for ℓ∈[k]s_j= cases1& if j∈\1,3k+3,…,9k+7\;\\ 2& if j=3k+2;\\ +2& if x_j-1∈ X _ for ∈[k] cases Observe that for all t∈1,…,3k+1t∈\1,…,3k+1\, every agent i≥3i≥ 3 holds at most three positively-valued goods, whose total value is at most T+9T=10T+9T=10T. Thus, maxi∈Nv(Ait)=10T _i∈ Nv(A_i^t)=10T and mini∈Nv(Ait)=0 _i∈ Nv(A_i^t)=0, so we have that ct(S,π)=10Tc_t(S,π)=10T. Moreover, since each agent in N∖1,2N \1,2\ has bundle value T+3⋅3T=10T+3· 3T=10T, we get that c3k+2(S,π)=0c_3k+2(S,π)=0. Then, cost(S,π) cost(S,π) =∑t=13k+2ct(S,π)+∑t=3k+39k+7ct(S,π) = _t=1^3k+2c_t(S,π)+ _t=3k+3^9k+7c_t(S,π) =10T⋅(3k+1)+0+0=10T⋅(3k+1). =10T·(3k+1)+0+0=10T·(3k+1). (⇐ ) Suppose there does not exist a solution to 3-Partition. This means that there does not exist a partition of integers in X=x1,…,x3kX=\x_1,…,x_3k\ into k subsets of equal sum T. Equivalently, there is no way to partition the 3k3k goods g2,…,g3k+1\g_2,…,g_3k+1\ into k bundles each of total value 10T10T. Let i∗∈Ni^*∈ N be the agent that receives good g3k+2g_3k+2, i.e., g3k+2∈Ai∗g_3k+2∈ A_i^*. We split our analysis into two cases. Case 1: No good in g1,…,g3k+1\g_1,…,g_3k+1\ allocated to agent i∗i^*. Let g1g_1 be allocated to agent i′∈N∖i∗i ∈ N \i^*\. Then, Ai′1=g1A_i ^1=\g_1\ and v(Ai′1)=10Tv(A_i ^1)=10T. Now, since no goods in g1,…,g3k+1\g_1,…,g_3k+1\ was allocated to agent i∗i^*, for all t∈1,…,3k+1t∈\1,…,3k+1\, we have that Ai∗t=∅A_i^*^t= , giving us ct(S,π)≥10Tc_t(S,π)≥ 10T. At round 3k+23k+2, agent i∗i^* receives a good valued at 10T10T and thus has value exactly 10T10T (since she received nothing earlier). If c3k+2(S,π)=0c_3k+2(S,π)=0, then every agent must have value exactly 10T10T at round 3k+23k+2 (since the total value of the first 3k+23k+2 goods is 10T(k+2)10T(k+2), equality across k+2k+2 agents forces each to have value 10T10T). The agent i′i holding the first good valued at 10T10T (i.e., g1g_1) cannot hold any other positively-valued good (each such good has value >3T>3T), else it would exceed 10T10T. Therefore, the remaining k agents must partition the 3k3k goods of values xj−1+3Tx_j-1+3T into k bundles each of value 10T10T. Since each such good has value strictly between 3T3T and 4T4T, each bundle must contain exactly 33 goods, and the xjx_j parts in each bundle must sum to T, which is a 3-Partition solution, giving us a contradiction. Thus, c3k+2(S,π)≥1c_3k+2(S,π)≥ 1, and together with ∑t=13k+1ct(S,π)≥10T(3k+1) _t=1^3k+1c_t(S,π)≥ 10T(3k+1), we get cost(S,π)>10T(3k+1) cost(S,π)>10T(3k+1). Case 2: Some good in g1,…,g3k+1\g_1,…,g_3k+1\ allocated to agent i∗i^*. Let g1g_1 be allocated to agent i′∈Ni ∈ N (note that it could be i′=i∗i =i^*). Since i∗i^* is also allocated good g3k+2g_3k+2, we have that v(Ai∗3k+2)≥3T+10T=13Tv(A_i^*^3k+2)≥ 3T+10T=13T. If i′=i∗i =i^*, then 3k3k goods are distributed among k+1k+1 agents, so some agent gets at most two goods from g2,…,g3k+1\g_2,…,g_3k+1\. If i′≠i∗i ≠ i^*, then i∗i^* must have taken at least one of the 3k3k goods (since g1g_1 went to i′i ), leaving at most 3k−13k-1 such goods for the remaining k agents in N∖i′,i∗N \i ,i^*\; and by pigeonhole one of them gets at most two goods from g2,…,g3k+1\g_2,…,g_3k+1\. Now, for each j∈2,…,3k+1j∈\2,…,3k+1\, we know that v(gj)<T+3T=4Tv(g_j)<T+3T=4T (by our assumption that x<Tx<T for each x∈Xx∈ X). Then, v(Ai3k+2)<8Tv(A_i^3k+2)<8T. This means that c3k+2(S,π)≥v(Ai∗3k+2)−v(Ai3k+2)>13T−8T=5Tc_3k+2(S,π)≥ v(A_i^*^3k+2)-v(A_i^3k+2)>13T-8T=5T. There are 6k+56k+5 zero-valued goods after round 3k+23k+2, i.e., rounds t=3k+3,…,9k+7t=3k+3,…,9k+7. Since these goods do not change any bundle values, ct(S,π)=c3k+2(S,π)c_t(S,π)=c_3k+2(S,π) for all such t. Thus, ∑t′=3k+39k+7ct′ _t =3k+3^9k+7c_t =(6k+5)⋅c3k+2(S,π)>(6k+5)⋅5T>10T(3k+1), =(6k+5)· c_3k+2(S,π)>(6k+5)· 5T>10T(3k+1), which implies cost(S,π)>10T(3k+1)cost(S,π)>10T(3k+1). Next, we argue that in (the same) setting where agents have identical valuations, there exists no constant-factor approximation algorithm, unless P = NP. Since 3-Partition is strongly NP-complete, meaning even when T=poly(n)T= poly(n), the problem remains NP-complete. Thus, we can assume T=poly(n)T= poly(n). Then, note that in the reduction above, we showed that given an instance ℐI and order π, determining whether we can find an allocation sequence S such that cost(S,π)≤10T⋅(3k+1) cost(S,π)≤ 10T·(3k+1) is NP-complete. Equivalently, • any yes-instance admits a sequence S with cost(S,π)≤10T⋅(3k+1) cost(S,π)≤ 10T·(3k+1), and in particular c3k+2(S,π)=0c_3k+2(S,π)=0; • any no-instance will force any sequence S to have c3k+2(S,π)≥1c_3k+2(S,π)≥ 1. Let B:=10T(3k+1)B:=10T(3k+1) and fix any constant α≥1α≥ 1. To amplify the gap, append Zα:=⌈B(α−1)⌉+1Z_α:= B(α-1) +1 zero-valued goods after g9k+7g_9k+7. In a yes-instance, the allocation above still has cost at most B, because the envy is already zero from round 3k+23k+2 onward. In a no-instance, every allocation has positive envy after round 3k+23k+2; since all appended goods have value zero, this envy persists through the appended rounds. Thus, every allocation has cost strictly larger than B+Zα>αB+Z_α>α B. Therefore, given a 3-Partition instance, run the assumed α-approximation on the corresponding Temporal-EnvyMin instance and compare its returned cost with αBα B. If the original 3-Partition instance is a yes-instance, the returned cost is at most αBα B. If it is a no-instance, every feasible allocation has cost greater than αBα B. The assumed approximation algorithm would therefore decide 3-Partition in polynomial time, which is impossible unless P=NP P= NP. Notably, the above hardness result continues to hold even when the maximum value of any good is bounded by a polynomial in n, owing to the strong NP-completeness property of the 3-Partition problem used in the reduction. In the offline setting, the minimum maximum envy cannot be approximated within any factor simply because it may be zero [52]. This argument does not apply directly to our objective under identical valuations, since the first good with positive value always creates envy, so even yes-instances have positive optimal cost. Our reductions instead end with zero-valued goods, so that any envy remaining after the last positively valued good is counted in each of the remaining rounds. We now turn to a different restricted setting in which agents have binary valuation functions—that is, for each agent i∈Ni∈ N and good g, vi(g)∈0,1v_i(g)∈\0,1\. In this case, we establish a second intractability result by reducing from a known NP-hard problem in the standard (offline) fair division literature: deciding whether there exists a complete envy-free allocation under binary valuations, a problem we refer to as Binary-EF. This hardness was first shown implicitly by Aziz et al. [5] and later made explicit by Hosseini et al. [44]. As in the previous case, we show that a constant-factor approximation algorithm is unlikely to exist. Theorem 3.2 Temporal-EnvyMin is NP-complete even when agents have binary valuations. Moreover, in this setting, there exists no constant-factor approximation algorithm, unless P=NP P= NP. 4 Tractability in Restricted Settings Given the computational hardness of finding an envy-minimizing allocation sequence, even under two distinct restricted settings (identical valuations or binary valuations), a natural follow-up question is whether there exists any restricted setting for which an optimal solution can be computed efficiently. We begin with a simple warm-up result. The most favorable remaining setting is when valuations are both binary and identical. While this does not exactly reduce the problem to one with identically-valued goods,33 3 This setting has also been studied in other fair division contexts; see, e.g., Elkind et al. [27]. it is closely related. In this case, a straightforward greedy algorithm (which allocates each arriving good to an agent with the currently lowest total bundle value) produces an allocation with minimum cost. This greedy rule is a special case of the algorithm that Elkind et al. [29] use to obtain TEF1 allocations under generalized binary valuations; we show that, under binary and identical valuations, it also minimizes the maximum envy at every round. Proposition 1 Under binary and identical valuations, an optimal sequence can be computed in polynomial time. Next, for the main result of this section, we present a dynamic programming algorithm that runs in time ((m+1)(Vmaxm2+1)(mVmax+1)n2⋅n3)O((m+1)(V_ m^2+1)(mV_ +1)^n^2· n^3), where Vmax:=maxi∈N,g∈Gvi(g)V_max:= _i∈ N,g∈ Gv_i(g) is the maximum value of any good in any agent’s view (and we can assume valuations are encoded in unary and scaled to integers). For t∈0,…,mt∈\0,…,m\, let Mt∈0,…,m⋅Vmaxn×nM^t∈\0,…,m· V_max\^n× n be the valuation matrix after the first t goods have arrived: Mi,jtM_i,j^t is the value agent i has for agent j’s bundle thus far, and M0M^0 is the all-zero matrix. The algorithm is presented as follows (Algorithm 1). Algorithm 1 Dynamic programming algorithm that returns an optimal sequence Input: Instance ℐ=(N,G,)I=(N,G,v) and order π=(g1,…,gm)π=(g_1,…,g_m). Output: Allocation sequence S=(s1,…,sm)S=(s_1,…,s_m). 1: Let M0M^0 be the all–zero n×n× n matrix 2: Create hash maps DP[0],…,DP[m]DP[0],…,DP[m] mapping keys (c,M)(c,M) to predecessor pointers 3: Initialize DP[0][(0,M0)]←∅DP[0][(0,M^0)]← 4: for t=0,…,m−1t=0,…,m-1 do 5: for all states (c,M)(c,M) in DP[t]DP[t] do 6: for s=1,…,ns=1,…,n do 7: M′←M ← M (deep copy) 8: for i=1,…,ni=1,…,n do 9: Mi,s′←Mi,s′+vi(gt+1)M _i,s← M _i,s+v_i(g_t+1) 10: end for 11: c′←c+maxi,jmax0,Mi,j′−Mi,i′c ← c+ _i,j \0,M _i,j-M _i,i\ 12: if (c′,M′)∉DP[t+1](c ,M ) [t+1] then 13: DP[t+1][(c′,M′)]←((c,M),s)DP[t+1][(c ,M )]←((c,M),s) 14: end if 15: end for 16: end for 17: end for 18: Let (c∗,M∗):=argmin(c,M)∈DP[m]c(c^*,M^*):= _(c,M) [m]c 19: Initialize S=(s1,…,sm)=(0,…,0)S=(s_1,…,s_m)=(0,…,0) and (c,M)←(c∗,M∗)(c,M)←(c^*,M^*) 20: for t=m,…,1t=m,…,1 do 21: ((cprev,Mprev),st)←DP[t][(c,M)]((c_prev,M_prev),s_t) [t][(c,M)] 22: S[t]←stS[t]← s_t 23: (c,M)←(cprev,Mprev)(c,M)←(c_prev,M_prev) 24: end for 25: return S=(s1,…,sm)S=(s_1,…,s_m) Intuitively, the algorithm explores every possible way to assign the first t goods while precisely tracking the valuation matrix M and cost (i.e., envy) incurred c. At each step, it branches on which agent receives the next good, updates the corresponding column of M, accrues the cost incurred, and records a predecessor pointer. At the end (layer m), it scans through all reachable pairs (c,M)(c,M) and returns the one minimizing cost, reconstructing a witnessing allocation by following the pointers backward. Our result is as follows. Theorem 4.1 Algorithm 1 returns an optimal sequence in time ((m+1)(Vmaxm2+1)(mVmax+1)n2⋅n3)O((m+1)(V_ m^2+1)(mV_ +1)^n^2· n^3). Proof We first prove correctness. Observe that the (c,M):(c,M)∈DP[m]\(c,M):(c,M) [m]\ is the set of pairs attainable after all goods have arrived. Then, selecting (c∗,M∗)(c^*,M^*) with minimum c∗c^* (Line 18) corresponds to one with minimum cost (or cumulative envy). From there, our algorithm is able to reconstruct a corresponding allocation sequence (Lines 20–24). Thus, it suffices for us to prove the following invariant. Let πt:=(g1,…,gt) _t:=(g_1,…,g_t). Invariant. For every t∈0,…,mt∈\0,…,m\ and pair (c,M)(c,M), DP[t][(c,M)]DP[t][(c,M)] exists if and only if there is an allocation sequence XtX_t for the first t goods (prefix πt _t) such that the resulting valuation matrix is M and c=∑τ=1tcτ(Xt,πτ)c= _τ=1^tc_τ(X_t, _τ). Moreover, the predecessor pointer encodes one such sequence. We prove the invariant by induction on t∈0,…,mt∈\0,…,m\. For the base case, at t=0t=0, DP[t]DP[t] only contains (0,M0)(0,M^0), where M0M^0 is the all-zero matrix; and the cost is 00. Thus the invariant holds trivially. Next, we prove the inductive step. Assume the invariant holds for some t<mt<m. Since for each round t, ct(S,π)≤t⋅Vmaxc_t(S,π)≤ t· V_max, we have ∑t=1mct(S,π)≤Vmax⋅m(m+1)/2<Vmax⋅m2 _t=1^mc_t(S,π)≤ V_max· m(m+1)/2<V_max· m^2. Consider any state (c,M)∈DP[t](c,M) [t]. By the induction hypothesis, there exists an allocation sequence Xt=(x1,…,xt)X_t=(x_1,…,x_t) of the first t goods with valuation matrix M and cost cost(Xt,πt)=c cost(X_t, _t)=c. When good gt+1g_t+1 arrives, Algorithm 1 considers every agent s∈Ns∈ N and for each s, constructs M′M by increasing column s by vi(gt+1)v_i(g_t+1). Hence every feasible extension is represented in DP[t+1]DP[t+1]. Conversely, suppose (c′,M′)(c ,M ) is inserted into DP[t+1]DP[t+1] from predecessor (c,M)(c,M) using agent s. By the induction hypothesis, (c,M)(c,M) arises from some allocation sequence (x1,…,xt)(x_1,…,x_t) with matrix M and cost cost(Xt,πt) cost(X_t, _t); extending by xt+1=sx_t+1=s gives us matrix M′M and updating the cost to c′c , so (c′,M′)(c ,M ) corresponds to a feasible allocation of t+1t+1 goods. Note that after updating column s, M′M is exactly the valuation matrix after t+1t+1 items under the extended sequence. Therefore, the maximum envy at round t+1t+1 is ct+1=maxi,jmax0,Mi,j′−Mi,i′,c_t+1= _i,j \0,\,M _i,j-M _i,i\, so the cumulative cost is consistent with Line 11 of the algorithm. Thus the invariant holds for t+1t+1. By induction, the invariant holds for all t≤mt≤ m, and optimality follows. Next, we prove the running time. The state space is indexed by (t,c,M)(t,c,M) with t∈0,…,m,c∈0,…,Vmax⋅m2t∈\0,…,m\,c∈\0,…,V_max· m^2\, and M∈0,…,m⋅Vmaxn×nM∈\0,…,m· V_max\^n× n. Thus, the number of states is (m+1)⋅(Vmax⋅m2+1)⋅(m⋅Vmax+1)n2. (m+1)·(V_max· m^2+1)·(m· V_max+1)^n^2. From each state, there are n agents the algorithm can consider allocating the incoming good to, updates one column of M and computes the new cost. Both operations (i.e., per transition) take (n2)O(n^2) time. Since there are n transitions per state, it takes (n3)O(n^3) per state. Thus, the total running time is ((m+1)(Vmaxm2+1)(mVmax+1)n2⋅n3)O((m+1)(V_maxm^2+1)(mV_max+1)^n^2· n^3). Reconstruction follows m pointers and is (m)O(m), which does not change the bound. This result has two important implications. First, for fixed n, the running time is polynomial in m and VmaxV_max; thus the algorithm is pseudopolynomial. In particular, if item values are polynomially bounded integers (or given in unary), the algorithm runs in polynomial time. Corollary 1 Temporal-EnvyMin is XP [33, 60] with respect to (n,Vmax)(n,V_max). Equivalently, it is solvable in pseudopolynomial time when n is bounded by a constant. Second, in the case of binary valuations,44 4 Binary valuations are very well-studied in online fair division [1, 2, 67] and in the broader fair division literature [13, 44, 41, 57, 65]. the size of the state space in the dynamic program becomes more structured. Then, the number of agents is constant, the problem is polynomial-time solvable (i.e. slicewise polynomial in n). Corollary 2 Under binary valuations, Temporal-EnvyMin is XP with respect to n. These results show that, despite the general computational hardness of the problem, efficient algorithms are achievable under natural and practically motivated restrictions. That being said, an intriguing open question remains: is the problem polynomial-time solvable when the number of agents is constant and agents have identical valuation functions? We conjecture that the answer is ‘no’. As a partial positive result, we provide an FPTAS for identical valuations (with integer item values) when n is fixed. Theorem 4.2 For any fixed n≥2n≥ 2, under identical valuations with integer-valued items, and for every ε∈(0,1) ∈(0,1), there exists a (1+ε)(1+ )-approximation algorithm whose running time is polynomial in m and 1/ε1/ . Our FPTAS follows the standard approach of rounding the values and solving the rounded instance by dynamic programming [45, 62]; Lipton et al. [52] use the same approach for the envy-ratio with a constant number of agents. The step specific to our objective is a lower bound of (1−1/n)v(G)(1-1/n)\,v(G) on the cost of every allocation sequence, which bounds the rounding error added up over all m rounds. 5 Choosing the Arrival Sequence The results presented in Section 3 show that computing a cost-minimizing allocation sequence is generally intractable, even under restricted settings such as identical or binary valuations. While Section 4 presents some positive algorithmic results under stronger assumptions, the overall hardness results align with existing impossibility results in the literature on online and temporal fair division: fairness objectives remain elusive in the presence of fixed input sequences. In fact, we illustrate with an example how an adversary deciding the arrival order can make a significant difference when it comes to minimizing cumulative envy. Example 2 Consider an instance with n=2n=2 and identical valuation function v. Fix any integer q≥2q≥ 2, let m:=2q+1m:=2q+1, and set ε:=99/(2q) :=99/(2q). Thus, m is odd and (m−1)ε=99(m-1) =99. There is one good of value 100100 and m−1m-1 goods of value ε . • If the arrival order is π=(g1,…,gm)π=(g_1,…,g_m) with v(g1)=100v(g_1)=100 and v(gt)=εv(g_t)= for all t≥2t≥ 2, then after round 11, c1(S,π)=100c_1(S,π)=100 for every allocation sequence S. Furthermore, each subsequent ε -good can reduce the gap |v(A1t)−v(A2t)||v(A_1^t)-v(A_2^t)| by at most ε , so for k=0,1,…,m−1k=0,1,…,m-1, c1+k(S,π)≥100−kεc_1+k(S,π)≥ 100-k . Allocating every ε -good to the currently lagging agent achieves equality at every round, and therefore minS∈cost(S,π)=∑k=0m−1(100−kε)=100m−εm(m−1)2=101m2 _S cost(S,π)= _k=0^m-1(100-k )=100m- m(m-1)2= 101m2, which is Θ(m) (m). • In contrast, if the ε -goods arrive first (e.g., π′=(g2,…,gm,g1)π =(g_2,…,g_m,g_1)), then allocating the first m−1m-1 goods alternately keeps ct(S,π′)≤εc_t(S,π )≤ for all t≤m−1t≤ m-1, and the last step contributes cm(S,π′)=100c_m(S,π )=100. Consequently, cost(S,π′)=m−12ε+100=2992cost(S,π )= m-12 +100= 2992, which is O(1)O(1) in m. Thus, when one item dominates in value, placing it early can force cumulative cost that is a factor Θ(m) (m) larger than an order that places it last. Motivated by this example, we study a variant in which the algorithm chooses the order of the goods, while the agents’ valuations are fixed in advance. This models settings where the full set of goods is known and goods can be held briefly before release. For example, a food bank may have several donated pallets in storage and choose which pallet to allocate next, or a public agency may choose the order in which approved permits are issued. We ask whether control over the order can reduce cumulative envy.55 5 Many related online problems assume a random arrival order as a way to circumvent impossibility results that arise under adversarial input models [6, 26, 31, 32, 36, 40, 48, 49]. Related forms of flexibility have recently been studied for existence questions: Choi and Li [19] allow each good to be delayed by a bounded number of rounds in order to obtain TEF1 allocations, and Amanatidis et al. [3] let an online algorithm hold and reorder a bounded number of goods. In our variant, the algorithm may choose any order, but each good is still allocated in its own round and the envy at every round counts; hence, choosing the order does not reduce our problem to the offline one. Importantly, this setting is not inherently “stronger” or “weaker” than the standard one; it is simply of a different structure. Although the ability to control the arrival order offers additional flexibility, the benchmark for optimization also shifts: the optimal solution under this new setting may differ from that in the fixed-order setting. As a result, the optimization problem (e.g., obtaining approximation results) does not necessarily become easier—the performance is still measured relative to a stronger baseline, and the underlying computational challenges remain significant. Observe that the cost objective is cumulative, so even when the final allocation can be envy-free, early rounds may still incur substantial envy. In the special case of identical valuations, Lemma 1 (stated below) implies the universal lower bound OPT(ℐ)≥(1−1/n)⋅v(G) OPT(I)≥(1-1/n)· v(G). One might hope that by choosing the arrival order, the algorithm could always achieve this bound. Our next result shows that even deciding whether this lower bound is attainable is NP-complete. Temporal-EnvyMin-Seq Given an instance ℐ=(N,G,)I=(N,G,v) and an integer γ∈ℤ≥0γ _≥ 0, can we find a permutation π over the goods in G and an allocation sequence S such that cost(S,π)≤γ cost(S,π)≤γ? Theorem 5.1 Temporal-EnvyMin-Seq is NP-complete even for two agents with identical valuations. Theorem 5.1 shows that allowing the algorithm to choose the arrival order does not eliminate computational intractability: the problem remains NP-hard even under identical valuations.66 6 This setting has also been extensively studied both in sequential fair division models [29, 46, 66] and in the broader fair division literature [8, 22, 61, 63]. Nevertheless, this setting admits simple algorithms with provable approximation and additive guarantees. We first state a universal lower bound (independent of the chosen order), which will serve as a benchmark for both hardness and approximation results. Importantly, the bound holds for any number of agents, assuming identical valuations. Given an instance ℐI, let OPT(ℐ):=minS∈,π∈Πcost(S,π) OPT(I):= _S ,π∈ cost(S,π) denote the minimum possible cost achievable over all arrival orders π and allocation sequence S. Lemma 1 For any instance ℐ=(N,G,)I=(N,G,v) where n≥2n≥ 2 and agents have identical valuations, OPT(ℐ)≥(1−1/n)v(G) OPT(I)≥(1-1/n)\,v(G). Moreover, the bound is tight. Next, we introduce the following algorithm (Algorithm 2), designed for the setting where agents have identical valuations. The algorithm proceeds by first sorting the goods in increasing order of value (that will be the π), then iteratively allocating each good to the agent with the currently smallest bundle value. Despite its simplicity, we will show that this greedy approach is able to give us several positive approximation guarantees. Algorithm 2 Identical-Lowest-First Input: Instance ℐ=(N,G,)I=(N,G,v). Output: An order π and allocation sequence S=(s1,…,sm)S=(s_1,…,s_m). 1: Initialize (0)←(∅,…,∅)A^(0)←( ,…, ) and label goods such that v(g1)≤⋯≤v(gm)v(g_1)≤…≤ v(g_m) 2: π←(g1,…,gm)π←(g_1,…,g_m) 3: for t=1,…,mt=1,…,m do 4: Let i∗∈argmini∈Nv(Ait−1)i^*∈ _i∈ Nv(A_i^t-1), with ties broken in favor of the lowest-index agent 5: st←i∗s_t← i^* 6: Ai∗t←Ai∗t−1∪gtA_i^*^t← A_i^*^t-1∪\g_t\ 7: Ait←Ait−1A_i^t← A_i^t-1 for all i∈N∖i∗i∈ N \i^*\ 8: end for 9: return π and allocation sequence S=(s1,…,sm)S=(s_1,…,s_m) Relation to envy-cycle elimination and list scheduling. Under identical valuations, no envy cycle can arise, and an agent is unenvied exactly when her bundle has minimum value. Hence, Algorithm 2 is the envy-cycle elimination algorithm of Lipton et al. [52] applied to the goods in nondecreasing order of value. Their analysis, applied to the first t goods, shows that after each round the maximum envy is at most the largest value of a good allocated so far, i.e., ct≤v(gt)c_t≤ v(g_t); our proofs combine this bound with the lower bound of Lemma 1 and with an exact expression for the cost of Algorithm 2. Note that Algorithm 2 uses the opposite order to Graham’s greedy rule [39], which processes goods in nonincreasing order of value and, under identical valuations, yields EFX allocations [7, 61]; placing large goods last keeps the envy small in early rounds (cf. Example 2). Lipton et al. [52] also observed that, under identical valuations, envy minimization is closely related to scheduling on identical machines. Indeed, Algorithm 2 has the same steps as shortest-processing-time-first list scheduling on identical machines: goods are jobs, agents are machines, and v(g)v(g) is the processing time of job g. The objectives are different, however. List scheduling is usually analyzed using the final makespan, that is, the largest final machine load. In our setting, ctc_t is the difference between the largest and smallest loads after the first t jobs, and we minimize ∑tct _tc_t. Thus, the 3/23/2 factor in Theorem 5.2 does not follow from the usual list-scheduling analysis, although the common greedy rule may help explain why the same constant appears [38]. First, we show that in the case of two agents, we can get a 3/23/2-approximation to the optimal cost. Theorem 5.2 When n=2n=2 and the agents have identical valuations, Algorithm 2 achieves a 3/23/2-approximation to the optimal cost. We can extend the analysis to any n, obtaining an n−1 nn-1-approximation (which approaches 11 as n grows). Theorem 5.3 For all n≥2n≥ 2, if the agents have identical valuations, then Algorithm 2 achieves a n−1 nn-1-approximation to the optimal cost. For n=2n=2, the 3/23/2-approximation guarantee of Theorem 5.2 is tight; see Appendix 0.C.5. For n≥3n≥ 3, Appendix 0.C.6 provides an instance on which Identical-Lowest-First achieves approximation ratio 2n−12n−2 2n-12n-2. Finally, we complement the multiplicative bounds with an additive approximation guarantee, stated in terms of VmaxV_max. Theorem 5.4 For all n≥2n≥ 2, if agents have identical valuations, then Algorithm 2 outputs an order π and allocation sequence S such that cost(S,π)≤OPT(ℐ)+(1−1n)Vmax cost(S,π)≤ OPT(I)+ (1- 1n )\,V_ . In Appendix 0.C.8, we present a matching lower bound. 6 Conclusion In this paper, we initiated the study of envy minimization in temporal fair division from an optimization perspective, departing from the traditional focus on discrete relaxations like EF1 and EFX and on the prefix-based notions studied in earlier temporal work. In the standard model where the order of goods is adversarially chosen and fixed, we show that minimizing this objective is computationally intractable and cannot be approximated within any constant factor unless P=NP P= NP. In spite of this, we provide a dynamic programming algorithm that computes an optimal solution in several special cases. We then explored a natural variant in which the algorithm is allowed to choose the arrival order of goods, while an adversary pre-selects the valuations. Even with this additional flexibility, we show that the problem remains NP-complete for just two agents and identical valuations. We complement this with efficient approximation algorithms. Our results contribute to the growing understanding of temporal fairness in sequential allocation problems. Several directions remain open. In particular, it would be interesting to study discounted cumulative envy where recent unfairness matters more than past inequities; Kahana et al. [47] recently studied a related discounted model in an online setting. Acknowledgments PWG was supported by EPSRC grants EP/X040461/1 and EP/X038548/1. PWG and NT were supported by ARIA project “Aggregating Safety Preferences for AI Systems: A Social Choice Approach”. IR was supported by a Rhodes scholarship. References [1] M. Aleksandrov, H. Aziz, S. Gaspers, and T. Walsh (2015) Online fair division: analysing a food bank problem. In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI), p. 2540–2546. Cited by: §1, footnote 4. [2] M. Aleksandrov and T. Walsh (2017) Pure nash equilibria in online fair division. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI), p. 42–48. Cited by: footnote 4. [3] G. Amanatidis, G. Giaconi, E. Markakis, and N. Protopapas (2026) Online fair division meets reordering buffers. Note: arXiv:2607.01159 Cited by: §1.2, §5. [4] G. Amanatidis, A. Lolos, E. Markakis, and V. Turmel (2025) Online fair division for personalized 22-value instances. In Proceedings of the 18th International Symposium on Algorithmic Game Theory (SAGT), p. 209–227. Cited by: §1.2. [5] H. Aziz, S. Gaspers, S. Mackenzie, and T. Walsh (2015) Fair assignment of indivisible objects under ordinal preferences. Artificial Intelligence 227, p. 71–92. Cited by: §0.A.1, §3. [6] M. Babaioff, N. Immorlica, D. Kempe, and R. Kleinberg (2007) A knapsack secretary problem with applications. In Proceedings of the 10th International Workshop on Approximation (APPROX) and the 11th International Workshop on Randomization, and Combinatorial Optimization. Algorithms and Techniques (RANDOM), p. 16–28. Cited by: footnote 5. [7] S. Barman and S. K. Krishnamurthy (2020) Approximation algorithms for maximin fair division. ACM Transactions on Economics and Computation 8 (1), p. 5:1–5:28. Cited by: §5. [8] S. Barman and R. G. Sundaram (2020) Uniform welfare guarantees under identical subadditive valuations. In Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI), p. 46–52. Cited by: footnote 6. [9] X. Bei, Z. Li, and J. Luo (2022) Fair and efficient multi-resource allocation for cloud computing. In Proceedings of the 18th Conference on Web and Internet Economics (WINE), p. 169–186. Cited by: §1. [10] G. Benadè, A. M. Kazachkov, A. D. Procaccia, A. Psomas, and D. Zeng (2024) Fair and efficient online allocations. Operations Research 72 (4), p. 1438–1452. External Links: Document Cited by: §1.2. [11] G. Benadè, A. M. Kazachkov, A. D. Procaccia, and C. Psomas (2018) How to make envy vanish over time. In Proceedings of the 19th ACM Conference on Economics and Computation (EC), p. 593–610. Cited by: §1.2, §2, footnote 2. [12] S. J. Brams and A. D. Taylor (1996) Fair division: from cake-cutting to dispute resolution. Cambridge University Press. Cited by: §1. [13] F. Brandl, W. Suksompong, and N. Teh (2026) Fair division with binary valuations: characterizations. In Proceedings of the 19th International Symposium on Algorithmic Game Theory (SAGT), Cited by: footnote 4. [14] E. Budish (2011) The combinatorial assignment problem: approximate competitive equilibrium from equal incomes. Journal of Political Economy 119 (6), p. 1061–1103. Cited by: §1. [15] I. Caragiannis, D. Kurokawa, H. Moulin, A. D. Procaccia, N. Shah, and J. Wang (2019) The unreasonable fairness of maximum Nash welfare. ACM Transactions on Economics and Computation 7 (3), p. 12:1–12:32. Cited by: §1. [16] I. Caragiannis and S. Narang (2024) Repeatedly matching items to agents fairly and efficiently. Theoretical Computer Science 981, p. 114246. Cited by: §1.2. [17] B. R. Chaudhury, J. Garg, and K. Mehlhorn (2024) EFX exists for three agents. Journal of the ACM 71 (1), p. 1–27. Cited by: §1. [18] K. Choi, M. Li, and N. Teh (2026) Temporal fair division of indivisible mixed manna: tractable settings. Note: arXiv:2608.20033 Cited by: §1.2. [19] K. Choi and M. Li (2026) Temporal fair division of indivisible goods with scheduling. Note: arXiv:2601.12835 Cited by: §1.2, §5. [20] K. Choi and M. Li (2026) Temporal fair division of indivisible goods with structured constraints. In Proceedings of the 19th International Symposium on Algorithmic Game Theory (SAGT), Cited by: §1.2. [21] D. Choo, W. Fu, D. Khu, T. Y. Neoh, T. Poon, and N. Teh (2026) Approximate proportionality in online fair division. In Proceedings of the 43rd International Conference on Machine Learning (ICML), Cited by: §1.2. [22] D. Choo, Y. H. Ling, W. Suksompong, N. Teh, and J. Zhang (2024) Envy-free house allocation with minimum subsidy. Operations Research Letters 54, p. 107103. Cited by: footnote 6. [23] S. Cohen, N. Teh, P. W. Goldberg, and M. J. Wooldridge (2026) Online fair division with budget constraints. Note: arXiv:2607.23310 Cited by: §1.2. [24] S. Cohen, N. Teh, and M. Wooldridge (2026) Online fair division against an oblivious adversary. Note: arXiv:2609.28333 Cited by: §1.2. [25] B. Cookson, S. Ebadian, and N. Shah (2025) Temporal fair division. In Proceedings of the 39th AAAI Conference on Artificial Intelligence (AAAI), p. 13727–13734. Cited by: §1.2, §1. [26] N. R. Devanur and T. P. Hayes (2009) The adwords problem: online keyword matching with budgeted bidders under random permutations. In Proceedings of the 10th ACM Conference on Electronic Commerce (EC), p. 71–78. Cited by: footnote 5. [27] E. Elkind, A. Igarashi, and N. Teh (2024) Fair division of chores with budget constraints. In Proceedings of the 17th International Symposium on Algorithmic Game Theory (SAGT), p. 55–71. Cited by: footnote 3. [28] E. Elkind, S. Kraiczy, and N. Teh (2022) Fairness in temporal slot assignment. In Proceedings of the 15th International Symposium on Algorithmic Game Theory (SAGT), p. 490–507. Cited by: §1.2. [29] E. Elkind, A. Lam, M. Latifian, T. Y. Neoh, and N. Teh (2025) Temporal fair division of indivisible items. In Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), p. 676–685. Cited by: §1.2, §1, §2, §4, footnote 6. [30] E. Elkind, S. Obraztsova, and N. Teh (2024) Temporal fairness in multiwinner voting. In Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI), p. 22633–22640. Cited by: §1.2. [31] J. Feldman, N. Korula, V. Mirrokni, S. Muthukrishnan, and M. Pál (2009) Online ad assignment with free disposal. In Proceedings of the 5th International Workshop on Internet and Network Economics (WINE), S. Leonardi (Ed.), p. 374–385. Cited by: footnote 5. [32] J. Feldman, A. Mehta, V. Mirrokni, and S. Muthukrishnan (2009) Online stochastic matching: beating 1-1/e. In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS), p. 117–126. Cited by: footnote 5. [33] J. Flum and M. Grohe (2006) Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series, Springer. Cited by: Corollary 1. [34] M. R. Garey and D. S. Johnson (1975) Complexity results for multiprocessor scheduling under resource constraints. SIAM Journal on Computing 4 (4), p. 397–411. Cited by: Proof. [35] M. R. Garey and D. S. Johnson (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman. Cited by: §0.C.1. [36] G. Goel and A. Mehta (2008) Online budgeted matching in random input models with applications to adwords. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), p. 982–991. Cited by: footnote 5. [37] L. Gourvès, J. Monnot, and L. Tlilane (2014) Near fairness in matroids. In Proceedings of the 21st European Conference on Artificial Intelligence (ECAI), p. 393–398. Cited by: §1. [38] R. L. Graham (1966) Bounds for certain multiprocessing anomalies. The Bell System Technical Journal 45, p. 1563–1581. Cited by: §5. [39] R. L. Graham (1969) Bounds on multiprocessing timing anomalies. SIAM Journal on Applied Mathematics 17 (2), p. 416–429. Cited by: §5. [40] M. Hajiaghayi, M. Khani, D. Panigrahi, and M. Springer (2022) Online algorithms for the Santa Claus problem. In Proceedings of the 36th International Conference on Neural Information Processing Systems (NeurIPS), p. 30732–30743. Cited by: footnote 5. [41] D. Halpern, A. D. Procaccia, A. Psomas, and N. Shah (2020) Fair division with binary valuations: one rule to rule them all. In Proceedings of the 16th Conference on Web and Internet Economics (WINE), p. 370–383. Note: Extended version available at arXiv:2007.06073v2 Cited by: footnote 4. [42] D. Halpern, A. Psomas, P. Verma, and D. Xie (2025) Online envy minimization and multicolor discrepancy: equivalences and separations. In Proceedings of the 26th ACM Conference on Economics and Computation (EC), p. 188. Cited by: §1.2, §2. [43] J. He, A. D. Procaccia, A. Psomas, and D. Zeng (2019) Achieving a fairer future by changing the past. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI), p. 343–349. Cited by: §1.2. [44] H. Hosseini, S. Sikdar, R. Vaish, H. Wang, and L. Xia (2020) Fair division through information withholding. In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), p. 2014–2021. Cited by: §0.A.1, §3, footnote 4. [45] O. H. Ibarra and C. E. Kim (1975) Fast approximation algorithms for the knapsack and sum of subset problems. Journal of the ACM 22 (4), p. 463–468. Cited by: §4. [46] A. Igarashi, M. Lackner, O. Nardi, and A. Novaro (2024) Repeated fair allocation of indivisible items. In Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI), p. 9781–9789. Cited by: §1.2, footnote 6. [47] I. Kahana, E. Segal-Halevi, and N. Hazon (2026) Perpetual fully-online approximate fairness. Note: arXiv:2605.19844 Cited by: §6. [48] C. Karande, A. Mehta, and P. Tripathi (2011) Online bipartite matching with unknown distributions. In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC), p. 587–596. Cited by: footnote 5. [49] R. Kleinberg (2005) A multiple-choice secretary algorithm with applications to online auctions. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), p. 630–631. Cited by: footnote 5. [50] M. Lackner (2020) Perpetual voting: fairness in long-term decision making. In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), p. 2103–2110. Cited by: §1.2. [51] E. Lim, T. Y. Neoh, and N. Teh (2026) Fairness in repeated matching: a maximin perspective. In Proceedings of the 40th AAAI Conference on Artificial Intelligence (AAAI), p. 17111–17119. Cited by: §1.2, §2. [52] R. Lipton, E. Markakis, E. Mossel, and A. Saberi (2004) On approximately fair allocations of indivisible goods. In Proceedings of the 5th ACM Conference on Electronic Commerce (EC), p. 125–131. Cited by: §0.C.4, §1.1, §1.2, §1, §1, §1, §2, §3, §4, §5. [53] K. J. Micheel and A. Wilczynski (2024) Fairness in repeated house allocation. In Proceedings of the 27th European Conference on Artificial Intelligence (ECAI), p. 3549–3556. Cited by: §1.2. [54] H. Moulin (2003) Fair division and collective welfare. MIT Press. Cited by: §1. [55] R. Murray, C. Kroer, A. Peysakhovich, and P. Shah (2020) Robust market equilibria with uncertain preferences. In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), p. 2192–2199. Cited by: §1. [56] T. Y. Neoh, J. Peters, and N. Teh (2026) Online fair division with additional information. In Proceedings of the 43rd International Conference on Machine Learning (ICML), Cited by: §1.2. [57] T. Y. Neoh and N. Teh (2025) Understanding efx allocations: counting and variants. In Proceedings of the 39th AAAI Conference on Artificial Intelligence (AAAI), p. 14036–14044. Cited by: footnote 4. [58] T. Y. Neoh and N. Teh (2026) Closing gaps in online fair division. Note: arXiv:2609.05310 Cited by: §1.2. [59] T. T. Nguyen and J. Rothe (2014) Minimizing envy and maximizing average Nash social welfare in the allocation of indivisible goods. Discrete Applied Mathematics 179, p. 54–68. Cited by: §1.2, §1. [60] R. Niedermeier (2006) Invitation to Fixed-Parameter Algorithms. Oxford University Press. Cited by: Corollary 1. [61] B. Plaut and T. Roughgarden (2020) Almost envy-freeness with general valuations. SIAM Journal on Discrete Mathematics 34 (2), p. 1039–1068. Cited by: §5, footnote 6. [62] S. Sahni (1976) Algorithms for scheduling independent tasks. Journal of the ACM 23 (1), p. 116–127. Cited by: §4. [63] J. Scarlett, N. Teh, and Y. Zick (2023) For one and all: individual and group fairness in the allocation of indivisible goods. In Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS), p. 2466–2468. Cited by: footnote 6. [64] J. Spencer (1977) Balancing games. Journal of Combinatorial Theory, Series B 23 (1), p. 68–74. Cited by: §1.2. [65] W. Suksompong and N. Teh (2022) On maximum weighted Nash welfare for binary valuations. Mathematical Social Sciences 117, p. 101–108. Cited by: footnote 4. [66] N. Teh, S. Cohen, K. F. Celine, B. Yu, and M. J. Wooldridge (2026) Online house allocation with subsidy. Note: arxiv:2609.29691 Cited by: footnote 6. [67] Y. Wang and T. Wei (2026) Online fair allocations with binary valuations and beyond. In Proceedings of the 40th AAAI Conference on Artificial Intelligence (AAAI), p. 17267–17275. Cited by: footnote 4. Appendix Appendix 0.A Omitted Proofs from Section 3 0.A.1 Proof of Theorem 3.2 We reduce from the Binary-EF problem, which is known to be NP-hard [5, 44]. An instance of Binary-EF is given by a set of agents N^=1,…,n N=\1,…, n\, a set of goods G^=g^1,…,g^m G=\ g_1,…, g_ m\, and a valuation profile ^=(v^1,…,v^n^) v=( v_1,…, v_ n) where agents have additive binary valuations over the set of goods; it is a yes-instance if there exists an allocation A of goods to agents such that A is envy-free, i.e., v^i(A^i)≥v^i(A^j) v_i( A_i)≥ v_i( A_j) for every pair of agents i,j∈N^i,j∈ N, and a no-instance otherwise. Construct an instance of our problem, where N=[n^]N=[ n] and we have m^+m^3 m+ m^3 goods arriving in the order π=(g1,…,gm^+m^3)π=(g_1,…,g_ m+ m^3), with valuations defined as follows: vi(gj)=v^i(g^j) if j∈1,…,m^;0 otherwise.v_i(g_j)= cases v_i( g_j)& if j∈\1,…, m\;\\ 0& otherwise. cases We first show that Temporal-EnvyMin is NP-complete (it is easy to see that the problem is in NP, we thus focus on proving NP-hardness). We do so by proving that there exists an envy-free allocation A for Binary-EF if and only if there exists an allocation A (and hence corresponding allocation sequence S) such that cost(S,π)≤m^3−1 cost(S,π)≤ m^3-1 for the above constructed instance. The zero-valued goods make any envy present after the first m m rounds persist. If the Binary-EF instance is a yes-instance, we allocate the first m m goods according to an envy-free allocation, so all later rounds have zero envy. If it is a no-instance, every allocation has maximum envy at least 11 at round m m, and this remains true while the zero-valued goods arrive. The same idea, with additional zero-valued goods, gives the constant-factor inapproximability result. (⇒ ) Suppose there exists an envy-free allocation A for Binary-EF. Then, consider the sequence S=(s1,…,sm^+m^3)S=(s_1,…,s_ m+ m^3) whereby sj=ℓ if j≤m and g^j∈A^ℓ, for ℓ∈[n^];1 if j>m^.s_j= cases & if j≤ m and g_j∈ A_ , for ∈[ n];\\ 1& if j> m. cases Observe that for each t∈[m^−1]t∈[ m-1],77 7 This is because under binary valuations, at round t, each bundle contains at most t goods and each good is worth at most 11 to any agent. ct(S,π)≤tc_t(S,π)≤ t, and cm^(S,π)=0c_ m(S,π)=0, since A is envy-free, which means under m^A m, there is no envy (and cost is 00). Thus, we also get that for t′∈m^+1,…,m^+m^3t ∈\ m+1,…, m+ m^3\, ct′(S,π)=0c_t (S,π)=0, giving us cost(S,π) cost(S,π) =∑t=1m^+m^2ct(S,π) = _t=1 m+ m^2c_t(S,π) =∑t=1m^−1ct(S,π)+cm^(S,π)+∑t=m^+1m^+m^3ct(S,π) = _t=1 m-1c_t(S,π)+c_ m(S,π)+ _t= m+1 m+ m^3c_t(S,π) ≤∑t=1m^−1ct(S,π)+0+0=m^(m^−1)2. ≤ _t=1 m-1c_t(S,π)+0+0= m( m-1)2. Then, m^(m^−1)2≤m^3−1 m( m-1)2≤ m^3-1 for all m^≥1 m≥ 1. (⇐ ) Suppose there does not exist an envy-free allocation A for Binary-EF. This means that for any sequence S, the allocation induced on the first m m goods is not envy-free, and cm^(S,π)≥1c_ m(S,π)≥ 1. Since the next m^3 m^3 goods gm^+1,…,gm^+m^3g_ m+1,…,g_ m+ m^3 are zero-valued, we have that cm^+1(S,π)=⋯=cm^+m^3(S,π)≥1c_ m+1(S,π)=…=c_ m+ m^3(S,π)≥ 1. Thus, for any sequence S, cost(S,π)≥∑t=m^m^+m^3ct(S,π)≥m^3+1>m^3−1. cost(S,π)≥ _t= m m+ m^3c_t(S,π)≥ m^3+1> m^3-1. Next, we argue that in (the same) setting where agents have binary valuations, there exists no constant-factor approximation algorithm, unless P = NP. Note that in the reduction above, we showed that given an instance ℐI and order π, determining whether we can find an allocation sequence S such that cost(S,π)≤m^3−1 cost(S,π)≤ m^3-1 is NP-complete. Equivalently, • any yes-instance admits a sequence S with cost(S,π)≤m^3−1 cost(S,π)≤ m^3-1; • any no-instance will force any sequence S to have cost(S,π)≥m^3+1 cost(S,π)≥ m^3+1. Observe that for yes-instances, cm^(S,π)=0c_ m(S,π)=0, which means the cost of m^3−1 m^3-1 is incurred at earlier rounds, whereas for no-instances, cm^(S,π)≥1c_ m(S,π)≥ 1. Let B:=mb3−1B:=m_b^3-1 and fix any constant α≥1α≥ 1. We may assume mb≥2m_b≥ 2, so B>0B>0. Append Zα:=⌈B(α−1)⌉+1Z_α:= B(α-1) +1 additional zero-valued goods. If the Binary-EF instance is a yes-instance, the same allocation still has cost at most B. If it is a no-instance, then envy is at least 11 from round mbm_b onward, and therefore it remains at least 11 throughout the appended zero-valued rounds. Thus every no-instance has cost at least mb3+1+Zα>αB.m_b^3+1+Z_α>α B. Thus, running an α-approximation on the constructed Temporal-EnvyMin instance and comparing its returned cost with αBα B would decide the original Binary-EF instance in polynomial time. This is impossible unless P=NP P= NP. Appendix 0.B Omitted Proofs from Section 4 0.B.1 Proof of Proposition 1 Consider the greedy algorithm that, at each round t∈[m]t∈[m], allocates the arriving good to an agent with minimum current bundle value v(Ait−1)v(A_i^t-1). This can be implemented in (mn)O(mn) time. Since valuations are binary and identical, each bundle value v(Ait)v(A_i^t) is an integer that represents the number of goods of value 11 assigned to agent i among the first t arrivals. Let qtq_t be the number of goods of value 11 among the first t goods in π. Under identical valuations, ct(S,π)=maxi,j∈N(v(Ajt)−v(Ait))=maxi∈Nv(Ait)−mini∈Nv(Ait). c_t(S,π)= _i,j∈ N (v(A_j^t)-v(A_i^t) )= _i∈ Nv(A_i^t)- _i∈ Nv(A_i^t). Then, since ∑i∈Nv(Ait)=qt _i∈ Nv(A_i^t)=q_t and all v(Ait)v(A_i^t) are integers, maxi∈Nv(Ait)≥⌈qt/n⌉ and mini∈Nv(Ait)≤⌊qt/n⌋. _i∈ Nv(A_i^t)≥ q_t/n and _i∈ Nv(A_i^t)≤ q_t/n . Thus, for every allocation, ct(S,π)≥⌈qt/n⌉−⌊qt/n⌋,c_t(S,π)≥ q_t/n - q_t/n , which equals 00 if and only if qt≡0(modn)q_t≡ 0 n, and equals 11 otherwise. We claim the greedy algorithm maintains maxi∈Nv(Ait)−mini∈Nv(Ait)≤1 for all t, _i∈ Nv(A_i^t)- _i∈ Nv(A_i^t)≤ 1 for all t, proved by induction on t: initially it is 00. If the arriving good has value 00, bundle values do not change. If it has value 11, the algorithm adds 11 to a minimum bundle value, so the gap cannot increase beyond 11. Thus, ct(S,π)≤1c_t(S,π)≤ 1 always. Moreover, if qt≢0(modn)q_t ≡ 0 n, the bundle values cannot be equal integers summing to qtq_t, so ct(S,π)≠0c_t(S,π)≠ 0 and thus ct(S,π)=1c_t(S,π)=1. If qt≡0(modn)q_t≡ 0 n, the gap ≤1≤ 1 forces equality, giving us ct(S,π)=0c_t(S,π)=0. To see why, if maxi∈Nv(Ait)−mini∈Nv(Ait)≤1 _i∈ Nv(A_i^t)- _i∈ Nv(A_i^t)≤ 1, then all v(Ait)∈mini∈Nv(Ait),mini∈Nv(Ait)+1v(A_i^t)∈\ _i∈ Nv(A_i^t), _i∈ Nv(A_i^t)+1\. Writing r for the number of agents with value mini∈Nv(Ait)+1 _i∈ Nv(A_i^t)+1, we have qt=nmini∈Nv(Ait)+rq_t=n _i∈ Nv(A_i^t)+r. If qt≡0(modn)q_t≡ 0 n, then r≡0(modn)r≡ 0 n, but 0≤r≤n−10≤ r≤ n-1, thus r=0r=0 and all values equal. Thus, the greedy algorithm achieves a per-round lower bound for every t, and summing over t shows that it minimizes ∑t=1mct(S,π) _t=1^mc_t(S,π). 0.B.2 Proof of Theorem 4.2 Fix a constant n≥2n≥ 2, an instance ℐ=(N,G,v)I=(N,G,v) with identical valuation function v, and a fixed arrival order π=(g1,…,gm)π=(g_1,…,g_m). Let OPT:=minS∈costv(S,π) OPT:= _S cost_v(S,π) denote the optimal cumulative maximum envy for this fixed order under v. If v(G)=0v(G)=0, then every bundle has value 00 at every round, so ct(S,π)=0c_t(S,π)=0 for all t and all S. Hence OPT=0OPT=0, and any allocation sequence is optimal. We therefore assume v(G)>0v(G)>0. Set δ:=ε(1−1/n)⋅v(G)m(m+1),δ:= (1-1/n)· v(G)m(m+1), and define a scaled (integer) valuation v~ v by v~(g):=⌊v(g)/δ⌋for each g∈G. v(g):= v(g)/δ each g∈ G. Let ℐ~:=(N,G,v~) I:=(N,G, v) be the scaled instance. Compute an allocation sequence S~ S that optimizes costv~(S,π) cost_ v(S,π) for the instance ℐ~ I and the same order π (e.g., using Algorithm 1 together with Theorem 4.1), and output S~ S for the original instance. For every g∈Gg∈ G, v~(g)≤v(g)δ≤v(G)δ=m(m+1)ε(1−1/n), v(g)≤ v(g)δ≤ v(G)δ= m(m+1) (1-1/n), so V~max:=maxg∈Gv~(g)=(m2/ε) V_max:= _g∈ G v(g)=O(m^2/ ) (for fixed n). By Theorem 4.1, for fixed n, Algorithm 1 runs in time polynomial in m and V~max V_max, hence polynomial in m and 1/ε1/ . Now, we prove the approximation guarantee. For any allocation sequence S and any round t, write xit:=v(Ait)andx~it:=v~(Ait)for each i∈N.x_i^t:=v(A_i^t) x_i^t:= v(A_i^t) each i∈ N. Since δv~(g)≤v(g)<δ(v~(g)+1)δ v(g)≤ v(g)<δ( v(g)+1) for each good g and |Ait|≤t|A_i^t|≤ t (because at most t goods have arrived by round t), we have that for every i∈Ni∈ N and t∈[m]t∈[m], δx~it≤xit<δx~it+tδ.δ\, x_i^t\ ≤\ x_i^t\ <\ δ\, x_i^t+tδ. (1) Define Ut:=maxi∈NxitU_t:= _i∈ Nx_i^t and Lt:=mini∈NxitL_t:= _i∈ Nx_i^t, and similarly U~t:=maxi∈Nx~it U_t:= _i∈ N x_i^t and L~t:=mini∈Nx~it L_t:= _i∈ N x_i^t. Under identical valuations we have ct(S,π)=Ut−Ltandc~t(S,π)=U~t−L~t.c_t(S,π)=U_t-L_t c_t(S,π)= U_t- L_t. From (1), we get Ut≤δU~t+tδU_t≤δ U_t+tδ and Lt≥δL~tL_t≥δ L_t, thus ct(S,π)=Ut−Lt≤δ(U~t−L~t)+tδ=δc~t(S,π)+tδ.c_t(S,π)=U_t-L_t≤δ( U_t- L_t)+tδ=δ c_t(S,π)+tδ. Also Ut≥δU~tU_t≥δ U_t and Lt≤δL~t+tδL_t≤δ L_t+tδ, hence ct(S,π)=Ut−Lt≥δ(U~t−L~t)−tδ=δc~t(S,π)−tδ.c_t(S,π)=U_t-L_t≥δ( U_t- L_t)-tδ=δ c_t(S,π)-tδ. Therefore, for every S, δcostv~(S,π)−δ∑t=1mt δ cost_ v(S,π)-δ _t=1^mt ≤costv(S,π) ≤ cost_v(S,π) ≤δcostv~(S,π)+δ∑t=1mt. ≤δ cost_ v(S,π)+δ _t=1^mt. (2) Since ∑t=1mt=m(m+1)/2 _t=1^mt=m(m+1)/2, (2) becomes δcostv~(S,π)−δm(m+1)2 δ cost_ v(S,π)-δ m(m+1)2 ≤costv(S,π) ≤ cost_v(S,π) ≤δcostv~(S,π)+δm(m+1)2. ≤δ cost_ v(S,π)+δ m(m+1)2. (3) Let S∗S^* be optimal for the original instance (so costv(S∗,π)=OPT cost_v(S^*,π)= OPT). By optimality of S~ S for the scaled instance, costv~(S~,π)≤costv~(S∗,π) cost_ v( S,π)≤ cost_ v(S^*,π). Applying (3) first to S~ S and then to S∗S^* gives us costv(S~,π) cost_v( S,π) ≤δcostv~(S~,π)+δm(m+1)2 ≤δ cost_ v( S,π)+δ m(m+1)2 ≤δcostv~(S∗,π)+δm(m+1)2 ≤δ cost_ v(S^*,π)+δ m(m+1)2 ≤costv(S∗,π)+δm(m+1) ≤ cost_v(S^*,π)+δ m(m+1) =OPT+δm(m+1). = OPT+δ m(m+1). It remains to lower bound OPT in terms of v(G)v(G). Fix any sequence S and define xit,Ut,Ltx_i^t,U_t,L_t as above. If gtg_t is allocated to agent j, then xjt−xjt−1=v(gt)x_j^t-x_j^t-1=v(g_t). Since Ut≥xjtU_t≥ x_j^t and Lt−1≤xjt−1L_t-1≤ x_j^t-1, v(gt)=xjt−xjt−1≤Ut−Lt−1.v(g_t)\ =\ x_j^t-x_j^t-1\ ≤\ U_t-L_t-1. Using Ut=(Ut−Lt)+Lt=ct(S,π)+LtU_t=(U_t-L_t)+L_t=c_t(S,π)+L_t, we get v(gt)≤ct(S,π)+(Lt−Lt−1).v(g_t)≤ c_t(S,π)+(L_t-L_t-1). Summing over t=1,…,mt=1,…,m and using L0=0L_0=0 gives us v(G)=∑t=1mv(gt)≤∑t=1mct(S,π)+Lm=costv(S,π)+Lm.v(G)= _t=1^mv(g_t)≤ _t=1^mc_t(S,π)+L_m= cost_v(S,π)+L_m. Since Lm=mini∈Nv(Aim)≤1n∑i∈Nv(Aim)=v(G)/nL_m= _i∈ Nv(A_i^m)≤ 1n _i∈ Nv(A_i^m)=v(G)/n, it follows that costv(S,π)≥(1−1n)v(G) cost_v(S,π)≥(1- 1n)v(G). Minimizing over S yields OPT≥(1−1n)v(G). OPT≥(1- 1n)\,v(G). (4) Finally, by our choice of δ, δm(m+1)=ε(1−1n)v(G)≤εOPT,δ m(m+1)= (1- 1n)v(G)≤ OPT, where the inequality follows from (4). Consequently, costv(S~,π)≤OPT+εOPT=(1+ε)OPT, cost_v( S,π)≤ OPT+ OPT=(1+ ) OPT, which proves the claimed (1+ε)(1+ )-approximation and completes the proof. Appendix 0.C Omitted Proofs from Section 5 0.C.1 Proof of Theorem 5.1 Membership in NP is easy to see: given π=(g1,…,gm)π=(g_1,…,g_m) and S=(s1,…,sm)S=(s_1,…,s_m), we can compute all partial bundles (Ait)i∈N,t∈[m](A_i^t)_i∈ N,t∈[m] and the values ct(S,π)c_t(S,π) for each t∈[m]t∈[m], and verify whether ∑t=1mct(S,π)≤γ _t=1^mc_t(S,π)≤γ in polynomial time. Thus, we focus on showing NP-hardness. We reduce from the NP-hard Partition problem [35]. An instance of Partition consists of positive integers x1,…,xqx_1,…,x_q with total sum T:=∑i=1qxiT:= _i=1^qx_i; we may assume T is even (otherwise it is a trivial no-instance). We construct an instance ℐ=(N,G,)I=(N,G,v) of Temporal-EnvyMin-Seq with N=1,2N=\1,2\ and identical additive valuations (so v1=v2=v_1=v_2=v). Let M:=T+1M:=T+1. Create 2q2q goods (thus the number of goods is m=|G|=2qm=|G|=2q), consisting of pairs (ai,bi)(a_i,b_i) for each i∈[q]i∈[q], where v(ai)=Mandv(bi)=M+xi.v(a_i)=M v(b_i)=M+x_i. Then the total value is v(G)=∑i=1q(v(ai)+v(bi))=∑i=1q(2M+xi)=2qM+T,v(G)= _i=1^q(v(a_i)+v(b_i))= _i=1^q(2M+x_i)=2qM+T, and let γ:=v(G)2=qM+T2,γ:= v(G)2=qM+ T2, which is an integer since T is even. We will use the following fact, which holds for every order π and sequence S in this constructed instance. Since n=2n=2 and valuations are identical, for every t∈[m]t∈[m] we have ct(S,π)=|v(A1t)−v(A2t)|.c_t(S,π)=|v(A_1^t)-v(A_2^t)|. Define Dt:=v(A1t)−v(A2t)D_t:=v(A_1^t)-v(A_2^t), so ct(S,π)=|Dt|c_t(S,π)=|D_t|. For each t≥2t≥ 2, the t-th arriving good gtg_t is allocated to exactly one agent, so Dt=Dt−1±v(gt)D_t=D_t-1± v(g_t) and therefore |Dt−Dt−1|=v(gt)|D_t-D_t-1|=v(g_t). By the triangle inequality, we have that v(gt)=|Dt−Dt−1|≤|Dt|+|Dt−1|=ct(S,π)+ct−1(S,π)v(g_t)=|D_t-D_t-1|≤|D_t|+|D_t-1|=c_t(S,π)+c_t-1(S,π) (5) for all t≥2t≥ 2. Summing (5) over t=2,…,mt=2,…,m we get ∑t=2m(ct−1(S,π)+ct(S,π))≥∑t=2mv(gt)=v(G)−v(g1). _t=2^m(c_t-1(S,π)+c_t(S,π))≥ _t=2^mv(g_t)=v(G)-v(g_1). The left-hand side equals c1(S,π)+cm(S,π)+2∑t=2m−1ct(S,π)=2∑t=1mct(S,π)−c1(S,π)−cm(S,π)c_1(S,π)+c_m(S,π)+2 _t=2^m-1c_t(S,π)=2 _t=1^mc_t(S,π)-c_1(S,π)-c_m(S,π), so 2cost(S,π)−c1(S,π)−cm(S,π)≥v(G)−v(g1).2 cost(S,π)-c_1(S,π)-c_m(S,π)≥ v(G)-v(g_1). Moreover, after the first good arrives exactly one agent has received g1g_1 and the other has an empty bundle, thus c1(S,π)=v(g1)c_1(S,π)=v(g_1). Substituting gives us 2cost(S,π)−cm(S,π)≥v(G).2 cost(S,π)-c_m(S,π)≥ v(G). Since cm(S,π)≥0c_m(S,π)≥ 0, we conclude that for every (S,π)(S,π), cost(S,π)≥v(G)2=γ. cost(S,π)≥ v(G)2=γ. (6) We now prove correctness of the reduction. (⇒ ) Suppose the Partition instance is a yes-instance, so there exists P⊆[q]P [q] with ∑i∈Pxi=T/2 _i∈ Px_i=T/2. We define a permutation π of the 2q2q goods by listing the goods in q consecutive pairs as follows: • for each i∈Pi∈ P, place the pair (ai,bi)(a_i,b_i) in π, • for each i∉Pi∉ P, place the pair (bi,ai)(b_i,a_i) in π, with all pairs corresponding to indices i∈Pi∈ P appearing first (in arbitrary order among themselves), followed by all pairs corresponding to indices i∉Pi∉ P (in arbitrary order among themselves). Next define an allocation sequence S by the greedy rule: at each round t, allocate gtg_t to an agent in argmini∈[2]v(Ait−1) _i∈[2]v(A_i^t-1) (break ties arbitrarily). We analyze the contribution of each consecutive pair to the total cost. Fix a pair and let d be the absolute difference |v(A1t−1)−v(A2t−1)||v(A_1^t-1)-v(A_2^t-1)| immediately before the first good of the pair is allocated. We first consider pairs (ai,bi)(a_i,b_i) with i∈Pi∈ P. During this part of the sequence, the difference d is the sum of the x-values of some already-processed indices in P, hence d≤∑i∈Pxi=T/2<Md≤ _i∈ Px_i=T/2<M. Assume w.l.o.g. that v(A1t−1)≤v(A2t−1)v(A_1^t-1)≤ v(A_2^t-1), so v(A2t−1)−v(A1t−1)=dv(A_2^t-1)-v(A_1^t-1)=d. The greedy rule gives aia_i to agent 1, so the new difference is M−dM-d and the incurred cost at that round is M−dM-d. Now agent 2 has the smaller bundle, so bib_i is given to agent 2; the new difference becomes (M+xi)−(M−d)=d+xi,(M+x_i)-(M-d)=d+x_i, and the cost at the next round is d+xid+x_i. Therefore, this pair contributes (M−d)+(d+xi)=M+xi(M-d)+(d+x_i)=M+x_i to cost(S,π) cost(S,π), and the absolute difference after the pair increases by xix_i. After all i∈Pi∈ P are processed, the absolute difference equals ∑i∈Pxi=T/2 _i∈ Px_i=T/2. Next, we consider pairs (bi,ai)(b_i,a_i) with i∉Pi∉ P. At the start of this part, the difference is T/2T/2, and we maintain the invariant that after processing some subset Q⊆([q]∖P)Q ([q] P), the current absolute difference is ∑i∈([q]∖P)∖Qxi _i∈([q] P) Qx_i. In particular, before processing any remaining i∉Pi∉ P, we have d≥xid≥ x_i. Again assume w.l.o.g. that agent 1 has the smaller bundle before the pair, so agent 2 is ahead by d. The greedy rule assigns bib_i to agent 1. Since M+xi>dM+x_i>d, the new difference is (M+xi)−d(M+x_i)-d and the cost at that round is M+xi−dM+x_i-d. Then the greedy rule assigns aia_i to agent 2, and the new difference becomes |(M+xi−d)−M|=|xi−d|=d−xi, |(M+x_i-d)-M |=|x_i-d|=d-x_i, using d≥xid≥ x_i. The pair therefore contributes (M+xi−d)+(d−xi)=M(M+x_i-d)+(d-x_i)=M to cost(S,π) cost(S,π) and decreases the absolute difference by xix_i, preserving the invariant. After all i∉Pi∉ P are processed, the absolute difference returns to 00. Summing contributions over all q pairs, cost(S,π) cost(S,π) =∑i∈P(M+xi)+∑i∉PM = _i∈ P(M+x_i)+ _i∉ PM =qM+∑i∈Pxi=qM+T2=γ. =qM+ _i∈ Px_i=qM+ T2=γ. Thus, there exists (S,π)(S,π) with cost(S,π)≤γ cost(S,π)≤γ. (⇐ ) Conversely, suppose there exist π and S with cost(S,π)≤γ cost(S,π)≤γ. By (6), we must have cost(S,π)=γ=v(G)/2 cost(S,π)=γ=v(G)/2. From 2cost(S,π)−cm(S,π)≥v(G)2 cost(S,π)-c_m(S,π)≥ v(G) and cost(S,π)=v(G)/2 cost(S,π)=v(G)/2, we get cm(S,π)=0c_m(S,π)=0. Also, define for each t≥2t≥ 2 the slack δt:=(ct−1(S,π)+ct(S,π))−v(gt)≥0 _t:= (c_t-1(S,π)+c_t(S,π) )-v(g_t)≥ 0 from (5). Since equality holds in the summed inequality, we must have ∑t=2mδt=0 _t=2^m _t=0, and therefore δt=0 _t=0 for every t≥2t≥ 2, i.e., for all t=2,…,mt=2,…,m, ct−1(S,π)+ct(S,π)=v(gt).c_t-1(S,π)+c_t(S,π)=v(g_t). (7) Rearranging gives us ct(S,π)=v(gt)−ct−1(S,π)c_t(S,π)=v(g_t)-c_t-1(S,π) for all t≥2t≥ 2, and unrolling this recurrence, we get cm(S,π) c_m(S,π) =v(gm)−v(gm−1)+v(gm−2)−⋯+(−1)m−1v(g1). =v(g_m)-v(g_m-1)+v(g_m-2)-·s+(-1)^m-1v(g_1). Since m=2qm=2q is even and cm(S,π)=0c_m(S,π)=0, we get ∑t∈[m],t is evenv(gt)=∑t∈[m],t is oddv(gt). _t∈[m],t is evenv(g_t)= _t∈[m],t is oddv(g_t). Every good in G has value either M or M+xiM+x_i. Write v(gt)=M+ytv(g_t)=M+y_t, where yt∈0,x1,…,xqy_t∈\0,x_1,…,x_q\ and each xix_i appears exactly once among the yty_t’s (coming from the unique good bib_i of value M+xiM+x_i). Since there are exactly q even positions and q odd positions, the M-terms cancel, giving us ∑t∈[m],t is evenyt=∑t∈[m],t is oddyt. _t∈[m],t is eveny_t= _t∈[m],t is oddy_t. Because ∑t=1myt=∑i=1qxi=T _t=1^my_t= _i=1^qx_i=T, each side must equal T/2T/2. Let P⊆[q]P [q] be the set of indices i such that the good bib_i (the unique good of value M+xiM+x_i) appears in an even position of π. Then ∑i∈Pxi=∑t∈[m],t is evenyt=T2, _i∈ Px_i= _t∈[m],t is eveny_t= T2, so the original Partition instance is a yes-instance. This completes the reduction, and proves our result. 0.C.2 Proof of Lemma 1 Fix any arrival order π=(g1,…,gm)π=(g_1,…,g_m) and allocation sequence S. For each t∈0,1,…,mt∈\0,1,…,m\ define xit:=v(Ait),Lt:=mini∈Nxit,Ut:=maxi∈Nxit.x_i^t:=v(A_i^t), L_t:= _i∈ Nx_i^t, U_t:= _i∈ Nx_i^t. Under identical valuations, ct(S,π)=maxi,j∈Nmax0,xjt−xit=Ut−Lt.c_t(S,π)= _i,j∈ N \0,x_j^t-x_i^t\=U_t-L_t. Now fix any t∈1,…,mt∈\1,…,m\ and let j be the agent who receives gtg_t. By additivity, xjt−xjt−1=v(gt)x_j^t-x_j^t-1=v(g_t). Since Ut≥xjtU_t≥ x_j^t and Lt−1≤xjt−1L_t-1≤ x_j^t-1, we have v(gt)=xjt−xjt−1≤Ut−Lt−1.v(g_t)=x_j^t-x_j^t-1\ ≤\ U_t-L_t-1. Using Ut=(Ut−Lt)+Lt=ct(S,π)+LtU_t=(U_t-L_t)+L_t=c_t(S,π)+L_t, this becomes v(gt)≤ct(S,π)+(Lt−Lt−1).v(g_t)\ ≤\ c_t(S,π)+(L_t-L_t-1). Summing over t=1,…,mt=1,…,m and using L0=miniv(Ai0)=v(∅)=0L_0= _iv(A_i^0)=v( )=0, we get v(G)=∑t=1mv(gt) v(G)= _t=1^mv(g_t) ≤∑t=1mct(S,π)+∑t=1m(Lt−Lt−1) ≤ _t=1^mc_t(S,π)+ _t=1^m(L_t-L_t-1) =cost(S,π)+Lm. = cost(S,π)+L_m. Rearranging gives us cost(S,π)≥v(G)−Lm=v(G)−miniv(Aim). cost(S,π)≥ v(G)-L_m=v(G)- _iv(A_i^m). Finally, miniv(Aim)≤1n∑i∈Nv(Aim)=v(G)n, _iv(A_i^m)≤ 1n _i∈ Nv(A_i^m)= v(G)n, so cost(S,π)≥(1−1n)v(G) cost(S,π)≥(1- 1n)v(G). Taking a minimum over (S,π)(S,π) gives us the same bound for OPT(ℐ) OPT(I). Next, we prove the factor 1−1/n1-1/n is tight. For any k≥1k≥ 1, take m=knm=kn goods each with value 11, so v(G)=knv(G)=kn. Consider the round-robin allocation (one good per agent each cycle). At every round t that is not a multiple of n, the bundle values differ by exactly 11, so ct=1c_t=1; at rounds t that are multiples of n, all bundle values are equal and ct=0c_t=0. Thus cost(S,π)=kn−k=k(n−1)=(1−1n)⋅v(G) cost(S,π)=kn-k=k(n-1)=(1- 1n)· v(G), matching the lower bound. 0.C.3 Proof of Theorem 5.2 Consider any instance ℐ=(N,G,)I=(N,G,v) where N=1,2N=\1,2\ and agents have identical valuations. Let S=(s1,…,sm)S=(s_1,…,s_m) be the allocation sequence induced from the order π and allocation A returned by the algorithm. Also consider any t∈2,…,mt∈\2,…,m\. Suppose, without loss of generality, that v(A1t−1)≤v(A2t−1)v(A_1^t-1)≤ v(A_2^t-1). Then, ct−1(S,π)=v(A2t−1)−v(A1t−1).c_t-1(S,π)=v(A_2^t-1)-v(A_1^t-1). We first prove the following claim. Claim. Under Algorithm 2 with n=2n=2 and goods ordered so that v(g1)≤⋯≤v(gm)v(g_1)≤…≤ v(g_m), we have ct−1(S,π)≤v(gt)c_t-1(S,π)≤ v(g_t) for every t≥2t≥ 2. Thus, after allocating gtg_t to the agent with the smaller current bundle value, that agent becomes (weakly) the one with a larger bundle value, and therefore ct(S,π)=v(gt)−ct−1(S,π)c_t(S,π)=v(g_t)-c_t-1(S,π) (equivalently, ct(S,π)+ct−1(S,π)=v(gt)c_t(S,π)+c_t-1(S,π)=v(g_t). Proof (Proof of Claim) We prove this claim by induction. For the base case: c1(S,π)=v(g1)≤v(g2)c_1(S,π)=v(g_1)≤ v(g_2), so c1(S,π)≤v(g2)c_1(S,π)≤ v(g_2). For the inductive step: assume ct−1(S,π)≤v(gt)c_t-1(S,π)≤ v(g_t). Then, after allocating gtg_t to the agent with the smaller bundle, ct(S,π)=v(gt)−ct−1(S,π)c_t(S,π)=v(g_t)-c_t-1(S,π). In particular, ct(S,π)≤v(gt)≤v(gt+1)c_t(S,π)≤ v(g_t)≤ v(g_t+1). Thus, ct(S,π)≤v(gt+1)c_t(S,π)≤ v(g_t+1), i.e., ct(S,π)≤v(gt+1)c_t(S,π)≤ v(g_t+1). Thus, Algorithm 2 will allocate gtg_t to agent 11, giving us A1t=A1t−1∪gtandA2t=A2t−1.A_1^t=A_1^t-1∪\g_t\ A_2^t=A_2^t-1. Then, we get that ct(S,π)=v(A1t)−v(A2t) c_t(S,π)=v(A_1^t)-v(A_2^t) =v(A1t−1)+v(gt)−v(A2t−1) =v(A_1^t-1)+v(g_t)-v(A_2^t-1) =−ct−1(S,π)+v(gt). =-c_t-1(S,π)+v(g_t). Thus, for all t∈2,…,mt∈\2,…,m\, ct(S,π)+ct−1(S,π)=v(gt).c_t(S,π)+c_t-1(S,π)=v(g_t). Together with the fact that c1(S,π)=v(g1)c_1(S,π)=v(g_1), we get v(G) v(G) =v(g1)+∑t=2mv(gt) =v(g_1)+ _t=2^mv(g_t) =c1(S,π)+∑t=2m(ct(S,π)+ct−1(S,π)) =c_1(S,π)+ _t=2^m (c_t(S,π)+c_t-1(S,π) ) =cm(S,π)+2⋅∑t=1m−1ct(S,π). =c_m(S,π)+2· _t=1^m-1c_t(S,π). Algebraic manipulation gives us v(G)+cm(S,π)2=∑t=1mct(S,π)=cost(S,π). v(G)+c_m(S,π)2= _t=1^mc_t(S,π)= cost(S,π). From Lemma 1, we know that OPT(ℐ)≥12⋅v(G). OPT(I)≥ 12· v(G). If cm(S,π)≤v(G)2c_m(S,π)≤ v(G)2, then cost(S,π)OPT(ℐ) cost(S,π) OPT(I) ≤(v(G)+cm(S,π))/2v(G)/2 ≤ (v(G)+c_m(S,π) )/2v(G)/2 ≤v(G)+v(G)/2v(G)=32. ≤ v(G)+v(G)/2v(G)= 32. If cm(S,π)>v(G)2c_m(S,π)> v(G)2, then given that OPT(ℐ)≥v(gm)≥cm(S,π) OPT(I)≥ v(g_m)≥ c_m(S,π), we have OPT(ℐ)≥v(gm)≥cm(S,π). OPT(I)≥ v(g_m)≥ c_m(S,π). To see why OPT(ℐ)≥v(gm) OPT(I)≥ v(g_m): For any order π and sequence S, let gτg_τ be a maximum-valued item (so OPENv(gτ)=Vmax=v(gm))v(g_τ)=V_max=v(g_m)). If τ=1τ=1 then cost(S,π)≥c1=Vmax cost(S,π)≥ c_1=V_max. If τ≥2τ≥ 2, then by the inequality cτ−1+cτ≥v(gτ)c_τ-1+c_τ≥ v(g_τ),88 8 To see this inequality, let Dt−1=v(A1t−1)−v(A2t−1)D_t-1=v(A^t-1_1)-v(A^t-1_2). After item gtg_t is allocated, Dt=Dt−1±v(gt)D_t=D_t-1± v(g_t). Thus, ct−1(S,π)+ct(S,π)=|Dt−1|+|Dt|≥|Dt−Dt−1|=v(gt)c_t-1(S,π)+c_t(S,π)=|D_t-1|+|D_t|≥|D_t-D_t-1|=v(g_t). we get cost(S,π)≥cτ−1+cτ≥Vmax cost(S,π)≥ c_τ-1+c_τ≥ V_max. Thus, OPT(ℐ)≥Vmax=v(gm) OPT(I)≥ V_max=v(g_m). Using this, we obtain cost(S,π)OPT(ℐ) cost(S,π) OPT(I) =(v(G)+cm(S,π))/2OPT(ℐ) = (v(G)+c_m(S,π))/2 OPT(I) ≤(v(G)+cm(S,π))/2cm(S,π) ≤ (v(G)+c_m(S,π))/2c_m(S,π) =12(v(G)cm(S,π)+1) = 12 ( v(G)c_m(S,π)+1 ) <12(2+1)=32, < 12(2+1)= 32, where the strict inequality follows from the fact that cm(S,π)>v(G)/2⟹v(G)/cm(S,π)<2c_m(S,π)>v(G)/2 v(G)/c_m(S,π)<2. Thus, in both cases, we get that cost(S,π)≤32⋅OPT(ℐ), cost(S,π)≤ 32· OPT(I), as desired. 0.C.4 Proof of Theorem 5.3 Consider any instance ℐ=(N,G,)I=(N,G,v) in which agents have identical valuations. Let π=(g1,…,gm)π=(g_1,…,g_m) be the order produced by Algorithm 2 (i.e., the goods are labeled so that v(g1)≤⋯≤v(gm)v(g_1)≤·s≤ v(g_m)), and let S=(s1,…,sm)S=(s_1,…,s_m) be the allocation sequence induced by Algorithm 2 on this order. For each t∈[m]t∈[m] and i∈Ni∈ N, let AitA_i^t denote agent i’s bundle after the first t goods of π have been allocated. For each t∈[m]t∈[m], define Ut:=maxi∈Nv(Ait) and Lt:=mini∈Nv(Ait).U_t:= _i∈ Nv(A_i^t) and L_t:= _i∈ Nv(A_i^t). Since valuations are identical, for every t∈[m]t∈[m] we have ct(S,π)=maxi,j∈Nmax0,v(Ajt)−v(Ait)=Ut−Lt.c_t(S,π)= _i,j∈ N \0,\,v(A_j^t)-v(A_i^t)\=U_t-L_t. Indeed, for any i,j∈Ni,j∈ N, v(Ajt)−v(Ait)≤Ut−Ltv(A_j^t)-v(A_i^t)≤ U_t-L_t, and equality is achieved by choosing j∈argmaxℓ∈Nv(Aℓt)j∈ _ ∈ Nv(A_ ^t) and i∈argminℓ∈Nv(Aℓt)i∈ _ ∈ Nv(A_ ^t). We now prove that ct(S,π)≤v(gt) for all t∈[m],c_t(S,π)≤ v(g_t) for all t∈[m], by induction on t (this is the bound of envy-cycle elimination [52] applied to the first t goods; we include a proof for completeness). Base case (t=1t=1). After allocating g1g_1, some agent has value v(g1)v(g_1), and since n≥2n≥ 2, at least one agent has value 00. Thus, U1=v(g1)U_1=v(g_1) and L1=0L_1=0. Therefore, c1(S,π)=U1−L1=v(g1).c_1(S,π)=U_1-L_1=v(g_1). Inductive step. Fix t∈2,…,mt∈\2,…,m\ and assume ct−1(S,π)≤v(gt−1)c_t-1(S,π)≤ v(g_t-1). Since Algorithm 2 sorts goods by nondecreasing value, v(gt−1)≤v(gt)v(g_t-1)≤ v(g_t), and thus Ut−1−Lt−1=ct−1(S,π)≤v(gt),U_t-1-L_t-1=c_t-1(S,π)≤ v(g_t), which implies Ut−1≤Lt−1+v(gt).U_t-1≤ L_t-1+v(g_t). Algorithm 2 allocates gtg_t to some agent j∈argmini∈Nv(Ait−1)j∈ _i∈ Nv(A_i^t-1), so v(Ajt−1)=Lt−1v(A_j^t-1)=L_t-1. After allocating gtg_t we have v(Ajt)=v(Ajt−1)+v(gt)=Lt−1+v(gt),v(A_j^t)=v(A_j^t-1)+v(g_t)=L_t-1+v(g_t), and for every i≠ji≠ j, v(Ait)=v(Ait−1)≥Lt−1v(A_i^t)=v(A_i^t-1)≥ L_t-1. Thus, Lt=mini∈Nv(Ait)≥Lt−1.L_t= _i∈ Nv(A_i^t)≥ L_t-1. Moreover, since v(Ajt)=Lt−1+v(gt)≥Ut−1v(A_j^t)=L_t-1+v(g_t)≥ U_t-1 and all other bundle values remain unchanged (and are therefore at most Ut−1U_t-1), we have Ut=maxi∈Nv(Ait)=v(Ajt).U_t= _i∈ Nv(A_i^t)=v(A_j^t). Therefore, ct(S,π)=Ut−Lt=v(Ajt)−Lt c_t(S,π)=U_t-L_t=v(A_j^t)-L_t =Lt−1+v(gt)−Lt =L_t-1+v(g_t)-L_t ≤v(gt), ≤ v(g_t), where the last inequality follows from the fact that Lt≥Lt−1L_t≥ L_t-1. This completes the induction. Summing the per-round bound gives us cost(S,π)=∑t=1mct(S,π)≤∑t=1mv(gt)=v(G), cost(S,π)= _t=1^mc_t(S,π)≤ _t=1^mv(g_t)=v(G), since π is a permutation of G. By Lemma 1, OPT(ℐ)≥(1−1/n)v(G) OPT(I)≥(1-1/n)\,v(G), and therefore cost(S,π)OPT(ℐ)≤v(G)(1−1/n)v(G)=n−1. cost(S,π) OPT(I)≤ v(G)(1-1/n)\,v(G)= nn-1. so Algorithm 2 is a n/(n−1)n/(n-1)-approximation. 0.C.5 Tightness of Identical-Lowest-First Analysis for n=2n=2. We provide an example for which the Identical-Lowest-First algorithm has an approximation ratio of 3/23/2 for n=2n=2 Example 3 Consider an instance with n=2n=2 and m=3m=3 where agents have identical valuations and the multiset of good values is 1,1,2\1,1,2\. • Identical-Lowest-First (Algorithm 2): Sorting gives the order π=(1,1,2)π=(1,1,2). Using the algorithm with its stated tie-breaking rule (lowest-index agent), the induced allocation sequence is S=(1,2,1)S=(1,2,1), which gives us c1(S,π)=1,c2(S,π)=0,c3(S,π)=2c_1(S,π)=1,c_2(S,π)=0,c_3(S,π)=2, and cost(S,π)=3 cost(S,π)=3. • Optimal: Let the order be π′=(1,2,1)π =(1,2,1) and allocate according to S′=(1,2,1)S =(1,2,1). Then, c1(S′,π′)=1,c2(S′,π′)=1,c3(S′,π′)=0c_1(S ,π )=1,c_2(S ,π )=1,c_3(S ,π )=0, and so cost(S′,π′)=2 cost(S ,π )=2. By Lemma 1 (with n=2n=2), OPT(ℐ)≥(1−12)v(G)=2 OPT(I)≥(1- 12)\,v(G)=2, so this is optimal. Therefore, on this instance Algorithm 2 has approximation ratio 3/23/2, matching the bound in Theorem 5.2. 0.C.6 Approximation Ratio Lower Bound of 2n−12n−2 2n-12n-2 for n≥3n≥ 3. We provide an example for which the Identical-Lowest-First algorithm has an approximation ratio of 2n−12n−2 2n-12n-2 for n≥3n≥ 3. Example 4 Fix any n≥3n≥ 3. Consider an instance with identical valuation function v and m=n+1m=n+1 goods. Let two goods have value 11 and n−1n-1 goods have value 22. Thus, we have that v(G)=2nv(G)=2n. • Identical-Lowest-First (Algorithm 2): Sorting gives the order π=(1,1,2,2,…,2)π=(1,1,2,2,…,2). Using the algorithm with its stated tie-breaking rule (lowest-index agent), after allocating the first two goods of value 11, we have bundle values (1,1,0,…,0)(1,1,0,…,0). Then the next n−2n-2 goods each of value 22 are allocated one by one to agents 3,4,…,n3,4,…,n, giving us bundle values (1,1,2,…,2)(1,1,2,…,2) after round n; the final 22 is then allocated to agent 11, giving us (3,1,2,…,2)(3,1,2,…,2) after round n+1n+1. Let S be the induced allocation sequence. Under identical valuations, the per-round cost is the gap between the maximum and minimum bundle values. Thus the maximum envy values are c1(S,π)=1c_1(S,π)=1, c2(S,π)=1c_2(S,π)=1, ct(S,π)=2c_t(S,π)=2 (for t=3,…,n−1t=3,…,n-1, cn=1c_n=1), and cn+1(S,π)=2c_n+1(S,π)=2. Therefore, cost(S,π) cost(S,π) =∑t=1n+1ct(S,π) = _t=1^n+1c_t(S,π) =1+1+2(n−3)+1+2=2n−1. =1+1+2(n-3)+1+2=2n-1. • Optimal solution. Consider the arrival order π∗=(1,2,2,…,2,1)π^*=(1,2,2,…,2,1), and allocate the first and last value 11 goods to agent 11, while allocating the n−1n-1 value 22 goods to agents 2,3,…,n2,3,…,n (one each). Denote the resulting allocation sequence by S∗S^*. Then the per-round maximum envy values are c1(S∗,π∗)=1c_1(S^*,π^*)=1, ct(S∗,π∗)=2c_t(S^*,π^*)=2 for t=2,…,n−1t=2,…,n-1, cn(S∗,π∗)=1c_n(S^*,π^*)=1, cn+1(S∗,π∗)=0c_n+1(S^*,π^*)=0. Consequently, cost(S∗,π∗)=1+2(n−2)+1+0=2n−2 cost(S^*,π^*)=1+2(n-2)+1+0=2n-2. By Lemma 1, OPT(ℐ)≥(1−1n)v(G)=(1−1n)⋅2n=2n−2 OPT(I)≥(1- 1n)\,v(G)=(1- 1n)· 2n=2n-2, giving us OPT(ℐ)=2n−2 OPT(I)=2n-2. Thus, on this instance, Algorithm 2 has approximation ratio cost(S,π)OPT(ℐ)=2n−12n−2. cost(S,π) OPT(I)= 2n-12n-2. 0.C.7 Proof of Theorem 5.4 Fix an instance ℐ=(N,G,v)I=(N,G,v) with identical valuations, where n≥2n≥ 2. Let Algorithm 2 order the goods as π=(g1,…,gm)π=(g_1,…,g_m) with v(g1)≤⋯≤v(gm)v(g_1)≤·s≤ v(g_m), and let S be the induced allocation sequence. For each t∈0,1,…,mt∈\0,1,…,m\ define Lt:=mini∈Nv(Ait)andUt:=maxi∈Nv(Ait)L_t:= _i∈ Nv(A_i^t) U_t:= _i∈ Nv(A_i^t) where AitA_i^t denotes agent i’s bundle after round t (and L0=U0=0L_0=U_0=0). Under identical valuations, ct(S,π)=Ut−Ltc_t(S,π)=U_t-L_t. We claim that ct(S,π)≤v(gt)c_t(S,π)≤ v(g_t) for all t∈[m]t∈[m]. For t=1t=1, after allocating g1g_1 we have U1=v(g1)U_1=v(g_1) and L1=0L_1=0 (since n≥2n≥ 2 means some agent is still empty after round 11), thus, c1(S,π)=v(g1)c_1(S,π)=v(g_1). Now fix t≥2t≥ 2 and assume inductively that ct−1(S,π)≤v(gt−1)c_t-1(S,π)≤ v(g_t-1). Since the goods are sorted, v(gt−1)≤v(gt)v(g_t-1)≤ v(g_t), so ct−1(S,π)≤v(gt)c_t-1(S,π)≤ v(g_t). Algorithm 2 allocates gtg_t to an agent j with minimum bundle value at time t−1t-1, i.e., v(Ajt−1)=Lt−1v(A_j^t-1)=L_t-1. After allocation, v(Ajt)=Lt−1+v(gt)≥Lt−1+ct−1(S,π)=Ut−1,v(A_j^t)=L_t-1+v(g_t)≥\ L_t-1+c_t-1(S,π)=\ U_t-1, so j becomes a (weak) maximizer and therefore Ut=Lt−1+v(gt)U_t=L_t-1+v(g_t). Also Lt≥Lt−1L_t≥ L_t-1. Thus ct(S,π)=Ut−Lt=(Lt−1+v(gt))−Lt≤v(gt),c_t(S,π)=U_t-L_t=(L_t-1+v(g_t))-L_t≤ v(g_t), proving the claim. In particular, cm(S,π)≤v(gm)=Vmaxc_m(S,π)≤ v(g_m)=V_max. From Ut=Lt−1+v(gt)U_t=L_t-1+v(g_t) we have, for every t∈[m]t∈[m], ct(S,π)=Ut−Lt=(Lt−1+v(gt))−Ltc_t(S,π)=U_t-L_t=(L_t-1+v(g_t))-L_t; equivalently, v(gt)=ct(S,π)+(Lt−Lt−1)v(g_t)=c_t(S,π)+(L_t-L_t-1). Summing over t=1,…,mt=1,…,m gives us v(G)=∑t=1mv(gt) v(G)= _t=1^mv(g_t) =∑t=1mct(S,π)+∑t=1m(Lt−Lt−1) = _t=1^mc_t(S,π)+ _t=1^m(L_t-L_t-1) =cost(S,π)+Lm, = cost(S,π)+L_m, and thus cost(S,π)=v(G)−Lm. cost(S,π)=v(G)-L_m. (8) Let i∗∈argmini∈Nv(Aim)i^*∈ _i∈ Nv(A_i^m), so v(Ai∗m)=Lmv(A_i^*^m)=L_m, while every other bundle is ≤Lm+cm≤ L_m+c_m. Thus, v(G)=∑i∈Nv(Aim) v(G)= _i∈ Nv(A_i^m) ≤Lm+(n−1)(Lm+cm) ≤ L_m+(n-1)(L_m+c_m) =nLm+(n−1)cm. =nL_m+(n-1)c_m. Rearranging, we get Lm≥v(G)−(n−1)cmn.L_m≥ v(G)-(n-1)c_mn. Plugging this into (8) gives us cost(S,π)=v(G)−Lm cost(S,π)=v(G)-L_m ≤v(G)−v(G)−(n−1)cmn ≤ v(G)- v(G)-(n-1)c_mn =(1−1n)v(G)+(1−1n)cm. = (1- 1n )v(G)+ (1- 1n )c_m. Using cm≤Vmaxc_m≤ V_max, we get cost(S,π)≤(1−1n)v(G)+(1−1n)Vmax. cost(S,π)≤ (1- 1n )v(G)+ (1- 1n )V_max. By Lemma 1, OPT(ℐ)≥(1−1n)v(G) OPT(I)≥ (1- 1n )v(G). Therefore, cost(S,π)≤OPT(ℐ)+(1−1n)Vmax, cost(S,π)≤ OPT(I)+ (1- 1n )V_max, which completes the proof. 0.C.8 Tightness of the Additive Approximation Guarantee. We provide an example showing that the additive error term in Theorem 5.4 is tight. Example 5 Fix any n≥2n≥ 2. Consider an instance with identical valuation function v and the following multiset of good values: for each k∈1,…,n−1k∈\1,…,n-1\ there are exactly n goods of value k, and there are n−1n-1 goods of value n. Thus Vmax=nV_max=n, the number of goods is m=n(n−1)+(n−1)=n2−1m=n(n-1)+(n-1)=n^2-1, and v(G)=n∑k=1n−1k+(n−1)⋅n v(G)=n _k=1^n-1k+(n-1)· n =n⋅n(n−1)2+n(n−1) =n· n(n-1)2+n(n-1) =n(n−1)(n+2)2. = n(n-1)(n+2)2. • Identical-Lowest-First (Algorithm 2) Sorting gives the order π=(1,…,1⏟n,2,…,2⏟n,…,n−1,…,n−1⏟n,n,…,n⏟n−1).π=( 1,…,1_n, 2,…,2_n,…, n-1,…,n-1_n, n,…,n_n-1). For each k∈1,…,n−1k∈\1,…,n-1\, when the n goods of value k arrive, all bundle values are equal at the start of this block, so the greedy rule gives one such good to each agent. Thus, during this block, the gap (maximum minus minimum bundle value) is ct(S,π)=kc_t(S,π)=k for the first n−1n-1 arrivals and ct(S,π)=0c_t(S,π)=0 on the n-th, contributing (n−1)k(n-1)k to the cumulative cost. After the first n(n−1)n(n-1) arrivals, every agent has value ∑k=1n−1k=n(n−1)2. _k=1^n-1k= n(n-1)2. The remaining n−1n-1 goods (each of value n) are then given to n−1n-1 distinct agents; after each such round, the gap is exactly n. Therefore, cost(S,π) cost(S,π) =∑k=1n−1(n−1)k+(n−1)⋅n = _k=1^n-1(n-1)k+(n-1)· n =(n−1)(∑k=1n−1k+n) =(n-1) ( _k=1^n-1k+n ) =(n−1)(n(n−1)2+n) =(n-1) ( n(n-1)2+n ) =n(n−1)(n+1)2. = n(n-1)(n+1)2. • Optimal solution. We show a pair (S∗,π∗)(S^*,π^*) that achieves the universal lower bound of Lemma 1. Define an arrival order π∗π^* in (n−1)(n-1) blocks as follows: for each k=n−1,n−2,…,1k=n-1,n-2,…,1, append the block π∗=(k,(k+1),(k+1),…,(k+1)⏟k times,k,k,…,k⏟(n−k) times).π^*=(k,\; (k+1),(k+1),…,(k+1)_k times,\; k,k,…,k_(n-k) times). Note that for each k≤n−1k≤ n-1, value k appears n−k+1n-k+1 times in block k (once at the start, and n−kn-k times at the end), and appears k−1k-1 times in block k−1k-1. Thus, the total number of times value k appears is (n−k+1)+(k−1)=n(n-k+1)+(k-1)=n. Also, value n appears exactly n−1n-1 times in block n−1n-1. Let S∗S^* allocate each arriving good to an agent with currently minimum bundle value (break ties arbitrarily). Claim. After the block for k is processed, the multiset of bundle values is Lk,…,Lk⏟k agents,Lk+(k−1),…,Lk+(k−1)⏟n−k agents,\ L_k,…,L_k_k agents, L_k+(k-1),…,L_k+(k-1)_n-k agents\, where Ln−1=nL_n-1=n and Lk−1=Lk+kL_k-1=L_k+k for k∈2,…,n−1k∈\2,…,n-1\. Proof of claim. For k=n−1k=n-1, the first block is (n−1,n,…,n⏟n−1,n−1)(n\!-\!1, n,…,n_n-1,n\!-\!1), and allocating each good to a minimum-valued agent yields n−1n-1 agents at value n and one agent at value 2n−2=n+(n−2)2n-2=n+(n-2), so Ln−1=nL_n-1=n. For the inductive step, assume the claim holds after the block for k (so the current gap is k−1k-1). The next block is (k−1,k,…,k⏟k−1,k−1,…,k−1⏟n−k+1). (k-1, k,…,k_k-1, k-1,…,k-1_n-k+1 ). The first (k−1)(k-1) goes to a minimum agent, bringing her up to the current maximum. Then the (k−1)(k-1) goods of value k are given to the remaining minimum agents, making them the new maxima. Finally, each of the n−k+1n-k+1 goods of value (k−1)(k-1) is given to a (new) minimum agent; after all are assigned, we obtain k−1k-1 agents at value Lk+kL_k+k and n−k+1n-k+1 agents at value (Lk+k)+(k−2)(L_k+k)+(k-2), i.e., the claim with Lk−1=Lk+kL_k-1=L_k+k. □ In particular, after the final block (k=1k=1), all agents have equal value L1L_1. Unrolling the recurrence, L1=n+(n−1)+⋯+2=(n−1)(n+2)2=v(G)n.L_1=n+(n-1)+·s+2= (n-1)(n+2)2= v(G)n. Moreover, each arriving good is allocated to an agent with minimum bundle value. As in the proof of Lemma 1, this implies cost(S∗,π∗) cost(S^*,π^*) =v(G)−miniv(Ai) =v(G)- _iv(A_i) =v(G)−v(G)n=(1−1n)v(G). =v(G)- v(G)n= (1- 1n )v(G). By Lemma 1, OPT(ℐ)≥(1−1n)v(G) OPT(I)≥(1- 1n)v(G), so we conclude OPT(ℐ)=(1−1n)v(G) OPT(I)=(1- 1n)v(G). Finally, we have that cost(S,π)−OPT(ℐ) cost(S,π)- OPT(I) =(v(G)−n(n−1)2)−(v(G)−v(G)n) = (v(G)- n(n-1)2 )- (v(G)- v(G)n ) =v(G)n−n(n−1)2 = v(G)n- n(n-1)2 =(n−1)(n+2)2−n(n−1)2 = (n-1)(n+2)2- n(n-1)2 =n−1=(1−1n)Vmax. =n-1= (1- 1n )V_max. Thus, the additive term (1−1n)Vmax (1- 1n )V_max cannot be improved in general.