The price of fairness for indivisible goods

DOI10.1007/S00224-021-10039-8zbMATH Open1471.91196arXiv1905.04910OpenAlexW2944428860MaRDI QIDQ2230722FDOQ2230722

Authors: Xiaohui Bei, Xinhang Lu, Pasin Manurangsi, Warut Suksompong 

Publication date: 28 September 2021

Published in: Theory of Computing Systems (Search for Journal in Brave)

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 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.

Full work available at URL: https://arxiv.org/abs/1905.04910

Recommendations

• The efficiency of fair division
• The price of fairness for a small number of indivisible items
• Improving Nash social welfare approximations of indivisible goods
• The price of fairness
• Maximum Nash welfare and other stories about EFX

zbMATH Keywords

efficiencyfair divisionindivisible goodsprice of fairness

Mathematics Subject Classification ID

Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Cites Work

• The price of fairness
• Title not available (Why is that?)
• The Santa Claus problem
• Random Matching Under Dichotomous Preferences
• How to Cut A Cake Fairly
• Almost envy-freeness with general valuations
• The efficiency of fair division
• Dividing connected chores fairly
• Fair enough: guaranteeing approximate maximin shares
• On the number of almost envy-free allocations
• The price of envy-freeness in machine scheduling
• Optimal bounds on the price of fairness for indivisible goods
• Fairly allocating many goods with few queries
• Approximate maximin shares for groups of agents
• Fair Allocation of Indivisible Goods to Asymmetric Agents
• The price of fairness for a small number of indivisible items
• Finding fair and efficient allocations when valuations don't add up
• Multiple birds with one stone: beating 1/2 for EFX and GMMS via envy cycle elimination
• Almost envy-freeness in group resource allocation
• Democratic fair allocation of indivisible goods
• Closing gaps in asymptotic fair division
• When do envy-free allocations exist?

Cited In (10)

• Two birds with one stone: fairness and welfare via transfers
• The price of fairness
• Fair division of goods in the shadow of market values
• Optimal bounds on the price of fairness for indivisible goods
• The existence and efficiency of PMMS allocations
• The efficiency of fair division
• Fair division of indivisible goods: recent progress and open questions
• The price of fairness for a small number of indivisible items
• EFX allocations exist for binary valuations
• The price of equity with binary valuations and few agent types

This page was built for publication: The price of fairness for indivisible goods

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2230722)