Preprint
Sep 2026
Randomized Online Fair Division: High-Probability and Expected Realized Fairness
We study randomized algorithms for the fully online allocation of indivisible goods among $n\ge2$ agents with nonnegative additive valuations. Goods arrive sequentially and must be allocated immediately and irrevocably, with only $n$ known in advance. Since exact ex-ante envy freeness and proportionality are readily ac...
Tian-Qi Chen, Jing-Xiao Long
· 1 citation