# Fairness-Efficiency Tradeoffs in Dynamic Fair Division

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Jul 2019.

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

- [Online Fair Division with Additional Information](https://mlsanity.com/paper/2505.24503/) (2025)
- [Approximate Proportionality in Online Fair Division](https://mlsanity.com/paper/2508.03253/) (2025)
- [Subgroup Fairness in Two-Sided Markets](https://mlsanity.com/paper/2106.02702/) (2021)
- [Sequential Fair Resource Allocation under a Markov Decision Process Framework](https://mlsanity.com/paper/2301.03758/) (2023)
- [Fair Allocation in Dynamic Mechanism Design](https://mlsanity.com/paper/2406.00147/) (2024)
- [Online Fair Allocation of Perishable Resources](https://mlsanity.com/paper/2406.02402/) (2024)
- [Credit Fairness: Online Fairness In Shared Resource Pools](https://mlsanity.com/paper/2601.17944/) (2026)
- [Trading Utility for Dynamic Fairness in Multiple Resource Division with Sequential Demand](https://mlsanity.com/paper/2606.10472/) (2026)
- [Online Fair Division with Budget Constraints](https://mlsanity.com/paper/2607.23310/) (2026)

## Abstract (arXiv)

We investigate the tradeoffs between fairness and efficiency when allocating indivisible items over time. Suppose T items arrive over time and must be allocated upon arrival, immediately and irrevocably, to one of n agents. Agent i assigns a value vit in [0,1] to the t-th item to arrive and has an additive valuation function. If the values are chosen by an adaptive adversary it is known that the algorithm that minimizes maximum pairwise envy simply allocates each item uniformly at random; the maximum pairwise envy is then sublinear in T. If the values are independently and identically drawn from an adversarially chosen distribution D, it is also known that, under some mild conditions on D, allocating to the agent with the highest value -- a Pareto efficient allocation -- is envy-free with high probability. In this paper we study fairness-efficiency tradeoffs in this setting and provide matching upper and lower bounds under a spectrum of progressively stronger adversaries. On one hand we show that, even against a non-adaptive adversary, there is no algorithm with sublinear maximum pairwise envy that Pareto dominates the simple algorithm that allocates each item uniformly at random. On the other hand, under a slightly weaker adversary regime where item values are drawn from a known distribution and are independent with respect to time, i.e. vit is independent of vit' but possibly correlated with vi't, optimal (in isolation) efficiency is compatible with optimal (in isolation) fairness. That is, we give an algorithm that is Pareto efficient ex-post and is simultaneously optimal with respect to fairness: for each pair of agents i and j, either i envies j by at most one item (a prominent fairness notion), or i does not envy j with high probability. En route, we prove a structural result about allocations of divisible items that might be of independent interest.