Abstract
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 envyfreeness up to one good (EF1), balancedness, maximum Nash welfare (MNW), and leximin. We
mostly provide tight or asymptotically tight bounds
on the worst-case efficiency loss for allocations satisfying these notions