Randomized Online Fair Division: High-Probability and Expected Realized Fairness

Tianqi Chen, Jingxiao Long

We study randomized algorithms for the fully online allocation of indivisible goods among $n\ge 2$ agents with nonnegative additive valuations. Goods arrive sequentially and must be…