Skip to Main content Skip to Navigation
Conference papers

Finding Fair and Efficient Allocations When Valuations Don't Add Up

Abstract : 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 (monotonicity, submodularity) which naturally models 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 fair-ness/efficiency combination, by showing that they can be achieved by minimizing any symmetric strictly convex function over utilitarian optimal outcomes. 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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [34 references]  Display  Hide  Download
Contributor : Nawal Benabbou <>
Submitted on : Friday, October 2, 2020 - 10:19:52 AM
Last modification on : Wednesday, October 7, 2020 - 3:20:31 AM


Files produced by the author(s)



Nawal Benabbou, Mithun Chakraborty, Ayumi Igarashi, Yair Zick. Finding Fair and Efficient Allocations When Valuations Don't Add Up. The 13th Symposium on Algorithmic Game Theory (SAGT 2020), Sep 2020, Augsburg (Virtual Conference), Germany. pp.32-46, ⟨10.1007/978-3-030-57980-7_3⟩. ⟨hal-02955635⟩



Record views


Files downloads