Finding Fair and E � cient Allocations for Matroid Rank Valuations

In this paper, we present new results on the fair and e � cient allocation of indivis-ible goods to agents whose preferences correspond to matroid rank functions . This valuation class has several properties such as monotonicity and submodularity that make it naturally applicable to many real-world domains. We show that when agent valuations are matroid rank functions, an allocation that that maximizes utilitarian social welfare and also 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/e � ciency 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.

在本文中，我们针对偏好对应于拟阵秩函数的主体，给出了不可分割物品公平且高效分配的新结果。这种估值类别具有单调性和次模性等若干性质，使其自然适用于许多现实领域。我们表明，当主体估值是拟阵秩函数时，存在一种能使功利主义社会福利最大化且达到至多一项无嫉妒（EF1）的分配，并且这种分配在计算上是易于处理的。我们还通过证明在功利主义最优结果上最小化任何对称严格凸函数可以实现纳什福利最大化分配和字典序最小分配，从而证明它们都呈现出这种公平/效率组合。据我们所知，这是第一个不被加法估值所包含的估值函数类别，对于该类别，已确定使纳什福利最大化的分配是EF1。此外，对于基于最大（无权）二分匹配的这些估值函数的一个子类，我们表明可以在多项式时间内计算出字典序最小分配。