# Online Fair Division for Personalized 2-Value Instances

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 37 references that are in the map.
- First posted on arXiv 28 May 2025.

## Builds on (most cited first, 27 of 27)

- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [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)
- [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)
- [Sequential Fair Allocation: Achieving the Optimal Envy-Efficiency Tradeoff Curve](https://mlsanity.com/paper/2105.05308/) (2021)
- [Maximum Nash Welfare and Other Stories About EFX](https://mlsanity.com/paper/2001.09838/) (2020)
- [Universal and Tight Online Algorithms for Generalized-Mean Welfare](https://mlsanity.com/paper/2109.00874/) (2021)
- [Temporal Fair Division of Indivisible Items](https://mlsanity.com/paper/2410.14593/) (2024)
- [Proportionally Fair Online Allocation of Public Goods with Predictions](https://mlsanity.com/paper/2209.15305/) (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)
- [Fair and Efficient Online Allocations with Normalized Valuations](https://mlsanity.com/paper/2009.12405/) (2020)
- [Non-clairvoyant Scheduling with Partial Predictions](https://mlsanity.com/paper/2405.01013/) (2024)
- [Honor Among Bandits: No-Regret Learning for Online Fair Division](https://mlsanity.com/paper/2407.01795/) (2024)
- [Maximizing Nash Social Welfare in 2-Value Instances](https://mlsanity.com/paper/2107.08965/) (2021)
- [Multi-agent Online Scheduling: MMS Allocations for Indivisible Items](https://mlsanity.com/paper/2304.13405/) (2023)
- [Fair and Efficient Allocations of Chores under Bivalued Preferences](https://mlsanity.com/paper/2110.09601/) (2021)
- [Fair Allocation of Two Types of Chores](https://mlsanity.com/paper/2211.00879/) (2022)
- [Pushing the Frontier on Approximate EFX Allocations](https://mlsanity.com/paper/2406.12413/) (2024)
- [Monotone and Online Fair Division](https://mlsanity.com/paper/2006.15891/) (2020)
- [Computing Pareto-Optimal and Almost Envy-Free Allocations of Indivisible Goods](https://mlsanity.com/paper/2204.14229/) (2022)
- [Online Mechanism Design with Predictions](https://mlsanity.com/paper/2310.02879/) (2023)
- [On the Hardness of Fair Allocation under Ternary Valuations](https://mlsanity.com/paper/2403.00943/) (2024)
- [Online Fair Allocation of Perishable Resources](https://mlsanity.com/paper/2406.02402/) (2024)
- [Online Fair Division: Towards Ex-Post Constant MMS Guarantees](https://mlsanity.com/paper/2503.02088/) (2025)

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

- [Online Fair Division with Additional Information](https://mlsanity.com/paper/2505.24503/) (2025)
- [Probing EFX via PMMS: (Non-)Existence Results in Discrete Fair Division](https://mlsanity.com/paper/2507.14957/) (2025)
- [Online Fair Division with Budget Constraints](https://mlsanity.com/paper/2607.23310/) (2026)

## Abstract (arXiv)

We study an online fair division setting, where goods arrive one at a time and there is a fixed set of n agents, each of whom has an additive valuation function over the goods. Once a good appears, the value each agent has for it is revealed and it must be allocated immediately and irrevocably to one of the agents. It is known that without any assumptions about the values being severely restricted or coming from a distribution, very strong impossibility results hold in this setting. To bypass the latter, we turn our attention to instances where the valuation functions are restricted. In particular, we study personalized 2-value instances, where there are only two possible values each agent may have for each good, possibly different across agents, and we show how to obtain worst case guarantees with respect to well-known fairness notions, such as maximin share fairness and envy-freeness up to one (or two) good(s). We suggest a deterministic algorithm that maintains a 1/(2n-1)-MMS allocation at every time step and show that this is the best possible any deterministic algorithm can achieve if one cares about every single time step; nevertheless, eventually the allocation constructed by our algorithm becomes a 1/4-MMS allocation. To achieve this, the algorithm implicitly maintains a fragile system of priority levels for all agents. Further, we show that, by allowing some limited access to future information, it is possible to have stronger results with less involved approaches. By knowing the values of goods for n-1 time steps into the future, we design a matching-based algorithm that achieves an EF1 allocation every n time steps, while always maintaining an EF2 allocation. Finally, we show that our results allow us to get the first nontrivial guarantees for additive instances in which the ratio of the maximum over the minimum value an agent has for a good is bounded.