在噪声中实现公平分配，只需少量查询即可完成物品分配。
Envy-Free Allocation of Indivisible Goods via Noisy Queries
- 通过带噪声的查询获取估值，设计非自适应查询算法。
- 当公平性差距大于 $ m^{1/4} $ 时，查询量为 $ \frac{m^{2.5}}{Δ^2} $。
- 适用于资源分配、拍卖等场景，适合关注计算效率的研究者。
我们提出一种不可分物品的公平分配问题，其中参与者的估值无法直接观测，只能通过带噪声的查询获取。在两人情形下，假设估值有界且噪声服从高斯分布，我们推导出找到无嫉妒分配所需查询次数的上下界，其与物品数 $ m $ 及最优分配的负嫉妒值 $ Δ $ 相关。特别地，当 $ Δ \gg m^{1/4} $ 时，最优查询复杂度约为 $ \frac{m^{2.5}}{Δ^2} $（忽略对数因子）。上界基于非自适应查询和简单的阈值分配算法，可在多项式时间内完成；下界即使在自适应查询和任意计算时间下依然成立。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。