Researchers crack online fair division with new PROP1 approximation algorithm

A team of computer scientists (Davin Choo, Winston Fu, Derek Khu, Tzeh Yuan Neoh, Tze-Yang Poon, Nicholas Teh) has resolved a key open problem in online fair division: the approximability of proportionality up to one good (PROP1) when indivisible items arrive sequentially and must be allocated immediately. Their paper, accepted at ICML 2026, first demonstrates that three natural greedy allocation rules—standard baselines in fair division—fail to guarantee any multiplicative approximation to PROP1 against an adaptive adversary. This impossibility motivated two relaxations: restricting to non-adaptive adversaries and using coarse predictions in a learning-augmented setting.

Under a non-adaptive adversary, the authors show that uniform random allocation achieves a meaningful PROP1 approximation with high probability, and this guarantee is essentially tight. Moreover, when item values are sufficiently small, the allocation is near-PROP1 with high probability. Given maximum item value (MIV) predictions, they design an online algorithm with robust approximation guarantees for PROP1 that degrades gracefully under one-sided prediction error. In contrast, they prove that stronger fairness notions like envy-freeness up to one good (EF1), maximin share (MMS), and PROPX remain inapproximable even with perfect MIV predictions. This work provides practical tools for real-time resource allocation in ad exchanges, cloud computing, and emergency response systems.