Nash Social Welfare Approximation for Strategic Agents

• 成果类型: Article
• 署名作者: Bra, Simina; Gkatzelis, Vasilis; Mehta, Ruta
• 署名单位: Purdue University System; Purdue University; Drexel University; University of Illinois System; University of Illinois Urbana-Champaign
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2020.2056
• 发表日期: 2022
• 页码: 402-415
• 关键词: equilibrium; allocation; fairness; prices

摘要

A central goal in the long literature on fair division is the design of mechanisms that implement fair outcomes, despite the participants' strategic behavior. We study this question by measuring the fairness of an allocation using the geometric mean of the agents' values, known as the Nash social welfare (NSW). This objective is maximized by widely known concepts such as the Nash bargaining solution, proportional fairness, and the competitive equilibrium with equal incomes; we focus on (approximately) implementing this objective and analyze the Trading Post mechanism. We consider allocating goods that are substitutes or complements and show that this mechanism achieves an approximation of two for concave utility functions and becomes essentially optimal for complements, where it can reach (1 + epsilon) for any (epsilon > 0). Moreover, we show that the Nash equilibria of this mechanism are pure and provide individual fairness in the sense of proportionality.