Finding Fair and Efficient Allocations for Matroid Rank Valuations - Sorbonne Université Access content directly
Journal Articles ACM Transactions on Economics and Computation Year : 2021

Finding Fair and Efficient Allocations for Matroid Rank Valuations


In this paper, we present new results on the fair and efficient allocation of indivisible goods to agents whose preferences correspond to 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.
Fichier principal
Vignette du fichier
MatroidRank_journalversion.pdf (916.69 Ko) Télécharger le fichier
Origin : Publisher files allowed on an open archive

Dates and versions

hal-03271772 , version 1 (20-08-2021)


  • HAL Id : hal-03271772 , version 1


Nawal Benabbou, Mithun Chakraborty, Ayumi Igarashi, Yair Zick. Finding Fair and Efficient Allocations for Matroid Rank Valuations. ACM Transactions on Economics and Computation, 2021. ⟨hal-03271772⟩
32 View
182 Download


Gmail Facebook X LinkedIn More