论文标题
统一的福利保证在相同的亚收益估值下
Uniform Welfare Guarantees Under Identical Subadditive Valuations
论文作者
论文摘要
我们研究了对商品具有相同次级估值的代理商分配不可分割的商品的问题。分配的公平性和效率的程度是通过代理之间分配产生的价值的广义方式来衡量的。由指数术语$ p $参数化，广义公平的福利包括多个研究的目标，例如社会福利，纳什社会福利和平等主义福利。 我们确定，在相同的亚添加估值和需求甲骨文模型下，人们可以有效地找到一个单个分配，该分配近似于最佳的广义均值福利 - 在40美元以内，均为$ 40 $ ---对于所有$ p \ in（ - \ infty，1] $。相同的亚收益估值的福利。
We study the problem of allocating indivisible goods among agents that have an identical subadditive valuation over the goods. The extent of fairness and efficiency of allocations is measured by the generalized means of the values that the allocations generate among the agents. Parameterized by an exponent term $p$, generalized-mean welfares encompass multiple well-studied objectives, such as social welfare, Nash social welfare, and egalitarian welfare. We establish that, under identical subadditive valuations and in the demand oracle model, one can efficiently find a single allocation that approximates the optimal generalized-mean welfare---to within a factor of $40$---uniformly for all $p \in (-\infty, 1]$. Hence, by way of a constant-factor approximation algorithm, we obtain novel results for maximizing Nash social welfare and egalitarian welfare for identical subadditive valuations.
