Envy-Free Allocation of Indivisible Goods via Noisy Queries
This addresses a practical challenge in fair division for scenarios with noisy data, though it is incremental as it builds on existing envy-free allocation frameworks.
The paper tackles the problem of fairly allocating indivisible goods when agents' valuations are only accessible via noisy queries, deriving upper and lower bounds on the number of queries needed to find an envy-free allocation, with an optimal scaling of m^{2.5}/Δ^2 up to logarithmic factors under certain conditions.
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, $Δ$. In particular, when $Δ$ is not too small (namely, $Δ\gg m^{1/4}$), we establish that the optimal number of queries scales as $\frac{\sqrt m }{(Δ/ m)^2} = \frac{m^{2.5}}{Δ^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.