The price of fairness for indivisible goods

DOI10.1007/S00224-021-10039-8MaRDI QIDQ2230722zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

efficiencyfair divisionindivisible goodsprice of fairness

Mathematics Subject Classification ID

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

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.

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

Cites work

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