We study fair and economically efficient allocation of indivisible goods among agents whose valuations are rank functions of matroids. Such valuations constitute a well-studied class of submodular functions (i.e., they exhibit a diminishing returns property) and model preferences in several resource-allocation settings. We prove that, for matroid-rank valuations, a social welfare-maximizing allocation that gives each agent her maximin share always exists. Furthermore, such an allocation can be computed in polynomial time. We establish similar existential and algorithmic results for the pairwise maximin share guarantee as well. To complement these results, we show that if the agents have binary XOS valuations or weighted-rank valuations, then maximin fair allocations are not guaranteed to exist. Both of these valuation classes are immediate generalizations of matroid-rank functions.
翻译:我们研究的是,在那些其估值是机器人等级功能的代理人之间,如何公平和经济有效地分配不可分割的商品,这种估值构成了一种经过良好研究的亚模式功能类别(即,它们显示出回报率下降的财产)和在若干资源分配环境中的模式偏好。我们证明,对于机车级别估值而言,始终存在社会福利和最大比例的分配,使每个代理人都享有最大份额。此外,这种分配可以在多元时间内计算。我们为对称最大份额担保也建立了类似的存在和算法结果。为了补充这些结果,我们表明,如果代理人拥有二进制XOS估值或加权估值,那么无法保证存在最高比例的公平分配。这两个估值类别都是对称最大份额功能的即时一般化。