Skip to content
Preprint

Closing Gaps in Online Fair Division

Sep 2026 · 9 citations · ⚡ 2 influential · 44 references
Computer Science

TL;DR

This work determines the tight high-probability PROP1 guarantee of the classical Like rule, which assigns each good uniformly among the agents who value it positively, and improves when fewer agents value the same good, unlike uniform random allocation.

Abstract

We study the online fair division of indivisible items, where items arrive one at a time and must be allocated immediately and irrevocably. We address three central open questions in the literature. First, we show that for every $n\ge 2$ agents, every fixed $k\ge 1$, and every $\alpha\in(0,1]$, no online algorithm can guarantee $\alpha$-PROP$k$ against an adaptive adversary. This remains true even when the total number of goods is known in advance, all values lie in $[0,1]$, and every good is positively valued by at most two agents. The impossibility extends to a broad range of standard envy-based, proportionality-based, and share-based fairness notions. We also establish an analogous impossibility for chores. Second, in the setting with predictions, a lightweight form of future information, the maximum item value, was previously known to guarantee only $1/n$-PROP1, leaving open whether the dependence on $n$ is necessary. We give a deterministic $19/30$-PROP1 algorithm against adaptive adversaries that does not require knowing the total number of goods. Given an additional upper bound $\kappa\in[2,n]$ on the number of agents who value any good positively, the guarantee improves to $\max \{ 19/30, n/(n+\kappa) \}$. The guarantee remains a positive constant under any fixed one-sided prediction error below one. When predictions are exact and the total number of goods $m\ge n\log n$ is known in advance, a deterministic algorithm achieves the same $19/30$-PROP1 factor together with $O(\sqrt{m\log n/n})$ maximum additive envy after normalizing each agent's values by their maximum item value. Third, against a non-adaptive adversary, we determine the tight high-probability PROP1 guarantee of the classical Like rule, which assigns each good uniformly among the agents who value it positively. Its guarantee improves when fewer agents value the same good, unlike uniform random allocation.

View source

Similar papers

Preprint Sep 2026

Online Fair Division Against an Oblivious Adversary

This work studies the online allocation of indivisible goods among $n agents, where each good must be allocated immediately and irrevocably upon arrival, and shows that allocating each good to a uniformly random agent among those with positive values achieves an approximation factor arbitrarily close to one for envy-fr...

Saar Cohen, Nicholas J. Teh, Michael Wooldridge · 3 citations
Preprint Sep 2026

Online Fair Division: Pushing the Frontier of Approximate Proportionality

Online fair division captures allocation problems in which indivisible resources arrive over time and must be assigned before future resources are known. Understanding what fairness remains achievable when allocation decisions are immediate and irrevocable is a fundamental question in this setting. We study determinist...

Ying-Jian Du, An-Kang Sun · 4 citations · ⚡1
Preprint Sep 2026

Randomized Online Fair Division: High-Probability and Expected Realized Fairness

We study randomized algorithms for the fully online allocation of indivisible goods among $n\ge2$ agents with nonnegative additive valuations. Goods arrive sequentially and must be allocated immediately and irrevocably, with only $n$ known in advance. Since exact ex-ante envy freeness and proportionality are readily ac...

Tian-Qi Chen, Jing Long · 3 citations
Preprint Oct 2026

Online Fair Division with Upgrade Recourse

We study the online fair division of indivisible goods. In the standard model, where assignments are irrevocable, no algorithm can guarantee any positive fraction of the maximin share (MMS). Reassigning earlier goods can restore fairness, but it may take value away from agents who already hold them. We ask how much fai...

Yi-Chen Huang, Nicholas J. Teh · 1 citation
Preprint Aug 2026

Temporal Fair Division of Indivisible Mixed Manna: Tractable Settings

Although deciding whether a TEF1 allocation exists is NP-hard even for goods, this work identifies several tractable settings and gives an exact pseudo-polynomial algorithm for deciding TEF1 existence.

Kui-Wang Choi, Min-Ming Li, Nicholas J. Teh · 10 citations
Preprint Oct 2026

Minimizing Cumulative Envy in Allocating a Sequence of Items

We study temporal fair division with indivisible goods that arrive sequentially and must be allocated irrevocably. In contrast to the usual online model, we assume that valuations and future arrivals are known in advance, and ask how unfairness evolves during the process. We introduce \emph{cumulative maximum envy}: th...

Paul W. Goldberg, Isaac Robinson, Nicholas J. Teh · 7 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.