PaperlayerView exact revision on arXiv

Source-linked AI summary

Online Fair Division Against an Oblivious Adversary

Saar Cohen, Nicholas Teh, Michael Wooldridge

arXiv:2609.28333v1cs.GT

TL;DR

Online allocation requires irrevocable decisions without knowing future goods, and adaptive adversaries preclude goods-independent approximations to PROP1 or fixed-k PROPk. Deficit Allocation retains unmatched fractional value and favors agents with larger deficits when allocating goods. DA gives Ω(1/loglog(n/δ))-PROP1 with probability at least 1−δ; α-EF1 success is at most e−Ω(n), α-EFX at most 1/n! with n+1 goods, and α-MMS success is uniformly bounded away from one for positive factors.

  • Problem

    Online allocation requires irrevocable decisions without knowing future goods, and adaptive adversaries preclude goods-independent approximations to PROP1 or fixed-k PROPk.

    Source: §1 · p. 2

  • Method

    Deficit Allocation retains unmatched fractional value and favors agents with larger deficits when allocating goods.

    Source: §1.2 · p. 5, §7 · p. 23

  • Results

    DA gives Ω(1/loglog(n/δ))-PROP1 with probability at least 1−δ; α-EF1 success is at most e−Ω(n), α-EFX at most 1/n! with n+1 goods, and α-MMS success is uniformly bounded away from one for positive factors.

    Source: §1.1 · p. 4, §7 · p. 23

  • Takeaways & Limitations

    The guarantees differ by fairness notion: proportionality improves through history-aware allocation, while approximate envy-freeness is attainable with high probability when logarithmically many goods may be removed.

    Source: §1.1 · p. 4, §7 · p. 23

    Whether unrestricted inputs permit a constant worst-case expected realized PROP1 guarantee, or whether the doubly logarithmic guarantee can coexist with exact ex-ante proportionality, remains open.

    Source: §7 · p. 23

Abstract

from arXiv · show

We study the online allocation of indivisible goods among $n$ agents, where each good must be allocated immediately and irrevocably upon arrival. Against an adaptive adversary, Neoh and Teh [2026] proved that no algorithm can guarantee a positive approximation to proportionality up to one good (PROP1) that is independent of the number of goods, and the same holds for proportionality up to $k$ goods (PROP$k$) for any fixed $k$. We instead consider an oblivious adversary, which fixes the input in advance. Choo et al. [2026] showed that the uniformly random allocation returns a $\Theta(1/\log(n/\delta))$-PROP1 allocation with probability at least $1-\delta$. We improve this to $\Omega(1/\log\log(n/\delta))$; our algorithm does not take $\delta$ as input, so the same algorithm achieves this bound for every $\delta\in(0,1)$. Moreover, with the same probability, a variant of our algorithm gives every agent almost her bundle, and even without adding any good when no single good is too valuable relative to this share. In contrast, for envy-freeness up to one good (EF1), we show that, for every $\alpha\in(0,1]$, every randomized algorithm has an input on which its probability of returning an $\alpha$-EF1 allocation is at most $e^{-\Omega(n)}$. For envy-freeness up to any good (EFX), this probability is at most $1/n!$ with only $n+1$ goods, a bound that is optimal within a factor of $(n+1)/2$. For the maximin share (MMS), this probability is at most $5/6$, however small $\alpha$ is. Allowing more removals gives a positive envy-freeness guarantee: allocating each good to a uniformly random agent among those with positive values achieves, with high probability, an approximation factor arbitrarily close to one for envy-freeness up to logarithmically many goods, and logarithmically many goods are necessary for this rule.

1 Introduction

The paper studies irrevocable online allocation under an oblivious adversary, seeking realized fairness guarantees despite unknown future goods. It improves proportionality guarantees with an allocation rule that accounts for prior allocations, while showing that envy-based guarantees remain difficult unless more goods may be removed.

