# Temporal Fair Division of Indivisible Items

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 40 of its 70 references that are in the map.
- First posted on arXiv 18 Oct 2024.

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

- [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)
- [Temporal Fairness in Multiwinner Voting](https://mlsanity.com/paper/2312.04417/) (2023)
- [Fair Division with Binary Valuations: One Rule to Rule Them All](https://mlsanity.com/paper/2007.06073/) (2020)
- [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)
- [Multiwinner Temporal Voting with Aversion to Change](https://mlsanity.com/paper/2408.11017/) (2024)
- [Finding Fair and Efficient Allocations](https://mlsanity.com/paper/1707.04731/) (2017)
- [Almost Envy-Freeness in Group Resource Allocation](https://mlsanity.com/paper/1901.08463/) (2019)
- [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)
- [Tight Approximation Algorithms for p-Mean Welfare Under Subadditive Valuations](https://mlsanity.com/paper/2005.07370/) (2020)
- [Repeatedly Matching Items to Agents Fairly and Efficiently](https://mlsanity.com/paper/2207.01589/) (2022)
- [Non-clairvoyant Scheduling with Partial Predictions](https://mlsanity.com/paper/2405.01013/) (2024)
- [On Maximum Weighted Nash Welfare for Binary Valuations](https://mlsanity.com/paper/2204.03803/) (2022)
- [On the Fairness of Normalized p-Means for Allocating Goods and Chores](https://mlsanity.com/paper/2402.14996/) (2024)
- [Envy-Freeness in House Allocation Problems](https://mlsanity.com/paper/1905.00468/) (2019)
- [Almost Group Envy-free Allocation of Indivisible Goods and Chores](https://mlsanity.com/paper/1907.09279/) (2019)
- [For One and All: Individual and Group Fairness in the Allocation of Indivisible Goods](https://mlsanity.com/paper/2302.06958/) (2023)
- [Group Envy Freeness and Group Pareto Efficiency in Fair Division with Indivisible Items](https://mlsanity.com/paper/2006.15893/) (2020)
- [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)
- [Weighted Fair Division with Matroid-Rank Valuations: Monotonicity and Strategyproofness](https://mlsanity.com/paper/2303.14454/) (2023)
- [Generalized binary utility functions and fair allocations](https://mlsanity.com/paper/2109.08461/) (2021)
- [How to Fairly Allocate Easy and Difficult Chores](https://mlsanity.com/paper/2110.11285/) (2021)

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

- [Strengthening Proportionality in Temporal Voting](https://mlsanity.com/paper/2505.22513/) (2025)
- [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)
- [Approximate Proportionality in Online Fair Division](https://mlsanity.com/paper/2508.03253/) (2025)
- [Online Fair Division for Personalized 2-Value Instances](https://mlsanity.com/paper/2505.22174/) (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)
- [The Coordination Gap: Multi-Agent Alternation Metrics for Temporal Fairness in Repeated Games](https://mlsanity.com/paper/2603.05789/) (2026)
- [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)
- [Proportional Representation in Temporal Voting with Ranked Preferences](https://mlsanity.com/paper/2609.30555/) (2026)

## Abstract (arXiv)

We study a fair division model where indivisible items arrive sequentially, and must be allocated immediately and irrevocably. Previous work on online fair division has shown impossibility results in achieving approximate envy-freeness under these constraints. In contrast, we consider an informed setting where the algorithm has complete knowledge of future items, and aim to ensure that the cumulative allocation at each round satisfies approximate envy-freeness -- which we define as temporal envy-freeness up to one item (TEF1). We focus on settings where items can be exclusively goods or exclusively chores. For goods, while TEF1 allocations may not always exist, we identify several special cases where they do -- two agents, two item types, generalized binary valuations, unimodal preferences -- and provide polynomial-time algorithms for these cases. We also prove that determining the existence of a TEF1 allocation is NP-hard. For chores, we establish analogous results for the special cases, but present a slightly weaker intractability result. We also establish the incompatibility between TEF1 and Pareto-optimality, with the implication that it is intractable to find a TEF1 allocation that maximizes any p-mean welfare, even for two agents.