Files and links (1)
SubmittedOpen Access (License Unspecified), Open
Journal article
Nash Social Welfare Approximation for Strategic Agents
Operations research, v 70(1), pp 402-415
01 Jan 2022
Abstract
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.
Metrics
Details
- Title
- Nash Social Welfare Approximation for Strategic Agents
- Creators
- Simina Bra - Purdue Univ, Comp Sci, W Lafayette, IN 47407 USAVasilis Gkatzelis - Drexel UniversityRuta Mehta - University of Illinois Urbana-Champaign
- Publication Details
- Operations research, v 70(1), pp 402-415
- Publisher
- Informs
- Number of pages
- 15
- Grant note
- 2014389 / United States-Israel Binational Science Foundation; US-Israel Binational Science Foundation 1408635; 1216073; 1161813 / Division of Computing and Communication Foundations; National Science Foundation (NSF); NSF - Directorate for Computer & Information Science & Engineering (CISE) 740282 / European Research Council under the European Union; European Research Council (ERC) 1435/14 / Israel Science Foundation CCF-175595; CCF-1750436 / National Science Foundation; National Science Foundation (NSF)
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- Computer Science
- Web of Science ID
- WOS:000709015000001
- Scopus ID
- 2-s2.0-85125008964
- Other Identifier
- 991019302292104721
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Collaboration types
- Domestic collaboration
- Web of Science research areas
- Management
- Operations Research & Management Science