1 Introduction

  • Online goods must be allocated immediately and irrevocably, and PROP1 asks that each agent reach her proportional share after adding one outside good.Although PROP1 allocations always exist when all goods are known in advance, online decisions must be made without knowing how many goods remain or their values.Source: §1 · p. 2

1.1 Our Results

  • Ω(1/ log log(n/δ))-PROP1 is achieved with probability at least 1 −δ by Deficit Allocation, improving the uniformly random allocation’s Θ(1/ log(n/δ)) guarantee.DA does not take δ as input; the comparison guarantee is from Choo et al. [2026].Source: §1 · p. 2, §1.1 · p. 3
  • With probability at least 1 −δ, a DA variant gives each agent at least (1 −ε)µi −Oε(νi log log(n/δ)); under a small-good condition it gives (1 −ε) of her proportional share without adding a good.Here µi is fractional-benchmark utility and νi is the agent’s largest single-good value; the variant also achieves (1 −ε)-PROPk for k = Oε(log log(n/δ)).Source: §1.1 · pp. 3–4
  • For every α ∈(0, 1], some input limits every randomized algorithm’s α-EF1 success probability to e−Ω(n), and its α-EFX success probability to 1/n! with n + 1 goods.The EFX bound is tight up to a factor of (n + 1)/2.Source: §1.1 · p. 4
  • For every α ∈(0, 1], some input limits the probability of an α-MMS allocation to 1 −⌊n/2⌋/(2n), at most 5/6.The lower bound relies on goods large relative to agents’ shares; the small-good condition for Corollary 4.2 also guarantees near-MMS allocations.Source: §1.1 · p. 4
  • Like achieves (1 −ε)-EFk with probability at least 1 −δ for k = O(ε−1 log(n/δ)), and this rule needs logarithmically many removals over a range of parameters.Like assigns each good independently and uniformly among agents who value it positively; the result is exact ex-ante envy-free as well.Source: §1.1 · p. 4

1.2 Our Techniques

  • DA keeps per-agent, per-scale deficits for unmatched fractional value and favors larger deficits using probabilities proportional to doubly exponential weights.The doubly exponentially small tail probability for large deficits makes the loss O(log log(n/δ)) times the largest single-good value, without a union bound over scales or arrivals.Source: §1.2 · p. 5

1.3 Related Work

  • The paper improves on prior oblivious-adversary proportionality bounds by correlating allocations across arrivals, while Chen and Long [2026] retain exact ex-ante proportionality where DA does not.Choo et al. [2026] established the uniformly random allocation baseline; the paper also contrasts its no-advance-information guarantees with work using information about future values [Neoh et al., 2026; Du and Sun, 2026; Neoh and Teh, 2026].Source: §1.3 · p. 6

2 Preliminaries

The model is fully online under an oblivious input, and evaluates fairness through proportionality, envy-freeness, and maximin-share criteria, as well as ex-ante notions.

Online model

  • Goods arrive sequentially with current valuations revealed, and each must be allocated immediately and irrevocably; the input is fixed before the algorithm runs.Algorithms know only n in advance, not the number of goods, future valuations, maximum good value, or agents’ total values.Source: §2 · p. 7

Proportionality

  • PROPk requires each agent’s utility plus the value of at most k outside goods to reach an α fraction of her total value divided by n.For k = 1 this is PROP1; the benchmark µi is a fractional allocation that divides each good equally among agents who value it positively.Source: §2 · pp. 7–8

Envy-freeness and MMS

  • EFk compares an agent’s utility with her value for another agent’s bundle after removing up to k goods, while EFX requires the comparison to hold after removing any one good.The maximin share is the value an agent can guarantee by partitioning the goods into n bundles and receiving her least-preferred bundle.Source: §2 · p. 8

Ex-ante fairness

  • The paper also considers ex-ante proportionality and envy-freeness, which compare expected utilities; its realized fairness ratios take the minimum across agents before expectation.Success probabilities concern simultaneous fairness of the final allocation.Source: §2 · pp. 8–9

3 Approximate PROP1 via Deficit Allocation

