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


Benabbou N, Chakraborty M, Igarashi A, Zick Y. Finding Fair and Efficient Allocations When Valuations Don’t Add Up, in AI for Social Good Workshop. ; 2020.


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 several 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 of agents’ valuations 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.

Back to AI for Social Good event

Last updated on 07/01/2021