Envy-Free Allocation of Indivisible Goods via Noisy Queries

arXiv:2602.06361v2 Announce Type: replace-cross Abstract: 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 m^{1/4}), we establish that the optimal number of queries scales as frac{sqrt m }{(Delta / m)^2} = frac{m^{2.5}}{Delta^2} 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.

Source: arXiv cs.LG | 2026-05-29