Nash Social Welfare for Indivisible Items under Separable, Piecewise-Linear Concave Utilities
Nash Social Welfare for Indivisible Items under Separable, Piecewise-Linear Concave Utilities
复制标题
可分离分段线性凹效用下不可分项的纳什社会福利
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
V. Vazirani
中科院分区：
文献类型：
--
作者：
Nima Anari;Tung Mai;S. Gharan;V. Vazirani
最近，Cole和Gkatzelis [10]给出了第一个常数因子近似算法，即在添加估值下将不可分割的项目分配给代理的问题，以最大程度地提高NASH社会福利（NSW）。对于可分离的分段线性凹入效用函数，我们给出了对其问题进行实质性概括的恒定因子算法。我们给出了两种这样的算法，第一种算法使用市场均衡，第二种是使用实际稳定多项式的理论。两种方法都需要新的算法想法。
Recently Cole and Gkatzelis [10] gave the first constant factor approximation algorithm for the problem of allocating indivisible items to agents, under additive valuations, so as to maximize the Nash social welfare (NSW). We give constant factor algorithms for a substantial generalization of their problem - to the case of separable, piecewise-linear concave utility functions. We give two such algorithms, the first using market equilibria and the second using the theory of real stable polynomials. Both approaches require new algorithmic ideas.