Deficit Allocation (DA) uses earlier allocations to favor agents whose fractional share is under-matched, yielding a high-probability PROP1 guarantee that improves with fewer agents valuing each good.

Deficit Allocation

  • DA allocates a good to an interested agent with probability proportional to her fractional amount times a doubly exponential weight in her current deficit.Each relevant deficit increases by the agent’s fractional amount; the recipient’s deficit decreases by six, but not below zero.Source: §3 · p. 9

Guarantee

  • With probability at least 1 − δ, DA returns an Ω(min{1, n/(κ log log(n/δ))})-PROP1 allocation, and thus an Ω(1/log log(n/δ))-PROP1 allocation.Here κ is the maximum number of agents who value a single good positively.Source: §3 · p. 10
  • DA takes neither δ nor κ as input, so the same algorithm satisfies the guarantee for every δ and benefits from small κ without knowing it.The guarantee includes an explicit factor min{1, n/(κ(12 + 4Bn,δ))}.Source: §3 · pp. 10–11

Analysis

  • The deficit accounting compares fractional utility with received utility and final deficits, while a doubly exponential tail bound controls the deficits with high probability.The proof’s probabilistic step bounds deficits, then combines the scales and applies a union bound over agents.Source: §3 · p. 10

Consequences

  • DA also has expected PROP1 ratio Ω(min{1, n/(κ log log n)}); when µi is sufficiently large relative to νi, it guarantees utility without adding an outside good.Specifically, µi ≥ 8Bn,δνi for every agent yields vi(Ai) ≥ µi/24 on the same event.Source: §3 · p. 11

4 Near-Proportionality and PROPk

The section refines proportionality guarantees and studies PROPk, while showing that DA need not be exactly ex-ante proportional even on a two-agent, two-good instance.

4.1 Preserving almost the entire fractional share

  • With probability at least 1 − δ, Aε gives each agent utility at least (1 − ε)µi − Oε(νi log log(n/δ)); under a small-good condition it reaches (1 − ε)Vi/n.The condition is Vi/n ≥ Kενi log log(n/δ), and the latter guarantee holds with probability at least 1 − δ.Source: §4.1 · pp. 11–12

4.2 Proportionality up to k goods

  • With probability at least 1 − δ, DA achieves Ω(min{1, nk/(κ log log(n/δ))})-PROPk; the refined method guarantees (1 − ε)-PROPk for k = Oε(log log(n/δ)).It gives exact PROPk when κ ≤ (1 − ε)n, including when every good is valued at zero by at least an ε fraction of agents.Source: §4.2 · p. 12

4.3 Exact ex-ante proportionality

  • DA is not ex-ante proportional even for two agents and two goods.The section notes that realized guarantees do not imply exact ex-ante proportionality.Source: §4.3 · p. 13

5 Lower Bounds Against an Oblivious Adversary

The section establishes lower bounds against an oblivious adversary, showing that high-probability PROP1 guarantees do not extend to EF1, MMS, or EFX. In particular, with n + 1 goods, exact PROP1 is deterministically achievable, yet every randomized online algorithm can have EFX success probability at most 1/n!, and the optimal worst-case expected realized EFX guarantee is exponentially small in n.

5 Lower Bounds Against an Oblivious Adversary

  • Each lower bound is obtained from a finite distribution over inputs chosen before the algorithm runs, yielding at least one fixed input with the stated success-probability bound.The argument first bounds deterministic rules on a random input, then fixes a randomized algorithm's choices and averages over them.Source: §5 · p. 14

5.1 Exponentially small success probability for EF1

  • For every α in (0, 1], EF1 success is at most e^-Ω(n) on some fixed input with O(n) goods, even when all values are positive, drawn from four levels, and the goods count is known.The exponent is uniform in α; moreover, O_a(ln n) goods beyond the first n suffice for success probability at most n^-a for any fixed a > 0.Source: §5.1 · p. 14

