arXiv preprint ·
Online Fair Division with Frequency Predictions
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computer Science & Game Theory
Weighted Fairness in Multi-User Earth Observation Satellite Scheduling
Order-selection Prophet Inequality (Almost) Goes I.I.D
Game theory of academic effort and hiring in the age of AI
Jointly Modeling Preferences and Imperfect Decision-Making in Large Language Models
Seeing Through Distractions: Context-Stable Attribution via the Least Core
Get the few papers worth your time in Computer Science & Game Theory every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.