Finding Fair and Efficient Allocations When Valuations Don't Add Up
This addresses fair allocation problems in domains like resource distribution, offering new theoretical guarantees for non-additive valuations, though it is incremental in extending known results to a broader class.
The paper tackles the problem of fairly and efficiently allocating indivisible goods to agents with matroid rank function valuations, showing that socially optimal allocations achieving envy-freeness up to one item (EF1) exist and are computationally tractable, and proving that Nash welfare-maximizing and leximin allocations also exhibit this combination, with polynomial-time computation for a subclass.
In this paper, we present new results on the fair and efficient allocation of indivisible goods to agents whose preferences correspond to {\em 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.