摘要翻译：
我们研究了一组不可分商品在具有加性估价的代理之间的公平分配问题。分配的公平性程度是用它的纳什社会福利来衡量的，纳什社会福利是代理人对其捆绑的估价的几何平均数。虽然纳什社会福利最大化问题通常是APX困难的，但我们在两个有趣的特殊情况下研究了简单贪婪算法在解决该问题中的有效性。首先，我们证明了一个简单的贪婪算法在Agent具有相同的估值时提供了1.061近似保证，尽管纳什社会福利最大化问题在这种情况下仍然是NP困难的。其次，我们证明了当代理对货物具有二元价值时，通过贪婪算法可以在多项式时间内找到精确解（即纳什最优分配）。我们在二元集合中的结果扩展为在凹估值下优化纳什社会福利提供了新的、精确的算法。值得注意的是，对于上面提到的场景，我们的技术提供了一个简单的替代现有的几个更复杂的技术来解决这个问题，如构造Fisher市场的均衡或使用实稳定多项式。
---
英文标题：
《Greedy Algorithms for Maximizing Nash Social Welfare》
---
作者：
Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish
---
最新提交年份：
2018
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Computer Science and Game Theory        计算机科学与博弈论
分类描述：Covers all theoretical and applied aspects at the intersection of computer science and game theory, including work in mechanism design, learning in games (which may overlap with Learning), foundations of agent modeling in games (which may overlap with Multiagent systems), coordination, specification and formal methods for non-cooperative computational environments. The area also deals with applications of game theory to areas such as electronic commerce.
涵盖计算机科学和博弈论交叉的所有理论和应用方面，包括机制设计的工作，游戏中的学习（可能与学习重叠），游戏中的agent建模的基础（可能与多agent系统重叠），非合作计算环境的协调、规范和形式化方法。该领域还涉及博弈论在电子商务等领域的应用。
--
一级分类：Economics        经济学
二级分类：Theoretical Economics        理论经济学
分类描述：Includes theoretical contributions to Contract Theory, Decision Theory, Game Theory, General Equilibrium, Growth, Learning and Evolution, Macroeconomics, Market and Mechanism Design, and Social Choice.
包括对契约理论、决策理论、博弈论、一般均衡、增长、学习与进化、宏观经济学、市场与机制设计、社会选择的理论贡献。
--

---
英文摘要：
  We study the problem of fairly allocating a set of indivisible goods among agents with additive valuations. The extent of fairness of an allocation is measured by its Nash social welfare, which is the geometric mean of the valuations of the agents for their bundles. While the problem of maximizing Nash social welfare is known to be APX-hard in general, we study the effectiveness of simple, greedy algorithms in solving this problem in two interesting special cases.   First, we show that a simple, greedy algorithm provides a 1.061-approximation guarantee when agents have identical valuations, even though the problem of maximizing Nash social welfare remains NP-hard for this setting. Second, we show that when agents have binary valuations over the goods, an exact solution (i.e., a Nash optimal allocation) can be found in polynomial time via a greedy algorithm. Our results in the binary setting extend to provide novel, exact algorithms for optimizing Nash social welfare under concave valuations. Notably, for the above mentioned scenarios, our techniques provide a simple alternative to several of the existing, more sophisticated techniques for this problem such as constructing equilibria of Fisher markets or using real stable polynomials.
---
PDF链接：
https://arxiv.org/pdf/1801.09046