# Envy-Free Allocation of Indivisible Goods via Noisy Queries

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 26 of its 42 references that are in the map.
- First posted on arXiv 6 Feb 2026.

## Builds on (most cited first, 26 of 26)

- [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)
- [Fair Algorithms for Multi-Agent Multi-Armed Bandits](https://mlsanity.com/paper/2007.06699/) (2020)
- [Almost Envy-Freeness with General Valuations](https://mlsanity.com/paper/1707.04769/) (2017)
- [Fair Division of Indivisible Goods: Recent Progress and Open Questions](https://mlsanity.com/paper/2208.08782/) (2022)
- [Fairness and Welfare Quantification for Regret in Multi-Armed Bandits](https://mlsanity.com/paper/2205.13930/) (2022)
- [No-regret Algorithms for Fair Resource Allocation](https://mlsanity.com/paper/2303.06396/) (2023)
- [Nash Regret Guarantees for Linear Bandits](https://mlsanity.com/paper/2310.02023/) (2023)
- [Learning Fair Division from Bandit Feedback](https://mlsanity.com/paper/2311.09068/) (2023)
- [Honor Among Bandits: No-Regret Learning for Online Fair Division](https://mlsanity.com/paper/2407.01795/) (2024)
- [Bandit Social Learning: Exploration under Myopic Behavior](https://mlsanity.com/paper/2302.07425/) (2023)
- [Fair Division: The Computer Scientist's Perspective](https://mlsanity.com/paper/2005.04855/) (2020)
- [How to Design Robust Algorithms using Noisy Comparison Oracle](https://mlsanity.com/paper/2105.05782/) (2021)
- [Keep Everyone Happy: Online Fair Division of Numerous Items with Few Copies](https://mlsanity.com/paper/2408.12845/) (2024)
- [Stochastic Bandits for Egalitarian Assignment](https://mlsanity.com/paper/2410.05856/) (2024)
- [Developments in Multi-Agent Fair Allocation](https://mlsanity.com/paper/1911.09852/) (2019)
- [On Average-Case Error Bounds for Kernel-Based Bayesian Quadrature](https://mlsanity.com/paper/2202.10615/) (2022)
- [Active Learning for Fair and Stable Online Allocations](https://mlsanity.com/paper/2406.14784/) (2024)
- [Fair Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/2408.17313/) (2024)
- [Improved Regret Bounds for Online Fair Division with Bandit Learning](https://mlsanity.com/paper/2501.07022/) (2025)
- [Fairly Allocating Many Goods with Few Queries](https://mlsanity.com/paper/1807.11367/) (2018)
- [On the Optimal Bounds for Noisy Computing](https://mlsanity.com/paper/2306.11951/) (2023)
- [Communication Complexity of Discrete Fair Division](https://mlsanity.com/paper/1711.04066/) (2017)
- [Logarithmic Comparison-Based Query Complexity for Fair Division of Indivisible Goods](https://mlsanity.com/paper/2404.18133/) (2024)
- [Complexity of Round-Robin Allocation with Potentially Noisy Queries](https://mlsanity.com/paper/2404.19402/) (2024)
- [Bandit Max-Min Fair Allocation](https://mlsanity.com/paper/2505.05169/) (2025)

## Abstract (arXiv)

We introduce a problem of fairly allocating indivisible goods (items) in which the agents' valuations cannot be observed directly, but instead can only be accessed via noisy queries. In the two-agent setting with Gaussian noise and bounded valuations, we derive upper and lower bounds on the required number of queries for finding an envy-free allocation in terms of the number of items, m, and the negative-envy of the optimal allocation, Delta. In particular, when Delta is not too small (namely, Delta gg m1/4), we establish that the optimal number of queries scales as frac√ m (Delta / m)2 = fracm2.5Delta2 up to logarithmic factors. Our upper bound is based on non-adaptive queries and a simple thresholding-based allocation algorithm that runs in polynomial time, while our lower bound holds even under adaptive queries and arbitrary computation time.