We investigate the efficiency of fair allocations of indivisible goods using the well-studied price of fairness concept. Previous work has focused on classical fairness notions such as envy-freeness, proportionality, and equitability. However, these notions cannot always be satisfied for indivisible goods, leading to certain instances being ignored in the analysis. In this paper, we focus instead on notions with guaranteed existence, including envy-freeness up to one good (EF1), balancedness, maximum Nash welfare (MNW), and leximin. We also introduce the concept of strong price of fairness, which captures the efficiency loss in the worst fair allocation as opposed to that in the best fair allocation as in the price of fairness. We mostly provide tight or asymptotically tight bounds on the worst-case efficiency loss for allocations satisfying these notions, for both the price of fairness and the strong price of fairness.
翻译:我们利用经过深思熟虑的公平价格概念来调查公平分配不可分割货物的效率; 以往的工作侧重于传统的公平概念,如忌妒、相称性和公平性; 然而,这些概念不能总是为不可分割货物所满足,从而导致分析中忽略某些情况; 在本文中,我们侧重于有保障存在的概念,包括无忌妒至一种商品(EF1)、平衡性、最大纳什福利(MNW)和法规。 我们还引入了强烈的公平价格概念,它抓住了效率损失,在最不公平的分配中,而不是在最公平的分配中,如在公平价格中那样。 我们大多为达到这些概念的分配提供最坏的效率损失的紧凑或间接的紧凑界限,既是为了公平价格,也是为了公平价格。