论文标题
在RADO估值下近似纳什的社会福利
Approximating Nash Social Welfare under Rado Valuations
论文作者
论文摘要
我们考虑到近似NASH社会福利（NSW）的问题，同时将一组不可分割的物品分配给$ n $代理。新南威尔士州是一个流行的目标，在公平和效率的经常冲突要求之间提供了平衡的权衡，该要求定义为代理商估值的加权几何平均值。对于该问题的对称添加剂情况，如果代理具有相同的重量和添加估值，则在2015年获得了第一个恒定因素近似算法。这导致了一系列在符合量的属性案例中获得恒定因素近似算法的工作，该算法是在添加剂和$ o（n）$ o（n）$ -O-近似值中的更多符合案例，以获取更多的一般性算法和更多的一般性。 在本文中，我们在对称和不对称的新南威尔士州问题方面取得了重大进展。我们介绍了RADO估值下的对称情况的第一个恒定因子近似算法。 RADO估值构成了由最大成本独立匹配问题引起的一般估值功能，包括特殊情况分配（OX）估值和加权矩阵等级功能。此外，我们的方法还提供了第一个恒定因子近似算法，对于RADO估值下的不对称情况，只要权重之间的最大比率是由常数界定的。
We consider the problem of approximating maximum Nash social welfare (NSW) while allocating a set of indivisible items to $n$ agents. The NSW is a popular objective that provides a balanced tradeoff between the often conflicting requirements of fairness and efficiency, defined as the weighted geometric mean of agents' valuations. For the symmetric additive case of the problem, where agents have the same weight with additive valuations, the first constant-factor approximation algorithm was obtained in 2015. This led to a flurry of work obtaining constant-factor approximation algorithms for the symmetric case under mild generalizations of additive, and $O(n)$-approximation algorithms for more general valuations and for the asymmetric case. In this paper, we make significant progress towards both symmetric and asymmetric NSW problems. We present the first constant-factor approximation algorithm for the symmetric case under Rado valuations. Rado valuations form a general class of valuation functions that arise from maximum cost independent matching problems, including as special cases assignment (OXS) valuations and weighted matroid rank functions. Furthermore, our approach also gives the first constant-factor approximation algorithm for the asymmetric case under Rado valuations, provided that the maximum ratio between the weights is bounded by a constant.
