PaperlayerView exact revision on arXiv

Source-linked AI summary

Online Fair Division with Frequency Predictions

Tzeh Yuan Neoh, Nicholas Teh

arXiv:2610.34625v1cs.GTcs.MA

TL;DR

The paper asks whether frequency predictions can support envy-based guarantees in online fair division. It gives constructive algorithms and impossibility proofs, and applies Neoh et al. [2026]'s meta-algorithm to compute EEFX for any number of agents. A positive approximation of EF1 is possible exactly through four agents, while EFX has no positive approximation for three or more.

  • Problem

    Whether frequency predictions can support a positive approximation of EF1 in online allocation remained an open question across agent counts.

    Source: §1 · p. 2, §2 · p. 5

  • Method

    The paper gives constructive algorithms and impossibility proofs, and applies Neoh et al. [2026]'s meta-algorithm to compute EEFX for any number of agents.

    Source: §1.1 · p. 3, §7 · p. 14

  • Results

    A positive approximation of EF1 is possible exactly through four agents, while EFX has no positive approximation for three or more agents.

    Source: §1.1 · p. 3, §7 · pp. 14–15

  • Takeaways & Limitations

    Frequency predictions suffice for guarantees depending only on an agent’s own bundle, such as shares and EEFX, but not for EF1 with five or more agents.

    Source: §7 · p. 15

    Whether the four-agent EF1 approximation factor is optimal remains unknown.

    Source: §5 · p. 12

Abstract

from arXiv · show

We study online fair division of indivisible goods among $n$ agents with frequency predictions: before any good arrives, the algorithm learns the multiset of each agent's values for the goods, but neither the arrival order nor which values of different agents belong to the same good. Neoh et al. (ICML 2026) showed that such predictions allow every share-based guarantee that is achievable offline, and left open whether a positive approximation of envy-freeness up to one good (EF1) is possible. We show that deterministic online algorithms can guarantee $1/2$-EF1 for three agents and $(3-\sqrt5)/2$-EF1 for four agents, whereas for five or more agents, no online algorithm can guarantee any positive approximation of EF1, even with $n+1$ goods and identical predictions. Together with the known result for two agents, a positive approximation of EF1 is therefore possible if and only if $n\leq4$. We also rule out any positive approximation of EFX for three or more agents, even when the valuations take only two distinct positive values. Next, we use the meta-algorithm of Neoh et al. (ICML 2026) to compute an epistemic EFX (EEFX) allocation in polynomial time for any $n$, and hence a $1/(n-1)$-EF$(n-2)$ allocation for $n\geq3$, whereas algorithms that fix a picking sequence in advance can guarantee a positive approximation of EF$k$ if and only if $n\leq k+2$. Finally, for noisy predictions, we give algorithms that return EEFX allocations when the predictions are exact, and guarantee $(1-2\varepsilon+O(\varepsilon^2))$-EEFX under underestimates and, for $n\geq3$, $(1-2(n-1)\varepsilon+O(\varepsilon^2))$-EEFX under overestimates; the linear terms are the best possible, and larger overestimates rule out any positive approximation for such algorithms.

1 Introduction

Frequency predictions leave open whether envy-based guarantees can be achieved because they do not reveal how agents’ values align across goods. This paper establishes when positive EF1 approximations are possible and extends the analysis to EFX, EEFX, fixed picking sequences, and noisy predictions.

1 Introduction

  • Frequency predictions support share-based guarantees but leave cross-agent value alignment unknown, motivating the open question of positive EF1 approximation.The paper situates this question within work on online fair division and learning-augmented algorithms.Source: §1 · p. 2, §1.2 · p. 4

