Finding fair and efficient allocations when valuations don't add up

DOI10.1007/978-3-030-57980-7_3MaRDI QIDQ2109945zbMATH OpenOpenAlexFDO

Authors Nawal Benabbou, Mithun Chakraborty, Ayumi Igarashi, Yair Zick

Publication date 21 December 2022

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

zbMATH Keywords

submodularityfair divisiondichotomous preferencesenvy-freenessmatroid rank functionsoptimal welfare

Mathematics Subject Classification ID

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

Abstract: In this paper, we present new results on the fair and efficient allocation of indivisible goods to agents whose preferences correspond to {em matroid rank functions}. This is a versatile valuation class with several desirable properties (such as monotonicity and submodularity), which naturally lends itself to a number of real-world domains. We use these properties to our advantage; first, we show that when agent valuations are matroid rank functions, a socially optimal (i.e. utilitarian social welfare-maximizing) allocation that achieves envy-freeness up to one item (EF1) exists and is computationally tractable. We also prove that the Nash welfare-maximizing and the leximin allocations both exhibit this fairness/efficiency combination, by showing that they can be achieved by minimizing any symmetric strictly convex function over utilitarian optimal outcomes. To the best of our knowledge, this is the first valuation function class not subsumed by additive valuations for which it has been established that an allocation maximizing Nash welfare is EF1. Moreover, for a subclass of these valuation functions based on maximum (unweighted) bipartite matching, we show that a leximin allocation can be computed in polynomial time. Additionally, we explore possible extensions of our results to fairness criteria other than EF1 as well as to generalizations of the above valuation classes.

Recommendations

• Computing fair and efficient allocations with few utility values
• Almost envy-freeness with general valuations
• Almost envy-freeness with general valuations
• Worst case compromises in matroids with applications to the allocation of indivisible goods

Cited in

(14)

• Two birds with one stone: fairness and welfare via transfers
• Worst case compromises in matroids with applications to the allocation of indivisible goods
• Computing welfare-maximizing fair allocations of indivisible goods
• Near fairness in matroids
• Dividing good and great items among agents with bivalued submodular valuations
• The good, the bad and the submodular: fairly allocating mixed manna under order-neutral submodular preferences
• A fair and truthful mechanism with limited subsidy
• Envy-free relaxations for goods, chores, and mixed items
• Weighted fair division with matroid-rank valuations: monotonicity and strategyproofness
• The price of fairness for indivisible goods
• Approximating Nash social welfare under binary XOS and binary subadditive valuations
• On Fair Division under Heterogeneous Matroid Constraints
• Computing fair and efficient allocations with few utility values
• Generalized binary utility functions and fair allocations

This page was built for publication: Finding fair and efficient allocations when valuations don't add up

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