Closing Gaps in Online Fair Division
Tzeh Yuan Neoh, Nicholas Teh
cs.GT
2026-09-05
No online algorithm approximates PROPk against adaptive adversaries; a per-agent max-item-value prediction lifts PROP1 from 1/n to 1/2, or n/(n+κ) when overlap is bounded.
Goods arrive one at a time and must be given to someone immediately, with no later swaps. Ad impressions, recommendation slots, and shared compute queues look like this. Offline, PROP1 (proportionality up to one good: after adding at most one missed item, each agent reaches a 1/n share of their total value) is a weak floor that EF1 and MMS already imply. Online, those stronger notions are known to be inapproximable. The open question was whether the hardness comes from the strength of EF1/MMS, or from irrevocable online assignment itself, which might already forbid every positive multiplicative approximation to PROP1.
Choo et al. had ruled out selected greedy rules and obtained 1/n-PROP1 from a max-item-value prediction. This paper closes three remaining gaps.
The first result is negative. For every n≥2, k≥1, and α in (0,1], no online algorithm can guarantee α-PROPk against an adaptive adversary. The claim survives a known horizon, values in [0,1], and the restriction that at most two agents value any good. Randomization does not help against an adaptive adversary. The proof reduces PROPk to PROP1 (α-PROPk implies (α/k)-PROP1), then reduces n agents to two. For two agents it tracks the normalized slack in each agent's current PROP1 inequality. The adversary repeatedly pushes one slack back into a controlled range while decreasing the other by a fixed amount, until both sit below a threshold; one last good valued by both agents then breaks the agent who does not receive it. Standard implications extend the same impossibility to EF, EFX, EF1, MMS, PROPX, and related notions. For chores the bound is stronger: no λ-PROPk exists for any λ<n.
The second result uses a cheap prediction: one scalar per agent, their maximum item value (MIV), with no total value and no arrival order. The algorithm books that predicted maximum as the one outside good PROP1 allows, maintains a potential equal to the sum of reciprocals of normalized slacks, and assigns each arriving good to a recipient that does not raise the potential. For every affected agent there is a receive probability that leaves their reciprocal term unchanged in expectation; those probabilities sum to at most 1, so some deterministic recipient exists. With no extra information this is 1/2-PROP1. If at most κ agents value any good, the factor becomes n/(n+κ). Under one-sided overestimates of relative error at most ε, it becomes n(1-ε)/(n+κ-ε), still a positive constant for every fixed ε<1.
When the horizon T is known and T≥n log n, the reciprocal potential is combined with Benadè et al.'s exponential envy potential. Each agent first gets the probability that preserves their reciprocal term; leftover probability is split equally. For every fixed β in (0,1/2) this yields β-PROP1 together with O(√(T log n / n)) maximum additive envy after dividing each agent's values by their predicted maximum.
The third result compares two classical randomized rules against a non-adaptive adversary. Rand assigns each good uniformly among all n agents; Like assigns it only among agents who value it positively. Like's high-probability PROP1 factor is Θ(min{1, n/(κ log(n/δ))}), which improves on Rand's Θ(1/log(n/δ)) by about n/κ when few agents like each good. Both bounds are tight. Additive envy flips the comparison: Like has larger relevant variance, and on binary instances its expected maximum envy can be Ω(√(m/κ)).
| Setting | Guarantee | Baseline |
| No predictions, adaptive adversary | no α-PROPk for any α>0 | prior negatives covered selected greedy rules |
| Exact MIV predictions | 1/2-PROP1 (n/(n+κ) if κ is known) | 1/n-PROP1 in Choo et al. |
| MIV with one-sided error ε | n(1-ε)/(n+κ-ε)-PROP1 | factor degrades continuously in ε |
| Known T≥n log n plus MIV | any fixed β<1/2 as β-PROP1, plus O(√(T log n / n)) normalized max envy | a shorter appendix argument only reaches Θ(1/log n)-PROP1 |
| Like vs non-adaptive adversary | Θ(min{1, n/(κ log(n/δ))}) | Rand stays Θ(1/log(n/δ)) even when κ=1 |
For chores, every multiplicative PROPk factor strictly below n is impossible.
This draws a boundary for any "assign on arrival" pipeline: ads, recommendations, compute scheduling. Give the algorithm no future information, and multiplicative proportionality is gone, even if each agent may add k extra goods. Store one extra number per agent (their predicted per-item maximum) and PROP1 jumps from 1/n to a constant independent of n. The Like/Rand split is operational: Like is the better proportionality rule when items have narrow audiences, and the worse envy rule.
This is a theory paper, not a drop-in scheduler. The online rule uses O(n) arithmetic per good, which is easy. Getting an MIV prediction, and living with preferences that are not additive, is not.
The impossibility is for adaptive adversaries. Randomization against a non-adaptive adversary does give positive guarantees; the two numbers should not be mixed. An MIV forecast is still future information, and one-sided overestimates require the error to point the right way. The simultaneous envy bound is additive envy after per-agent max-value normalization, not EF1. Like's tight bound uses binary valuations. Chen and Tan compare online fairness with the best offline fairness on the same instance, which is a different ratio from the direct PROP share used here.