# Online Fair Division with Budget Constraints

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 40 of its 67 references that are in the map.
- First posted on arXiv 25 Jul 2026.

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

- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [Improving Online Algorithms via ML Predictions](https://mlsanity.com/paper/2407.17712/) (2024)
- [Online Fair Division: analysing a Food Bank problem](https://mlsanity.com/paper/1502.07571/) (2015)
- [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)
- [Temporal Fairness in Multiwinner Voting](https://mlsanity.com/paper/2312.04417/) (2023)
- [A Little Charity Guarantees Almost Envy-Freeness](https://mlsanity.com/paper/1907.04596/) (2019)
- [Universal and Tight Online Algorithms for Generalized-Mean Welfare](https://mlsanity.com/paper/2109.00874/) (2021)
- [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)
- [Envy-freeness up to any item with high Nash welfare: The virtue of donating items](https://mlsanity.com/paper/1902.04319/) (2019)
- [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)
- [Better Collective Decisions via Uncertainty Reduction](https://mlsanity.com/paper/2207.04983/) (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)
- [Repeatedly Matching Items to Agents Fairly and Efficiently](https://mlsanity.com/paper/2207.01589/) (2022)
- [Temporal Fair Division](https://mlsanity.com/paper/2410.23416/) (2024)
- [Online Ad Allocation with Predictions](https://mlsanity.com/paper/2302.01827/) (2023)
- [Strategyproof Scheduling with Predictions](https://mlsanity.com/paper/2209.04058/) (2022)
- [Online Fair Division with Additional Information](https://mlsanity.com/paper/2505.24503/) (2025)
- [Not in My Backyard! Temporal Voting Over Public Chores](https://mlsanity.com/paper/2508.08810/) (2025)
- [Multi-agent Online Scheduling: MMS Allocations for Indivisible Items](https://mlsanity.com/paper/2304.13405/) (2023)
- [A General Framework for Learning-Augmented Online Allocation](https://mlsanity.com/paper/2305.18861/) (2023)
- [Approximate Proportionality in Online Fair Division](https://mlsanity.com/paper/2508.03253/) (2025)
- [How to Match when All Vertices Arrive Online](https://mlsanity.com/paper/1802.03905/) (2018)
- [Online Algorithms for the Santa Claus Problem](https://mlsanity.com/paper/2210.07333/) (2022)
- [Best of Many in Both Worlds: Online Resource Allocation with Predictions under Unknown Arrival Model](https://mlsanity.com/paper/2402.13530/) (2024)
- [Plant-and-Steal: Truthful Fair Allocations via Predictions](https://mlsanity.com/paper/2406.07024/) (2024)
- [Fair Division of Chores with Budget Constraints](https://mlsanity.com/paper/2410.23979/) (2024)

## Abstract (arXiv)

We study an online variant of discrete fair division under generalized assignment budget constraints. Goods arrive one at a time and must be assigned irrevocably to a feasible agent or to charity, which holds all unallocated goods, while fairness is evaluated only against budget-feasible subsets of every recipient's bundle. We first show that, without additional structure, no deterministic online algorithm can guarantee any fixed approximation to feasible envy-freeness, even in highly symmetric instances. We then identify bounded density spread as a structural condition that restores meaningful guarantees, obtaining approximation algorithms for arbitrary item sizes and showing that, under common valuations and sufficiently small goods, these guarantees can be strengthened to an optimal deterministic frontier. We further study resource augmentation, where the online algorithm is allowed slightly larger budgets than the fairness benchmark, and characterize the resulting improvement in the achievable guarantees. Finally, we develop a learning-augmented framework based on predicting joint value-size types, proving consistency under perfect predictions, robustness to prediction error, and showing that separate predictions of value and size marginals are insufficient to recover strong fairness guarantees.