论文标题
在矩阵估值下的最大值公平分配的存在和计算
Existence and Computation of Maximin Fair Allocations Under Matroid-Rank Valuations
论文作者
论文摘要
我们研究了估值是矩形函数的代理商中不可分割的商品的公平和经济有效的分配。这些估值构成了一类精心培养的子模函数（即它们在几种资源分配设置中表现出降低的回报属性）和模型偏好。我们证明，对于矩阵估值，社会福利最大化的分配，使每个代理人的最大值份额始终存在。此外，可以在多项式时间内计算这种分配。我们为成对最大蛋白共享保证的同样存在和算法结果建立了类似的存在和算法结果。 为了补充这些结果，我们表明，如果代理具有二进制XOS估值或加权级别的估值，则不能保证最大值公平分配。这两个估值类都是矩阵量函数的直接概括。
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.