5.2 Success probability for MMS

  • For every α in (0, 1], some fixed input limits MMS success to 1 −⌊n/2⌋/(2n), regardless of how small α is.This is 3/4 for even n and 3/4 + 1/(4n) for odd n; the input can have exactly 2n −⌊n/2⌋ goods with values in [0, 1].Source: §5.2 · pp. 17–18

5.3 EFX with only n + 1 goods

  • With n + 1 goods, the probability of an α-EFX allocation is at most 1/n!, while some randomized algorithm achieves exact EFX with probability at least 2/((n + 1)n!).The lower bound holds with strictly positive values at most one and a known goods count; a single incorrect choice among the first n − 1 arrivals rules out α-EFX.Source: §5.3 · pp. 18–19
  • With n + 1 goods, exact PROP1 is deterministically achievable, so the PROP1–EFX gap already arises with one more good than agents.Give the first n goods to distinct agents and allocate the last good arbitrarily.Source: §5.3 · p. 20
  • The optimal worst-case success probability for each positive EFX factor and expected realized EFX guarantee are exp(−n ln n + n + O(ln n)).These bounds apply when the input is restricted to n + 1 goods.Source: §5.3 · p. 20
  • With n + 1 goods, every randomized online algorithm has an input on which its probability of returning an α-EFX allocation is at most 1/n!.This holds for every α ∈ (0, 1].Source: §5.3 · p. 20
  • The result shows that exponentially small success probability persists even when the algorithm knows agents’ maximum values, using only three positive values.Source: §5.3 · p. 20

6 Approximate Envy-Freeness up to k Goods

Like and Rand achieve high-probability approximate EFk with logarithmically many removals, while the logarithmic dependence is necessary for Like. Like also retains exact ex-ante envy-freeness.

6 Approximate Envy-Freeness up to k Goods

  • Like and Rand return (1 − ε)-EFk allocations with high probability for a removal count depending on n, δ, and accuracy, but not on the number or values of goods.Neither rule needs the number of goods or the parameters ε, k, or δ as input.Source: §6 · pp. 20–21
  • A single probability bound over every position in an agent’s value ordering controls pairwise count differences and yields the realized EFk guarantee.Like also retains exact ex-ante envy-freeness, so the realized guarantee coexists with that ex-ante property.Source: §6 · p. 21

6.1 Matching dependence for Like

  • For Like, logarithmically many removals are necessary: independent allocations can make a pair’s bundle sizes differ by more than k, and every pair must satisfy the condition.The matching-dependence result is specific to Like; Balanced Like achieves exact EF1 on binary-valued inputs.Source: §6.1 · p. 22
  • For Like and Rand, the lower bound on required removals matches the logarithmic dependence on n, δ, and ε in the high-probability guarantee within the stated range.The construction uses disjoint agent pairs and independent allocation across pairs.Source: §6.1 · p. 22

7 Conclusion

The paper’s guarantees depend on the fairness notion: proportionality admits improved online guarantees, while EF1, EFX, and MMS face lower bounds on success probability. Allowing logarithmically many removals makes approximate envy-freeness attainable, and a constant worst-case expected PROP1 guarantee remains an open question.

7 Conclusion

  • Deficit Allocation improves the dependence on n/δ for proportionality, while no algorithm can guarantee high success probability for approximate EF1 or MMS on every input.For EFX, the success probability can be at most 1/n! with only n + 1 goods.Source: §7 · p. 23
  • Allowing more removals also yields envy-freeness: Like achieves (1 − ε)-EFk with k = O(ε^-1 log(n/δ)), and its worst-case expected EFk ratio is 1 − Θ(log n/k) for k ≥ log n.Source: §7 · p. 23
  • Whether a constant worst-case expected realized PROP1 guarantee is achievable on unrestricted inputs, or requires dependence on n, remains open.It is also open whether the doubly logarithmic guarantee can coexist with exact ex-ante proportionality for Deficit Allocation.Source: §7 · p. 23

