Estimating the Nash Social Welfare for coverage and other submodular valuations
Estimating the Nash Social Welfare for coverage and other submodular valuations
复制标题
估计纳什社会福利的覆盖范围和其他子模块估值
DOI：
10.1137/1.9781611976465.69
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
J. Vondrák
中科院分区：
文献类型：
--
作者：
Wenzheng Li;J. Vondrák
We study the Nash Social Welfare problem: Given $n$ agents with valuation functions $v_i:2^{[m]} \rightarrow {\mathbb R}$, partition $[m]$ into $S_1,\ldots,S_n$ so as to maximize $(\prod_{i=1}^{n} v_i(S_i))^{1/n}$. The problem has been shown to admit a constant-factor approximation for additive, budget-additive, and piecewise linear concave separable valuations; the case of submodular valuations is open. We provide a $\frac{1}{e} (1-\frac{1}{e})^2$-approximation of the {\em optimal value} for several classes of submodular valuations: coverage, sums of matroid rank functions, and certain matching-based valuations.
We study the Nash Social Welfare problem: Given $n$ agents with valuation functions $v_i:2^{[m]} \rightarrow {\mathbb R}$, partition $[m]$ into $S_1,\ldots,S_n$ so as to maximize $(\prod_{i=1}^{n} v_i(S_i))^{1/n}$. The problem has been shown to admit a constant-factor approximation for additive, budget-additive, and piecewise linear concave separable valuations; the case of submodular valuations is open. We provide a $\frac{1}{e} (1-\frac{1}{e})^2$-approximation of the {\em optimal value} for several classes of submodular valuations: coverage, sums of matroid rank functions, and certain matching-based valuations.
通过（非）匹配逼近子模估值下的纳什社会福利
DOI：
10.1137/1.9781611975994.163
发表时间：
2020
期刊：
Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
Garg, Jugal;Kulkarni, Pooja;Kulkarni, Rucha
通讯作者：
Kulkarni, Rucha
论不可分割物品的公平分割
影响因子：
--
作者：
Chaudhury, Bhaskar Ray;Cheung, Yun Kuen;Garg, Jugal;Garg, Naveen;Hoefer, Martin;Mehlhorn, Kurt
通讯作者：
Mehlhorn, Kurt