1.1 Our Results

  • For online allocation, a positive approximation of EF1 is possible if and only if there are at most four agents; for every n ≥ 5 and every α > 0, no online algorithm guarantees α-EF1.Source: §1.1 · p. 2
  • The online meta-algorithm yields polynomial-time EEFX for any n and, for n >= 3, a 1/(n-1)-EF(n-2) allocation.If the picking sequence is fixed in advance, a positive EFk approximation is possible if and only if n <= k+2.Source: §1.1 · pp. 2–3
  • No positive EFX approximation is possible for three or more agents, even when values take only two distinct positive values.For five or more agents, the EF1 impossibility already holds with n+1 goods and identical predictions.Source: §1.1 · p. 3
  • For four agents, an algorithm that does not fix its picking sequence in advance guarantees (3 - sqrt5)/2-EF1; whether this factor is best possible is unknown.It selects high-value goods as they arrive, then allocates remaining goods using concave potential functions.Source: §1.1 · p. 3
  • For noisy predictions, consistent algorithms attain (1 - 2ε + O(ε^2))-EEFX underestimates and (1 - 2(n-1)ε + O(ε^2))-EEFX underestimates for n >= 3.The first-order losses are best possible; overestimates by a factor of 3/2 rule out any positive approximation for n >= 3.Source: §1.1 · p. 3

2 Preliminaries

The preliminaries define the online frequency-prediction setting and the fairness notions used in the paper. They also describe a meta-algorithm that implements a picking sequence online and establish a value-preserving matching between its online and ordered-instance allocations.

2 Preliminaries

  • Before goods arrive, the algorithm learns each agent’s multiset of values; goods then arrive sequentially and are allocated irrevocably against an adaptive adversary respecting those multisets.The paper evaluates guarantees on the final allocation.Source: §2 · p. 5

2.1 Fairness Notions

  • EF1 permits removing one good from an envied bundle to eliminate envy, while EFX requires the comparison to hold after removing any good.EFk compares against the envied bundle after its k most valuable goods are removed; α scales the comparison.Source: §2.1 · p. 5
  • EEFX requires that each agent’s unreceived goods can be partitioned into n-1 bundles toward which she satisfies EFX.The partition may differ by agent, so EEFX depends on an agent’s own bundle and valuation, not on how the remaining goods are allocated.Source: §2.1 · p. 5

2.2 The Meta-Algorithm

  • The meta-algorithm represents predictions as an identical-ordering instance, where all agents rank goods in the same order, then implements a given picking sequence online.On each arrival it simulates the remaining sequence using the arriving good and hypothetical goods valued at remaining predicted values.Source: §2.2 · p. 6
  • For each agent, every good in her ordered-instance bundle can be matched to a distinct online good she values at least as much.The online allocation also has the same bundle size and at least the ordered-instance bundle’s total value for that agent.Source: §2.2 · p. 6

3 Picking Sequences, EFk, and Three Agents

The meta-algorithm yields polynomial-time EEFX allocations for any number of agents, which also give approximate EF(n−2) guarantees when there are at least three agents. The section also characterizes when fixed picking sequences can guarantee positive EFk and establishes a three-agent EF1 guarantee.

3.1 Two Properties of EEFX

  • EEFX is preserved when an agent’s bundle is replaced by one that stochastically dominates it, and for n ≥3 it implies 1/(n−1)-EF(n−2) when every bundle is nonempty.The n ≥3 and nonempty-bundle conditions matter: for two agents, EEFX is equivalent to EFX, which does not imply envy-freeness.Source: §3.1 · p. 7

3.2 Guarantees of the Meta-Algorithm

  • For any number of agents, a deterministic polynomial-time online algorithm using exact frequency predictions returns an EEFX allocation.When there are at least n goods, every bundle is nonempty and the EEFX witness partitions can match the sizes of the other agents’ bundles.Source: §3.2 · p. 7
  • For n ≥3, a deterministic polynomial-time online algorithm guarantees 1/(n−1)-EF(n−2), including 1/2-EF1 for three agents.The guarantee follows from EEFX when every bundle is nonempty; with fewer than n goods, assigning goods to different agents gives EF1.Source: §3.2 · p. 8

3.3 Limits of Fixed Picking Sequences

  • A picking sequence chosen in advance guarantees a positive approximation of EFk if and only if n ≤k + 2.When n ≥k + 3, impossibility holds even with nk + 1 goods, identical predictions, and normalized valuations whose values are distinct and positive.Source: §3.3 · p. 8
  • For four agents, the fixed-sequence impossibility already holds with five goods, so a positive EF1 approximation requires an algorithm that does not fix its picking sequence in advance.The section’s meta-algorithm computes an offline allocation with a common goods ranking and implements its picking sequence online.Source: §3.2 · p. 7, §3.3 · p. 8

