Keep Everyone Happy: Online Fair Division of Numerous Items with Few Copies

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 must be irrevocably allocated to one of the agents to achieve 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, e.g., an online platform with a large number of users (items) who use the platform's service providers (agents) only a few times (a few copies of items), making 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, achieving provable sub-linear regret. Our experimental results further validate the effectiveness of the proposed algorithms. The code is publicly available in this GitHub repository.

Imagine an online platform, such as a job board or tutoring marketplace, that must assign incoming users to service providers in real time, one match at a time, with each decision being permanent. The platform's objective is to allocate opportunities fairly while also maximizing overall match quality. Most existing approaches assume that the same types of users and providers interact repeatedly, allowing the system to build reliable estimates of match quality from past outcomes. In many real-world settings, however, users are highly diverse and often appear only once or a few times, making gradual learning infeasible. This paper addresses that challenge by predicting match quality from observable user and provider characteristics rather than relying on repeated pairwise observations. Building on the contextual bandit framework, this paper develops algorithms that adapt and improve over time while providing theoretical performance guarantees. Experiments further validate our approach, demonstrating that it enables fair and efficient allocation even in environments with sparse interactions.