Keep Everyone Happy: Online Fair Division of Numerous Items with Few Copies
Arun Verma, Indrajit Saha, Makoto Yokoo, Bryan Kian Hsiang Low
Abstract
This paper considers a novel variant of the online fair division problem involving multiple agents in which a learner sequentially observes an indivisible item that has to be irrevocably allocated to one of the agents while satisfying a desired balance between fairness and efficiency. Existing algorithms assume a small number of items with a sufficiently large number of copies, which ensures a good utility estimation for all item-agent pairs from noisy observed utilities. However, this assumption may not hold in many real-life applications, for example, an online platform that has a large number of users (items) who use the platform's service providers (agents) only a few times (a few copies of items), which makes it difficult to accurately estimate utilities for all item-agent pairs. To address this limitation, we assume utility is an unknown function of item-agent features. We propose algorithms that model online fair division as a contextual bandit problem, with provable sub-linear regret upper bound guarantees. Our experimental results further validate the effectiveness of the proposed algorithms.
BibTeX
@inproceedings{
verma2026keep,
title={Keep Everyone Happy: Online Fair Division of Numerous Items with Few Copies},
author={Arun Verma and Indrajit Saha and Makoto Yokoo and Bryan Kian Hsiang Low},
booktitle={Forty-third International Conference on Machine Learning},
year={2026},
url={https://openreview.net/forum?id=2XMLJj67yY}
}