Online Fair Division with Additional Information

We study the problem of fairly allocating indivisible goods to agents in an online setting, where goods arrive sequentially and must be allocated irrevocably. Focusing on the popular fairness notions of envy-freeness, proportionality, and maximin share fairness (and their approximate variants), we investigate how access to future information changes what guarantees are achievable. Without any information, we prove strong impossibility results even for approximate fairness. With normalization information (agents' total values), we provide an algorithm that achieves stronger fairness guarantees than previously known results, and show matching impossibilities for stronger notions. With frequency predictions (value multisets without order), we design a meta-algorithm that lifts a broad class of offline “share-based” guarantees to the online setting, matching the best-known offline bounds. Finally, we provide learning-augmented variants of both models: under noisy totals or noisy frequency predictions, our guarantees are robust and degrade gracefully with the error parameters.

Many online platform allocate items as they arrive; for instance, ad impressions, cloud-computing slots, donation items, or moderation tasks. These items often cannot be split, and once an item is assigned, the decision cannot be taken back. This makes it hard to ensure that every participant is treated fairly by the end. This paper asks what kinds of predictive information make fair allocations possible in such online settings. We show that, with no information about future items, even very weak fairness goals can be impossible to guarantee. If the system only knows each participant’s total eventual value for all items, we give an algorithm that guarantees everyone a fair share up to one extra item, and gives a stronger fairness guarantee for two participants. If the system has richer forecasts about how often each value will appear, but not the order of arrival, we show how to recover many fairness guarantees known from offline allocation. We also study imperfect predictions and show that the guarantees degrade smoothly as prediction errors grow. Overall, the results identify which predictions are useful for building sequential ML-driven allocation systems with transparent fairness guarantees.