@conference {1523378,
	title = {Finding Fair and Efficient Allocations When Valuations Don{\textquoteright}t Add Up},
	booktitle = {AI for Social Good Workshop},
	year = {2020},
	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 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{\textquoteright} 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

},
	author = {Nawal Benabbou and Mithun Chakraborty and Ayumi Igarashi and Yair Zick}
}
