Online fair division algorithms approximate envy freeness for up to four agents
Online Fair Division with Frequency Predictions
Computer Science and Game TheoryMultiagent Systems
Summary
Dividing items fairly among people when items arrive one by one is hard, especially if you only know predictions about their preferences. The authors show that for up to four people, it is possible to divide items in a way that nearly avoids envy if you allow some approximation and have frequency predictions, but for five or more people, no method can guarantee this. They also show that certain stronger fairness guarantees are impossible online from three people onward. Additionally, they develop algorithms that work well with noisy predictions and provide provable fairness guarantees.
What this means in practice
- •For resource allocation teams: Design online allocation systems that achieve approximate envy-freeness guarantees for up to four participants using frequency predictions.
- •For online advertising platforms: Implement fair and efficient ad slot allocations to a small set of advertisers when predicted audience value patterns are available but arrival order is uncertain.
Authors
Tzeh Yuan Neoh, Nicholas Teh
Abstract
We study online fair division of indivisible goods among $n$ agents with frequency predictions: before any good arrives, the algorithm learns the multiset of each agent's values for the goods, but neither the arrival order nor which values of different agents belong to the same good. Neoh et al. (ICML 2026) showed that such predictions allow every share-based guarantee that is achievable offline, and left open whether a positive approximation of envy-freeness up to one good (EF1) is possible. We show that deterministic online algorithms can guarantee $1/2$-EF1 for three agents and $(3-\sqrt5)/2$-EF1 for four agents, whereas for five or more agents, no online algorithm can guarantee any positive approximation of EF1, even with $n+1$ goods and identical predictions. Together with the known result for two agents, a positive approximation of EF1 is therefore possible if and only if $n\leq4$. We also rule out any positive approximation of EFX for three or more agents, even when the valuations take only two distinct positive values. Next, we use the meta-algorithm of Neoh et al. (ICML 2026) to compute an epistemic EFX (EEFX) allocation in polynomial time for any $n$, and hence a $1/(n-1)$-EF$(n-2)$ allocation for $n\geq3$, whereas algorithms that fix a picking sequence in advance can guarantee a positive approximation of EF$k$ if and only if $n\leq k+2$. Finally, for noisy predictions, we give algorithms that return EEFX allocations when the predictions are exact, and guarantee $(1-2\varepsilon+O(\varepsilon^2))$-EEFX under underestimates and, for $n\geq3$, $(1-2(n-1)\varepsilon+O(\varepsilon^2))$-EEFX under overestimates; the linear terms are the best possible, and larger overestimates rule out any positive approximation for such algorithms.