论文标题
不可分割商品的公平价格的最佳范围
Optimal Bounds on the Price of Fairness for Indivisible Goods
论文作者
论文摘要
在将资源分配给一组代理商中，公平性保证如何影响社会福利？对这种影响的定量衡量标准是公平的代价，这可以衡量由于公平限制而导致的最严重的社会福利丧失。尽管最初研究可划分的商品，但最新关于公平价格的工作也研究了不可分割的商品的设置。 在本文中，我们解决了分配不可分割的商品的两个经过充分研究的公平概念的价格：嫉妒性最高（EF1）（EF1）和近似的最大值份额（MMS）。对于EF1和1/2-mms的保证，我们通过不同的技术表明，公平价格为$ O（\ sqrt {n}）$，其中$ n $是代理的数量。从以前的工作中，我们的界限很紧。我们的边界是通过有效的算法获得的。对于1/2-mms，我们的界限具有添加剂估值，而对于EF1，我们的界限符合更一般的次要估值类别。这解决了Bei等人提出的一个空旷的问题。 （2019）。
In the allocation of resources to a set of agents, how do fairness guarantees impact the social welfare? A quantitative measure of this impact is the price of fairness, which measures the worst-case loss of social welfare due to fairness constraints. While initially studied for divisible goods, recent work on the price of fairness also studies the setting of indivisible goods. In this paper, we resolve the price of two well-studied fairness notions for the allocation of indivisible goods: envy-freeness up to one good (EF1), and approximate maximin share (MMS). For both EF1 and 1/2-MMS guarantees, we show, via different techniques, that the price of fairness is $O(\sqrt{n})$, where $n$ is the number of agents. From previous work, it follows that our bounds are tight. Our bounds are obtained via efficient algorithms. For 1/2-MMS, our bound holds for additive valuations, whereas for EF1, our bound holds for the more general class of subadditive valuations. This resolves an open problem posed by Bei et al. (2019).
