Approximating the Nash Social Welfare with Budget-Additive Valuations
Approximating the Nash Social Welfare with Budget-Additive Valuations
复制标题
用预算加法估值近似纳什社会福利
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
K. Mehlhorn
中科院分区：
文献类型：
--
作者：
J. Garg;M. Hoefer;K. Mehlhorn
我们介绍了第一种恒定因素近似算法，用于在将不可分割的项目分配给具有预算添加估值功能的代理商时最大化NASH社会福利。预算添加的估值代表了一类重要的子解多功能。由于许多有趣的应用，近年来，他们引起了很多研究兴趣。对于每一个$ \ varepsilon> 0 $，我们的算法都会获得$（2.404 + \ varepsilon）$ - 输入大小的时间多项式和$ 1/\ varepsilon $。
我们的算法依赖于在线性渔民市场上汇总的近似平衡，在该市场中，卖方拥有赚钱限制（他们想要赚取的钱的上限），买家具有公用事业限制（他们想要实现的效用量的上限）。与获得收入或公用事业限制的市场相反，这些市场以前尚未研究。它们证明具有根本不同的属性。
尽管不能保证存在平衡的存在，但我们表明，纳什社会福利问题产生的市场实例始终具有平衡。此外，我们表明一组平衡不是凸，回答了[Cole等，EC 2017]的问题。我们设计了一个FPTA来计算近似平衡，这可能是独立的。
We present the first constant-factor approximation algorithm for maximizing the Nash social welfare when allocating indivisible items to agents with budget-additive valuation functions. Budget-additive valuations represent an important class of submodular functions. They have attracted a lot of research interest in recent years due to many interesting applications. For every $\varepsilon > 0$, our algorithm obtains a $(2.404 + \varepsilon)$-approximation in time polynomial in the input size and $1/\varepsilon$.
Our algorithm relies on rounding an approximate equilibrium in a linear Fisher market where sellers have earning limits (upper bounds on the amount of money they want to earn) and buyers have utility limits (upper bounds on the amount of utility they want to achieve). In contrast to markets with either earning or utility limits, these markets have not been studied before. They turn out to have fundamentally different properties.
Although the existence of equilibria is not guaranteed, we show that the market instances arising from the Nash social welfare problem always have an equilibrium. Further, we show that the set of equilibria is not convex, answering a question of [Cole et al, EC 2017]. We design an FPTAS to compute an approximate equilibrium, a result that may be of independent interest.
DOI：
10.1145/3313276.3316340
发表时间：
2018-09
期刊：
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
J. Garg;László A. Végh
通讯作者：
J. Garg;László A. Végh
论不可分割物品的公平分割
影响因子：
--
作者：
Chaudhury, Bhaskar Ray;Cheung, Yun Kuen;Garg, Jugal;Garg, Naveen;Hoefer, Martin;Mehlhorn, Kurt
通讯作者：
Mehlhorn, Kurt