A Further Related Work

  • Offline randomized rounding can combine ex-ante fairness with realized guarantees, but those algorithms use all valuations before allocating any good.This paper instead studies allocations made before future goods are known.Source: A Further Related Work · p. 28
  • The paper’s guarantees apply to every fixed input with unrestricted nonnegative additive valuations, unlike cited results for restricted valuation classes or stochastic arrivals.Those earlier results include exact EF1 for binary valuations and high-probability guarantees under independent draws.Source: A Further Related Work · p. 28
  • The correlated-selection analysis tracks deficits remaining after repeated selections, rather than only whether an element was selected in specified rounds.Its selection constraint also differs from processor-scheduling results, which can reduce any accumulated total rather than only the recipient’s deficit at the current good’s scale.Source: A Further Related Work · pp. 28–29

B Joint Deficit Bounds for the Proofs of Theorems 3.1 and 4.1

The appendix proves a joint deficit bound for fixed fractional amounts, extending an outside-set argument to also handle selection within the set. Its induction applies to every set and threshold vector.

B Joint Deficit Bounds for the Proofs of Theorems 3.1 and 4.1

  • DA uses agent–scale pairs as elements, while the refined algorithm uses copies of those pairs; their fractional amounts are fixed by the input.The algorithm need not know those amounts before the elements arrive.Source: B Joint Deficit Bounds for the Proofs… · p. 29
  • The bound covers every round, set S, and vector of nonnegative thresholds.It is proved by induction over rounds.Source: B Joint Deficit Bounds for the Proofs… · p. 30
  • For selection within S, the selected element’s deficit must exceed the threshold without selection by at least c − ξ, keeping this case small enough to preserve the bound.The proof uses the rapid decrease of the right-hand side and chooses weights that keep relevant weighted expectations finite.Source: B Joint Deficit Bounds for the Proofs… · p. 30
  • For selection outside S, a jointly concave weight function and Jensen’s inequality control the probability bound.The induction and concavity argument for selection outside the set follows Gao et al. [2021a, Theorem 9].Source: B Joint Deficit Bounds for the Proofs… · pp. 29–30
  • The proof combines the outside- and within-set cases to complete the induction.The appendix identifies handling selection within the set as the additional argument beyond the cited outside-set approach.Source: B Joint Deficit Bounds for the Proofs… · pp. 29, 31

B.1 Parameters for Deficit Allocation in the Proof of Theorem 3.1

The proof of Theorem 3.1 instantiates the joint deficit lemma with fixed parameters, verifies its conditions, and applies its singleton case to DA.

B.1 Parameters for Deficit Allocation in the Proof of Theorem 3.1

  • γ = 1, β = 4/3, θ = 1/3, and c = 6, with ξ = 1, are the parameters used for DA.Source: §B.1 · p. 32
  • The proof verifies all three lemma conditions, including the third using C = 3/2 and γ(β − 1) = 1/3.Source: §B.1 · p. 32
  • After omitting all-zero arrivals, DA’s fractional amounts sum to one per round and are input-fixed, so the lemma applies to encountered agent–scale pairs.The singleton case proves (3).Source: §B.1 · p. 32

C Proof of Theorem 4.1

Theorem 4.1 is proved by applying the joint deficit analysis to copies in the refined algorithm and summing the resulting bounds over scales and copies. The proof obtains a per-agent guarantee with probability at least 1 − δ.

C Proof of Theorem 4.1

  • The analysis verifies the joint deficit bound when each decrease is only 1 + ε/2, then sums the bounds over scales and copies.Source: C Proof of Theorem 4.1 · p. 32
  • The proof applies the joint deficit lemma to copies, each receiving at most ξ ≤ ε/8 fractional amount per round, with amounts across copies summing to one.The per-copy weight is the algorithm’s weight.Source: C Proof of Theorem 4.1 · p. 32
  • Each selection corresponds to a distinct good given to the relevant agent, valued at least (1 + ε/2)d, while fractional amounts across copies sum to the original benchmark amounts.Source: C Proof of Theorem 4.1 · p. 33
  • 11 log log(n/δ) bounds B_n,δ, and the resulting per-agent inequality holds with probability at least 1 − δ.The factor C_ε depends only on ε.Source: C Proof of Theorem 4.1 · p. 33

