Paper deep dive
Online Fair Division with Budget Constraints
Saar Cohen, Nicholas Teh, Paul W. Goldberg, Michael J. Wooldridge
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We study an online variant of discrete fair division under generalized assignment budget constraints. Goods arrive one at a time and must be assigned irrevocably to a feasible agent or to charity, which holds all unallocated goods, while fairness is evaluated only against budget-feasible subsets of every recipient's bundle. We first show that, without additional structure, no deterministic online algorithm can guarantee any fixed approximation to feasible envy-freeness, even in highly symmetric instances. We then identify bounded density spread as a structural condition that restores meaningful guarantees, obtaining approximation algorithms for arbitrary item sizes and showing that, under common valuations and sufficiently small goods, these guarantees can be strengthened to an optimal deterministic frontier. We further study resource augmentation, where the online algorithm is allowed slightly larger budgets than the fairness benchmark, and characterize the resulting improvement in the achievable guarantees. Finally, we develop a learning-augmented framework based on predicting joint value-size types, proving consistency under perfect predictions, robustness to prediction error, and showing that separate predictions of value and size marginals are insufficient to recover strong fairness guarantees.
Tags
Links
- Source: https://arxiv.org/abs/2607.23310v1
- Canonical: https://arxiv.org/abs/2607.23310v1
Trouble viewing inline? Open PDF directly →
Full Text
162,097 characters extracted from source content.
Expand or collapse full text
Online Fair Division with Budget Constraints Saar Cohen* Nicholas Teh* Paul W. Goldberg Michael J. Wooldridge Abstract We study an online variant of discrete fair division under generalized assignment budget constraints. Goods arrive one at a time and must be assigned irrevocably to a feasible agent or to charity, which holds all unallocated goods, while fairness is evaluated only against budget-feasible subsets of every recipient’s bundle. We first show that, without additional structure, no deterministic online algorithm can guarantee any fixed approximation to feasible envy-freeness, even in highly symmetric instances. We then identify bounded density spread as a structural condition that restores meaningful guarantees, obtaining approximation algorithms for arbitrary item sizes and showing that, under common valuations and sufficiently small goods, these guarantees can be strengthened to an optimal deterministic frontier. We further study resource augmentation, where the online algorithm is allowed slightly larger budgets than the fairness benchmark, and characterize the resulting improvement in the achievable guarantees. Finally, we develop a learning-augmented framework based on predicting joint value-size types, proving consistency under perfect predictions, robustness to prediction error, and showing that separate predictions of value and size marginals are insufficient to recover strong fairness guarantees. 1 Introduction **footnotetext: Equal contribution. Fair division asks how resources should be allocated among agents with heterogeneous preferences so that no agent feels unfairly treated. In its classical form, all goods are available before the allocation is computed, and every good is assigned to some agent. Many practical allocation problems, however, must satisfy capacity or budget constraints in addition to fairness. For instance, a food bank cannot send a household more perishable goods than it can store, a cloud scheduler cannot place more jobs on a machine than its available memory permits, and a course-allocation mechanism must respect limits on the number of credit hours assigned to each student. Many of these applications are naturally modeled by fair division under generalized assignment constraints, introduced by Barman et al. [10]. In this framework, each good may have a different value and consume a different amount of capacity for each agent, and each agent may receive only a bundle whose total size does not exceed her budget. Since the agents’ combined capacity may be insufficient to accommodate all goods, the standard convention is to introduce a distinguished recipient called charity, which holds all unallocated goods [18, 64, 16, 39]. This also changes the appropriate notion of fairness. Another recipient’s entire bundle may not fit within an agent’s budget, so comparing against that bundle is no longer meaningful. Instead, envy is evaluated only with respect to subsets that are feasible for the comparing agent. An allocation is therefore feasibly envy-free if every agent weakly prefers her own bundle to every budget-feasible subset of every other recipient’s bundle, including charity [10]. For indivisible goods, this notion is naturally relaxed by allowing a bounded number of goods to be removed from the comparison set before evaluating envy. A central assumption in this literature is that all goods, together with the agents’ values and sizes for them, are known before the allocation is computed. An algorithm can thus optimize over the complete instance and coordinate its capacity decisions globally. In many practical settings, however, this is unrealistic. Goods arrive over time and must be committed immediately. For example, donated items are shelved as they arrive, jobs are scheduled when they are submitted, and perishable resources cannot wait for a global optimization. In this work, we therefore introduce the online version of budget-constrained fair division, in which indivisible goods arrive one at a time. When a good arrives, the algorithm learns its complete value-size profile and must irrevocably assign it either to an agent whose remaining budget can accommodate it or to charity. The algorithm has no information about future arrivals unless such information is explicitly supplied through predictions. Fairness is evaluated with respect to all recipients, including charity, and only against subsets that fit within the comparing agent’s original budget. This problem is not merely the classical online fair-division problem with an additional feasibility constraint. Budget constraints and charity create two interacting difficulties that are absent from the unconstrained model. First, accepting a good irrevocably consumes scarce capacity, so an early assignment may prevent an agent from receiving a more valuable good later. Second, a good that is not assigned to an agent is placed in charity rather than disappearing from the instance. Since fairness is evaluated against feasible subsets of the charity bundle, rejecting a good may itself create future envy. Every online decision therefore balances preserving capacity against avoiding future envy. These observations naturally raise the question of what additional structure or algorithmic power is sufficient to recover meaningful fairness guarantees in online budgeted fair division. Our contributions provide several complementary answers to this question and are listed below. Limits of online budgeted fair division. We prove that no deterministic online algorithm can guarantee any fixed approximation to feasible envy-freeness in the unrestricted adversarial model, even for two agents, equal budgets, common valuations, uniform item sizes, and a known horizon. Bounded density spread restores tractability. For arbitrary item sizes, we derive capacity-aware online algorithms whose fairness guarantees depend only on the variation in value per unit of budget. Under common valuations, sizes common across agents, and globally small goods, we further obtain matching upper and lower bounds that exactly characterize the optimal deterministic approximation frontier. Value of additional online capacity. We study a resource-augmentation model in which the online algorithm may allocate using budgets that are slightly larger than the original budgets against which fairness is evaluated. For arbitrary item sizes, we quantify the resulting improvement in achievable fairness guarantees and establish matching lower bounds. Under common valuations, sizes common across agents, and globally small goods, we completely characterize the optimal tradeoff between resource augmentation and fairness. Learning-augmented online budgeted fair division. Using predictions of future joint value-size types, we develop an online algorithm that exactly reproduces any offline guarantee when predictions are correct and degrades gracefully when they are not. We also prove that this robustness guarantee is essentially tight and that predicting values and sizes separately is fundamentally insufficient. 2 Related Work Fair division under constraints and charity. Fair division under cardinality, matroid, connectivity, and budget constraints has received considerable attention; see the survey of Suksompong [60]. Closest to our work is the generalized assignment model of Barman et al. [10], in which goods have agent-specific values and sizes, agents are subject to budgets, and unallocated goods are assigned to charity. Building on earlier work on constrained fair division [18, 64, 16, 39], they formulate fairness through feasible envy, comparing each agent’s allocation only with budget-feasible subsets of other recipients’ bundles. These works study the offline setting, whereas we introduce its online version, where goods arrive sequentially and allocation decisions are irrevocable. Elkind et al. [31] subsequently studied an analogous model for the setting with chores. Online fair division. Online fair division was introduced through applications such as food banks by Aleksandrov et al. [2]; see the survey of Aleksandrov and Walsh [1]. Subsequent work studies the fairness-efficiency tradeoff under online arrivals [12, 13], dynamic reallocation [41], and online variants of envy-based fairness notions [54, 19]. These works often assume that every arriving good is allocated to an agent and that fairness is evaluated with respect to entire bundles. Our model instead incorporates budget constraints and charity, leading to capacity-aware feasible-envy comparisons; see Appendix A for a broader discussion. EF1, EFX, and their feasible analogues. Envy-freeness up to one good (EF1) [14, 48] and up to any good (EFX) [17, 53] are standard relaxations of envy-freeness for indivisible goods. Under budget constraints, however, another recipient’s bundle may be infeasible for the comparing agent. To address this issue, Barman et al. [10] introduced feasible envy-freeness (FEF) and its relaxation FEFx (building on related feasible-envy notions for other constraint classes), which restrict comparisons to budget-feasible subsets and include charity as a recipient. We adopt these fairness notions. Learning-augmented online algorithms. Algorithms with machine-learned predictions aim to achieve consistency under accurate predictions while remaining robust to prediction error [56, 49]; see the survey of Mitzenmacher and Vassilvitskii [52]. Learning-augmented techniques have recently been applied to online fair division [8, 9, 21, 6, 43, 67, 54, 58, 7, 20, 19, 63]. Unlike these works, which predict aggregate values, normalization information, value frequencies, or maximum item values, we predict joint value-size types, reflecting that budget feasibility depends on value-size correlations; see Appendix A for further discussion. Budgeted allocation and knapsack. Our model shares the capacity-constrained allocation structure of generalized assignment, online knapsack, and AdWords-style problems [50, 51]. Unlike these problems, however, our objective is fairness rather than welfare or revenue. The logarithmic frontier that we obtain in the small-item setting is closely related to the optimal competitive ratio for online knapsack with bounded value-to-size ratios [68], although our multi-agent fairness analysis requires additional techniques. 3 Preliminaries For a positive integer z, let [z]=1,…,z[z]=\1,…,z\. We study an online allocation problem in which a fixed set of agents receives indivisible goods that arrive one at a time, and each arrival must be assigned irrevocably before the next good is revealed. Formally, there is a fixed set of agents N=[n]N=[n]. Each agent i∈Ni∈ N has a strictly positive budget BiB_i, which limits the total size of the goods she may receive. Goods arrive sequentially in discrete rounds. Let G=g1,…,gTG=\g_1,…,g_T\ denote the finite set of goods, where gtg_t is the good arriving in round t. By a slight abuse of notation, we also use G to refer to this arrival sequence when the order is relevant. For each round t∈[T]t∈[T], we denote by Gt=g1,…,gtG^t=\g_1,…,g_t\ the set of goods that have arrived by the end of round t. Goods arriving in different rounds are treated as distinct, even if they have identical values and sizes. Each agent i∈Ni∈ N has an additive valuation vi:2G→ℝ≥0v_i:2^G _≥ 0 and an additive size function si:2G→ℝ≥0s_i:2^G _≥ 0. For every good g∈Gg∈ G, we assume vi(g)≥0v_i(g)≥ 0 and si(g)>0s_i(g)>0. For every bundle S⊆GS G, vi(S)=∑g∈Svi(g)v_i(S)= _g∈ Sv_i(g) and si(S)=∑g∈Ssi(g)s_i(S)= _g∈ Ss_i(g). A bundle S is feasible for agent i if si(S)≤Bis_i(S)≤ B_i. A good g is individually feasible for agent i if si(g)≤Bis_i(g)≤ B_i. An instance of our problem is thus specified by I=(N,G,(Bi,vi,si)i∈N)I=(N,G,(B_i,v_i,s_i)_i∈ N). Budget constraints may make it impossible, or undesirable, to assign every good to an agent. We therefore include a distinguished recipient C, called charity, which holds all goods that are not assigned to agents. Let R=N∪CR=N∪\C\ denote the set of recipients. An allocation after round t is a tuple At=(Art)r∈RA^t=(A_r^t)_r∈ R that partitions GtG^t. It is feasible if si(Ait)≤Bis_i(A_i^t)≤ B_i for every agent i; charity is not subject to a budget constraint. We write A=ATA=A^T for the final allocation and abbreviate its components by AiA_i and ACA_C. The interaction is online and irrevocable. After observing gtg_t, the algorithm must immediately choose one recipient rt∈Rr_t∈ R. Assigning gtg_t to agent i is permitted only if si(Ait−1)+si(gt)≤Bis_i(A_i^t-1)+s_i(g_t)≤ B_i, while assignment to charity is always permitted. Once a good has been assigned, its recipient cannot change. We distinguish between unknown and known horizons. In the unknown-horizon model, the number of arrivals is not revealed to the algorithm, and a guarantee must remain valid whenever the finite sequence stops. In the known-horizon model, the total number of rounds is announced before the first arrival. We also use the standard distinction between adaptive and oblivious adversaries. An adaptive adversary may choose later arrivals after observing the algorithm’s earlier decisions, while an oblivious adversary fixes the entire input sequence before its execution. Unless explicitly stated otherwise, algorithms in this paper are deterministic. 3.1 Valuation, Size, and Density Structure Our general model allows values and sizes to depend on both the agent and the good. Several of our results impose additional structure. We collect the recurring special cases here so that later sections can state their assumptions compactly. Valuations are common if there is a single function v:G→ℝ≥0v:G _≥ 0 such that vi(g)=v(g)v_i(g)=v(g) for every i∈Ni∈ N and g∈Gg∈ G. They are scaled common if there is a base value function v and positive constants βi _i satisfying vi(g)=βiv(g)v_i(g)= _iv(g) for every agent and good. Common valuations are the special case in which all scales are equal. The size assumptions require a separate distinction. Saying that sizes are common across agents does not mean that all goods have the same size. Definition 3.1 (Sizes common across agents and uniform item sizes). Sizes are common across agents if there is a function s:G→ℝ>0s:G _>0 such that si(g)=s(g)s_i(g)=s(g) for every agent i∈Ni∈ N and good g∈Gg∈ G. Thus, different goods may still have different sizes. Sizes are uniform across goods if there is a constant δ>0δ>0 such that si(g)=δs_i(g)=δ for every agent i∈Ni∈ N and good g∈Gg∈ G. Uniform item sizes therefore imply sizes common across agents, but the converse need not hold. For σmax≥0 _ ≥ 0, an instance is globally σmax _ -small if si(g)≤σmaxBis_i(g)≤ _ B_i for every i∈Ni∈ N and g∈Gg∈ G. When budgets are 11 and sizes are common across agents, this condition reduces to s(g)≤σmaxs(g)≤ _ for every g∈Gg∈ G. Whenever vi(g)>0v_i(g)>0, define the density ρi(g)=vi(g)/si(g) _i(g)=v_i(g)/s_i(g), the value agent i derives per unit of budget consumed. Thus, higher-density goods are more budget-efficient. Many of our guarantees depend not on absolute densities but on their variation within an instance, captured by the ratio of the largest and smallest positive densities. Definition 3.2 (Density spread). For an agent i having at least one good g such that vi(g)>0v_i(g)>0 and si(g)≤Bis_i(g)≤ B_i, define ρimin:=minρi(g):g∈G,vi(g)>0,si(g)≤Bi _i := \ _i(g):g∈ G,v_i(g)>0,s_i(g)≤ B_i\ and ρimax:=maxρi(g):g∈G,vi(g)>0,si(g)≤Bi _i := \ _i(g):g∈ G,v_i(g)>0,s_i(g)≤ B_i\. The density spread of agent i is Γi:=ρimaxρimin≥1 _i:= _i _i ≥ 1. If no good satisfies vi(g)>0v_i(g)>0 and si(g)≤Bis_i(g)≤ B_i, set Γi:=1 _i:=1; in this case, every set feasible for i has value zero for i. The density spread of the instance is Γ:=maxi∈NΓi := _i∈ N _i. Only positively valued goods that are individually feasible enter Γi _i, since other goods cannot belong to any feasible comparison set for agent i. 3.2 Feasible Envy-Based Fairness Notions Under generalized assignment constraints, another recipient’s bundle may be infeasible for the comparing agent. Following Barman et al. [10] and related work on constrained fair division [18, 64, 16, 39], we therefore compare an agent’s bundle only with budget-feasible subsets of every recipient’s bundle, including charity. The strongest notion requires the agent to weakly prefer her own bundle to every such comparison set. Definition 3.3 (Feasible envy-freeness). An allocation A is feasibly envy-free (FEF) if vi(Ai)≥vi(S)v_i(A_i)≥ v_i(S) for any agent i∈Ni∈ N, recipient r∈Rr∈ R, and set S⊆ArS A_r feasible for i. Exact FEF is generally too demanding for indivisible goods under generalized assignment constraints, as feasible envy-free allocations need not exist [10]. We therefore consider relaxations that permit the comparison set to lose a bounded number of goods. Our primary notion is a multiplicative approximation of FEFkk, which generalizes feasible envy-freeness up to one good and related notions studied in the constrained fair-division literature [10, 64, 18]. Definition 3.4 (Multiplicative α-FEFkk). Let α∈[0,1]α∈[0,1] and let k≥0k≥ 0 be an integer. An allocation A is α-FEFkk if, for every agent i∈Ni∈ N, recipient r∈Rr∈ R, and set S⊆ArS A_r feasible for i, there exists a set X⊆SX S with |X|≤k|X|≤ k such that vi(Ai)≥αvi(S∖X)v_i(A_i)≥α\,v_i(S X). When α=1α=1, we simply write FEFkk. For an online algorithm, an α-FEFkk guarantee is prefix-wise if, after every round t∈[T]t∈[T], the current allocation AtA^t of GtG^t is α-FEFkk. The most prominent case is FEF11, which permits the removal of at most one good from the comparison set. A related, stronger notion requires the inequality to survive the removal of every good. Definition 3.5 (FEFx). An allocation A is feasibly envy-free up to any good (FEFx) if, for every agent i∈Ni∈ N, every recipient r∈Rr∈ R, and every strict subset S⊊ArS A_r that is feasible for i, vi(Ai)≥vi(S)v_i(A_i)≥ v_i(S). Multiplicative guarantees are natural when values may be rescaled. For the prediction-based results later in the paper, it is also useful to measure fairness loss additively. Definition 3.6 (Additive η-FEFkk). Let η≥0η≥ 0 and let k≥0k≥ 0 be an integer. An allocation A is additive η-FEFkk if, for any agent i∈Ni∈ N, recipient r∈Rr∈ R, and set S⊆ArS A_r feasible for i, there exists X⊆SX S with |X|≤k|X|≤ k such that vi(Ai)≥vi(S∖X)−ηv_i(A_i)≥ v_i(S X)-η. The notions presented above satisfy the natural hierarchy inherited from their classical counterparts. In particular, FEF0 implies FEF11, which in turn implies FEF22, and more generally FEFkk implies FEFk′k whenever k≤k′k≤ k . Likewise, FEFx implies FEF11 by definition. Finally, if every feasible comparison set has cardinality at most k, then every feasible allocation is FEFkk, as the entire comparison set may be removed. This explains why allowing k to depend freely on the instance would make the notion uninformative. Remark 3.7 (k must be instance-independent). For an instance I, let its maximum feasible comparison cardinality be κ(I):=maxi∈Nmax|S|:S⊆G,si(S)≤Biκ(I):= _i∈ N \|S|:S G,s_i(S)≤ B_i\. Since every feasible comparison set contains at most κ(I)κ(I) goods, every feasible allocation is trivially FEFκ(I)κ(I): one may simply remove the entire comparison set. Thus, meaningful FEFkk guarantees require k to remain independent of the instance. 4 No Fixed α-FEFkk Guarantee in General We first show that no deterministic algorithm can guarantee any fixed multiplicative α-FEFkk relaxation, even against an oblivious adversary and regardless of the values of α and k. Thus, without additional structural assumptions, even very weak relaxations of feasible envy-freeness are unattainable online. Perhaps surprisingly, this impossibility already holds on highly symmetric instances. The hard instances involve only two agents with equal budgets, common valuations, uniform item sizes, and even a known horizon. The only source of difficulty is the interaction between irrevocable budget consumption and charity-inclusive feasible envy. The proof uses phases whose values grow sufficiently quickly that each phase dominates the total value accumulated in all previous phases. To avoid an immediate violation of α-FEFkk, the algorithm must devote a positive amount of capacity to every phase. Since capacities are finite, these requirements eventually become incompatible. Although the proof is conveniently described through a phase simulation, determinism allows the resulting finite hard sequence to be fixed before its actual execution. Theorem 4.1. Fix any integer k≥0k≥ 0 and any α∈(0,1]α∈(0,1]. For every deterministic online algorithm in the irrevocable model, there exists a fixed finite input sequence on which the final allocation is not α-FEFkk. Equivalently, no deterministic online algorithm guarantees α-FEFkk even against an oblivious adversary. The impossibility holds even when simultaneously: (1) there are only two agents, n=2n=2; (2) the budgets are equal, B1=B2=1B_1=B_2=1; (3) valuations are common; (4) sizes are uniform across goods; (5) the horizon T is known to the algorithm in advance. The proof appears in Appendix B.1. Theorem˜4.1 immediately yields two useful specializations. Setting α=1α=1 shows that exact FEFkk is impossible for every fixed value of k. Corollary 4.2. For every fixed integer k≥0k≥ 0, no deterministic online algorithm guarantees exact FEFkk on all instances, even against an oblivious adversary and even under assumptions (1)–(5) of Theorem˜4.1. The hard instances constructed in the proof of Theorem˜4.1 have an additional structural property. Since every good has size 1/Q1/Q and every budget is 11, every feasible comparison set contains at most Q goods. Consequently, the same construction yields an impossibility result parameterized by the maximum feasible comparison cardinality. We stress that the result establishes the existence of a sufficiently large value q>kq>k; it does not claim that hardness holds for every q>kq>k. The proof appears in Appendix B.2. Corollary 4.3. For every fixed integer k≥0k≥ 0, there exists an integer q>kq>k such that no deterministic online algorithm guarantees exact FEFkk on all instances satisfying κ(I)=qκ(I)=q (Remark 3.7), even against an oblivious adversary and even under assumptions (1)–(5) of Theorem˜4.1. Theorem˜4.1 is not implied by existing impossibility results for online EF1 by Neoh et al. [54], which assume that every good is allocated to an agent and measure envy with respect to entire bundles. Our lower bound instead relies on the interaction between budget constraints and charity-inclusive feasible envy: accepting goods irrevocably consumes capacity, while goods sent to charity remain valid objects of comparison. The hardness therefore arises from capacity-limited feasible comparisons rather than from heterogeneous preferences or unknown horizons. The construction of Theorem˜4.1 has unbounded density spread. Thus, the theorem establishes impossibility in the absence of additional structure, but does not determine the best guarantee under bounded density spread. Appendix E addresses this question by identifying the optimal limiting frontier in the globally small common-valuation setting through a separate lower-bound construction. 5 Greedy Algorithms under Bounded Density Spread We now identify bounded density spread as a structural condition under which meaningful online fairness guarantees become possible. For arbitrary item sizes, we derive simple capacity-aware greedy algorithms that achieve multiplicative guarantees under common, scaled-common, and fully heterogeneous valuations. Appendix E strengthens these results in the globally-small common-valuation model, where a different algorithm yields a sharp deterministic frontier. 5.1 Common Valuations We begin with the common-valuation setting, where every agent agrees on the value of each good. In this setting, we introduce Positive-GreedyFit (Algorithm˜1), a deterministic online greedy algorithm that forms the basis of all positive results in this section. The algorithm balances two competing objectives. First, it never allocates a good of zero value to an agent (line 3), thereby preserving scarce budget capacity for future arrivals. Second, whenever a positive-value good is feasible for multiple agents, it assigns the good to an agent whose current bundle has minimum value (lines 4–6), thus balancing the accumulated value across agents. The algorithm is deterministic, processes each arrival in (n)O(n) time, and maintains feasibility by construction, since goods are assigned only to agents with sufficient remaining budget. Algorithm 1 Positive-GreedyFit (common valuations) 1:Initialize Ai←∅A_i← for all i∈Ni∈ N and AC←∅A_C← 2:for each arriving good g do 3: if v(g)=0v(g)=0 then assign g to charity 4: else Let Fg←i∈N:si(Ai)+si(g)≤BiF_g←\i∈ N:s_i(A_i)+s_i(g)≤ B_i\ be the agents that can accommodate good g. 5: if Fg=∅F_g= then assign g to charity. 6: else assign g to an arbitrary i∗∈argminh∈Fgv(Ah)i^*∈ *arg\,min_h∈ F_gv(A_h), using a fixed tie-breaking order. 7:return A=(A1,…,An,AC)A=(A_1,…,A_n,A_C) The following theorem shows that bounded density spread is sufficient to recover a multiplicative FEF11 guarantee. Moreover, the guarantee depends only on the density spread. Theorem 5.1. Positive-GreedyFit guarantees Γ−1 ^-1-FEF11 under common valuations. In particular, if Γ=1 =1, then the algorithm returns an exact FEF11 allocation. Proof sketch. In Appendix C.1, we fix a feasible comparison set and remove its last-arriving positively valued good f. If f was feasible for the comparing agent when it arrived, the minimum-value rule bounds the remaining comparison value. Otherwise, infeasibility yields a size inequality, which translates to the factor Γi−1 _i^-1 via ρimin _i and ρimax _i . Theorem˜5.1 is consistent with the impossibility result of Theorem˜4.1. In the family of instances used in the proof of Theorem˜4.1, all goods have the same size but the phase values increase rapidly, so the density spread of that family can be arbitrarily large and the factor Γ−1 ^-1 can be arbitrarily small. Thus, Theorem˜5.1 gives a nonzero instance-independent factor only when Γ is bounded in advance. Scaled-common valuations. The analysis of Positive-GreedyFit extends directly to scaled-common valuations, where vi(g)=βiv(g)v_i(g)= _iv(g) for a common base valuation v. Running the algorithm on v preserves both the ordering of goods and the density spread, so the Γ−1 ^-1-FEF1 guarantee of Theorem˜5.1 continues to hold. The formal statement and proof are given in Appendix C.2. 5.2 Fully Heterogeneous Valuations We now allow agent-specific additive valuations. The proof from the common-valuation case cannot be used directly because agent i and the recipient of a good may assign different values to that good. The algorithm below compares the numerical quantities vi(Ai)v_i(A_i) across agents. We therefore assume in this subsection that the reported numerical values are directly comparable across agents. Rescaling only one agent’s valuation may change both the allocation produced by the algorithm and the bound below. The algorithm assigns a good only to feasible agents that value it positively. To compare valuations across agents, define χi:=max(1∪vi(g)/vj(g):vj(g)>0) _i:= (\1\∪\v_i(g)/v_j(g):v_j(g)>0\), which is a cross-comparability bound that measures how much larger agent i’s value for a good can be than that assigned by any recipient who values it positively. Now, define Λi:=maxΓi,χi _i:= \ _i, _i\ and Λ:=maxi∈NΛi := _i∈ N _i, where Γi _i captures the loss due to capacity constraints and χi _i the additional loss from heterogeneous valuations. The analysis incurs the former when the last relevant good is infeasible for agent i, and the latter otherwise, yielding a Λi−1 _i^-1 guarantee. Hetero-GreedyFit differs from Positive-GreedyFit only by restricting eligible agents to those assigning positive value to the arriving good; see Appendix C.3. The following theorem establishes the corresponding Λ−1 ^-1-FEF11 guarantee. Theorem 5.2. Hetero-GreedyFit guarantees Λ−1 ^-1-FEF11 under agent-specific additive valuations whose numerical values are directly comparable across agents. In particular, if both the density spread and the cross-comparability are bounded, i.e., Λ≤λ ≤λ for some constant λ, the algorithm guarantees λ−1λ^-1-FEF11. The proof is similar to that of Theorem˜5.1 and thus deferred to Appendix C.4. The guarantee of Theorem˜5.2 is meaningful when χi _i is bounded. If the base valuation is not identically zero, scaled-common valuations satisfy vi(g)/vj(g)=βi/βjv_i(g)/v_j(g)= _i/ _j on every positively valued good, so χi=maxjβi/βj _i= _j _i/ _j; otherwise, all fairness comparisons are trivial. More generally, any valuation class with uniformly bounded vi(g)/vj(g)v_i(g)/v_j(g) for positively valued goods yields a constant-factor FEF11 guarantee. On scaled-common valuations, however, Theorem˜C.1 remains sharper, as it exploits the common base ranking and avoids the additional factor χi _i. All three results, Theorems˜5.1, 5.2 and C.1, allow arbitrary good sizes. Appendix E strengthens the common-valuation analysis for common sizes, unit budgets, and goods whose maximum size tends to zero by determining the exact limiting factor, while Appendix G gives a separate known-horizon lower bound for arbitrary good sizes. 6 Resource Augmentation for Arbitrary Sizes The previous section showed that bounded density spread restores meaningful multiplicative guarantees, but the approximation factor deteriorates as the density spread increases. Moreover, Theorem˜4.1 rules out any fixed feasible-envy relaxation in complete generality. A standard way to overcome such online limitations is resource augmentation [44, 57], in which the algorithm is given more resources than the benchmark against which it is evaluated. Since the difficulty in our setting stems from irrevocable budget consumption, we augment the agents’ online budgets. Fairness is still evaluated with respect to the original budgets, so only the algorithm’s capacity constraints are relaxed. The results below apply to arbitrary item sizes. Appendix E shows that under the additional globally-small assumption, resource augmentation admits a substantially sharper characterization. Formally, fix an augmentation parameter ε≥0 ≥ 0. Each agent i has original budget BiB_i, while the online algorithm allocates using the enlarged algorithmic budget (1+ε)Bi(1+ )B_i. Fairness, however, is still evaluated with respect to the original budgets. We thus call an allocation A=(A1,…,An,AC)A=(A_1,…,A_n,A_C) bicriteria-feasible if si(Ai)≤(1+ε)Bis_i(A_i)≤(1+ )B_i for each agent i. Throughout this section, every α-FEFkk guarantee is interpreted using the original budgets, i.e., any comparison set must satisfy si(S)≤Bis_i(S)≤ B_i. Hence, resource augmentation relaxes only the algorithm’s capacity constraints, not the fairness benchmark. When ε=0 =0, we recover the original model. We introduce Aug-GreedyFit(ε)( ), which modifies Positive-GreedyFit by replacing each budget BiB_i with (1+ε)Bi(1+ )B_i. A good is eligible for agent i only if it is individually feasible under the original budget BiB_i and its assignment keeps the total allocated size within (1+ε)Bi(1+ )B_i. The first condition excludes goods that can never appear in a feasible comparison set. See Appendix D.1 for a pseudocode. Resource augmentation enlarges the algorithm’s capacity, improving the achievable fairness guarantee. The following result quantifies this tradeoff, interpolating between the Γ−1 ^-1-FEF11 guarantee of Theorem˜5.1 when ε=0 =0 and exact FEF11. Theorem 6.1. Under common valuations, for every ε≥0 ≥ 0, Aug-GreedyFit returns an allocation A satisfying si(Ai)≤(1+ε)Bis_i(A_i)≤(1+ )B_i for every i∈Ni∈ N, and A is min1,1+εΓ-FEF1 \1, 1+ \-FEF1 when fairness is evaluated using the original budgets. In particular, if ε≥Γ−1 ≥ -1, then A is exact FEF1. The proof appears in Appendix D.2. The next theorem shows that no fixed finite extra budget overcomes the unrestricted-density lower bound. This is stronger than ruling out only small values of ε . Theorem 6.2. Fix an integer k≥0k≥ 0, a factor α∈(0,1]α∈(0,1], and any fixed ε≥0 ≥ 0. Every deterministic online algorithm maintaining si(Ait)≤(1+ε)Bis_i(A_i^t)≤(1+ )B_i for every agent i∈Ni∈ N and every prefix t fails to guarantee α-FEFkk on some fixed finite input sequence, even against an oblivious adversary. This holds with two agents, equal unit budgets, common valuations, uniform good sizes, a known horizon, and fairness evaluated using the original budgets. The proof appears in Appendix D.3. Theorem 6.2 shows that no finite augmentation ε yields a positive instance-independent guarantee without bounding the density spread. Under Γ≤γ ≤γ, however, Theorem 6.1 achieves exact FEF1 whenever ε≥γ−1 ≥γ-1. Appendix E further sharpens this frontier under common valuations, common sizes, and unit budgets: as the maximum item size tends to zero, the optimal limiting guarantee is min1,1+ε1+lnγ \1, 1+ 1+ γ\ in both the known- and unknown-horizon models. Thus, every ε>lnγ > γ suffices for exact FEF1 once goods are sufficiently small. Appendix F shows that this stronger guarantee relies on the threshold policy, since Aug-GreedyFit is not exact for density spread exceeding 11, even with arbitrarily small goods. 7 Learning-Augmented Online Algorithms We next overcome the limitations of the online model using predictions about future arrivals. Our algorithm reserves capacity for a planned offline allocation while remaining robust to prediction errors. Unlike preceding results, its guarantees are independent of the density spread and instead degrade gracefully with prediction error. 7.1 The Type-Count Prediction Model Goods with identical values but different sizes may play different roles in feasible allocations. We therefore predict their joint value-size profiles. Formally, fix a finite type set T containing every predicted and realized type. A type is a value-size profile θ=((vi,θ)i∈N,(si,θ)i∈N)∈ℝ≥0n×ℝ>0nθ=((v_i,θ)_i∈ N,(s_i,θ)_i∈ N) _≥ 0^n×R_>0^n. Under common valuations, vi,θ=vθv_i,θ=v_θ for every i∈Ni∈ N. The predictor supplies type counts f^=(f^θ)θ∈ f=( f_θ)_θ , while f=(fθ)θ∈f=(f_θ)_θ denotes the realized counts. An arriving good has type θ iff its values and sizes match θ. The predicted multiset M M contains f^θ f_θ copies of each type θ. An offline planner computes a feasible allocation A^=(A^r)r∈R A=( A_r)_r∈ R with quotas qr,θq_r,θ satisfying ∑r∈Rqr,θ=f^θ _r∈ Rq_r,θ= f_θ. We measure prediction quality by the total value of goods whose type counts are mispredicted. The value-weighted prediction error for agent i and the overall error are Δi(f,f^)=∑θ∈vi,θ|fθ−f^θ| _i(f, f)= _θ v_i,θ\,|f_θ- f_θ| and Δ∞(f,f^)=maxi∈NΔi(f,f^) _∞(f, f)= _i∈ N _i(f, f). Under common valuations, Δ(f,f^)=∑θvθ|fθ−f^θ| (f, f)= _θv_θ|f_θ- f_θ|. Given the predicted multiset, Plan-Reserve-Fulfill (Algorithm˜2) computes a target feasible allocation. Online, it realizes this plan whenever possible by reserving capacity for planned assignments, greedily allocating excess goods whenever doing so preserves the reserved capacity, and otherwise sending them to charity. A realized type-θ good is excess if it arrives after all planned type-θ quotas have been filled. For each recipient r and type θ, the algorithm maintains the remaining planned quota qr,θunfq^unf_r,θ, initialized to qr,θq_r,θ. For each agent i, it maintains the reserved size resi=∑θ∈qi,θunfsi,θres_i= _θ q^unf_i,θs_i,θ, the total size of planned goods assigned to i whose quotas remain unfilled, while ensuring si(Ai)+resi≤Bis_i(A_i)+res_i≤ B_i. The online phase runs in (n)O(n) time per arriving good once the offline quotas have been computed. The preprocessing time equals that of the chosen planner, e.g., pseudo-polynomial using the exact FEFx algorithm of Barman et al. [10] or polynomial using their FPTAS. The key invariant is that reserved capacity never compromises feasibility: reserved goods always fit within the budget, and every good assigned to satisfy a planned quota is accepted immediately. The proof appears in Appendix I.1. Algorithm 2 Plan-Reserve-Fulfill 1:Run the offline planner on M M to get A A and quotas qr,θq_r,θ. 2:Initialize qr,θunf←qr,θq^unf_r,θ← q_r,θ for every recipient r and predicted type θ, Ar←∅A_r← for all r, and resi←∑θqi,θunfsi,θres_i← _θq^unf_i,θs_i,θ for every agent i. When an unpredicted type θ first appears, initialize qr,θunf←0q^unf_r,θ← 0 for every r. 3:for each arriving good g of realized type θ do 4: if qi,θunf>0q^unf_i,θ>0 for some agent i then 5: Pick such an agent via a fixed tie-breaking rule. 6: Assign g to i. 7: qi,θunf←qi,θunf−1q^unf_i,θ← q^unf_i,θ-1, resi←resi−si,θres_i _i-s_i,θ. 8: else if qC,θunf>0q^unf_C,θ>0 then 9: Assign g to charity and update qC,θunf←qC,θunf−1q^unf_C,θ← q^unf_C,θ-1. 10: else if ∃i∈N:si(Ai)+si,θ+resi≤Bi∃ i∈ N:s_i(A_i)+s_i,θ+res_i≤ B_i then 11: Pick such an agent via a fixed tie-breaking rule. 12: Assign g to i. 13: else assign g to charity. 14:return (A1,…,An,AC)(A_1,…,A_n,A_C). Lemma 7.1. Throughout the execution of Plan-Reserve-Fulfill, the reserved-capacity invariant is maintained. Consequently, the algorithm always returns a budget-feasible allocation, and every good assigned to satisfy a planned agent quota is accepted without violating feasibility. 7.2 Consistency under Perfect Predictions A fundamental requirement of learning-augmented algorithms is consistency: under perfect predictions, the online algorithm should reproduce the planned offline allocation. For Plan-Reserve-Fulfill, this means that every predicted quota is eventually filled, so the online allocation matches the planned allocation up to the identities of identical goods. Theorem 7.2. If f=f^f= f, then Plan-Reserve-Fulfill fills every planned quota and returns an allocation with the same per-recipient type counts as the planned allocation A A. See Appendix I.2 for a proof. Theorem 7.2 immediately lifts any offline fairness guarantee determined solely by the per-recipient type counts to the online setting. In particular, FEF, FEFkk, α-FEFkk, additive η-FEFkk, and FEFx are all preserved; see Appendix I.3. 7.3 Robustness to Prediction Errors We now quantify the effect of prediction errors. Planned goods may fail to arrive, leaving quotas unfilled, while additional realized goods create excess allocations. We measure additive fairness loss by the k-violation violk(A)viol_k(A), the minimum η≥0η≥ 0 such that A is additive η-FEFkk; see Appendix I.4 for an equivalent explicit expression. The key step is to relate this fairness loss to the missing and excess goods caused by prediction errors. Appendix I.5 establishes this intermediate bound, which yields the following robustness guarantee after relating those quantities to the prediction error Δ∞(f,f^) _∞(f, f); see Appendix I.6 for the proof. Theorem 7.3. Suppose the planned allocation A A is additive η0 _0-FEFkk, and let A be the allocation returned by Plan-Reserve-Fulfill. Then, violk(A)≤η0+Δ∞(f,f^)viol_k(A)≤ _0+ _∞(f, f). In the common-valuation case, violk(A)≤η0+Δ(f,f^)viol_k(A)≤ _0+ (f, f). Combining Theorems˜7.2 and 7.3, Plan-Reserve-Fulfill recovers the planner’s allocation under perfect predictions and otherwise degrades gracefully with prediction error. Appendix J shows that weaker advice consisting only of the minimum positive density and a valid spread bound does not improve the optimal spread-bounded frontier. 7.4 Tightness of the Prediction-Error Bound The robustness guarantee of Theorem˜7.3 degrades additively with the prediction error. The following theorem shows that this dependence is essentially tight: no deterministic prediction-augmented online algorithm can guarantee a substantially smaller additive dependence on the prediction error while remaining perfectly consistent. Theorem 7.4. Fix k≥1k≥ 1 and ζ∈(0,1)ζ∈(0,1). Any deterministic online algorithm that returns an exact FEFkk allocation under correct type-count predictions satisfies violk(A)≥(1−ζ)Δ(f,f^)viol_k(A)≥(1-ζ) (f, f) on some instance, even for two agents with equal budgets, common valuations, sizes common across agents, and a known horizon. The proof appears in Appendix I.7. The lower bound uses only exact FEFkk under correct predictions; it does not assume that the algorithm follows a particular offline plan. On the correct instance, exact FEFkk forces each agent to accept almost all of the low-valued prefix. Replacing the predicted zero-valued suffix by high-valued goods then leaves too little capacity to accept those goods, creating a fairness violation proportional to the value-weighted prediction error. 7.5 Value and Size Marginals Do Not Suffice The following result shows that exact FEFkk cannot be achieved using only value and size marginals, even when several natural aggregate statistics are also predicted. Budget feasibility depends on the correlation between values and sizes, making joint type information essential. Theorem 7.5. Fix k≥1k≥ 1. No deterministic online algorithm can guarantee exact FEFkk given only the exact value and size multisets and the horizon, even for two agents with equal budgets, common valuations, and sizes common across agents. The result continues to hold if the total value and maximum item value are also provided. Proof sketch. Appendix I.8 constructs two instances with identical marginal predictions but different value-size pairings, forcing different online decisions. Unlike unconstrained online fair division, where predicting future values can suffice [54], budget constraints make the pairing of values and sizes essential. Theorem 7.5 thus explains why our prediction model uses joint value-size types instead of separate value and size marginals. Joint type counts provide one sufficient representation of this information, though not the only possible one. 8 Conclusion and Future Work We initiated the study of online fair division under budget constraints. We proved that deterministic online algorithms admit no meaningful fairness guarantees in full generality, and showed how bounded density spread, resource augmentation, and learning-augmented algorithms restore tractability. Together, these results delineate the boundary between impossibility and tractability. Several directions remain for future work. It would be interesting to extend the sharp frontier characterizations beyond the small-item setting, particularly to arbitrary and agent-specific item sizes, and to better understand the power of randomization, recourse, richer arrival models, and other forms of resource augmentation. It also remains to develop richer prediction models, and to establish tighter bounds on the predictive information required to recover strong fairness guarantees. References Aleksandrov and Walsh [2020] Martin Aleksandrov and Toby Walsh. Online fair division: A survey. In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), pages 13557–13562, 2020. Aleksandrov et al. [2015] Martin Damyanov Aleksandrov, Haris Aziz, Serge Gaspers, and Toby Walsh. Online fair division: Analysing a food bank problem. In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI), pages 2540–2546, 2015. Alouf-Heffetz et al. [2022] Shiri Alouf-Heffetz, Laurent Bulteau, Edith Elkind, Nimrod Talmon, and Nicholas Teh. Better collective decisions via uncertainty reduction. In Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI), pages 24–30, 2022. Amanatidis et al. [2025] Georgios Amanatidis, Alexandros Lolos, Evangelos Markakis, and Victor Turmel. Online fair division for personalized 2-value instances. In Proceedings of the 18th International Symposium on Algorithmic Game Theory (SAGT), pages 209–227, 2025. Amanatidis et al. [2026] Georgios Amanatidis, Giulio Giaconi, Evangelos Markakis, and Nicos Protopapas. Online fair division meets reordering buffers. arXiv preprint, arXiv:2607.01159, 2026. An et al. [2024] Lin An, Andrew A Li, Benjamin Moseley, and Gabriel Visotsky. Best of many in both worlds: Online resource allocation with predictions under unknown arrival model. arXiv preprint arXiv:2402.13530, 2024. Balkanski et al. [2023] Eric Balkanski, Vasilis Gkatzelis, and Xizhi Tan. Strategyproof scheduling with predictions. In Proceedings of the 14th Innovations in Theoretical Computer Science Conference (ITCS), page 11, 2023. Banerjee et al. [2022] Siddhartha Banerjee, Vasilis Gkatzelis, Artur Gorokh, and Billy Jin. Online nash social welfare maximization with predictions. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1–19. SIAM, 2022. Barman et al. [2022] Siddharth Barman, Arindam Khan, and Arnab Maiti. Universal and tight online algorithms for generalized-mean welfare. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI), pages 4793–4800, 2022. Barman et al. [2023] Siddharth Barman, Arindam Khan, Sudarshan Shyam, and KVN Sreenivas. Guaranteeing envy-freeness under generalized assignment constraints. In Proceedings of the 24th ACM Conference on Economics and Computation (EC), pages 242–269, 2023. Benade et al. [2018] Gerdus Benade, Aleksandr M Kazachkov, Ariel D Procaccia, and Christos-Alexandros Psomas. How to make envy vanish over time. In Proceedings of the 19th ACM Conference on Economics and Computation (EC), pages 593–610, 2018. Benadè et al. [2024] Gerdus Benadè, Aleksandr M. Kazachkov, Ariel D. Procaccia, Alexandros Psomas, and David Zeng. Fair and efficient online allocations. Operations Research, 72(4):1438–1452, 2024. Benadè et al. [2025] Gerdus Benadè, Daniel Halpern, and Alexandros Psomas. Dynamic fair division with partial information. Operations Research, 73(4):1876–1896, 2025. Budish [2011] Eric Budish. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy, 119(6):1061–1103, 2011. Caragiannis and Narang [2023] Ioannis Caragiannis and Shivika Narang. Repeatedly matching items to agents fairly and efficiently. In Proceedings of the 16th International Symposium on Algorithmic Game Theory (SAGT), pages 347–364, 2023. Caragiannis et al. [2019a] Ioannis Caragiannis, Nick Gravin, and Xin Huang. Envy-freeness up to any item with high nash welfare: The virtue of donating items. In Proceedings of the 20th ACM Conference on Economics and Computation (EC), pages 527–545, 2019a. Caragiannis et al. [2019b] Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D Procaccia, Nisarg Shah, and Junxing Wang. The unreasonable fairness of maximum nash welfare. ACM Transactions on Economics and Computation, 7(3):1–32, 2019b. Chaudhury et al. [2021] Bhaskar Ray Chaudhury, Telikepalli Kavitha, Kurt Mehlhorn, and Alkmini Sgouritsa. A little charity guarantees almost envy-freeness. SIAM Journal on Computing, 50(4):1336–1358, 2021. Choo et al. [2026] Davin Choo, Winston Fu, Derek Khu, Tzeh Yuan Neoh, Tze-Yang Poon, and Nicholas Teh. Approximate proportionality in online fair division. In Proceedings of the 43rd International Conference on Machine Learning (ICML), 2026. Cohen et al. [2024] Ilan R Cohen, Alon Eden, Talya Eden, and Arsen Vasilyan. Plant-and-steal: Truthful fair allocations via predictions. In Proceedings of the 38th International Conference on Neural Information Processing Systems (NeurIPS), pages 110057–110096, 2024. Cohen and Panigrahi [2023] Ilan Reuven Cohen and Debmalya Panigrahi. A general framework for learning-augmented online allocation. In Proceedings of the 50th International Colloquium on Automata, Languages, and Programming (ICALP), pages 43:1–43:21, 2023. Cohen [2026] Saar Cohen. Delayed assignments in online non-centroid clustering with stochastic arrivals. In Proceedings of the 25th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 1091–1100, 2026. Cohen and Agmon [2023] Saar Cohen and Noa Agmon. Online coalitional skill formation. In Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 494–503, 2023. Cohen and Agmon [2024a] Saar Cohen and Noa Agmon. Online learning of partitions in additively separable hedonic games. In Proceedings of the 33rd International Joint Conference on Artificial Intelligence (IJCAI), pages 2722–2730, 2024a. Cohen and Agmon [2024b] Saar Cohen and Noa Agmon. Online friends partitioning under uncertainty. In Proceedings of the 27th European Conference on Artificial Intelligence (ECAI), pages 3332–3339. IOS Press, 2024b. Cohen and Agmon [2025a] Saar Cohen and Noa Agmon. Decentralized online learning by selfish agents in coalition formation. In Proceedings of the 34th International Joint Conference on Artificial Intelligence (IJCAI), 2025a. Cohen and Agmon [2025b] Saar Cohen and Noa Agmon. Online learning of fair coalition structures. In Proceedings of the 28th European Conference on Artificial Intelligence (ECAI), pages 4937–4944, 2025b. Cohen and Agmon [2025c] Saar Cohen and Noa Agmon. Online learning of coalition structures by selfish agents. In Proceedings of the 39th AAAI Conference on Artificial Intelligence (AAAI), pages 13709–13717, 2025c. Cookson et al. [2025] Benjamin Cookson, Soroush Ebadian, and Nisarg Shah. Temporal fair division. In Proceedings of the 39th AAAI Conference on Artificial Intelligence (AAAI), pages 13727–13734, 2025. Elkind et al. [2022] Edith Elkind, Sonja Kraiczy, and Nicholas Teh. Fairness in temporal slot assignment. In Proceedings of the 15th International Symposium on Algorithmic Game Theory (SAGT), pages 490–507, 2022. Elkind et al. [2024a] Edith Elkind, Ayumi Igarashi, and Nicholas Teh. Fair division of chores with budget constraints. In Proceedings of the 17th International Symposium on Algorithmic Game Theory (SAGT), pages 55–71, 2024a. Elkind et al. [2024b] Edith Elkind, Tzeh Yuan Neoh, and Nicholas Teh. Temporal elections: Welfare, strategyproofness, and proportionality. In Proceedings of the 27th European Conference on Artificial Intelligence (ECAI), pages 3292–3299, 2024b. Elkind et al. [2024c] Edith Elkind, Svetlana Obraztsova, and Nicholas Teh. Temporal fairness in multiwinner voting. In Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI), pages 22633–22640, 2024c. Elkind et al. [2025a] Edith Elkind, Alexander Lam, Mohamad Latifian, Tzeh Yuan Neoh, and Nicholas Teh. Temporal fair division of indivisible items. In Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 676–685, 2025a. Elkind et al. [2025b] Edith Elkind, Tzeh Yuan Neoh, and Nicholas Teh. Not in my backyard! temporal voting over public chores. In Proceedings of the 34th International Joint Conference on Artificial Intelligence (IJCAI), pages 3814–3820, 2025b. Elkind et al. [2025c] Edith Elkind, Svetlana Obraztsova, Jannik Peters, and Nicholas Teh. Verifying proportionality in temporal voting. In Proceedings of the 39th AAAI Conference on Artificial Intelligence (AAAI), pages 13805–13813, 2025c. Feldman et al. [2009] Jon Feldman, Nitish Korula, Vahab Mirrokni, Shanmugavelayutham Muthukrishnan, and Martin Pál. Online ad assignment with free disposal. In Proceedings of the 5th International Workshop on Internet and Network Economics (WINE), pages 374–385. Springer, 2009. Friedman et al. [2015] Eric Friedman, Christos-Alexandros Psomas, and Shai Vardi. Dynamic fair division with minimal disruptions. In Proceedings of the 16th ACM conference on Economics and Computation (EC), pages 697–713, 2015. Gan et al. [2023] Jiarui Gan, Bo Li, and Xiaowei Wu. Approximation algorithm for computing budget-feasible ef1 allocations. In Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 170–178, 2023. Goldberg et al. [2026] Paul Goldberg, Isaac Robinson, and Nicholas Teh. Minimizing cumulative envy in allocating a sequence of items. In Proceedings of the 19th International Symposium on Algorithmic Game Theory (SAGT), 2026. He et al. [2019] Jiafan He, Ariel D Procaccia, Alexandros Psomas, and David Zeng. Achieving a fairer future by changing the past. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pages 343–349, 2019. Huang et al. [2018] Zhiyi Huang, Ning Kang, Zhihao Gavin Tang, Xiaowei Wu, Yuhao Zhang, and Xue Zhu. How to match when all vertices arrive online. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 17–29, 2018. Huang et al. [2025] Zhiyi Huang, Chui Shan Lee, Xinkai Shu, and Zhaozi Wang. The long arm of Nashian allocation in online p-mean welfare maximization. In Proceedings of the 52nd International Colloquium on Automata, Languages, and Programming (ICALP), pages 98:1–98:18, 2025. Kalyanasundaram and Pruhs [2000] Bala Kalyanasundaram and Kirk Pruhs. Speed is as powerful as clairvoyance. Journal of the ACM, 47(4):617–643, 2000. Karp et al. [1990] Richard M Karp, Umesh V Vazirani, and Vijay V Vazirani. An optimal algorithm for on-line bipartite matching. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC), pages 352–358, 1990. Li et al. [2018] Bo Li, Wenyang Li, and Yingkai Li. Dynamic fair division problem with general valuations. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI), pages 375–381, 2018. Lim et al. [2026] Eugene Lim, Tzeh Yuan Neoh, and Nicholas Teh. Fairness in repeated matching: A maximin perspective. In Proceedings of the 40th AAAI Conference on Artificial Intelligence (AAAI), pages 17111–17119, 2026. Lipton et al. [2004] Richard J Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi. On approximately fair allocations of indivisible goods. In Proceedings of the 5th ACM Conference on Electronic Commerce (EC), pages 125–131, 2004. Lykouris and Vassilvitskii [2021] Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. Journal of the ACM, 68(4):1–25, 2021. Martello and Toth [1990] Silvano Martello and Paolo Toth. Knapsack problems: algorithms and computer implementations. John Wiley & Sons, Inc., 1990. Mehta et al. [2007] Aranyak Mehta, Amin Saberi, Umesh Vazirani, and Vijay Vazirani. Adwords and generalized online matching. Journal of the ACM, 54(5):22–es, 2007. Mitzenmacher and Vassilvitskii [2021] Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with Predictions, page 646–662. Cambridge University Press, 2021. Neoh and Teh [2025] Tzeh Yuan Neoh and Nicholas Teh. Understanding efx allocations: Counting and variants. In Proceedings of the 39th AAAI Conference on Artificial Intelligence (AAAI), pages 14036–14044, 2025. Neoh et al. [2026] Tzeh Yuan Neoh, Jannik Peters, and Nicholas Teh. Online fair division with additional information. In Proceedings of the 43rd International Conference on Machine Learning (ICML), 2026. Phillips et al. [2026] Bradley Phillips, Edith Elkind, Nicholas Teh, and Tomasz Wąs. Strengthening proportionality in temporal voting. In Proceedings of the 25th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 3823–3832, 2026. Purohit et al. [2018] Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ml predictions. In Proceedings of the 32nd International Conference on Neural Information Processing Systems (NeurIPS), 2018. Roughgarden [2021] Tim Roughgarden. Beyond the worst-case analysis of algorithms. Cambridge University Press, 2021. Spaeh and Ene [2023] Fabian Spaeh and Alina Ene. Online ad allocation with predictions. In Proceedings of the 37th International Conference on Neural Information Processing Systems (NeurIPS), pages 17265–17295, 2023. Springer et al. [2022] Max Springer, MohammadTaghi Hajiaghayi, Debmalya Panigrahi, and Mohammad Khani. Online algorithms for the Santa Claus problem. In Proceedings of the 36th International Conference on Neural Information Processing Systems (NeurIPS), pages 30732–30743, 2022. Suksompong [2021] Warut Suksompong. Constraints in fair division. ACM SIGecom Exchanges, 19(2):46–61, 2021. Teh [2026] Nicholas Teh. The price of proportional representation in temporal voting. Proceedings of the 35th International Joint Conference on Artificial Intelligence (IJCAI), 2026. Wang and Wong [2015] Yajun Wang and Sam Chiu-wai Wong. Two-sided online bipartite matching and vertex cover: Beating the greedy algorithm. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP), pages 1070–1081. Springer, 2015. Wang and Wei [2026] Yuanyuan Wang and Tianze Wei. Online fair allocations with binary valuations and beyond. In Proceedings of the 40th AAAI Conference on Artificial Intelligence (AAAI), pages 17267–17275, 2026. Wu et al. [2021] Xiaowei Wu, Bo Li, and Jiarui Gan. Budget-feasible maximum nash social welfare is almost envy-free. In Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI), pages 465–471, 2021. Zech et al. [2024] Valentin Zech, Niclas Boehmer, Edith Elkind, and Nicholas Teh. Multiwinner temporal voting with aversion to change. In Proceedings of the 27th European Conference on Artificial Intelligence (ECAI), pages 3236–3243, 2024. Zeng and Psomas [2020] David Zeng and Alexandros Psomas. Fairness-efficiency tradeoffs in dynamic fair division. In Proceedings of the 21st ACM Conference on Economics and Computation (EC), pages 911–912, 2020. Zhou et al. [2023] Shengwei Zhou, Rufan Bai, and Xiaowei Wu. Multi-agent online scheduling: Mms allocations for indivisible items. In Proceedings of the 40th International Conference on Machine Learning (ICML), pages 42506–42516, 2023. Zhou et al. [2008] Yunhong Zhou, Deeparnab Chakrabarty, and Rajan M. Lukose. Budget constrained bidding in keyword auctions and online knapsack problems. In Proceedings of the 17th International Conference on World Wide Web (W), pages 1243–1244, 2008. Appendix A Additional Related Work A.1 Online Fair Division As discussed in Section 2, our work is closely related to the literature on online fair division, where goods arrive sequentially and must be allocated without knowledge of future arrivals. The area was introduced by Aleksandrov et al. [2], motivated by applications such as food banks, and has since grown substantially. A large body of work studies the interplay between fairness and efficiency in online allocation. Beyond the original food bank model, which assumes binary additive valuations [2], subsequent works consider general additive valuations and investigate fairness notions such as vanishing envy [11], the compatibility of fairness and approximate Pareto efficiency [66], and dynamic information models in which only partial information about future items is available [13]. Other works instead optimize social welfare objectives such as egalitarian welfare under online arrivals [59], while additional variants study dynamic reallocations [38, 41, 46], the use of reordering buffers [5], restricted valuations structures [4, 63] and related online allocation models. These works differ fundamentally from our setting in two respects. First, they assume that every arriving good is allocated to some agent, whereas budget constraints in our model may require goods to be assigned to charity. Second, fairness is evaluated with respect to entire bundles, whereas our model compares only budget-feasible subsets of recipients’ bundles. Consequently, the techniques and guarantees developed for classical online fair division do not directly extend to the budget-constrained setting considered in this paper. A.2 Semi-Online Fair Division A rapidly growing line of work studies semi-online (or learning-augmented) fair division, where the online algorithm has access to side information about future arrivals, typically obtained from historical data. Much of this literature considers divisible goods and uses predictions to improve welfare objectives such as Nash social welfare or more general welfare functions. Existing prediction models include monopolist-value predictions [8], normalization information [9, 43], and related forms of aggregate information about future items [21, 6]. Prediction models have also been studied for indivisible goods. Zhou et al. [67] initiated the study of learning-augmented online allocation of indivisible goods and chores under normalized valuations, focusing on maximin share (MMS) fairness. Building on this work, Neoh et al. [54] investigated predictions of aggregate values and value frequencies for achieving fairness notions such as MMS and EF1, while several subsequent works considered related prediction models for online allocation of indivisible items [58, 7, 20]. More recently, Choo et al. [19] studied PROP1 in online fair division with predictions. Besides establishing impossibility results against adaptive adversaries, they considered prediction models based on maximum item values and showed that these suffice to recover meaningful PROP1 guarantees, while stronger notions such as EF1 and MMS remain inapproximable under the same information model. Finally, Wang and Wei [63] investigated semi-online allocation of indivisible goods and chores under additive and submodular valuations, obtaining fairness and efficiency guarantees in a substantially weaker adversarial model than the fully adaptive setting considered here. Our learning-augmented framework differs fundamentally from these approaches. Rather than predicting aggregate values, normalization information, value frequencies, or maximum item values, we predict joint value-size types. This richer prediction model is necessitated by budget constraints: feasibility depends not only on the marginal distributions of values and sizes, but also on their correlation. Our necessity result shows that these correlations cannot, in general, be recovered from separate value and size predictions. A.3 Temporal Fair Division Recently, Elkind et al. [34] introduced the model of temporal fair division, in which indivisible goods or chores arrive sequentially according to a fixed sequence that is known in advance, and the objective is to maintain approximately fair allocations throughout the process. Cookson et al. [29] study a closely related model, considering alternative fairness notions and their simultaneous satisfaction over allocation prefixes and in the final allocation. Recently, Goldberg et al. [40] study the problem of minimizing cumulative envy in this setting. These models differ fundamentally from ours in the information available to the algorithm. Temporal fair division assumes complete knowledge of all future arrivals and agents’ valuations, allowing the allocation to be planned over the entire sequence. In contrast, we study the online setting, in which future goods are unknown unless explicitly predicted, and allocation decisions must be made irrevocably as goods arrive. Moreover, temporal fair division does not consider the budget constraints and charity-based feasible fairness notions that are central to our work. A.4 Online Matching Online matching is one of the classical problems in online algorithms, originating with the seminal work of Karp et al. [45], who introduced the online bipartite matching problem and the Ranking algorithm with its optimal competitive ratio of 1−1/e1-1/e. A large body of subsequent work has extended this model in several directions, including weighted matchings [37], fully online matching where both sides of the graph arrive over time [62, 42], repeated matching [15, 47], and numerous other variants (e.g., slot assignment [30]). Our work shares the irrevocable decision-making paradigm of online matching: arriving objects must be assigned without knowledge of future arrivals. However, the optimization objective is fundamentally different. Online matching seeks to maximize the size or weight of the matching, whereas our goal is to produce fair allocations under generalized assignment budget constraints. Consequently, the notions of fairness, the role of budget feasibility, and the resulting algorithmic techniques differ substantially from those studied in the online matching literature. A.5 Additional Related Online Problems Other related online settings include online coalition formation [25, 24, 28, 26, 22, 23, 27], concerns forming or learning partitions of agents, and temporal voting [3, 33, 61, 55, 35, 36, 32, 65], which concerns repeated collective choices and notions of representation or fairness across time. These models are related to ours primarily through their sequential decision-making structure. In contrast, our setting requires the irrevocable allocation of arriving indivisible goods under per-agent budgets, with unallocated goods retained by charity and fairness evaluated through budget-feasible comparisons. Appendix B Omitted Proofs for Section 4 B.1 Proof of Theorem 4.1 See 4.1 Proof. Fix k≥0k≥ 0 and α∈(0,1]α∈(0,1]. We first describe a phase simulation that identifies a hard stopping phase. Since the algorithm is deterministic, the stopping phase identified by this simulation determines a fixed finite input sequence; we formalize this point at the end of the proof. We construct an adversarial instance in which every good has the same size 1/Q1/Q, where Q is chosen sufficiently large. Since each agent has budget 11, no agent can receive more than Q goods. Choose an integer Q>kQ>k sufficiently large that τ:=⌊α(Q−k)4⌋≥1.τ:= α(Q-k)4 ≥ 1. (1) Such a choice is possible because α(Q−k)/4→∞α(Q-k)/4→∞ as Q→∞Q→∞. The quantity τ will serve as the minimum number of goods that each agent must receive from every phase in order to avoid an immediate violation of α-FEFkk. Note τ≥1τ≥ 1 is an integer and, by the definition of the floor function, τ≤α(Q−k)4.τ≤ α(Q-k)4. (2) Choose an integer L satisfying Lτ>Q.Lτ>Q. (3) Such a choice is possible because τ≥1τ≥ 1. We will partition the construction into L phases and set the (known) horizon to T=3QLT=3QL so that each phase consists of exactly 3Q3Q goods. It remains to specify the values of the goods released in each phase. Let V1,…,VLV_1,…,V_L be positive numbers defined recursively by setting V1=1V_1=1 and, for every t≥2t≥ 2, choosing VtV_t large enough that Q∑r<tVr<α(Q−k)4Vt.Q _r<tV_r< α(Q-k)4\,V_t. (4) Thus, the total value of all goods that an agent could possibly retain from earlier phases is dominated by the value contributed by only a constant fraction of the goods released in phase t. Such a sequence always exists. For example, one may take Vt=8Qα(Q−k)∑r<tVr,t≥2,V_t= 8Qα(Q-k) _r<tV_r, t≥ 2, which satisfies (4) since it gives Q∑r<tVr=α(Q−k)8Vt<α(Q−k)4VtQ _r<tV_r= α(Q-k)8V_t< α(Q-k)4V_t. In the remainder of the proof we use only property (4), not the explicit construction. For each phase t∈[L]t∈[L], choose a positive number dtd_t satisfying Qdt<α(Q−k)4Vt.Qd_t< α(Q-k)4V_t. (5) Such a choice is possible because Vt>0V_t>0. These values will be used only if the adversary terminates the phase construction early. The adversary proceeds in phases. During phase t, it releases 3Q3Q goods, each of value VtV_t and size 1/Q1/Q. After the phase is completed, it checks whether the algorithm satisfies the condition described below. If so, the adversary proceeds to the next phase. If not, it terminates the construction by replacing all remaining phases with dummy goods of value dtd_t and size 1/Q1/Q. Since exactly 3QL−3Qt3QL-3Qt goods remain to be released, the total number of goods is T=3QLT=3QL, regardless of the phase at which the construction terminates. The first observation is that, after every completed phase, at least Q goods from that phase must be assigned to charity. Indeed, phase t contains 3Q3Q goods, whereas the two agents together can hold at most 2Q2Q goods in total because every good has size 1/Q1/Q and both budgets are equal to 11. Consequently, at least 3Q−2Q=Q3Q-2Q=Q goods released during phase t must remain in charity. Suppose that, after completing phase t, one of the two agents, say agent i∈1,2i∈\1,2\, has received fewer than τ goods released during that phase. The adversary then terminates the phase construction and completes the remaining rounds using dummy goods of value dtd_t. We show that the resulting allocation violates α-FEFkk. By the previous observation, charity contains at least Q goods from phase t. Let S be any such set. Since every good has size 1/Q1/Q, si(S)=Q⋅1Q=1=Bis_i(S)=Q· 1Q=1=B_i, so S is feasible for agent i. Moreover, for every X⊆SX S with |X|≤k|X|≤ k, v(S∖X)≥(Q−k)Vt,v(S X)≥(Q-k)V_t, (6) because S∖XS X contains at least Q−kQ-k goods, each of value VtV_t. It remains to upper-bound the final value v(Ai)v(A_i) accumulated by agent i. The goods held by i fall into three categories: goods received during phase t, goods received in earlier phases, and dummy goods released after the construction terminates. First, by assumption, agent i receives fewer than τ goods from phase t. Hence, the total contribution of these goods is less than τVt≤α(Q−k)4Vt,τ V_t≤ α(Q-k)4V_t, where the inequality follows from the definition of τ, which satisfies τ≤α(Q−k)/4τ≤α(Q-k)/4 by (2). Second, agent i holds at most Q goods in total. If nr≤Qn_r≤ Q denotes the number of goods retained from phase r<tr<t, then ∑r<tnr≤Q _r<tn_r≤ Q, and therefore ∑r<tnrVr≤Q∑r<tVr<α(Q−k)4Vt, _r<tn_rV_r≤ Q _r<tV_r< α(Q-k)4V_t, where the final inequality follows from (4). Finally, every dummy good has value dtd_t, and agent i can hold at most Q goods altogether. Thus, the total value contributed by dummy goods is at most Qdt<α(Q−k)4VtQd_t< α(Q-k)4V_t by (5). Combining the three estimates gives us v(Ai)<3⋅α(Q−k)4Vt=3α(Q−k)4Vt<α(Q−k)Vt.v(A_i)<3· α(Q-k)4V_t= 3α(Q-k)4V_t<α(Q-k)V_t. (7) Together with (6), this implies that for every X⊆SX S with |X|≤k|X|≤ k, v(Ai)<α(Q−k)Vt≤αv(S∖X).v(A_i)<α(Q-k)V_t≤α\,v(S X). Hence, no set X⊆SX S with |X|≤k|X|≤ k satisfies the α-FEFkk inequality for the comparison set S, so the final allocation violates α-FEFkk. To complete the argument, suppose that the failure condition never occurs. Then, after every phase t∈[L]t∈[L], each agent must hold at least τ goods released during that phase. Since goods released in different phases are distinct, by the end of phase L each agent holds at least LτLτ goods. By (3), Lτ>QLτ>Q, contradicting the fact that each agent can hold at most Q goods. Therefore, the failure condition must occur after some phase t≤Lt≤ L, and the argument above shows that the resulting allocation violates α-FEFkk. Although the phase construction was described adaptively, it yields a fixed hard input for the deterministic algorithm. Simulate the construction above and let t⋆t be the first phase at which the failure condition occurs. Before the actual execution, fix the input sequence consisting of phases 1,…,t⋆1,…,t , followed by exactly 3Q(L−t⋆)3Q(L-t ) dummy goods of value dt⋆d_t and size 1/Q1/Q. A fresh execution of the algorithm on this fixed sequence has the same announced horizon T=3QLT=3QL and the same observed arrival prefix through phase t⋆t as the simulation. Determinism therefore forces the algorithm to make the same assignments through that phase. The violation established above consequently occurs on this fixed input sequence. Hence, the lower bound holds even against an oblivious adversary. Finally, observe that the constructed instance satisfies all the restrictions stated in the theorem. There are two agents with equal budgets B1=B2=1B_1=B_2=1; every good has the same size 1/Q1/Q; valuations are common across agents; and the horizon is fixed to T=3QLT=3QL and announced in advance. Thus, the impossibility holds even under assumptions (1)–(5). ∎ B.2 Proof of Corollary 4.3 See 4.3 Proof. Apply Corollary˜4.2 with the value Q chosen in the proof of Theorem˜4.1, and let q=Qq=Q. Since every good has size 1/Q1/Q and every budget is 11, a set S is feasible for an agent if and only if |S|≤Q|S|≤ Q. For an instance I, recall that its maximum feasible comparison cardinality is κ(I):=maxi∈Nmax|S|:S⊆G,si(S)≤Biκ(I):= _i∈ N \|S|:S G,s_i(S)≤ B_i\. Hence, every hard instance satisfies κ(I)=Q=qκ(I)=Q=q, and the same construction establishes the claimed impossibility. ∎ Appendix C Omitted Proofs for Section 5 C.1 Proof of Theorem 5.1 See 5.1 Proof. Fix an agent i, a recipient r, and a nonempty feasible set S⊆ArS A_r. If v(S)=0v(S)=0, then v(S∖x)=0v(S \x\)=0 for every x∈Sx∈ S, and the claim is immediate. Assume therefore that v(S)>0v(S)>0. Let f be the last-arriving good in S with v(f)>0v(f)>0, and set x=fx=f. Every positively valued good in S∖fS \f\ arrived before f, while zero-value goods do not affect the value of S∖fS \f\ under v(⋅)v(·). We distinguish two cases according to whether f was feasible for agent i when it arrived. For the analysis below, we write Ah<fA_h^<f for the bundle held by agent h immediately before processing a good f. Case 1: f was feasible for agent i when it arrived. That is, suppose that si(Ai<f)+si(f)≤Bis_i(A_i^<f)+s_i(f)≤ B_i. Then, i∈Ffi∈ F_f. Since v(f)>0v(f)>0 and Ff≠∅F_f≠ , Positive-GreedyFit assigned f to an agent rather than to charity, so r=jr=j for some agent j∈Nj∈ N and thus f∈Ajf∈ A_j. Since both i and j were feasible when f arrived, and f was assigned to agent j, the greedy min-value choice in line 6 implies v(Aj<f)≤v(Ai<f)v(A_j^<f)≤ v(A_i^<f). Every positively valued good in S∖fS \f\ lies in Ar=AjA_r=A_j and arrived before f, and hence belongs to Aj<fA^<f_j. Therefore v(S∖f)≤v(Aj<f)≤v(Ai<f)≤v(Ai).v(S \f\)≤ v(A_j^<f)≤ v(A_i^<f)≤ v(A_i). Thus v(Ai)≥v(S∖f)≥Γi−1v(S∖f),v(A_i)≥ v(S \f\)≥ _i^-1v(S \f\), which is stronger than required (the factor satisfies 1≥Γi−11≥ _i^-1). Case 2: f was not feasible for agent i when it arrived. That is, suppose instead that si(Ai<f)+si(f)>Bis_i(A_i^<f)+s_i(f)>B_i. Since S is feasible for agent i and f∈Sf∈ S, si(S∖f)≤Bi−si(f)<si(Ai<f).s_i(S \f\)≤ B_i-s_i(f)<s_i(A_i^<f). Since Positive-GreedyFit assigns a good to an agent only if it has positive value, every good in Ai<fA_i^<f has density at least ρiminρ _i. Hence v(Ai<f)=∑g∈Ai<fρi(g)si(g)≥ρiminsi(Ai<f).v(A_i^<f)= _g∈ A_i^<f _i(g)s_i(g)≥ρ _i\,s_i(A_i^<f). Likewise, v(S∖f)≤ρimaxsi(S∖f),v(S \f\)≤ρ _i\,s_i(S \f\), since every positively valued good in S∖fS \f\ has density at most ρimaxρ _i, while zero-value goods contribute nothing. Combining these inequalities yields v(S∖f)≤ρimaxsi(S∖f)<ρimaxsi(Ai<f)≤ρimaxρiminv(Ai<f)=Γiv(Ai<f)≤Γiv(Ai).v(S \f\)≤ρ _i\,s_i(S \f\)<ρ _i\,s_i(A_i^<f)≤ ρ _iρ _iv(A_i^<f)= _i\,v(A_i^<f)≤ _i\,v(A_i). Therefore, rearranging gives us v(Ai)≥Γi−1v(S∖f).v(A_i)≥ _i^-1v(S \f\). The desired inequality holds in both cases. Since Γi≤Γ _i≤ for every agent i, the allocation is Γ−1 ^-1-FEF11. If Γ=1 =1, then every Γi=1 _i=1, and the guarantee becomes exact FEF11. ∎ C.2 Proof of Theorem C.1 Common valuations require all agents to agree on the value of every good. A natural relaxation allows agents to differ only by an individual scaling factor while preserving the common ranking of goods. Formally, each agent i has valuation vi(g)=βiv(g)v_i(g)= _iv(g), where v is a common base valuation and βi>0 _i>0 is an agent-specific scaling factor. The same algorithm from Section 5.1 can be applied without modification by using the common base valuation v in the greedy algorithm. Indeed, multiplying all values of a single agent by the positive constant βi _i does not change the relative ordering of that agent’s goods. Moreover, the density spread is unchanged, since Γi=ρimaxρimin _i= _i _i by Definition˜3.2 and the common factor βi _i cancels. Thus, we run Positive-GreedyFit exactly as in the common-valuation setting, using the base valuation v. Theorem C.1. Under scaled-common valuations, Positive-GreedyFit run with the base valuation v, or with any positive scalar multiple of v, guarantees Γ−1 ^-1-FEF1. Proof. Apply Theorem 5.1 to the common base valuation v. For every agent i, recipient r, and nonempty feasible set S⊆ArS A_r, there is a good x∈Sx∈ S such that v(Ai)≥Γi−1v(S∖x)v(A_i)≥ _i^-1v(S \x\). Since vi=βiv_i= _iv and βi>0 _i>0, multiplying both sides by βi _i gives vi(Ai)≥Γi−1vi(S∖x)v_i(A_i)≥ _i^-1v_i(S \x\). Positive scaling does not change which goods are individually feasible or the density ratio Γi _i. Therefore, the allocation is Γ−1 ^-1-FEF1. ∎ C.3 Pseudocode of Hetero-GreedyFit Algorithm 3 Hetero-GreedyFit 1:Initialize Ai←∅A_i← for all i∈Ni∈ N and AC←∅A_C← . 2:for each arriving good g do 3: Fg+=i∈N:si(Ai)+si(g)≤Bi&vi(g)>0F_g^+=\i∈ N:s_i(A_i)+s_i(g)≤ B_i\ \&\ v_i(g)>0\. 4: if Fg+=∅F_g^+= then assign g to charity. 5: else assign g to an arbitrary i∗∈argmini∈Fg+vi(Ai)i^*∈ _i∈ F_g^+v_i(A_i), using a fixed tie-breaker. 6:return A=(A1,…,An,AC)A=(A_1,…,A_n,A_C). C.4 Proof of Theorem 5.2 See 5.2 Proof. Fix an agent i, a recipient r, and a nonempty feasible set S⊆ArS A_r. If vi(S)=0v_i(S)=0, then the claim is immediate. Assume therefore that vi(S)>0v_i(S)>0. Let f denote the last-arriving good in S with vi(f)>0v_i(f)>0, and set x=fx=f. Every positively valued good in S∖fS \f\ arrived before f. We distinguish two cases according to whether f was feasible for agent i when it arrived. Case 1: f was feasible for agent i when it arrived. That is, suppose that si(Ai<f)+si(f)≤Bis_i(A_i^<f)+s_i(f)≤ B_i. Then i∈Ff+i∈ F_f^+ since vi(f)>0v_i(f)>0 and f was feasible for agent i when it arrived. Therefore, the set Ff+F_f^+ is nonempty, so Hetero-GreedyFit assigns f to an agent, say j. Consequently, r=jr=j and f∈Ajf∈ A_j. Moreover, vj(f)>0v_j(f)>0, since only positively valuing agents belong to Ff+F_f^+ (i.e., Hetero-GreedyFit assigns f to j only if j∈Ff+j∈ F_f^+). Since both i and j belong to Ff+F_f^+, the min-value choice in line 5 gives vj(Aj<f)≤vi(Ai<f).v_j(A_j^<f)≤ v_i(A_i^<f). (8) Now, consider any good h∈S∖fh∈ S \f\ with vi(h)>0v_i(h)>0. Then h∈Ar=Ajh∈ A_r=A_j and h arrived before f, so h∈Aj<fh∈ A^<f_j. Moreover, h was assigned to j only if j∈Fh+j∈ F_h^+, so vj(h)>0v_j(h)>0. Therefore, the definition of χi _i implies vi(h)≤χivj(h)v_i(h)≤ _iv_j(h). Summing over the (positively i-valued) goods of S∖fS \f\, and using the fact that these goods are distinct members of Aj<fA^<f_j with nonnegative vjv_j, vi(S∖f)=∑h∈S∖fvi(h)>0vi(h)≤χi∑h∈S∖fvi(h)>0vj(h)≤χivj(Aj<f)≤(8)χivi(Ai<f)≤χivi(Ai).v_i(S \f\)= _ subarraych∈ S \f\\\ v_i(h)>0 subarrayv_i(h)≤ _i _ subarraych∈ S \f\\\ v_i(h)>0 subarrayv_j(h)≤ _iv_j(A_j^<f) eq:hetgreedy≤ _iv_i(A_i^<f)≤ _iv_i(A_i). Hence vi(Ai)≥χi−1vi(S∖f)≥Λi−1vi(S∖f).v_i(A_i)≥ _i^-1v_i(S \f\)≥ _i^-1v_i(S \f\). Case 2: f was not feasible for agent i when it arrived. That is, suppose instead that si(Ai<f)+si(f)>Bis_i(A_i^<f)+s_i(f)>B_i. Exactly as in the proof of Theorem 5.1, si(S∖f)<si(Ai<f).s_i(S \f\)<s_i(A_i^<f). Hetero-GreedyFit assigns a good to i only when it has positive value for agent i, so every good in Ai<fA^<f_i has positive value for agent i and density at least ρiminρ _i. Hence, vi(Ai<f)≥ρiminsi(Ai<f),v_i(A_i^<f)≥ρ _is_i(A_i^<f), whereas vi(S∖f)≤ρimaxsi(S∖f).v_i(S \f\)≤ρ _is_i(S \f\). Therefore vi(S∖f)<ρimaxsi(Ai<f)≤Γivi(Ai<f)≤Γivi(Ai),v_i(S \f\)\ <\ ρ _i\,s_i(A^<f_i)\ ≤\ _i\,v_i(A^<f_i)\ ≤\ _i\,v_i(A_i), which implies vi(Ai)≥Γi−1vi(S∖f)≥Λi−1vi(S∖f).v_i(A_i)≥ _i^-1v_i(S \f\)≥ _i^-1v_i(S \f\). The desired inequality holds in both cases. Since Λi≤Λ _i≤ for every agent, we have Λi−1≥Λ−1 _i^-1≥ ^-1, which implies that vi(Ai)≥Λ−1vi(S∖f).v_i(A_i)≥ ^-1v_i(S \f\). Taking the worst case over i, r, and S shows that the allocation is Λ−1 ^-1-FEF11. ∎ Appendix D Omitted Proofs for Section 6 D.1 Pseudocode of Aug-GreedyFit(ε)( ) Algorithm 4 Aug-GreedyFit(ε)( ) 1:Initialize Ai←∅A_i← for all i∈Ni∈ N and AC←∅A_C← . 2:for each arriving good g do 3: if v(g)=0v(g)=0 then assign g to charity. 4: else let Fg:=i∈N:si(g)≤Biandsi(Ai)+si(g)≤(1+ε)BiF_g:=\i∈ N:s_i(g)≤ B_i\ and\ s_i(A_i)+s_i(g)≤(1+ )B_i\. 5: if Fg=∅F_g= then assign g to charity. 6: else Assign g to an arbitrary i∗∈argminh∈Fgv(Ah)i^*∈ _h∈ F_gv(A_h), using a fixed tie-breaking order. 7:return A=(A1,…,An,AC)A=(A_1,…,A_n,A_C). D.2 Proof of Theorem 6.1 See 6.1 Proof. The size bound si(Ai)≤(1+ε)Bis_i(A_i)≤(1+ )B_i follows directly from the feasibility test in the algorithm. It therefore remains to prove the fairness guarantee. Fix an agent i, a recipient r, and a nonempty set S⊆ArS A_r feasible for agent i under the original budget, i.e., si(S)≤Bis_i(S)≤ B_i. If v(S)=0v(S)=0, choose any x∈Sx∈ S. Then v(Ai)≥0=v(S∖x),v(A_i)≥ 0=v(S \x\), so the required inequality holds. Henceforth assume v(S)>0v(S)>0. Let f denote the last-arriving positively valued good in S, and set x=fx=f. Every other positively valued good in S∖fS \f\ arrived before f. As in the proof of Theorem˜5.1, we distinguish two cases according to whether f was feasible for agent i under the algorithmic budget. As before, let Ah<fA_h^<f be the bundle held by agent h immediately before processing a good f. Case 1: f was feasible for agent i under the augmented budget at its arrival. That is, suppose that si(Ai<f)+si(f)≤(1+ε)Bis_i(A_i^<f)+s_i(f)≤(1+ )B_i. Since f∈Sf∈ S and S is feasible for agent i under the original budget, we also have si(f)≤Bis_i(f)≤ B_i. Hence both eligibility conditions in Algorithm 4 hold for agent i, so i∈Ffi∈ F_f. The min-value rule therefore assigned f to some agent j with v(Aj<f)≤v(Ai<f)v(A_j^<f)≤ v(A_i^<f). Every positively valued good of S∖fS \f\ lies in Ar=AjA_r=A_j and arrived before f, and therefore belongs to Aj<fA_j^<f. Hence, v(S∖f)≤v(Aj<f)≤v(Ai<f)≤v(Ai),v(S \f\)≤ v(A_j^<f)≤ v(A_i^<f)≤ v(A_i), which is the claim with factor 11. Note that this is stronger than the desired guarantee. Case 2: f was not feasible for agent i under the augmented budget at its arrival. That is, suppose instead that si(Ai<f)+si(f)>(1+ε)Bis_i(A_i^<f)+s_i(f)>(1+ )B_i. Then si(Ai<f)>(1+ε)Bi−si(f).s_i(A_i^<f)>(1+ )B_i-s_i(f). Since S is feasible under the original budget, si(S∖f)≤Bi−si(f).s_i(S \f\)≤ B_i-s_i(f). If v(S∖f)=0v(S \f\)=0, the required inequality is immediate. We may therefore assume that v(S∖f)>0v(S \f\)>0. In particular, since every good has positive size, si(f)<Bis_i(f)<B_i. Let c:=si(f)c:=s_i(f). Since f∈Sf∈ S and S is feasible for i, we have si(f)≤Bis_i(f)≤ B_i. Therefore, if f was not eligible for i, the failed eligibility condition must be the total online budget condition: si(Ai<f)>(1+ε)Bi−c.s_i(A_i^<f)>(1+ )B_i-c. Every good in Ai<fA_i^<f has positive value, so v(Ai)≥v(Ai<f)≥ρiminsi(Ai<f)>ρimin((1+ε)Bi−c).v(A_i)≥ v(A_i^<f)≥ _i s_i(A_i^<f)> _i ((1+ )B_i-c). On the other hand, v(S∖f)≤ρimaxsi(S∖f)≤ρimax(Bi−c).v(S \f\)≤ _i s_i(S \f\)≤ _i (B_i-c). Therefore, v(Ai)>ρiminρimax(1+ε)Bi−cBi−cv(S∖f)=Γi−1(1+εBiBi−c)v(S∖f)≥Γi−1(1+ε)v(S∖f).v(A_i)> _i _i (1+ )B_i-cB_i-cv(S \f\)= _i^-1 (1+ B_iB_i-c )v(S \f\)≥ _i^-1(1+ )v(S \f\). In both cases, v(Ai)≥min1,Γi−1(1+ε)v(S∖f).v(A_i)≥ \1, _i^-1(1+ )\v(S \f\). Since Γi≤Γ _i≤ , min1,Γi−1(1+ε)≥min1,1+εΓ, \1, _i^-1(1+ )\≥ \1, 1+ \, and taking the worst case over i, r, and S proves the stated min1,(1+ε)/Γ \1,(1+ )/ \-FEF11 guarantee. Finally, if ε≥Γ−1 ≥ -1, then Γi−1(1+ε)≥Γ−1(1+ε)≥1 _i^-1(1+ )≥ ^-1(1+ )≥ 1 for every agent i. Hence, both cases yield factor 11, and the allocation is exactly FEF11. ∎ D.3 Proof of Theorem 6.2 See 6.2 Proof. Fix k, α, and ε . As in the proof of Theorem˜4.1, we first use a phase simulation to identify a hard stopping phase and then fix the resulting sequence before its actual execution. Choose an integer Q>kQ>k sufficiently large that τ:=⌊α(Q−k)4⌋≥1.τ:= α(Q-k)4 ≥ 1. Every good will have size 1/Q1/Q. Under online budget 1+ε1+ , each agent can hold at most M:=⌊(1+ε)Q⌋M:= (1+ )Q goods. Choose an integer L satisfying Lτ>MLτ>M. Each phase will contain P:=2M+QP:=2M+Q goods, and the known horizon is T:=LPT:=LP. Let V1:=1V_1:=1. For every t≥2t≥ 2, choose Vt>0V_t>0 so that M∑r<tVr<α(Q−k)4Vt.M _r<tV_r< α(Q-k)4V_t. For each t∈[L]t∈[L], also choose dt>0d_t>0 so that Mdt<α(Q−k)4Vt.Md_t< α(Q-k)4V_t. In phase t, release P goods, each having common value VtV_t and common size 1/Q1/Q. After the phase, check whether each agent has received at least τ goods from that phase. If some agent has received fewer than τ such goods, fill every remaining round with goods of common value dtd_t and common size 1/Q1/Q. First observe that charity receives at least Q goods from every completed phase. Indeed, the two agents together can hold at most 2M2M goods over the entire execution, whereas the phase contains 2M+Q2M+Q goods. Suppose that after phase t, agent i has received fewer than τ goods from that phase. Let S be any Q phase-t goods in charity. Then S is feasible under the original budget, because si(S)=Q⋅1Q=1s_i(S)=Q· 1Q=1. For every X⊆SX S with |X|≤k|X|≤ k, v(S∖X)≥(Q−k)Vt.v(S X)≥(Q-k)V_t. We now bound the final value of agent i. Its phase-t goods contribute less than τVt≤α(Q−k)4Vt.τ V_t≤ α(Q-k)4V_t. The agent holds at most M goods in total, so its goods from earlier phases contribute at most M∑r<tVr<α(Q−k)4VtM _r<tV_r< α(Q-k)4V_t by (D.3). Its later dummy goods contribute at most Mdt<α(Q−k)4VtMd_t< α(Q-k)4V_t by (D.3). Therefore, v(Ai)<3α(Q−k)4Vt<α(Q−k)Vt.v(A_i)< 3α(Q-k)4V_t<α(Q-k)V_t. Together with (D.3), this gives v(Ai)<αv(S∖X)v(A_i)<α v(S X) for every X⊆SX S with |X|≤k|X|≤ k. Hence the final allocation is not α-FEFkk. It remains to show that such a phase must occur. If it never occurs, then each agent receives at least τ goods in every phase. After L phases, each agent therefore holds at least Lτ>MLτ>M goods, contradicting the definition of M. To see that the hard input may be fixed in advance, simulate the phase construction and let t⋆t be the first phase at which an agent receives fewer than τ goods from that phase. Fix the sequence consisting of phases 1,…,t⋆1,…,t , followed by exactly P(L−t⋆)P(L-t ) dummy goods of value dt⋆d_t and size 1/Q1/Q. A fresh execution has the same announced horizon and the same arrival prefix through phase t⋆t , so determinism forces the same assignments and hence the same violation. Thus, the lower bound holds against an oblivious adversary. All goods have common value across the two agents and uniform size 1/Q1/Q, the original budgets are equal to 11, and the announced horizon is T=LPT=LP. This proves the theorem. ∎ Appendix E Small-Good Limits under Common Valuations and Sizes Common Across Agents Sections 5 and 6 establish broad greedy guarantees that apply to arbitrary item sizes, but they leave a quantitative gap between the corresponding upper and lower bounds. In this appendix, we show that this gap disappears under a more structured model consisting of common valuations, sizes common across agents, and globally small goods. In this setting, the limiting deterministic approximation frontier can be characterized exactly. Our analysis pairs a threshold-based algorithm with a matching multi-agent lower bound, yielding a sharp limiting characterization of the optimal deterministic guarantee. The upper bound controls charity comparisons through the threshold policy, while balanced acceptance ensures exact FEF11 for all agent–agent comparisons. The frontier results in this appendix are established for a structured class of instances that combines the assumptions introduced individually in earlier sections. Definition E.1 (Structured class with bounded density spread). For γ≥1γ≥ 1, let ℐγcomI^com_γ be the class of instances satisfying: 1. valuations are common, so vi=v_i=v for every agent i; 2. sizes are common across agents, so si=s_i=s for every agent i; 3. every original budget equals 11; and 4. the realized density spread satisfies Γ≤γ ≤γ according to Definition 3.2. The algorithm is told the valid bound γ. The horizon model is stated separately in each theorem. Throughout this appendix, Γ denotes the realized density spread of the instance, whereas γ denotes the valid upper bound supplied to the algorithm. The case γ=1γ=1 is already covered by Theorem˜5.1, which gives exact FEF11 for arbitrary item sizes. The frontier theorems below therefore focus on γ>1γ>1. All original budgets are normalized to 11, and sizes are common across agents. Hence, the globally σmax _ -small condition reduces to s(g)≤σmaxfor every g∈G.s(g)≤ _ every g∈ G. The upper bounds hold after every prefix and therefore apply under both known and unknown horizons. For each deterministic algorithm, the lower bounds provide a fixed finite hard sequence under either horizon model. All algorithms are required to respect the relevant online budget at every prefix, and all results hold for arbitrary n≥1n≥ 1. The lower-bound construction realizes density spread exactly γ, so the frontier is not an artefact of supplying a loose spread bound. Density normalization. If there is no positively valued good that is individually feasible under the original unit budget, then every feasible comparison set has value zero and all claims are immediate. Otherwise, define ρ¯:=minρ(g):v(g)>0,s(g)≤1. ρ:= \ρ(g):v(g)>0,\ s(g)≤ 1\. For the analysis, replace the common value function v by v/ρ¯v/ ρ. Since valuations and sizes are common across agents, all agents share the same density function. This single global scaling sends every positive density of an individually feasible good to the interval [1,Γ]⊆[1,γ][1, ] [1,γ]. It scales both sides of the threshold test v(Ai)<αρ(g)v(A_i)<αρ(g) by the same positive constant and preserves the ordering of current bundle values. Consequently, it preserves the entire execution of Threshold(α), including its minimum-current-value tie-breaking rule. The normalization is only an analytical device; the algorithm requires no knowledge of ρ¯ ρ. We now introduce the threshold policy Threshold(α)(α) (Algorithm 5), used to establish the upper-bound frontier. The frontier upper bound is achieved by a threshold-based allocation algorithm. An arriving good is assigned only to agents whose current bundle value remains below a density-dependent threshold, whose remaining online budget is sufficient to accommodate the good, and for whom the good is individually feasible under the original unit budget. Among all such eligible agents, the algorithm assigns the good to one whose current bundle has minimum value. Algorithm 5 Threshold(α) with online budget B′B 1:Initialize Ai←∅A_i← for all i∈Ni∈ N and AC←∅A_C← . 2:for each arriving good g do 3: Let Pg:=i∈N:v(g)>0,s(g)≤1,s(Ai)+s(g)≤B′,v(Ai)<αρ(g)P_g:=\i∈ N:v(g)>0,\ s(g)≤ 1,\ s(A_i)+s(g)≤ B ,v(A_i)<αρ(g)\. 4: if Pg=∅P_g= then 5: Assign g to charity. 6: else 7: Assign g to an agent i∗∈argmini∈Pgv(Ai)i^*∈ _i∈ P_gv(A_i) using a fixed tie-breaking order. The key property of Threshold(α)(α) is that an eligible agent never exhausts her remaining budget, provided every item is sufficiently small. The following lemma quantifies this residual-capacity invariant, which underlies all of the upper-bound results in this appendix. Lemma E.2 (Capacity and no filling). Assume that every positively valued good that is individually feasible under the original unit budget has density in [1,γ][1,γ], and that every good assigned to agent i has size at most σmax _ . Run Threshold(α) with α∈(0,1]α∈(0,1] and online budget B′≥1B ≥ 1. Then s(Ai)≤α(1+lnγ)+(1+γ)σmaxs(A_i)≤α(1+ γ)+(1+γ) _ . Consequently, if α(1+lnγ)+(2+γ)σmax≤B′,α(1+ γ)+(2+γ) _ ≤ B , (8) then, for every prefix t, s(Ait)+σmax≤B′s(A_i^t)+ _ ≤ B . Hence every arriving good of size at most σmax _ fits in agent i’s remaining online budget. Proof. If no good is assigned to agent i, the claim is immediate. Otherwise, let g1,…,gmg_1,…,g_m denote the goods assigned to i, listed in their order of acceptance. For each t∈[m]t∈[m], denote st:=si(gt),ρt:=ρi(gt),ut:=ρtst=v(gt),s_t:=s_i(g_t), _t:= _i(g_t), u_t:= _ts_t=v(g_t), so that st≤σmaxs_t≤ _ by assumption. Define wt:=∑r=1turw_t:= _r=1^tu_r and w0:=0w_0:=0. For each t∈[m]t∈[m], define Δt:=wt−wt−1=ut _t:=w_t-w_t-1=u_t. When gtg_t is assigned to i, the threshold condition implies wt−1<αρtw_t-1<α _t. Since also ρt≥1 _t≥ 1, ρt≥max1,wt−1α _t≥ \1, w_t-1α \. Define f(w):=1max1,w/αf(w):= 1 \1,w/α\. Then, the function f is nonincreasing, and therefore st=Δtρt≤Δtf(wt−1)s_t= _t _t≤ _tf(w_t-1). Summing over all accepted goods gives si(Ai)≤∑t=1mΔtf(wt−1).s_i(A_i)≤ _t=1^m _tf(w_t-1). (9) which is the left Riemann sum for f. Indeed, we now compare this left Riemann sum with the corresponding integral. For each t, Δtf(wt−1)=∫wt−1wtf(w)w+∫wt−1wt(f(wt−1)−f(w))w. _tf(w_t-1)= _w_t-1^w_tf(w)\,dw+ _w_t-1^w_t(f(w_t-1)-f(w))\,dw. Since f is nonincreasing, ∫wt−1wt(f(wt−1)−f(w))w≤Δt(f(wt−1)−f(wt))≤umax(f(wt−1)−f(wt)), _w_t-1^w_t(f(w_t-1)-f(w))\,dw≤ _t(f(w_t-1)-f(w_t))≤ u_ (f(w_t-1)-f(w_t)), where umax:=max1≤t≤mΔtu_ := _1≤ t≤ m _t. Summing over t telescopes: ∑t=1mΔtf(wt−1)≤∫0wmf(w)w+umax(f(0)−f(wm))≤∫0wmf(w)w+umax. _t=1^m _tf(w_t-1)≤ _0^w_mf(w)\,dw+u_ (f(0)-f(w_m))≤ _0^w_mf(w)\,dw+u_ . Since ρt≤γ _t≤γ and st≤σmaxs_t≤ _ , umax≤γσmaxu_ ≤γ _ . It remains to bound the integral by first bounding its upper integration limit wmw_m. The last accepted good satisfies wm−1<αρm≤αγw_m-1<α _m≤αγ, and hence wm=wm−1+Δm<αγ+γσmax=γ(α+σmax).w_m=w_m-1+ _m<αγ+γ _ =γ(α+ _ ). Two cases remain. If wm≤αw_m≤α, then ∫0wmf(w)w=wm≤α≤α(1+lnγ)+σmax. _0^w_mf(w)\,dw=w_m≤α≤α(1+ γ)+ _ . Otherwise, if wm>αw_m>α, then ∫0wmf(w)w _0^w_mf(w)\,dw =α+∫αwmαww =α+ _α^w_m αw\,dw =α+αlnwmα =α+α w_mα <α+αln(γ(1+σmaxα)) <α+α (γ (1+ _ α ) ) =α(1+lnγ)+αln(1+σmaxα) =α(1+ γ)+α (1+ _ α ) ≤α(1+lnγ)+σmax, ≤α(1+ γ)+ _ , where the last inequality uses ln(1+x)≤x (1+x)≤ x. Combining this with umax≤γσmaxu_ ≤γ _ in (9) gives us si(Ai)≤α(1+lnγ)+(1+γ)σmax.s_i(A_i)≤α(1+ γ)+(1+γ) _ . If condition (8) holds, then si(Ai)≤B′−σmaxs_i(A_i)≤ B - _ . Since the occupied size is monotone over time, the same bound holds at every prefix. Consequently, si(Ait)+σmax≤B′s_i(A_i^t)+ _ ≤ B for every round t, proving that every future arrival of size at most σmax _ remains feasible for agent i. ∎ The lemma uses only the sizes and densities of goods assigned to an agent. Since Threshold(α)(α) rejects individually infeasible goods, Definition 3.2 supplies the required density bounds for every accepted good. The previous lemma ensures that every sufficiently small arriving good fits for every agent. The next lemma then handles comparisons between agents: assigning each accepted good to an eligible agent with minimum current value maintains exact FEF1 between every ordered pair of agents. Lemma E.3 (Minimum-value assignment gives exact agent-agent FEF1). Assume common additive valuations and sizes common across agents. Run Threshold(α)(α) with a common algorithmic budget B′B . Suppose that, whenever a good g is assigned to an agent at round t, it is feasible for every agent immediately before the assignment; that is, s(Ait−1)+s(g)≤B′for every i∈N.s(A_i^t-1)+s(g)≤ B every i∈ N. (10) Then, after every prefix, every ordered pair of agents i,ji,j and every nonempty set S⊆AjS A_j that is feasible for agent i, satisfy the following property: there exists x∈Sx∈ S such that v(Ai)≥v(S∖x)v(A_i)≥ v(S \x\). Consequently, every agent–agent comparison satisfies exact FEF11, for every number of agents and independently of α. Proof. Fix a prefix, an ordered pair of agents i,ji,j, and suppose Aj≠∅A_j≠ ; otherwise, there is no nonempty comparison set S⊆AjS A_j, and the claim is vacuous. Let g∗g^* denote the last good assigned to agent j, and let Aj<:=Aj∖g∗A_j^<:=A_j \g^*\. For each agent h, let wh<w_h^< denote the value of agent h’s bundle immediately before g∗g^* was assigned. Since g∗g^* was assigned to agent j, the threshold rule gives wj<<αρ(g∗)w_j^<<αρ(g^*). We first show that wi<≥wj<w_i^<≥ w_j^<. If agent i was eligible to receive g∗g^*, then the smallest-current-value tie-breaking rule selected agent j, implying wj<≤wi<w_j^<≤ w_i^<. Otherwise, agent i was not eligible. By (10), this cannot be due to insufficient remaining online budget. The common original-feasibility test s(g∗)≤1s(g^*)≤ 1 also holds because g∗g^* was assigned to agent j, and v(g∗)>0v(g^*)>0. Hence the only remaining eligibility condition that can fail is the threshold condition. Therefore, wi<≥αρ(g∗)>wj<.w_i^<≥αρ(g^*)>w_j^<. Thus, wi<≥wj<w_i^<≥ w_j^< in either case. Since bundle values are nondecreasing over time, we have the following at the considered prefix v(Ai)≥wi<≥wj<=v(Aj<).v(A_i)≥ w_i^<≥ w_j^<=v(A_j^<). Now, let S⊆AjS A_j be any nonempty set feasible for agent i. If g∗∈Sg^*∈ S, choose x=g∗x=g^*. Then S∖x⊆Aj<S \x\ A_j^<, and therefore v(S∖x)≤v(Aj<)≤v(Ai).v(S \x\)≤ v(A_j^<)≤ v(A_i). Otherwise, g∗∉Sg^*∉ S, so S⊆Aj<S A_j^<. Hence v(S)≤v(Aj<)≤v(Ai)v(S)≤ v(A_j^<)≤ v(A_i). Choosing any x∈Sx∈ S, non-negativity of the valuation implies v(S∖x)≤v(S)≤v(Ai).v(S \x\)≤ v(S)≤ v(A_i). Thus, in both cases, there exists a good x∈Sx∈ S satisfying v(Ai)≥v(S∖x)v(A_i)≥ v(S \x\), proving exact agent–agent FEF11. ∎ The hypothesis of Lemma E.3 is verified through Lemma E.2. In Theorems E.6 and E.7, every good assigned to an agent satisfies the corresponding small-item condition, and Lemma E.2 guarantees that s(Ait−1)+σmax≤B′s(A_i^t-1)+ _ ≤ B for every agent i at every prefix. Consequently, every arriving good that is eligible for assignment is feasible for every agent immediately before it is assigned, establishing condition (10). E.1 Matching Lower Bound The previous lemmas establish the ingredients needed for the frontier upper bound. We now show that this guarantee is optimal in both the known-horizon and unknown-horizon models. The hard sequence below is fixed and finite, and the proof specifies how it is used in either model. Theorem E.4. Fix n≥1n≥ 1, γ>1γ>1, α∈(0,1]α∈(0,1], and ε≥0 ≥ 0 such that α(1+lnγ)>1+εα(1+ γ)>1+ . For every σmax>0 _ >0 and every deterministic online algorithm that respects online budget 1+ε1+ , there is a fixed finite instance such that: 1. there are n agents with original unit budgets; 2. valuations are common; 3. every good has the same size δ≤σmaxδ≤ _ ; 4. the realized positive-density spread is exactly γ; 5. the final allocation is not α-FEF1. The statement holds both when the horizon is announced before the first arrival and when it is not announced. Proof. For M≥1M≥ 1, define SM:=M(1−γ−1/M)S_M:=M (1-γ^-1/M ). Since SM→lnγS_M→ γ, first choose M and then choose an integer Q sufficiently large that, with δ:=1Qδ:= 1Q, all three conditions δ<min14,σmax,δ< \ 14, _ \, γδ<α(1−2δ),γδ<α(1-2δ), (11) and α(1−2δ)(1+SM)−(γ−1)δ>1+εα(1-2δ)(1+S_M)-(γ-1)δ>1+ (12) hold. Such a choice is possible because α(1+lnγ)>1+εα(1+ γ)>1+ . Release one initial good q having common size δ, common density γ, and common value v(q)=γδv(q)=γδ. For j=0,…,Mj=0,…,M, define hj:=γj/Mh_j:=γ^j/M. A level-j good has common size δ, common density hjh_j, and common value hjδh_jδ. Set P:=⌈(1+n(1+ε))Q⌉P:= (1+n(1+ ))Q and T:=1+(M+1)PT:=1+(M+1)P. In the known-horizon model, announce T before the first arrival. In the unknown-horizon model, reveal no horizon. Simulate the algorithm on the master sequence consisting of the initial good q, followed by P level-0 goods, then P level-11 goods, and so on through P level-M goods. After each level j, charity contains at least Q level-j goods. Indeed, the agents together can hold at most n(1+ε)Qn(1+ )Q goods, because every good has size 1/Q1/Q. Hence the number of level-j goods in charity is at least P−n(1+ε)Q≥Q.P-n(1+ )Q≥ Q. Let SjS_j be any Q such goods. Then s(Sj)=1s(S_j)=1, and for every X⊆SjX S_j with |X|≤1|X|≤ 1, v(Sj∖X)≥(Q−1)hjδ=hj(1−δ)≥hj(1−2δ).v(S_j X)≥(Q-1)h_jδ=h_j(1-δ)≥ h_j(1-2δ). (13) We claim that there are a level j and an agent i such that v(Aij)<αhj(1−2δ),v(A_i^j)<α h_j(1-2δ), (14) where AijA_i^j denotes agent i’s bundle immediately after level j. Suppose otherwise. Fix an agent i. Let yi:=δ,if q is assigned to i,0,otherwise,y_i:= casesδ,&if $q$ is assigned to $i$,\\ 0,&otherwise, cases and let xi,ℓx_i, be the total size of level-ℓ goods assigned to i. The assumed failure of (14) gives, for every j=0,…,Mj=0,…,M, γyi+∑ℓ≤jhℓxi,ℓ≥αhj(1−2δ).γ y_i+ _ ≤ jh_ x_i, ≥α h_j(1-2δ). Equivalently, ∑ℓ≤jhℓxi,ℓ≥ci,j,ci,j:=αhj(1−2δ)−γyi. _ ≤ jh_ x_i, ≥ c_i,j, c_i,j:=α h_j(1-2δ)-γ y_i. Since yi≤δy_i≤δ, condition (11) gives ci,0>0c_i,0>0. The sequence ci,0,…,ci,Mc_i,0,…,c_i,M is nondecreasing. Corollary H.2 therefore gives ∑ℓ=0Mxi,ℓ≥α(1−2δ)(1+SM)−γyi. _ =0^Mx_i, ≥α(1-2δ)(1+S_M)-γ y_i. Including the initial good, the total size assigned to i is at least yi+∑ℓ=0Mxi,ℓ≥α(1−2δ)(1+SM)−(γ−1)yi≥α(1−2δ)(1+SM)−(γ−1)δ>1+ε,y_i+ _ =0^Mx_i, ≥α(1-2δ)(1+S_M)-(γ-1)y_i≥α(1-2δ)(1+S_M)-(γ-1)δ>1+ , where the final inequality is (12). This contradicts the online budget. Hence (14) holds. Let j∗j^* be the first level for which (14) holds for some agent i. Define the actual input sequence as follows: 1. release the initial good q; 2. release all level goods through the end of level j∗j^*; 3. release exactly (M−j∗)P(M-j^*)P zero-value goods, each having common size δ. This sequence has exactly 1+(j∗+1)P+(M−j∗)P=1+(M+1)P=T1+(j^*+1)P+(M-j^*)P=1+(M+1)P=T arrivals. In the known-horizon model, the master simulation and the actual execution have the same announced horizon and the same arrival prefix through level j∗j^*. In the unknown-horizon model, they also have the same observed prefix. Since the algorithm is deterministic, it makes the same assignments through that level. All later goods have value zero, so the failing agent’s value does not increase. By (13), for every X⊆Sj∗X S_j^* with |X|≤1|X|≤ 1, v(Ai)<αhj∗(1−2δ)≤αv(Sj∗∖X).v(A_i)<α h_j^*(1-2δ)≤α v(S_j^* X). Thus the final allocation is not α-FEF1. Every good has size δ≤σmaxδ≤ _ . The initial good has density γ, the level-0 goods have density 11, and all other positive densities lie in [1,γ][1,γ]. Hence the realized positive-density spread is exactly γ. ∎ The calibration good is introduced solely to ensure that every hard instance has realized density spread exactly γ. Since its size δ may be chosen arbitrarily small, the lower bound of Theorem E.4 applies to the standard density-spread parameter ρmaxρmin _ _ , which depends only on the extreme positive densities. The proof does not establish the same lower bound under the stronger requirement that a fixed positive fraction of the total size or value lie near both density endpoints. Indeed, the logarithmic capacity obstruction is generated by the ascending phases, whereas the calibration good serves only to certify the realized spread. Requiring non-negligible endpoint mass would therefore define a different model. E.2 The Limiting Density Frontier The upper and lower bounds developed in the previous two subsections show that the approximation guarantee depends on the maximum item size σmax _ . Our goal is to characterize the best deterministic guarantee that remains achievable as the globally small-item assumption becomes increasingly accurate, that is, as σmax→0 _ → 0. The appropriate notion of optimality is therefore a limiting one: rather than asking for the best guarantee at a fixed positive item size, we ask for the largest approximation factor that can be achieved uniformly once the item-size bound is sufficiently small. Definition E.5 (Limiting supremum factor). For a fixed model and σ>0σ>0, let F(σ)F(σ) be the supremum of all factors α∈[0,1]α∈[0,1] for which some deterministic online algorithm guarantees α-FEF11 on every instance in the model whose maximum item size is at most σ. If 0<σ1≤σ20< _1≤ _2, then the size-σ1 _1 instance class is contained in the size-σ2 _2 class. Hence F(σ1)≥F(σ2)F( _1)≥ F( _2). Since F(σ)∈[0,1]F(σ)∈[0,1], the one-sided limit limσ→0F(σ) _σ→ 0F(σ) exists. We call this limit the limiting supremum factor. This terminology does not assert that the boundary factor is attained for any fixed positive item-size bound. We now combine the matching upper and lower bounds to identify the optimal deterministic approximation factor in the structured model. Throughout this theorem, the algorithmic budget coincides with the original unit budget. The approximation factor below is understood in the limiting-supremum sense of Definition E.5; in particular, the theorem does not assert that the boundary value is attained for any fixed positive item-size bound. Theorem E.6 (Limiting density frontier). Fix n≥1n≥ 1 and γ>1γ>1. Consider the class ℐγcomI^com_γ of common-valuation instances with sizes common across agents in the sense of Definition 3.1, original unit budgets, under either the known-horizon or the unknown-horizon model. (a) For every α∈(0,11+lnγ)α∈ (0, 11+ γ ), there exists σ0(α,γ)>0 _0(α,γ)>0 such that Threshold(α)(α) is prefix-wise α-FEF1 against all recipients on every instance of ℐγcomI^com_γ whose goods have size at most σ0(α,γ) _0(α,γ). (b) For every α∈(11+lnγ,1]α∈ ( 11+ γ,1 ], and every σmax>0 _ >0, no deterministic online algorithm guarantees α-FEF1 on all instances in ℐγcomI^com_γ whose goods have size at most σmax _ . The hard instance supplied by Theorem E.4 has realized spread exactly γ. The factor α=0α=0 is trivially achievable and is therefore omitted. Consequently, for the function F associated with this model in Definition E.5, limσ→0F(σ)=11+lnγ _σ→ 0F(σ)= 11+ γ. Proof. We first prove part (a). Define σ0(α,γ):=1−α(1+lnγ)2+γ. _0(α,γ):= 1-α(1+ γ)2+γ. This number is positive because α<11+lnγα< 11+ γ. If the input contains no goods, every fairness condition is trivial. Assume henceforth that G≠∅G≠ . Fix an instance whose goods all have size at most σ0(α,γ) _0(α,γ), and let σ¯:=maxg∈Gs(g) σ:= _g∈ Gs(g). Then σ¯≤σ0(α,γ) σ≤ _0(α,γ). Every good assigned to an agent has size at most σ¯ σ, so Lemma E.2, applied with B′=1B =1 and σmax=σ¯ _ = σ, gives s(Ait)+σ¯≤1for every agent i and prefix t.s(A_i^t)+ σ≤ 1 every agent $i$ and prefix $t$. Indeed, α(1+lnγ)+(2+γ)σ¯≤α(1+lnγ)+(2+γ)σ0(α,γ)=1.α(1+ γ)+(2+γ) σ≤α(1+ γ)+(2+γ) _0(α,γ)=1. The preceding inequality is the key invariant of the upper-bound analysis: every agent always retains enough residual capacity to accept any future good satisfying the prescribed size bound. We use this invariant to analyze charity and agent–agent comparisons separately. Comparisons with charity. Fix a prefix t, an agent i, and a feasible comparison set S⊆ACtS A_C^t. If v(S)=0v(S)=0, then v(Ai)≥0=αv(S)v(A_i)≥ 0=α v(S), so the desired inequality is immediate. Assume v(S)>0v(S)>0, and let ρ∗:=maxg∈S:v(g)>0ρ(g)ρ^*:= _g∈ S:v(g)>0ρ(g). Choose g∗∈Sg^*∈ S attaining ρ∗ρ^*, and let t∗t^* be its arrival round. Since g∗∈Sg^*∈ S, it satisfies s(g∗)≤1s(g^*)≤ 1 under the original unit budget. The residual-capacity invariant also makes it feasible for every agent under the online budget. Since g∗g^* has positive value but was sent to charity, agent i must therefore have failed the threshold value condition: v(Ait∗−1)≥αρ∗v(A_i^t^*-1)≥αρ^*. Agent values are nondecreasing over time, so at the currently considered prefix, v(Ait)≥v(Ait∗−1)≥αρ∗.v(A_i^t)≥ v(A_i^t^*-1)≥αρ^*. Moreover, v(S)=∑g∈S:v(g)>0ρ(g)s(g)≤ρ∗s(S)≤ρ∗.v(S)= _g∈ S:v(g)>0ρ(g)s(g)≤ρ^*s(S)≤ρ^*. Therefore v(Ait)≥αv(S)v(A_i^t)≥α v(S). Agent–agent comparisons. The residual-capacity invariant established above implies, at every prefix, s(Ait)+σ¯≤1s(A_i^t)+ σ≤ 1 for every i. Since every arriving good has size at most σ¯ σ, condition (10) holds at every assignment. Lemma E.3 therefore implies exact agent–agent FEF11. Both hold at every prefix, so Threshold(α)(α) is prefix-wise α-FEF11 against all recipients on ℐγcomI^com_γ. It remains to prove part (b). Applying Theorem E.4 with ε=0 =0, its hypothesis holds because α>1/(1+lnγ)α>1/(1+ γ). Hence, for every deterministic online algorithm A and every σmax>0 _ >0, Theorem E.4 supplies a fixed finite instance ℋ∈ℐγcomH_A ^com_γ whose goods all have size at most σmax _ and on which A fails to achieve α-FEF11. ∎ As in Definition E.5, no claim in Theorem E.6 is made that the boundary factor is attained for any fixed positive item-size bound. The lower bound in part (b) has quantifier order ∀∃ℋ \ _A, where ℋH_A is a fixed finite input sequence selected before the actual execution of A. Thus, the theorem does not claim that one universal sequence defeats every deterministic algorithm simultaneously. E.3 The Limiting Augmentation Frontier The previous theorem characterizes the best limiting factor as the maximum good size tends to zero without resource augmentation. We now allow the algorithm to use an algorithmic budget 1+ε1+ while fairness continues to be evaluated with respect to the original budgets. The resulting best limiting factor as the maximum good size tends to zero shifts upward by exactly the augmentation factor. Theorem E.7 (Limiting augmentation frontier). Fix n≥1n≥ 1, γ>1γ>1, and ε≥0 ≥ 0, and let α∗(ε)=min1,1+ε1+lnγα^*( )= \1, 1+ 1+ γ \. Under either the known-horizon or unknown-horizon model, the limiting supremum deterministic approximation factor for the structured class ℐγcomI^com_γ, under algorithmic budget 1+ε1+ and fairness evaluated with respect to the original unit budgets, is α∗(ε)α^*( ). More precisely, (a) For every α∈(0,1]α∈(0,1] satisfying α(1+lnγ)<1+ε,α(1+ γ)<1+ , (15) let σ0(α,ε,γ):=(1+ε)−α(1+lnγ)2+γ _0(α, ,γ):= (1+ )-α(1+ γ)2+γ. Then σ0>0 _0>0, and Threshold(α)(α), using algorithmic budget 1+ε1+ , is prefix-wise α-FEF1 against all recipients with respect to the original unit budgets whenever every good has size at most σ0 _0. (b) For every α∈(0,1]α∈(0,1] satisfying α(1+lnγ)>1+εα(1+ γ)>1+ , and for every σmax>0 _ >0, no deterministic online algorithm that maintains s(Ait)≤1+εs(A_i^t)≤ 1+ for every agent i and prefix t guarantees α-FEF1 on all instances in ℐγcomI^com_γ whose goods have size at most σmax _ . The hard instance may be chosen to have realized spread exactly γ. (c) In particular, if ε>lnγ > γ, then part (a) applies with α=1α=1 and σ0=ε−lnγ2+γ>0 _0= - γ2+γ>0. Thus, Threshold(1)(1) is prefix-wise exactly FEF1 against all recipients for sufficiently small goods. (d) If ε<lnγ < γ, then part (b) applies with α=1α=1, and exact FEF1 is impossible for every positive item-size bound. No claim is made regarding boundary attainment when ε=lnγ = γ. Proof. We first establish part (a). Since α(1+lnγ)<1+εα(1+ γ)<1+ , we have that σ0:=(1+ε)−α(1+lnγ)2+γ _0:= (1+ )-α(1+ γ)2+γ is strictly positive. If the input contains no goods, every fairness condition is trivial. Assume henceforth that G≠∅G≠ . Fix an instance whose goods all have size at most σ0 _0, and define σ¯:=maxg∈Gs(g) σ:= _g∈ Gs(g). Then σ¯≤σ0 σ≤ _0. Applying Lemma E.2 with B′=1+εB =1+ and σmax=σ¯ _ = σ gives us s(Ait)+σ¯≤1+εs(A_i^t)+ σ≤ 1+ for every agent i and prefix t, because α(1+lnγ)+(2+γ)σ¯≤α(1+lnγ)+(2+γ)σ0=1+ε.α(1+ γ)+(2+γ) σ≤α(1+ γ)+(2+γ) _0=1+ . As in the proof of Theorem E.6, this residual-capacity invariant allows us to analyze charity and agent–agent comparisons separately. Fix an agent i and a feasible charity set S⊆ACtS A_C^t. If v(S)=0v(S)=0, then v(Ai)≥0=αv(S)v(A_i)≥ 0=α v(S). Assume v(S)>0v(S)>0, and let g∗∈Sg^*∈ S maximize the common density ρ(g)ρ(g) over positive-value goods in S; let t∗t^* be its arrival round. Since g∗∈Sg^*∈ S, it satisfies s(g∗)≤1s(g^*)≤ 1 under the original unit budget. The residual-capacity invariant also makes it feasible for every agent under the online budget. Since g∗g^* has positive value but was sent to charity, agent i must therefore have failed the threshold value condition: v(Ait∗−1)≥αρ(g∗)v(A_i^t^*-1)≥αρ(g^*). By monotonicity of accepted value, v(Ai)≥v(Ait∗−1)≥αρ(g∗).v(A_i)≥ v(A_i^t^*-1)≥αρ(g^*). Also, v(S)=∑g∈S:v(g)>0ρ(g)s(g)≤ρ(g∗)s(S)≤ρ(g∗),v(S)= _g∈ S:v(g)>0ρ(g)s(g)≤ρ(g^*)s(S)≤ρ(g^*), because S is feasible for the original unit budget. Therefore v(Ai)≥αv(S)v(A_i)≥α v(S). Agent–agent comparisons. At every prefix, s(Ait)+σ¯≤1+εfor every i.s(A_i^t)+ σ≤ 1+ every i. Every arriving good has size at most σ¯ σ, so it is feasible for every agent immediately before any assignment. Lemma E.3 gives exact agent–agent FEF1. Since α≤1α≤ 1, the allocation is prefix-wise α-FEF1 against all recipients. The lower bound in part (b) follows directly from Theorem E.4. Indeed, the hypothesis of that theorem is precisely α(1+lnγ)>1+ε.α(1+ γ)>1+ . Parts (c) and (d) are obtained by substituting α=1α=1. It remains to identify the best limiting factor as the maximum good size tends to zero. Let c=α∗(ε)=min1,1+ε1+lnγ.c=α^*( )= \1, 1+ 1+ γ \. Suppose first that c<1c<1. Then c=1+ε1+lnγc= 1+ 1+ γ. The upper bound in part (a) established above yields every factor α<cα<c for sufficiently small goods, whereas the lower bound in part (b) excludes every factor β>cβ>c for every positive item-size bound. Consequently, limσ→0F(σ)=c _σ→ 0F(σ)=c, so c is the limiting supremum approximation factor. Now suppose that c=1c=1. The upper bound in part (a) yields every factor α<1α<1 for sufficiently small goods, while no approximation factor can exceed 11. Hence, the limiting supremum is 11. Moreover, if ε>lnγ > γ, then the upper-bound construction with α=1α=1 (part (c)) gives exact FEF11 for sufficiently small goods. At the boundary ε=lnγ = γ, the limiting supremum remains 11, although no claim is made that exact FEF11 is attained for any fixed positive item-size bound. Therefore, α∗(ε)=min1,1+ε1+lnγα^*( )= \1, 1+ 1+ γ \ is the limiting supremum deterministic approximation factor. Moreover, lnγ γ is the infimum augmentation threshold: every ε>lnγ > γ guarantees exact FEF11 for all sufficiently small goods, every ε<lnγ < γ does not, and attainment at the boundary ε=lnγ = γ remains open. ∎ The frontier theorems above rely critically on the assumption that item sizes are common across agents. The charity-side argument extends to agent-specific sizes, since the residual-capacity analysis of Lemma E.2 is carried out independently for each agent and requires only the corresponding small-item condition. However, the exact agent–agent FEF11 argument does not extend directly. When a good is assigned to agent j, its density and feasibility threshold for another agent i may differ, so the balanced-acceptance argument of Lemma E.3 no longer applies. Consequently, Theorems E.6 and E.7 establish the limiting frontiers only for the model with sizes common across agents. The ascending construction still yields the charity-side lower-bound obstruction α(1+lnγ)≤1+εα(1+ γ)≤ 1+ under the structured common-across-agent-size assumptions, but the corresponding upper bound for fully agent-specific sizes remains open. Remark E.8 (Only individually feasible goods need be small). Since Threshold(α)(α) rejects every good with s(g)>1s(g)>1, the upper-bound proofs of Theorems E.6 and E.7 use the small-item bound only for goods that are individually feasible under the original unit budget. Goods with s(g)>1s(g)>1 are never assigned to an agent and cannot belong to an original-budget feasible comparison set. The lower bound in Theorem E.4 already uses globally small goods. Hence both frontier theorems remain valid, under known and unknown horizons, if the size bound is imposed only on individually feasible goods. Appendix F Why Small Items Do Not Make Aug-GreedyFit Exact It is tempting to conjecture that small items alone suffice for exact FEF11 under augmentation: "if si(g)≤εBis_i(g)≤ B_i for all i,gi,g, then Aug-GreedyFit(ε)( ) is exactly FEF11." This is false when the density spread exceeds 11; Theorem˜6.1 correctly gives only min1,(1+ε)/Γ \1,(1+ )/ \, and the following instance shows the factor cannot be improved to 11 merely by shrinking items. Example F.1 (Arbitrarily small goods do not make Aug-GreedyFit exact when Γ>1 >1). Take one agent with original budget B=1B=1 and online budget 1.11.1. Fix any σ>0σ>0, and choose a multiple Q of 1010 such that Q≥10Q≥ 10 and 1/Q≤σ1/Q≤σ. Every good has size 1/Q1/Q. First, 11Q/1011Q/10 low goods arrive, each having value 11. They have density Q. The algorithm accepts all of them, filling the online budget exactly: 11Q10⋅1Q=1.1. 11Q10· 1Q=1.1. Next, Q high goods arrive, each having value 22 and density 2Q2Q. The agent has no remaining online capacity, so all high goods are assigned to charity. The realized density spread is therefore Γ=2 =2. The agent’s value is 11Q/1011Q/10. Let S consist of the Q high goods in charity. Then s(S)=1s(S)=1, so S is feasible under the original budget, and for every x∈Sx∈ S, v(S∖x)=2(Q−1).v(S \x\)=2(Q-1). Since Q≥10Q≥ 10, 11Q10<2(Q−1), 11Q10<2(Q-1), and hence the allocation is not exact FEF1. Because 1/Q≤σ1/Q≤σ and σ>0σ>0 was arbitrary, the failure occurs for arbitrarily small goods. The example shows that merely imposing a small-item condition does not upgrade Aug-GreedyFit’s arbitrary-item-size guarantee to exact FEF1. For that particular greedy algorithm, the proven general factor remains min1,1+εΓ \1, 1+ \, and exactness follows from this analysis only when ε≥Γ−1 ≥ -1. This does not contradict the sharper threshold policy of Section E. In the more structured common-valuation, common-across-agent-size, globally-small model, Threshold(1)(1) achieves exact FEF1 for every ε>lnγ > γ. The example therefore separates the broad arbitrary-size greedy analysis from the sharper structured small-item frontier; it is not a lower bound against all online algorithms in the latter model. Appendix G Density-Spread Lower Bound for Arbitrary Item Sizes For arbitrary item sizes, the frontier characterizations of Theorems E.6 and E.7 no longer apply. This appendix records a complementary lower bound showing that, under the paper’s density-spread convention, no deterministic online algorithm can guarantee an approximation factor exceeding γ/(2γ−1)γ/(2γ-1), even with a known horizon. Unlike the frontier results, this lower bound does not characterize the optimal approximation factor. Instead, it provides an auxiliary impossibility result for the arbitrary-item-size setting. The construction uses a high-density marker good in Continuation A to make the realized density spread exactly γ; all positive-valued goods remain individually feasible. Proposition G.1 (Density-spread lower bound for arbitrary item sizes). Fix an integer k≥1k≥ 1, a density bound γ>1γ>1, and α>γ2γ−1α> γ2γ-1. Even with a known horizon, no deterministic online algorithm guarantees α-FEFkk on all instances with two agents, equal unit budgets, common valuations, uniform item sizes, and realized density spread exactly γ. Proof. Choose an integer Q>kQ>k sufficiently large that α(Q−k)>γandγQ+γ(γ−1)<α(2γ−1)(Q−k).α(Q-k)>γ γ Q+γ(γ-1)<α(2γ-1)(Q-k). (16) Such a choice is possible because α>γ/(2γ−1)α>γ/(2γ-1). Every good has size 1/Q1/Q, and both agents have budget 11. Define three kinds of goods: • a low good has value 11 and density Q; • a high good has value γ and density γQγ Q; • a zero good has value 0. The known horizon is 6Q6Q. The first 3Q3Q arrivals are low goods. Since the two agents can hold at most 2Q2Q goods in total, at least Q low goods are assigned to charity during this prefix. Consider the following two continuations. Continuation A. The remaining arrivals are one high good followed by 3Q−13Q-1 zero goods. Let mim_i be the number of low goods assigned to agent i during the common prefix. The final value of agent i in this continuation is at most mi+γm_i+γ, because there is only one high good. Let S be any set of Q low goods in charity. For every X⊆SX S with |X|≤k|X|≤ k, v(S∖X)≥Q−kv(S X)≥ Q-k. Therefore, if the final allocation is α-FEFkk, then mi+γ≥α(Q−k)m_i+γ≥α(Q-k), and hence mi≥α(Q−k)−γfor each i∈1,2.m_i≥α(Q-k)-γ each i∈\1,2\. (17) Continuation B. The remaining 3Q3Q arrivals are high goods. The two continuations have the same announced horizon and the same first 3Q3Q arrivals. Since the algorithm is deterministic, the values m1,m2m_1,m_2 after the common prefix are the same in both continuations. Agent i can receive at most Q−miQ-m_i high goods. Thus, v(Ai)≤mi+γ(Q−mi)=γQ−(γ−1)mi≤γQ−(γ−1)(α(Q−k)−γ)<αγ(Q−k),v(A_i)≤ m_i+γ(Q-m_i)=γ Q-(γ-1)m_i≤γ Q-(γ-1)(α(Q-k)-γ)<αγ(Q-k), where the last inequality follows from (16). The number of high goods assigned to charity is at least 3Q−∑i=12(Q−mi)=Q+m1+m2≥Q+2(α(Q−k)−γ)≥Q,3Q- _i=1^2(Q-m_i)=Q+m_1+m_2≥ Q+2(α(Q-k)-γ)≥ Q, where the final inequality follows from (16). Let S be any set of Q high goods in charity. Then, for every X⊆SX S with |X|≤k|X|≤ k, v(S∖X)≥γ(Q−k).v(S X)≥γ(Q-k). Since v(Ai)<αγ(Q−k)v(A_i)<αγ(Q-k), both agents violate α-FEFkk toward charity. If the algorithm fails on Continuation A, that continuation is the required instance. Otherwise, the preceding argument shows that it fails on Continuation B. Both continuations have positive densities Q and γQγ Q, and all positive-valued goods are individually feasible. Therefore, their realized density spread under Definition 3.2 is exactly γ. ∎ All positive-valued goods in both continuations have size 1/Q≤11/Q≤ 1 and are therefore included in the density-spread parameter of Definition 3.2. The single high good in Continuation A serves only to ensure that this continuation, like Continuation B, has realized spread exactly γ. Appendix H An Ascending-Capacity Optimization Lemma This appendix proves a technical optimization lemma used in the lower-bound proof of Theorem˜E.4. That proof reduces to minimizing the total mass assigned to an increasing sequence of density levels subject to ascending cumulative-capacity constraints. The lemma solves this optimization problem in closed form, allowing the same argument to be invoked without reproving the underlying linear-programming calculation. Lemma H.1 (Ascending-capacity optimization). Let 0<h0<h1<⋯<hM0<h_0<h_1<·s<h_M and 0≤c0≤c1≤⋯≤cM0≤ c_0≤ c_1≤·s≤ c_M. Among all vectors x0,…,xM≥0x_0,…,x_M≥ 0 satisfying Wj:=∑ℓ=0jhℓxℓ≥cjW_j:= _ =0^jh_ x_ ≥ c_j for all j∈0,…,Mj∈\0,…,M\, the minimum of ∑ℓ=0Mxℓ _ =0^Mx_ is c0h0+∑ℓ=1Mcℓ−cℓ−1hℓ. c_0h_0+ _ =1^M c_ -c_ -1h_ . (18) It is attained by x0=c0h0,xℓ=cℓ−cℓ−1hℓ(ℓ=1,…,M)x_0= c_0h_0, x_ = c_ -c_ -1h_ ( =1,…,M), for which Wj=cj(j=0,…,M)W_j=c_j (j=0,…,M). Proof. We first verify that the proposed solution is feasible and then prove that no feasible solution can have a smaller objective value. Since 0≤c0≤⋯≤cM0≤ c_0≤·s≤ c_M, the proposed vector is nonnegative. Moreover, Wj=h0c0h0+∑ℓ=1jhℓcℓ−cℓ−1hℓ=c0+∑ℓ=1j(cℓ−cℓ−1)=cj.W_j=h_0 c_0h_0+ _ =1^jh_ c_ -c_ -1h_ =c_0+ _ =1^j(c_ -c_ -1)=c_j. Thus, every constraint is satisfied with equality, and the objective value is exactly (18). It remains to show that no feasible solution achieves a smaller objective value. Let =(x0,…,xM)x=(x_0,…,x_M) be any feasible solution, and define W−1:=0W_-1:=0. Since Wℓ−Wℓ−1=hℓxℓ,W_ -W_ -1=h_ x_ , we may rewrite the variables as xℓ=Wℓ−Wℓ−1hℓx_ = W_ -W_ -1h_ . Substituting into the objective and applying summation by parts gives ∑ℓ=0Mxℓ=∑ℓ=0MWℓ−Wℓ−1hℓ=∑ℓ=0M−1Wℓ(1hℓ−1hℓ+1)+WMhM. _ =0^Mx_ = _ =0^M W_ -W_ -1h_ = _ =0^M-1W_ ( 1h_ - 1h_ +1 )+ W_Mh_M. (19) Since h0<h1<⋯<hMh_0<h_1<·s<h_M, every coefficient on the right-hand side is strictly positive. Moreover, feasibility implies Wℓ≥cℓ,ℓ=0,…,M.W_ ≥ c_ , =0,…,M. Replacing each WℓW_ by its lower bound therefore yields ∑ℓ=0Mxℓ≥∑ℓ=0M−1cℓ(1hℓ−1hℓ+1)+cMhM=c0h0+∑ℓ=1Mcℓ−cℓ−1hℓ, _ =0^Mx_ ≥ _ =0^M-1c_ ( 1h_ - 1h_ +1 )+ c_Mh_M= c_0h_0+ _ =1^M c_ -c_ -1h_ , which is precisely the objective value attained by the proposed solution. Hence, the proposed solution is optimal. ∎ Corollary H.2 (Specialization used in the lower-bound proofs). Let hj=γj/Mh_j=γ^j/M and cj=αhj(1−2δ)−dc_j=α h_j(1-2δ)-d, where 0≤d<α(1−2δ)0≤ d<α(1-2δ). Then, c0=α(1−2δ)−d>0c_0=α(1-2δ)-d>0, so (cj)(c_j) is nonnegative and nondecreasing. Consequently, ∑ℓ=0Mxℓ≥α(1−2δ)(1+SM)−d, _ =0^Mx_ ≥α(1-2δ)(1+S_M)-d, where SM=M(1−γ−1/M)⟶lnγS_M=M(1-γ^-1/M) γ. Proof. Applying Lemma˜H.1 gives ∑ℓ=0Mxℓ≥c0h0+∑ℓ=1Mcℓ−cℓ−1hℓ=α(1−2δ)−d+α(1−2δ)∑ℓ=1M(1−hℓ−1hℓ)=α(1−2δ)(1+SM)−d. _ =0^Mx_ ≥ c_0h_0+ _ =1^M c_ -c_ -1h_ =α(1-2δ)-d+α(1-2δ) _ =1^M (1- h_ -1h_ )=α(1-2δ)(1+S_M)-d. ∎ Theorem E.4 applies this corollary with d=γyid=γ y_i, where yi∈0,δy_i∈\0,δ\. Condition (11) ensures d<α(1−2δ)d<α(1-2δ). Appendix I Omitted Proofs for Section 7 I.1 Proof of Lemma 7.1 See 7.1 Proof. We prove that the invariant si(Ai)+resi≤Bis_i(A_i)+res_i≤ B_i holds for every agent i throughout the execution. The claimed feasibility properties then follow immediately. Initially, Ai=∅A_i= and resi=∑θqi,θsi,θ=si(A^i)≤Bires_i= _θq_i,θs_i,θ=s_i( A_i)≤ B_i, the last inequality because A A is feasible for the planner. Consider the three assignment branches. Suppose the invariant holds immediately before processing an arriving good. We verify that it is preserved in each branch of Plan-Reserve-Fulfill. Filling a planned agent quota. If a type-θ good fills an unfilled quota of agent i, then qi,θunf>0q^unf_i,θ>0 before the step, so resires_i includes a term ≥si,θ≥ s_i,θ; thus si(Ai)+si,θ≤si(Ai)+resi≤Bis_i(A_i)+s_i,θ≤ s_i(A_i)+res_i≤ B_i, so the assignment is feasible. After it, si(Ai)s_i(A_i) increases by si,θs_i,θ and resires_i decreases by exactly si,θs_i,θ, leaving si(Ai)+resis_i(A_i)+res_i unchanged. Assigning to charity. Sending a good to charity changes no agent’s AiA_i and does not increase any resires_i (a charity quota decrement leaves resires_i untouched), so the invariant is preserved. Assigning an excess good to agent i. This branch is taken only when si(Ai)+si,θ+resi≤Bis_i(A_i)+s_i,θ+res_i≤ B_i is checked explicitly; afterwards si(Ai)s_i(A_i) grows by si,θs_i,θ and resires_i is unchanged, so the invariant holds. In all cases si(Ai)≤si(Ai)+resi≤Bis_i(A_i)≤ s_i(A_i)+res_i≤ B_i at termination. Thus, the invariant is preserved throughout the execution. At termination, si(Ai)≤si(Ai)+resi≤Bis_i(A_i)≤ s_i(A_i)+res_i≤ B_i for every agent, so the returned allocation is budget feasible. Moreover, every good used to satisfy a planned agent quota is accepted at the moment it arrives without violating feasibility. ∎ I.2 Proof of Theorem 7.2 See 7.2 Proof. Suppose f=f^f= f. Then, for every type θ, exactly fθ=f^θ=∑r∈Rqr,θf_θ= f_θ= _r∈ Rq_r,θ goods of type θ arrive, matching the total planned quota of that type. By Lemma˜7.1, every planned agent quota can be filled immediately upon the arrival of a matching good without violating budget feasibility. Moreover, Plan-Reserve-Fulfill always gives priority to unfilled planned quotas, first for agents and then for charity, before treating a good as excess. Since the total number of arriving type-θ goods exactly equals the total planned quota of that type, every planned quota is filled, and no good is ever processed as an excess good. It follows that, for every recipient r and type θ, the final allocation ArA_r contains exactly qr,θq_r,θ goods of type θ. Hence, the online allocation realizes the planned allocation A A up to a relabelling of identical goods. ∎ I.3 Proof of Corollary I.1 By Theorem˜7.2, every fairness property of A A determined solely by the per-recipient type counts is inherited by the online allocation, including FEF, FEFkk, α-FEFkk, additive η-FEFkk, and FEFx. Corollary I.1 (Lifting offline fairness guarantees). Suppose that the offline planner returns an additive η0 _0-FEFkk allocation on the predicted multiset M M. If f=f^f= f, then Plan-Reserve-Fulfill returns an additive η0 _0-FEFkk allocation. In particular, an exact offline FEFx planner gives exact FEFx under correct predictions, and hence also exact FEF1. Proof. The first claim follows from Theorem˜7.2 because additive η0 _0-FEFkk depends only on the type counts assigned to each recipient. The second claim follows by applying the same argument to an offline FEFx allocation. The implication from FEFx to FEF1 follows by definition. ∎ I.4 Characterization of k-Violation The smallest additive slack required by an allocation A can be expressed through the k-violation, defined as violk(A):=maxi∈N,r∈R,S⊆Ar,si(S)≤Bi[minX⊆S|X|≤kvi(S∖X)−vi(Ai)]+,viol_k(A):= _ subarrayci∈ N,\ r∈ R,\\ S A_r,\ s_i(S)≤ B_i subarray [ _ subarraycX S\\ |X|≤ k subarrayv_i(S X)-v_i(A_i) ]_+, where [x]+:=maxx,0[x]_+:= \x,0\. Equivalently, A is additive η-FEFkk if and only if violk(A)≤ηviol_k(A)≤η. In particular, we next prove that the above explicit expression is equivalent to the one specified in Section˜7.3. Lemma I.2 (Characterization of k-violation). For every allocation A and every η≥0η≥ 0, A is additive η-FEFkk if and only if violk(A)≤ηviol_k(A)≤η. Equivalently, violk(A)=minη≥0:A is additive η-FEFk.viol_k(A)= \η≥ 0:A is additive η-FEFk\. Proof. By Definition 3.6, A is additive η-FEFkk if and only if, for every agent i∈Ni∈ N, recipient r∈Rr∈ R, and set S⊆ArS A_r satisfying si(S)≤Bis_i(S)≤ B_i, there exists X⊆SX S with |X|≤k|X|≤ k such that vi(S∖X)−vi(Ai)≤η.v_i(S X)-v_i(A_i)≤η. For a fixed admissible triple (i,r,S)(i,r,S), this is equivalent to minX⊆S|X|≤k(vi(S∖X)−vi(Ai))≤η. _ subarraycX S\\ |X|≤ k subarray (v_i(S X)-v_i(A_i) )≤η. Define M(A):=maxi∈N,r∈R,S⊆Arsi(S)≤BiminX⊆S|X|≤k(vi(S∖X)−vi(Ai)).M(A):= _ subarrayci∈ N,\ r∈ R,\ S A_r\\ s_i(S)≤ B_i subarray\; _ subarraycX S\\ |X|≤ k subarray (v_i(S X)-v_i(A_i) ). It follows that A is additive η-FEFkk if and only if M(A)≤ηM(A)≤η. Since η≥0η≥ 0, M(A)≤η⟺[M(A)]+≤η.M(A)≤η [M(A)]_+≤η. By definition, violk(A)=[M(A)]+viol_k(A)=[M(A)]_+. Therefore, A is additive η-FEFk⟺violk(A)≤η.A is additive η-FEFk _k(A)≤η. Taking the minimum over η≥0η≥ 0 proves violk(A)=minη≥0:A is additive η-FEFk.∎viol_k(A)= \η≥ 0:A is additive η-FEFk\. I.5 Robustness via Local Prediction Errors Theorem I.3. Suppose the planned allocation A A is additive η0 _0-FEFkk. Let A be the allocation returned by Plan-Reserve-Fulfill. Let mim_i denote the total viv_i-value of unfilled planned quotas for agent i and ei,re_i,r the total viv_i-value of excess realized goods assigned to recipient r. Then, violk(A)≤η0+maxi,r(mi+ei,r)viol_k(A)≤ _0+ _i,r(m_i+e_i,r). Proof. Fix an agent i, a recipient r, and a set S⊆ArS A_r that is feasible for i. Partition S=Spl⊎SexS=S^pl S^ex, where SplS^pl contains the realized goods that filled planned quotas of r, and SexS^ex contains the excess goods assigned to r. For each good in SplS^pl, choose the distinct predicted copy whose quota it filled. Let S^pl⊆A^r S^pl A_r be the set of these predicted copies. Each realized good and its corresponding predicted copy have the same type. Therefore, si(S^pl)=si(Spl)≤si(S)≤Bis_i( S^pl)=s_i(S^pl)≤ s_i(S)≤ B_i and vi(S^pl)=vi(Spl).v_i( S^pl)=v_i(S^pl). Since A A is additive η0 _0-FEFkk, there exists X^⊆S^pl X S^pl with |X^|≤k| X|≤ k such that vi(A^i)≥vi(S^pl∖X^)−η0.v_i( A_i)≥ v_i( S^pl X)- _0. Let X⊆SplX S^pl be the realized goods corresponding to the predicted copies in X X. Then |X|≤k|X|≤ k and vi(S^pl∖X^)=vi(Spl∖X).v_i( S^pl X)=v_i(S^pl X). The filled planned quotas of agent i contribute exactly the value of the corresponding predicted copies. The only planned value missing from AiA_i is counted by mim_i, while excess goods assigned to i have nonnegative value. Hence, vi(Ai)≥vi(A^i)−mi.v_i(A_i)≥ v_i( A_i)-m_i. Combining the preceding inequalities gives vi(Ai)≥vi(Spl∖X)−η0−mi.v_i(A_i)≥ v_i(S^pl X)- _0-m_i. Finally, vi(Sex)≤ei,rv_i(S^ex)≤ e_i,r, and therefore vi(S∖X)=vi(Spl∖X)+vi(Sex)≤vi(Ai)+η0+mi+ei,r.v_i(S X)=v_i(S^pl X)+v_i(S^ex)≤ v_i(A_i)+ _0+m_i+e_i,r. Rearranging proves vi(Ai)≥vi(S∖X)−η0−mi−ei,r.v_i(A_i)≥ v_i(S X)- _0-m_i-e_i,r. Taking the maximum over all feasible comparisons proves the stated bound on violk(A)viol_k(A). ∎ I.6 Proof of Theorem 7.3 See 7.3 Proof. We bound the two local error terms appearing in Theorem˜I.3 by the corresponding prediction error. For each type θ, an unfilled planned quota can arise only if fewer than f^θ f_θ goods of that type are realized. Hence, the number of unfilled type-θ quotas is at most (f^θ−fθ)+( f_θ-f_θ)_+. Similarly, an excess good of type θ can arise only if more than f^θ f_θ goods of that type are realized. Thus, the number of excess type-θ goods is at most (fθ−f^θ)+(f_θ- f_θ)_+. Consequently, for every agent i and recipient r, mi≤∑θvi,θ(f^θ−fθ)+,ei,r≤∑θvi,θ(fθ−f^θ)+.m_i≤ _θv_i,θ( f_θ-f_θ)_+, e_i,r≤ _θv_i,θ(f_θ- f_θ)_+. For every type θ, at most one of (f^θ−fθ)+( f_θ-f_θ)_+ and (fθ−f^θ)+(f_θ- f_θ)_+ is nonzero, and their sum equals |fθ−f^θ||f_θ- f_θ|. Therefore, mi+ei,r≤∑θvi,θ|fθ−f^θ|=Δi(f,f^)≤Δ∞(f,f^).m_i+e_i,r\ ≤\ _θv_i,θ\,|f_θ- f_θ|\ =\ _i(f, f)\ ≤\ _∞(f, f). Substituting this bound into Theorem˜I.3 gives violk(A)≤η0+Δ∞(f,f^)viol_k(A)≤ _0+ _∞(f, f), proving the first claim. The common-valuation specialization follows immediately from the definition of Δ(f,f^) (f, f). ∎ I.7 Proof of Theorem 7.4 See 7.4 Proof. We construct two instances sharing the same prediction and the same arrival prefix. The first instance satisfies the prediction exactly and forces every perfectly consistent algorithm to reserve almost all capacity for low-valued goods. The second instance differs only in its final arrivals, replacing the predicted zero-valued goods by high-valued goods. Since the algorithm cannot distinguish the two instances before this point, it has too little remaining capacity to accept many of the high-valued goods. Formally, let B1=B2=1B_1=B_2=1. Choose Q sufficiently large that Q−2kQ+2k>1−ζ2, Q-2kQ+2k>1- ζ2, and choose δ>0δ>0 to be small, as fixed later. Every good has size 1/Q1/Q. The prediction consists of 3Q3Q low goods of value δ and size 1/Q1/Q, and Q+2kQ+2k zero-padding goods of value 0 and size 1/Q1/Q. Thus, the predicted horizon is T=4Q+2kT=4Q+2k. Perfect-prediction instance. Assume the prediction is correct and the first 3Q3Q arrivals are the low goods. After they arrive, since the two agents together can hold at most 2Q2Q goods in total, at least Q low goods must be assigned to charity. We claim that after this prefix each agent must already hold at least Q−kQ-k low goods. Otherwise, let S consist of Q low goods currently held by charity. Then, S is feasible since si(S)=1s_i(S)=1, and for every X⊆SX S with |X|≤k|X|≤ k, v(S∖X)≥(Q−k)δ,v(S X)≥(Q-k)δ, while the agent’s value is strictly smaller than (Q−k)δ(Q-k)δ, contradicting exact FEFkk. Since the remaining predicted goods all have value 0, later arrivals cannot repair such a violation. Actual instance. Now, keep the same prediction, the same horizon, and the same first 3Q3Q arrivals, but replace the final Q+2kQ+2k zero-padding goods by unpredicted high goods of value 11 and size 1/Q1/Q. The zero-padding goods are missing (since they have value 0, they contribute nothing to error), and the high goods are excess. The prediction error is therefore Δ(f,f^)=∑θvθ|fθ−f^θ|=1⋅(Q+2k)=Q+2k (f, f)= _θv_θ|f_θ- f_θ|=1·(Q+2k)=Q+2k since only the value-11 and value-0 types differ, and the latter contributes nothing to the weighted error. Since the two instances have identical low prefixes, AlgAlg makes exactly the same decisions during the first 3Q3Q arrivals. Hence, each agent already holds at least Q−kQ-k low goods and has capacity for at most k additional high goods, due to the capacity of size Q. Consequently, at most 2k2k of the Q+2kQ+2k high-valued goods can be accepted, so at least Q are assigned to charity. Let S be any Q of these high-valued charity goods. Then, si(S)=1s_i(S)=1, and for every X⊆SX S with |X|≤k|X|≤ k, v(S∖X)≥Q−k.v(S X)≥ Q-k. On the other hand, each agent receives value at most Qδ+kQδ+k, consisting of at most Q low goods of value δ together with at most k high-valued goods. Therefore, violk(A)≥(Q−k)−(Qδ+k)=Q−2k−Qδ.viol_k(A)≥(Q-k)-(Qδ+k)=Q-2k-Qδ. Finally, choose a sufficiently small δ so that Qδ≤ζ2(Q+2k)Qδ≤ ζ2(Q+2k). Then, Q−2k−Qδ≥(Q−2k)−ζ2(Q+2k)≥(1−ζ2)(Q+2k)−ζ2(Q+2k)=(1−ζ)(Q+2k),Q-2k-Qδ≥(Q-2k)- ζ2(Q+2k)≥ (1- ζ2 )(Q+2k)- ζ2(Q+2k)=(1-ζ)(Q+2k), where the second inequality uses Q−2k>(1−ζ2)(Q+2k).Q-2k> (1- ζ2 )(Q+2k). Since Δ(f,f^)=Q+2k (f, f)=Q+2k, the claimed lower bound follows. ∎ I.8 Proof of Theorem 7.5 See 7.5 Proof. We construct two instances having identical predicted value and size marginals, together with the same horizon, total value, maximum item value, and arrival prefix. They differ only in the correlation between values and sizes. The first instance forces every correct algorithm to reserve almost all of each agent’s capacity for low-valued goods, whereas the second requires that capacity for high-valued goods. Since a deterministic algorithm cannot distinguish the two instances before the common prefix ends, it cannot be correct on both. Let B1=B2=1B_1=B_2=1. Choose Q>2kQ>2k and δ>0δ>0 so that k+Qδ<Q−k+Qδ<Q-k, and let H=Q+2kH=Q+2k. The predicted value multiset consists of 3Q3Q values δ, H values 11, and H values 0. The predicted size multiset consists of 3Q+H3Q+H sizes 1/Q1/Q and H sizes 22. Both predicted multisets contain 3Q+2H3Q+2H entries. Hence, the announced horizon is T:=3Q+2HT:=3Q+2H. The total value is 3Qδ+H3Qδ+H, and the maximum item value is 11. The first 3Q3Q arrivals are low-valued goods of size 1/Q1/Q. As before, at least Q of these goods must be assigned to charity. We now consider two continuations of this common prefix, both consistent with the same predicted value and size marginals. Continuation I (high value paired with infeasible size). The remaining goods consist of H goods of value 11 and size 22, together with H goods of value 0 and size 1/Q1/Q. Since every value-11 good has size 2>12>1, it is infeasible for both agents and can never appear in a feasible comparison set. The only feasible goods remaining therefore have value 0. As in the proof of Theorem˜7.4, exact FEFkk requires each agent to hold at least Q−kQ-k low-valued goods after the common prefix. Otherwise, Q low charity goods yield a violation as in Theorem˜7.4. Continuation I (high value paired with feasible size). Now, interchange the sizes of the remaining goods. The last arrivals are H goods of value 11 and size 1/Q1/Q, together with H goods of value 0 and size 22. Since the common prefix is unchanged, the algorithm reaches exactly the same state as in Continuation I. Thus, each agent already holds at least Q−kQ-k low-valued goods and has capacity for at most k additional feasible goods. Of the H=Q+2kH=Q+2k feasible high-valued goods, at least Q must therefore be assigned to charity. Let S consist of any Q of these high-valued charity goods. Then, si(S)=1s_i(S)=1, while v(S∖X)≥Q−kv(S X)≥ Q-k for every X⊆SX S with |X|≤k|X|≤ k. On the other hand, each agent’s value is at most Qδ+k<Q−kQδ+k<Q-k, contradicting exact FEFkk. The two continuations have identical value marginals, size marginals, horizon, total value, and maximum item value. They differ only in the correlation between values and sizes. Thus, no deterministic online algorithm receiving only these marginal predictions can distinguish the two instances before their common prefix ends, even though correctness requires different decisions. Therefore, predicting marginal information alone is insufficient to guarantee exact FEFkk. ∎ Appendix J Lower Bound for Weak Scalar Advice The learning-augmented framework of Section˜7 assumes predictions over the joint value-size type space. This appendix considers a much weaker information model in which the algorithm receives only a single scalar parameter describing the density range. The resulting lower bound serves as a sanity check: knowing the exact minimum positive density together with a valid upper bound on the density spread does not improve the sharp spread-bounded frontier. Definition J.1 (Minimum-density advice with a spread bound). We consider instances having at least one positively valued good that is individually feasible under the original unit budget. The advice supplied to the algorithm consists of: 1. the exact minimum positive density ρmin:=minρ(g):v(g)>0,s(g)≤1; _ := \ρ(g):v(g)>0,\ s(g)≤ 1\; 2. a valid upper bound γ≥1γ≥ 1 on the ratio of maximum to minimum positive density among individually feasible goods, as in Definition 3.2. The value ρmin _ is supplied in the original numerical scale of the instance. No additional information is provided: in particular, the algorithm is not told the realized maximum density, the horizon, the multiplicities of the density levels, or the stopping prefix. The algorithm may use the numerical value of ρmin _ arbitrarily; in particular, no scale-invariance assumption is imposed. Theorem J.2 (Weak scalar advice does not improve the frontier). Fix n≥1,ρmin>0,γ>1,n≥ 1, _ >0,γ>1, and let ρmax:=γρmin. _ :=γ _ . For every α∈(11+lnγ,1]α∈ ( 11+ γ,1 ] and every deterministic online algorithm supplied with the exact minimum positive density ρmin _ together with the spread bound γ, there exists, for every σmax>0 _ >0, a finite unknown-horizon instance with common valuations and sizes common across agents such that 1. every good has size at most σmax _ ; 2. the minimum and maximum positive densities are exactly ρmin _ and ρmax _ , respectively; 3. the realized density spread is exactly γ; and 4. the algorithm does not produce an α-FEF1 allocation. Proof. We reduce the claimed lower bound to the frontier lower bound of Theorem˜E.4 by scaling every value by the advised minimum density. Fix a deterministic online algorithm A receiving the advice (ρmin,γ)( _ ,γ). We define a deterministic online algorithm A for normalized instances whose positive densities lie in [1,γ][1,γ]. Whenever a normalized good g with value v^(g) v(g) and size s(g)s(g) arrives, algorithm A forms a simulated good having the same size and value v(g):=ρminv^(g)v(g):= _ v(g), and presents this simulated arrival to A, together with the advice (ρmin,γ)( _ ,γ). Algorithm A then assigns the normalized good to the same recipient selected by A for the simulated good. This defines a deterministic online algorithm because the transformation uses only the current normalized arrival and the fixed constant ρmin _ . Since only the values are rescaled, while sizes and budgets are unchanged, the simulation preserves feasibility exactly when the corresponding normalized assignment is feasible. Since α∈(11+lnγ,1]α∈( 11+ γ,1], applying Theorem˜E.4 to A with ε=0 =0 yields a fixed finite normalized instance ℋ H such that (a) every good has size at most σmax _ ; (b) the minimum and maximum positive densities are exactly 11 and γ, respectively; and (c) the allocation returned by A is not α-FEF1. Construct the corresponding original-scale instance ℋH by multiplying every value in ℋ H by ρmin _ to obtain v(g):=ρminv^(g)v(g):= _ v(g), while leaving every size unchanged. Then, every positive density is multiplied by ρmin _ . Hence, ming:v(g)>0,s(g)≤1ρ(g)=ρmin _g:v(g)>0,\,s(g)≤ 1ρ(g)= _ and maxg:v(g)>0,s(g)≤1ρ(g)=γρmin=ρmax _g:v(g)>0,\,s(g)≤ 1ρ(g)=γ _ = _ , so the realized density spread is exactly γ. By construction, given advice ρmin _ and spread bound γ, the execution of A on ℋH is recipient-by-recipient identical to the execution of A on ℋ H, since A presents exactly the rescaled arrival sequence to A. Finally, multiplying every value by the positive constant ρmin _ preserves every multiplicative FEF1 comparison: v^(Ai)<αv^(S∖x)⇔ρminv^(Ai)<αρminv^(S∖x). v(A_i)<α v(S \x\) _ v(A_i)<α _ v(S \x\). Hence the α-FEF1 violation produced by A on ℋ H is preserved under scaling, yielding an α-FEF1 violation of A on ℋH. Since ℋH inherits the unknown-horizon property and the same item sizes as ℋ H, it satisfies all the required properties. ∎ The simulation does not assume that A is scale invariant. Instead, the auxiliary algorithm A explicitly rescales each normalized arrival to the original numerical scale before presenting it to A. The frontier lower bound is therefore applied to A, while the simulation transfers the resulting hard instance back to the original advice model. Although the constructed hard instance satisfies ρmax=γρmin _ =γ _ , the algorithm is never given ρmax _ explicitly. The advice consists only of the exact minimum positive density ρmin _ together with the valid spread bound γ. Theorem J.2 should be viewed as a sanity-check lower bound for a particularly weak advice model. Through the simulation reduction, the advice effectively specifies only the lower endpoint of the normalized density interval, while revealing nothing about the stopping prefix or the distribution of mass across higher density levels. Consequently, the theorem does not constitute an advice-complexity result and does not rule out richer forms of side information, such as predicted quantiles, density histograms, reservation profiles, or the joint value-size type counts used by Plan-Reserve-Fulfill. Rather, it shows only that knowing the minimum positive density together with a spread bound does not improve the sharp spread-bounded frontier.