4 Impossibility Results

The section establishes limits on online envy guarantees under exact frequency predictions. Positive EF1 approximation is impossible from five agents onward, and positive EFX approximation is impossible from three agents onward, even for a restricted two-value valuation class.

4.1 EF1 for Five or More Agents

  • The EF1 impossibility construction makes the remaining goods’ values depend on early allocation decisions while preserving the same frequency multiset for every agent.With n + 1 goods, if every agent receives a good, exactly one receives two; the construction uses n ≥5 to place agents’ remaining small values on different goods.Source: §4.1 · p. 9
  • For every n ≥5, no online algorithm guarantees any positive approximation of EF1, even with n + 1 goods, identical predictions, and normalized valuations with positive values.The construction’s instances remain proportional up to one good, so satisfying that share-based guarantee does not ensure an envy-based guarantee.Source: §4.1 · pp. 9–10

4.2 EFX with Two Positive Values

  • For every n ≥3, no online algorithm guarantees any positive approximation of EFX, even with identical predictions and normalized valuations taking only two positive values.The restriction allows each agent one larger-valued good and assigns that good among the last two arrivals.Source: §4.2 · p. 10

5 Four Agents: (3 −

For four agents, the paper gives a deterministic polynomial-time online algorithm that guarantees (3−√5)/2-EF1. It combines selected high-value goods with prediction-based concave potential functions; the authors do not establish that the factor is optimal.

5 Four Agents

  • The algorithm selects and allocates a few high-value goods online so that, for any two agents, at most one good in the other agent’s bundle exceeds the selected good’s value.Each agent receives one or two selected goods, including at least one of her first four occurrences.Source: §5 · pp. 10–11
  • Unselected goods are allocated online using concave potential functions computed from the frequency predictions.The potentials are bounded and favor agents whose bundles currently have low value to them.Source: §5 · pp. 11–12
  • For four agents, a deterministic polynomial-time online algorithm with exact frequency predictions guarantees (3−√5)/2-EF1.The authors do not know whether this factor is best possible.Source: §5 · pp. 10, 12
  • The proof chooses C = (3+√5)/2 as the smallest value meeting its potential-function requirements.The guarantee is 1/C-EF1, and the paper does not determine whether the resulting factor is optimal.Source: §5 · pp. 10, 12

6 Learning-Augmented Guarantees under Noisy Frequency Predictions

The paper gives consistent algorithms for noisy frequency predictions and bounds their EEFX guarantees by prediction error. It also proves limits for overestimates and gives an additive EFk guarantee based on instantiation error.

6 Learning-Augmented Guarantees under Noisy Frequency Predictions

  • Consistent algorithms instantiate each arriving good with an unused predicted value and then run an algorithm for exact predictions on the resulting valuations.Underestimates and overestimates use different deterministic matching rules; neither rule uses the error factors.Source: §6 · p. 12, §6.1 · p. 13

6.1 Relative Prediction Error

  • Underestimates yield a 1/(2ρ_i−1)-EEFX guarantee, while for n≥3 overestimates yield max{0, 1−2(n−1)(ρ_i−1)−(n−1)(2n−1)(ρ_i−1)^2}-EEFX.Each guarantee applies to agent i regardless of the other agents’ predictions.Source: §6.1 · p. 13
  • 1−2ε+O(ε^2) underestimates and 1−2(n−1)ε+O(ε^2) overestimates are the EEFX guarantees for fixed n≥3, and neither linear loss can be improved.The best possible first-order loss is independent of n for underestimates and grows linearly with n for overestimates.Source: §6.1 · p. 13

6.2 Impossibility under Larger Overestimates

  • For n≥3, no consistent algorithm guarantees positive EEFX under overestimates with error factor ρ=3/2, even with identical predictions and true valuations and known ρ.For two agents, a positive approximation is possible if and only if ρ<2; the exact threshold for n≥3 is left open.Source: §6.2 · pp. 13–14

6.3 Additive Guarantees in Terms of Instantiation Error

  • For any instantiation rule, running an algorithm that guarantees α-EFk on exact predictions yields vi(Ai) ≥ αD_i^(k)(Aj)−η_i, where η_i is agent i’s total instantiation error.With the closest-value rule, η_i=0 for exact predictions, and the argument also yields EEFX partitions.Source: §6.3 · p. 14

7 Conclusion

The conclusion summarizes the paper’s fairness guarantees and impossibility results for online fair division with frequency predictions. It also identifies settings for future study.

7 Conclusion

  • A positive approximation of EF1 is possible if and only if there are at most four agents, while no positive approximation of EFX is possible for three or more.The EFX impossibility holds even when valuations take only two distinct positive values.Source: §7 · p. 14
  • The meta-algorithm yields EEFX, while algorithms fixing a picking sequence in advance guarantee a positive approximation of EFk only when n≤k+2.Frequency predictions thus support EEFX for any number of agents, but fixed picking sequences have the stated EFk boundary.Source: §7 · pp. 14–15
  • For noisy predictions, the algorithms’ first-order losses are best possible; the authors conclude that frequency predictions suffice for own-bundle guarantees such as shares and EEFX, but not EF1 for five or more agents.Source: §7 · p. 15
  • The authors identify the exact four-agent factor and the overestimate threshold for n≥3 as open, alongside extensions to different entitlements, groups, chores, and mixed manna.Source: §7 · p. 15

A Proof of Lemma 2.2

The proof tracks predicted values associated with turns in a picking sequence as goods arrive. This establishes a value-preserving correspondence between online and offline bundles.

A Proof of Lemma 2.2

  • Each turn keeps its original label as turns are deleted, and its associated value is the agent’s corresponding largest remaining predicted value.Source: A Proof of Lemma 2.2 · p. 22
  • The simulation runs the remaining sequence on the arriving good and hypothetical goods; the associated value of every surviving turn never decreases until deletion.The turn that selects the arriving good receives a good worth at least its associated value.Source: A Proof of Lemma 2.2 · p. 22
  • Mapping each online good to the turn deleted when it arrived gives a bijection to the offline bundle in which each online good is worth at least its matched predicted value.Threshold counts then bound the values outside the online bundle using the corresponding offline bundle’s values.Source: A Proof of Lemma 2.2 · p. 22

B Proof of Theorem 3.5

The proof constructs an instance that defeats any algorithm fixing a picking sequence in advance when n≥k+3. It uses identical frequency multisets and stages the arrivals to separate one agent from another’s valuable bundle.

B Proof of Theorem 3.5

  • Each agent’s multiset contains k+1 copies of H and values 1 through ℓ, where ℓ=k(n−1); the construction uses m=nk+1 goods.If an offline bundle is empty, the corresponding online bundle is empty, and another bundle has at least k+1 goods, violating α-EFk.Source: B Proof of Theorem 3.5 · p. 23
  • Because n≥k+3, two agents have no turn among the first k+1 positions; choosing one with the fewest turns gives q≤⌊ℓ/2⌋.Source: B Proof of Theorem 3.5 · p. 23
  • The first q goods are allocated to the selected agent using her largest remaining small values, exhausting her turns before k+1 later goods worth H to her and another agent arrive.The other agent receives all k+1 large goods, while the selected agent receives none of them; the remaining goods use the remaining predicted values.Source: B Proof of Theorem 3.5 · p. 23
  • The selected agent values the other agent’s bundle at least H, so the allocation fails α-EFk; normalization preserves the argument.The construction can use distinct values, and fixing a sequence chosen with positive probability also rules out randomized sequence selection.Source: B Proof of Theorem 3.5 · p. 23

C Proof of Theorem 4.2

The proof uses a common low-value prefix and two final goods to construct an adversarial allocation, then develops rank-based selection rules with guarantees for the rank-three case.

C Proof of Theorem 4.2

  • For any α > 0, the construction uses one value 1 and m − 1 values ℓ per agent, then assigns the final two goods according to who received the prefix.It considers every possible allocation of those final goods and shows that the resulting allocation is not α-EFX; normalization preserves the comparisons, and the argument also applies to randomized algorithms.Source: C Proof of Theorem 4.2 · p. 24

D.1 A Rule for Targets and Marked Goods

  • The targets-and-marked-goods rule satisfies both designated agents, allocates marked goods to different agents, and gives each agent at most two selected goods.The rule selects marked goods, targets of unsatisfied agents, and goods whose label exceeds the third agent’s current maximum; its exceptions preserve the guarantees.Source: §D.1 · p. 25

D.2 The Initial Selections and the Rank-Three Case

  • The initial rank-based rule assigns the first high-rank good to a highest-rank agent, then defines f, c, p, and q for the remaining selections.If every good so far has rank at most 1, it first assigns a positive-rank good to an agent valuing it at rank 1, then ignores goods until a rank-at-least-2 good arrives.Source: §D.2 · p. 26
  • In the rank-three case, the initial selections give q a rank-3 good and p a target, while limiting the selected-good counts for f, p, and c.The subsequent argument bounds higher-ranked occurrences received by the agents and ensures that every occurrence above an agent’s final maximum rank is selected.Source: §D.2 · p. 26

D.3 The Rank-Two Case

The rank-two case handles different rank configurations for the agents and uses the targets-and-marked-goods rule to maintain selection bounds and distribute higher-ranked occurrences.

D.3 The Rank-Two Case

  • When c has no selected good or has rankc(g) = 2, the rule labels c’s remaining positive-rank occurrences and applies Lemma D.1 with f’s rank-3 occurrences marked.If c does not end with rank 3, her remaining rank-3 occurrences go to different agents in {p, q}.Source: §D.3 · p. 27
  • When c = b and rankc(g) = 3, the rule prioritizes p and q’s targets, then routes goods exceeding c’s current rank to c or to p and q.The argument shows that both p and q receive a rank-3 occurrence and at most two selected goods.Source: §D.3 · p. 27
  • When c = b and rankc(g) = 0, the rule branches on the arrival of c’s remaining rank-2 occurrence, then applies Lemma D.1 in two cases.The branches mark f’s rank-3 occurrences when uf remains 2, or mark none otherwise.Source: §D.3 · pp. 27–28
  • The rank-two cases ensure each agent receives at most two selected goods and that occurrences above an agent’s final maximum rank are selected.The proof also ensures certain higher-ranked occurrences are assigned to different agents, depending on whether c ends with maximum rank 1, 2, or 3.Source: §D.3 · pp. 27–28

E Proof of Lemma 5.2

The proof constructs concave, piecewise-linear potentials and bounds their total increase to establish the required potential guarantee and implementation time.

E Proof of Lemma 5.2

  • The potential Φi is nondecreasing, concave, and piecewise linear, with Φi(0) = 0, and its increase over an interval of length ai4 has a stated lower bound.For u < xi, the increase is ai4/((C − 1)ai4 + Cxi); the proof also derives a lower bound for u ≥ xi.Source: E Proof of Lemma 5.2 · pp. 28–29
  • The cited analysis states that S is decreasing in x, handling the proof away from its breakpoints and invoking continuity at the breakpoints to conclude.The final inequality follows from AM-GM and R² < 2C.Source: E Proof of Lemma 5.2 · p. 29
  • The four-agent algorithm has an O(m2)-time implementation because it uses O(m) constant-slope intervals and computes each potential increase in O(m) time.The interval construction follows from Fi ≤ max{m − 7, 0}ai4.Source: E Proof of Lemma 5.2 · p. 29

F Proof of Theorem 5.3

The proof bounds agents’ valuations of other bundles using the constructed potentials. It also establishes polynomial-time consistency and true-value guarantees for the algorithms discussed in Section 6.

F Proof of Theorem 5.3

  • The proof establishes Dwi(Aj) ≤ Cwi(Ai) for distinct agents i and j by combining the bound on unselected goods with a lower bound on ℓi.The argument separately handles whether Aj contains none of agent i’s first four occurrences and whether it contains one that can be removed.Source: F Proof of Theorem 5.3 · pp. 29–30
  • For the case ℓi < xi, removing selected goods of the other agents and one of i’s first four occurrences leaves goods with total value at least Fi.Applying the bound on unselected goods to the other three agents would otherwise imply Fi < Fi.Source: F Proof of Theorem 5.3 · p. 30

G Omitted Proofs in Section 6

  • The Section 6 algorithms are deterministic and polynomial-time; with exact predictions, both rules assign each good its true value and are consistent.Theorem 3.3 is EEFX with respect to predicted valuations regardless of prediction accuracy, and the partition argument proves its guarantees for true values agent by agent.Source: G Omitted Proofs in Section 6 · pp. 30–31

G.1 Proof of Theorem 6.1(i)

The proofs establish value bounds for noisy predictions and use consistency to derive lower bounds on achievable EEFX guarantees. Underestimates yield an aggregate excess bound, while overestimates admit a refined guarantee for at least three agents and constructions limiting what consistent algorithms can achieve.

G.1 Proof of Theorem 6.1(i)

  • For underestimates, an arrival-by-arrival matching ensures each true value is at least its assigned predicted value, and the aggregate excess is at most (ρ−1)V.The proof uses this bound to establish an EEFX factor for the agent’s bundle.Source: §G.1 · p. 31

G.2 Proof of Theorem 6.1(ii): General Bound

  • For overestimates, the exchange argument gives true values no larger than assigned predictions, while sorted true values remain at least 1/ρ of predicted values.These sorted bounds underpin the general comparison guarantee.Source: §G.2 · p. 32

G.3 Proof of Theorem 6.1(ii): Refined Bound for Three or More Agents

  • For n ≥3, the refined overestimate guarantee is at least ρ^−(2n−2), which is at least 1−2(n−1)ε.The proof treats separately the case where every remaining part consists of a pair of goods.Source: §G.3 · pp. 33–34

G.4 Proof of Theorem 6.1: Lower Bound for Underestimates

  • Underestimates rule out any consistent guarantee β greater than 1/(ρ+1−a), using predictions with a final value that differs between exact and inaccurate continuations.Here a=1/ρ; the contradiction uses the allocation forced by consistency on the exact continuation.Source: §G.4 · p. 34

G.5 Proof of Theorem 6.1: Lower Bound for Overestimates

  • For overestimates and n≥3, the construction rules out any consistent β-EEFX guarantee above ρ^−2(n−1).The exact continuation forces an agent to remain empty before the last arrival; the inaccurate continuation then makes that agent’s bundle too small.Source: §G.5 · pp. 34–35

G.6 Proof of Theorem 6.2

The proof uses consistent algorithms’ required behavior on exact continuations to derive impossibility results for overestimated predictions. It establishes a threshold for two agents, extends the construction to three or more, and shows that the restrictions also apply to randomized algorithms.

Two agents

  • For two agents, no consistent algorithm guarantees a positive EFX approximation under overestimates with error factor 2 or larger.For error factor ρ<2, the cited bound is (2−ρ)/ρ^2.Source: §G.6 · p. 35

Three or more agents

  • The exact-continuation argument rules out three disjoint bundles in Q satisfying the stated EFX partition condition, constraining which agents can receive the large goods.It is used to show that the goods of value J go to distinct recipients and the good of value 1 forms another agent’s bundle.Source: §G.6 · p. 36
  • For n≥3, the construction with error factor 3/2 forces an agent left empty before the final arrival to receive the last good, yet bounds her EEFX factor by ρ^−2(n−1).Choosing the construction parameter h sufficiently large makes this bound smaller than any proposed positive guarantee.Source: §G.6 · pp. 35, 37

Conclusion

  • The impossibility arguments also apply to randomized algorithms because the exact and inaccurate continuations share predictions and the same number of goods.The allocation restrictions on earlier goods follow for every sequence of allocation decisions.Source: §G.6 · p. 37

Related papers

Loading 2610.34625v1…