Approximating Nash Social Welfare under Submodular Valuations through (Un)Matchings
Approximating Nash Social Welfare under Submodular Valuations through (Un)Matchings
复制标题
通过（非）匹配逼近子模估值下的纳什社会福利
DOI：
10.1137/1.9781611975994.163
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Kulkarni, Rucha
中科院分区：
文献类型：
--
作者：
Garg, Jugal;Kulkarni, Pooja;Kulkarni, Rucha
研究了在具有次模估值的非对称智能体之间分配可分项目时的最大纳什社会福利（NSW）逼近问题。新南威尔士州是一个公认的公平和效率的概念，被定义为代理人估值的加权几何平均值。对于具有对称代理和可加性（类）估值函数的问题的特殊情况，已经使用针对这些特定设置定制的方法设计了近似算法，并且它们无法扩展到更一般的设置。因此，在此工作之前，对于具有可加性赋值的非对称代理或超出可加性（类）赋值的对称代理，都没有已知的具有独立因子的近似算法。在本文中，我们将对NSW问题的理解扩展到更一般的设置。我们的主要贡献是两种具有加性和次模估值的非对称代理的近似算法。这两种算法都很容易理解，并且涉及对贪婪重复匹配方法的重要修改。在这两种算法中，高价值项目的分配是通过不匹配某些项目和通过不同的过程重新匹配它们来单独完成的。我们证明了这些方法在可加性和次模情况下实现了o (n)和do （nlogn）的近似因子，与项目的数量无关。对于加性估值，我们的算法输出的分配也达到了一个项目（EF1）的无嫉妒公平性。此外，我们表明，在次模估值下的NSW问题严格地比所有目前已知的具有近似硬度因子的设置更难，即使对于不断多的代理也是如此。对于这种情况，我们提供了一种不同的近似算法，实现了因子，从而完全解决了它。
We study the problem of approximating maximum Nash social welfare (NSW) when allocatingmindivisible items amongnasymmetric agents with submodular valuations. The NSW is a well-established notion of fairness and efficiency, defined as the weighted geometric mean of agents’ valuations. For special cases of the problem with symmetric agents and additive(-like) valuation functions, approximation algorithms have been designed using approaches customized for these specific settings, and they fail to extend to more general settings. Hence, no approximation algorithm with a factor independent ofmwas known either for asymmetric agents with additive valuations or for symmetric agents beyond additive(-like) valuations before this work.In this article, we extend our understanding of the NSW problem to far more general settings. Our main contribution is two approximation algorithms for asymmetric agents with additive and submodular valuations. Both algorithms are simple to understand and involve non-trivial modifications of a greedy repeated matchings approach. Allocations of high-valued items are done separately by un-matching certain items and re-matching them by different processes in both algorithms. We show that these approaches achieve approximation factors ofO(n) andO(nlogn) for additive and submodular cases, independent of the number of items. For additive valuations, our algorithm outputs an allocation that also achieves the fairness property of envy-free up to one item (EF1).Furthermore, we show that the NSW problem under submodular valuations is strictly harder than all currently known settings with anfactor of the hardness of approximation, even for constantly many agents. For this case, we provide a different approximation algorithm that achieves a factor of, hence resolving it completely.
登录
查看更多内容
圣诞老人、超图和拟阵的故事
DOI：
10.1137/1.9781611975994.167
发表时间：
2020
期刊：
Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
Davies, Sami;Rothvoss, Thomas Rothvoss;Zhang, Yihao
通讯作者：
Zhang, Yihao
DOI：
--
发表时间：
2021
期刊：
The Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI-21
影响因子：
--
作者：
Chaudhury, Bhaskar Ray;Garg, Jugal;Mehta, Ruta
通讯作者：
Mehta, Ruta
最大-最小分配问题的近似算法
DOI：
10.1007/978-3-540-74208-1_15
发表时间：
2007
期刊：
SIAM J. Appl. Algebra Geom.
影响因子：
--
作者：
Subhash Khot;Ashok Kumar Ponnuswami
通讯作者：
Ashok Kumar Ponnuswami
可分离分段线性凹效用下不可分项的纳什社会福利
DOI：
--
发表时间：
2016
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
Nima Anari;Tung Mai;S. Gharan;V. Vazirani
通讯作者：
V. Vazirani
DOI：
--
发表时间：
2017
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
J. Garg;M. Hoefer;K. Mehlhorn
通讯作者：
K. Mehlhorn