Approximate Proportionality in Online Fair Division

We study the online fair division problem, where indivisible goods arrive sequentially and must be allocated immediately and irrevocably. Prior work establishes strong impossibility results for approximating classic notions such as envy-freeness up to one good (EF1) and maximin share (MMS) in this setting, but the approximability of proportionality up to one good (PROP1) has remained unresolved. We resolve this gap in two steps. First, we show that three natural greedy allocation rules (standard baselines in fair division) fail to guarantee any multiplicative approximation to PROP1 against an adaptive adversary. These limitations motivate two relaxations: (i) restricting attention to a non-adaptive adversary, and (ii) incorporating coarse predictions in the spirit of learning-augmented algorithms. Under a non-adaptive adversary, we show that the uniform random allocation achieves a meaningful PROP1 approximation with high probability, and this guarantee is essentially tight for this approach; moreover, when item values are sufficiently small, the allocation is near-PROP1 with high probability. Finally, given maximum item value (MIV) predictions, we design an online algorithm that achieves robust approximation guarantees for PROP1, and degrades gracefully under one-sided prediction error. In contrast, we show that EF1, MMS, and PROPX remain inapproximable even with perfect MIV predictions.

Many online platform allocate items as they arrive; e.g., ad impressions, tasks, service requests, or rides, one at a time, without knowing what will arrive next. This makes achieving fairness difficult: a choice that looks fair now may look unfair after future items appear. This paper studies a practical fairness goal called “proportionality up to one item”, meaning that every participant should get roughly their fair share, after accounting for at most one item they missed. We first show that three natural greedy rules, which make the locally obvious choice at each step, can be forced to fail badly. We then identify two ways to recover meaningful guarantees. If the sequence of items is fixed in advance, assigning each item randomly can provide fairness with high probability, especially when no single item is too valuable. If the system has a rough prediction of each participant’s largest possible item value, we design an online algorithm that remains fair even when these predictions are conservatively overestimated. We also show that stronger fairness goals remain impossible under the same weak predictive information, highlighting why this particular target is the right level for online settings. Overall, we show that a modest fairness target, combined with randomness or lightweight predictions, can make sequential allocation systems more reliable.