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

DOI10.1007/978-3-030-57980-7_3zbMATH Open1506.91066arXiv2003.07060OpenAlexW3012103574MaRDI QIDQ2109945FDOQ2109945

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

Publication date: 21 December 2022

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.

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

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

zbMATH Keywords

submodularityfair divisiondichotomous preferencesenvy-freenessmatroid rank functionsoptimal welfare

Mathematics Subject Classification ID

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

Cited In (9)

• Two birds with one stone: fairness and welfare via transfers
• The price of fairness for indivisible goods
• Generalized binary utility functions and fair allocations
• 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
• Approximating Nash social welfare under binary XOS and binary subadditive valuations
• Computing welfare-maximizing fair allocations of indivisible goods
• On Fair Division under Heterogeneous Matroid Constraints
• Envy-free relaxations for goods, chores, and mixed items

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)