A Complete Landscape for the Price of Envy-Freeness

A Complete Landscape for the Price of Envy-Freeness

3 Jan 2024 | Zihao Li, Shengxin Liu, Xinhang Lu, Biaoshuai Tao, and Yichen Tao
This paper studies the efficiency of fair allocations using the price of fairness concept, which quantifies the worst-case efficiency loss when enforcing fairness constraints. It provides a complete characterization of the price of envy-freeness (EF) in various settings. For two agents, it resolves open questions by determining tight bounds for the price of EF1 (scaled utilities) and EFX (unscaled utilities). It also introduces new fairness notions for mixed goods: envy-freeness for mixed goods (EFM) and envy-freeness up to any good for mixed goods (EFXM), and provides tight bounds for their prices. For mixed goods, it shows that the price of EFM and EFXM is asymptotically the same as the price of EFX. For n agents, it establishes asymptotically tight bounds for the price of EFM and EFXM, showing they are Θ(√n) for scaled utilities and Θ(n) for unscaled utilities. The paper also provides a constructive algorithm for achieving these bounds.This paper studies the efficiency of fair allocations using the price of fairness concept, which quantifies the worst-case efficiency loss when enforcing fairness constraints. It provides a complete characterization of the price of envy-freeness (EF) in various settings. For two agents, it resolves open questions by determining tight bounds for the price of EF1 (scaled utilities) and EFX (unscaled utilities). It also introduces new fairness notions for mixed goods: envy-freeness for mixed goods (EFM) and envy-freeness up to any good for mixed goods (EFXM), and provides tight bounds for their prices. For mixed goods, it shows that the price of EFM and EFXM is asymptotically the same as the price of EFX. For n agents, it establishes asymptotically tight bounds for the price of EFM and EFXM, showing they are Θ(√n) for scaled utilities and Θ(n) for unscaled utilities. The paper also provides a constructive algorithm for achieving these bounds.
Reach us at info@study.space