3 Jan 2024 | Zihao Li, Shengxin Liu, Xinhang Lu, Biaoshuai Tao, and Yichen Tao
This paper investigates the efficiency of fair allocations using the concept of the *price of fairness*, which quantifies the worst-case efficiency loss when imposing fairness constraints. The authors focus on the price of envy-freeness (EF) and its relaxations, such as EF1 and EFX, in both indivisible and mixed goods settings. They provide tight bounds for the price of EF1 and EFX for two agents, resolving open questions in the literature. For mixed goods, they introduce EFM and EFXM, which generalize EF1 and EFX, respectively, and provide tight or asymptotically tight bounds for these notions. The paper also discusses the interplay between fairness and efficiency, highlighting the importance of resource monotonicity in characterizing the price of fairness. The results are presented in tables, showing the tight bounds for various fairness notions under different utility scenarios. The paper concludes by summarizing the findings and suggesting future research directions.This paper investigates the efficiency of fair allocations using the concept of the *price of fairness*, which quantifies the worst-case efficiency loss when imposing fairness constraints. The authors focus on the price of envy-freeness (EF) and its relaxations, such as EF1 and EFX, in both indivisible and mixed goods settings. They provide tight bounds for the price of EF1 and EFX for two agents, resolving open questions in the literature. For mixed goods, they introduce EFM and EFXM, which generalize EF1 and EFX, respectively, and provide tight or asymptotically tight bounds for these notions. The paper also discusses the interplay between fairness and efficiency, highlighting the importance of resource monotonicity in characterizing the price of fairness. The results are presented in tables, showing the tight bounds for various fairness notions under different utility scenarios. The paper concludes by summarizing the findings and suggesting future research directions.