# Online Fair Division with Additional Information

arXiv: https://arxiv.org/abs/2505.24503 · HTML: https://mlsanity.com/paper/2505.24503/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 67 of its 106 references that are in the map.
- First posted on arXiv 30 May 2025.

## Builds on (most cited first, 30 of 67)

- [Almost Envy-Freeness with General Valuations](https://mlsanity.com/paper/1707.04769/) (2017)
- [Fair Public Decision Making](https://mlsanity.com/paper/1611.04034/) (2016)
- [Fair Division of Indivisible Goods: Recent Progress and Open Questions](https://mlsanity.com/paper/2208.08782/) (2022)
- [Online Fair Division: analysing a Food Bank problem](https://mlsanity.com/paper/1502.07571/) (2015)
- [Proportional Aggregation of Preferences for Sequential Decision Making](https://mlsanity.com/paper/2306.14858/) (2023)
- [Online Fair Division: A Survey](https://mlsanity.com/paper/1911.09488/) (2019)
- [Online Nash Social Welfare Maximization with Predictions](https://mlsanity.com/paper/2008.03564/) (2020)
- [EFX Exists for Three Agents](https://mlsanity.com/paper/2002.05119/) (2020)
- [Temporal Fairness in Multiwinner Voting](https://mlsanity.com/paper/2312.04417/) (2023)
- [Universal and Tight Online Algorithms for Generalized-Mean Welfare](https://mlsanity.com/paper/2109.00874/) (2021)
- [Online Bin Packing with Predictions](https://mlsanity.com/paper/2102.03311/) (2021)
- [Repeated Fair Allocation of Indivisible Items](https://mlsanity.com/paper/2304.01644/) (2023)
- [Temporal Elections: Welfare, Strategyproofness, and Proportionality](https://mlsanity.com/paper/2408.13637/) (2024)
- [Temporal Fair Division of Indivisible Items](https://mlsanity.com/paper/2410.14593/) (2024)
- [Multiwinner Temporal Voting with Aversion to Change](https://mlsanity.com/paper/2408.11017/) (2024)
- [Fairness-Efficiency Tradeoffs in Dynamic Fair Division](https://mlsanity.com/paper/1907.11672/) (2019)
- [Online Approval Committee Elections](https://mlsanity.com/paper/2202.06830/) (2022)
- [Single-Leg Revenue Management with Advice](https://mlsanity.com/paper/2202.10939/) (2022)
- [Better Collective Decisions via Uncertainty Reduction](https://mlsanity.com/paper/2207.04983/) (2022)
- [Proportionally Fair Online Allocation of Public Goods with Predictions](https://mlsanity.com/paper/2209.15305/) (2022)
- [Verifying Proportionality in Temporal Voting](https://mlsanity.com/paper/2502.05949/) (2025)
- [Strengthening Proportionality in Temporal Voting](https://mlsanity.com/paper/2505.22513/) (2025)
- [Approximation Algorithms for Maximin Fair Division](https://mlsanity.com/paper/1703.01851/) (2017)
- [Democratic Fair Allocation of Indivisible Goods](https://mlsanity.com/paper/1709.02564/) (2017)
- [Multiple Birds with One Stone: Beating 1/2 for EFX and GMMS via Envy Cycle Elimination](https://mlsanity.com/paper/1909.07650/) (2019)
- [Repeatedly Matching Items to Agents Fairly and Efficiently](https://mlsanity.com/paper/2207.01589/) (2022)
- [Learning Fair Division from Bandit Feedback](https://mlsanity.com/paper/2311.09068/) (2023)
- [Temporal Fair Division](https://mlsanity.com/paper/2410.23416/) (2024)
- [Comparing Approximate Relaxations of Envy-Freeness](https://mlsanity.com/paper/1806.03114/) (2018)
- [Weighted Envy-Freeness in Indivisible Item Allocation](https://mlsanity.com/paper/1909.10502/) (2019)

## Built on by (most cited first, 6 of 6)

- [Not in My Backyard! Temporal Voting Over Public Chores](https://mlsanity.com/paper/2508.08810/) (2025)
- [Approximate Proportionality in Online Fair Division](https://mlsanity.com/paper/2508.03253/) (2025)
- [The Price of Proportional Representation in Temporal Voting](https://mlsanity.com/paper/2605.11157/) (2026)
- [Fairness in Repeated Matching: A Maximin Perspective](https://mlsanity.com/paper/2510.04624/) (2025)
- [Online Fair Division with Budget Constraints](https://mlsanity.com/paper/2607.23310/) (2026)
- [EF1-Constrained Nash Social Welfare with Identical Additive Valuations: Complexity, Guarantees, and Experiments](https://mlsanity.com/paper/2609.03846/) (2026)

## Abstract (arXiv)

We study the problem of fairly allocating indivisible goods to agents in an online setting, where goods arrive sequentially and must be allocated irrevocably. Focusing on the popular fairness notions of envy-freeness, proportionality, and maximin share fairness (and their approximate variants), we investigate how access to future information changes what guarantees are achievable. Without any information, we prove strong impossibility results even for approximate fairness. With normalization information (agents' total values), we provide an algorithm that achieves stronger fairness guarantees than previously known results, and show matching impossibilities for stronger notions. With frequency predictions (value multisets without order), we design a meta-algorithm that lifts a broad class of offline ''share-based'' guarantees to the online setting, matching the best-known offline bounds. Finally, we provide learning-augmented variants of both models: under noisy totals or noisy frequency predictions, our guarantees are robust and degrade gracefully with the error parameters.