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

https://hal.sorbonne-universite.fr/hal-02955635
Contributor : Nawal Benabbou <>
Submitted on : Friday, October 2, 2020 - 10:19:52 AM
Last modification on : Wednesday, October 7, 2020 - 3:20:31 AM

File

SAGT2020_Paper22.pdf
Files produced by the author(s)

Identifiers

Citation

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⟩

Share

Metrics

Record views

9

Files downloads

16