论文标题
预算可行的最大NASH社会福利分配几乎不羡慕
Budget-feasible Maximum Nash Social Welfare Allocation is Almost Envy-free
论文作者
论文摘要
纳什社会福利（NSW）是众所周知的社会福利衡量标准，可以平衡单个公用事业和整体效率。在不可分割的商品的公平分配的背景下，Caragiannis等人已经表明了它。 （EC 2016和TEAC 2019），最大化新南威尔士州的分配是嫉妒的，最多是一种好处（EF1）。在本文中，我们对新南威尔士州在预算可行的分配问题中的公平性感兴趣，其中每个项目的成本将产生给其分配给代理商，每个代理商对她收到的物品的总成本都有预算限制。我们表明，最大化新南威尔士州实现EF1的1/4及时的预算分配，并且近似值比很紧。与代理商的预算相比，当物品的成本较小时，近似比优雅地提高；当预算比率接近无穷大时，它会收敛到1/2。
The Nash social welfare (NSW) is a well-known social welfare measurement that balances individual utilities and the overall efficiency. In the context of fair allocation of indivisible goods, it has been shown by Caragiannis et al. (EC 2016 and TEAC 2019) that an allocation maximizing the NSW is envy-free up to one good (EF1). In this paper, we are interested in the fairness of the NSW in a budget-feasible allocation problem, in which each item has a cost that will be incurred to the agent it is allocated to, and each agent has a budget constraint on the total cost of items she receives. We show that a budget-feasible allocation that maximizes the NSW achieves a 1/4-approximation of EF1 and the approximation ratio is tight. The approximation ratio improves gracefully when the items have small costs compared with the agents' budgets; it converges to 1/2 when the budget-cost ratio approaches infinity.
