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

arXiv: https://arxiv.org/abs/2408.12845 · HTML: https://mlsanity.com/paper/2408.12845/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 80 references that are in the map.
- First posted on arXiv 23 Aug 2024.

## Builds on (most cited first, 30 of 33)

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [Fairness in Learning: Classic and Contextual Bandits](https://mlsanity.com/paper/1605.07139/) (2016)
- [Neural Thompson Sampling](https://mlsanity.com/paper/2010.00827/) (2020)
- [Achieving Fairness in the Stochastic Multi-armed Bandit Problem](https://mlsanity.com/paper/1907.10516/) (2019)
- [Combinatorial Sleeping Bandits with Fairness Constraints](https://mlsanity.com/paper/1901.04891/) (2019)
- [Online Learning with an Unknown Fairness Metric](https://mlsanity.com/paper/1802.06936/) (2018)
- [Calibrated Fairness in Bandits](https://mlsanity.com/paper/1707.01875/) (2017)
- [Fairness of Exposure in Stochastic Bandits](https://mlsanity.com/paper/2103.02735/) (2021)
- [Fair Contextual Multi-Armed Bandits: Theory and Experiments](https://mlsanity.com/paper/1912.08055/) (2019)
- [Fair Algorithms for Multi-Agent Multi-Armed Bandits](https://mlsanity.com/paper/2007.06699/) (2020)
- [User Fairness, Item Fairness, and Diversity for Rankings in Two-Sided Markets](https://mlsanity.com/paper/2010.01470/) (2020)
- [Online Fair Division: analysing a Food Bank problem](https://mlsanity.com/paper/1502.07571/) (2015)
- [Fair Algorithms for Infinite and Contextual Bandits](https://mlsanity.com/paper/1610.09559/) (2016)
- [Fairness and Welfare Quantification for Regret in Multi-Armed Bandits](https://mlsanity.com/paper/2205.13930/) (2022)
- [Online Fair Division: A Survey](https://mlsanity.com/paper/1911.09488/) (2019)
- [Sequential Fair Allocation: Achieving the Optimal Envy-Efficiency Tradeoff Curve](https://mlsanity.com/paper/2105.05308/) (2021)
- [Censored Semi-Bandits: A Framework for Resource Allocation with Censored Feedback](https://mlsanity.com/paper/1909.01504/) (2019)
- [Group Meritocratic Fairness in Linear Contextual Bandits](https://mlsanity.com/paper/2206.03150/) (2022)
- [Nash Regret Guarantees for Linear Bandits](https://mlsanity.com/paper/2310.02023/) (2023)
- [Online Market Equilibrium with Application to Fair Division](https://mlsanity.com/paper/2103.12936/) (2021)
- [Best Arm Identification with Fairness Constraints on Subpopulations](https://mlsanity.com/paper/2304.04091/) (2023)
- [Learning Fair Division from Bandit Feedback](https://mlsanity.com/paper/2311.09068/) (2023)
- [Fair and Efficient Online Allocations with Normalized Valuations](https://mlsanity.com/paper/2009.12405/) (2020)
- [Online Algorithm for Unsupervised Sequential Selection with Contextual Information](https://mlsanity.com/paper/2010.12353/) (2020)
- [Exploiting Correlated Auxiliary Feedback in Parameterized Bandits](https://mlsanity.com/paper/2311.02715/) (2023)
- [Honor Among Bandits: No-Regret Learning for Online Fair Division](https://mlsanity.com/paper/2407.01795/) (2024)
- [Stochastic Network Utility Maximization with Unknown Utilities: Multi-Armed Bandits Approach](https://mlsanity.com/paper/2006.09997/) (2020)
- [Fairer LP-based Online Allocation via Analytic Center](https://mlsanity.com/paper/2110.14621/) (2021)
- [Fair Division of Indivisible Goods: A Survey](https://mlsanity.com/paper/2202.07551/) (2022)

## Built on by (most cited first, 4 of 4)

- [Online Fair Division with Additional Information](https://mlsanity.com/paper/2505.24503/) (2025)
- [Constrained Online Decision-Making: A Unified Framework](https://mlsanity.com/paper/2505.07101/) (2025)
- [COBRA: Contextual Bandit Algorithm for Ensuring Truthful Strategic Agents](https://mlsanity.com/paper/2505.23720/) (2025)
- [Envy-Free Allocation of Indivisible Goods via Noisy Queries](https://mlsanity.com/paper/2602.06361/) (2026)

## Abstract (arXiv)

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 and achieve provable sublinear regret. Our experimental results further validate the effectiveness of the proposed algorithms.