Envy-Free Allocation of Indivisible Goods via Noisy Queries

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.

We study a problem of fair allocation of indivisible items between two agents while maintaining a well-known notion called envy-freeness -- each item prefers their own set of received items to the set that the other agent received. This problem has been studied extensively in the case of known item valuations, whereas in this paper, we are studying the case that the valuations are unknown and only imperfect (noisy) information can be attained via queries. We establish the fundamental limits of how many queries are required to achieve this goal under natural modeling assumptions.