C.1 The refined guarantee in the proof of Theorem 4.3

The proof of the refined guarantee restricts its accounting to scales below an agent’s kth-largest value and combines that bound with the other inequalities used in the main proof.

C.1 The refined guarantee in the proof of Theorem 4.3

  • For an agent valuing at least k goods positively, the set G_i of goods at scales above her kth-largest value a_i has size less than k.The proof states that (7) and (8) also apply to this set.Source: §C.1 · p. 33
  • The proof restricts accounting to scales with (1 + ε/2)d ≤ a_i and bounds their total coefficient, including L copies.It applies the convexity and Markov argument to obtain a high-probability bound.Source: §C.1 · pp. 33–34
  • A union bound gives the comparison used in Theorem 4.3 at accuracy ε/2 without changing the allocation or removing arrivals from the run.Agents with fewer than k positively valued goods satisfy the inequality deterministically.Source: §C.1 · p. 34

D Probability Estimates in the Proof of Theorem 5.1

The proof estimates random intersections and group occupancy under a fixed allocation structure. It also invokes a concentration bound for independent fair bits.

D Probability Estimates in the Proof of Theorem 5.1

E Proof of Proposition 6.2

The proof constructs a fixed input with independent pairs of agents and analyzes Like’s allocations within each pair. It compares a binomial allocation distribution with a shifted binomial distribution to bound pairwise violations.

E Proof of Proposition 6.2

  • The fixed input pairs 2⌊n/2⌋ agents, gives each pair m0 = 2⌈k/ε⌉ goods valued at one by its members, and Like allocates independently within each pair.Any remaining agent values all goods at zero.Source: E Proof of Proposition 6.2 · p. 35
  • For a pair, the first agent’s allocation count X follows Bin(m0, 1/2), and the proof tests whether that agent violates (1−ε)-EFk.Since m0 ≥ 2k/ε, the violation threshold is at least (1−ε)m0/2.Source: E Proof of Proposition 6.2 · p. 35
  • The proof compares Bin(m0, 1/2) with Bin(m0, 1/2−ε), using an event below the violation threshold and Chebyshev’s inequality.It also bounds the ratio of binomial probabilities using ln u ≤ u−1.Source: E Proof of Proposition 6.2 · p. 35
  • A (1−ε)-EFk allocation must satisfy the pairwise comparison in every pair, and allocations of distinct pairs are independent.The proof combines this requirement with a lower bound on the one-pair event probability to obtain an upper bound on overall success.Source: E Proof of Proposition 6.2 · p. 35

F Proof of Theorem 5.5

The proof chooses a uniform hidden subset of agents and presents n+1 goods with specified valuations. It bounds how many choices of the hidden subset can permit success, then uses averaging to obtain a fixed input.

F Proof of Theorem 5.5

  • The construction chooses a uniform q-element set S before presenting n+1 goods, with q = ⌊n/2⌋.The final good makes every maximum value equal to one, while the initial valuation vectors and announced maxima do not reveal S.Source: F Proof of Theorem 5.5 · p. 36
  • For a deterministic rule, the recipients C of the first q goods are independent of S, and success requires a restriction on S relative to C.If |C|=q, at most 1+q(n−q) sets S satisfy that restriction; smaller C gives no more possibilities.Source: F Proof of Theorem 5.5 · p. 36
  • If two members of S receive no initial good, one receives neither an initial nor the final good, forcing singleton and two-good bundle constraints.These constraints imply initial recipients are distinct; then an agent in C\S must have utility α/4 while some middle-good bundle gives her value at least α, a contradiction.Source: F Proof of Theorem 5.5 · p. 36
  • The argument allows any allocation of later goods after their values are revealed, and averaging over random choices yields a fixed input proving the bound.Source: F Proof of Theorem 5.5 · p. 36
Loading 2609.28333v1…