Approximating Nash Social Welfare by Matching and Local Search
Approximating Nash Social Welfare by Matching and Local Search
复制标题
通过匹配和本地搜索近似纳什社会福利
DOI：
10.1145/3564246.3585255
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Vondrák, Jan
中科院分区：
文献类型：
--
作者：
Garg, Jugal;Husić, Edin;Li, Wenzheng;Végh, László A.;Vondrák, Jan
对于任意>，我们给出了一个简单的，确定性的(4+)-近似算法，用于求解亚模估值下的纳什社会福利问题。通过随机算法，之前的最佳近似因子为380。我们还考虑了该问题的非对称变体，其目标是最大化代理估值的加权几何平均值，并且如果最大权重与平均权重之间的比率不超过ω，则给出(ω + 2 +) -近似。我们还证明了用常因子近似可以同时获得12-EFX的无嫉妒性。更确切地说，我们可以在多项式时间内找到一个分配，它是对称NSW问题在次模值下的12-EFX和(8+)-逼近。先前在12-EFX下的最佳近似因子与药剂数量呈线性关系。
For any >0, we give a simple, deterministic (4+)-approximation algorithm for the Nash social welfare (NSW) problem under submodular valuations. The previous best approximation factor was 380 via a randomized algorithm. We also consider the asymmetric variant of the problem, where the objective is to maximize the weighted geometric mean of agents’ valuations, and give an (ω + 2 + ) -approximation if the ratio between the largest weight and the average weight is at most ω.We also show that the 12-EFX envy-freeness property can be attained simultaneously with a constant-factor approximation. More precisely, we can find an allocation in polynomial time which is both 12-EFX and a (8+)-approximation to the symmetric NSW problem under submodular valuations. The previous best approximation factor under 12-EFX was linear in the number of agents.
登录
查看更多内容
将附加估值扩展到对 EFX 存在的一般估值
DOI：
--
发表时间：
2021
期刊：
Embedded Systems and Applications
影响因子：
--
作者：
Ryoga Mahara
通讯作者：
Ryoga Mahara
四名特工的 EFX 几乎已满
DOI：
10.1609/aaai.v36i5.20410
发表时间：
2022
期刊：
ArXiv
影响因子：
--
作者：
Ben Berger;Avi Cohen;M. Feldman;A. Fiat
通讯作者：
A. Fiat
DOI：
--
发表时间：
2021
期刊：
The Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI-21
影响因子：
--
作者：
Chaudhury, Bhaskar Ray;Garg, Jugal;Mehta, Ruta
通讯作者：
Mehta, Ruta
水产市场的饱和度和纳什社会福利的近似
DOI：
10.1287/moor.2019.0129
发表时间：
2017
期刊：
Math. Oper. Res.
影响因子：
--
作者：
J. Garg;M. Hoefer;K. Mehlhorn
通讯作者：
K. Mehlhorn
最大纳什福利和有关 EFX 的其他故事
DOI：
10.24963/ijcai.2020/4
发表时间：
2020
期刊：
--
影响因子：
--
作者：
Amanatidis G
通讯作者：
Amanatidis G