Fair allocation of indivisible goods: Beyond additive valuations
Fair allocation of indivisible goods: Beyond additive valuations
复制标题
DOI：
10.1016/j.artint.2021.103633
复制
发表时间：
2021-11
期刊：
影响因子：
--
通讯作者：
M. Ghodsi;M. Hajiaghayi;Masoud Seddighin;Saeed Seddighin;Hadi Yami
中科院分区：
文献类型：
--
作者：
M. Ghodsi;M. Hajiaghayi;Masoud Seddighin;Saeed Seddighin;Hadi Yami
我们研究了以最大份额[1]作为公平度量时不可分商品的公平分配问题。目前对这一概念的研究大多局限于估值是累加的情况。在这篇文章中，我们超越了加法赋值，考虑了赋值是次模、分数次可加和次加的情况。我们给出了具有子模和XOS赋值的代理的恒定逼近保证，以及具有次可加赋值的代理的对数界。此外，我们通过提供每类赋值函数的接近上界来补充我们的结果。最后，我们给出了在多项式时间内找到子模和XOS设置的这种分配的算法。
We conduct a study on the problem of fair allocation of indivisible goods when maximin share [1] is used as the measure of fairness. Most of the current studies on this notion are limited to the case that the valuations are additive. In this paper, we go beyond additive valuations and consider the cases that the valuations are submodular, fractionally subadditive, and subadditive. We give constant approximation guarantees for agents with submodular and XOS valuations, and a logarithmic bound for the case of agents with subadditive valuations. Furthermore, we complement our results by providing close upper bounds for each class of valuation functions. Finally, we present algorithms to find such allocations for submodular and XOS settings in polynomial time.