# Nash Social Welfare Approximation for Strategic Agents

arXiv: https://arxiv.org/abs/1607.01569 · HTML: https://mlsanity.com/paper/1607.01569/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Jul 2016.

## Built on by (most cited first, 9 of 9)

- [Finite-Sample Analysis of Decentralized Q-Learning for Stochastic Games](https://mlsanity.com/paper/2112.07859/) (2021)
- [Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness](https://mlsanity.com/paper/2109.08644/) (2021)
- [Stochastic Online Fisher Markets: Static Pricing Limits and Adaptive Enhancements](https://mlsanity.com/paper/2205.00825/) (2022)
- [Fairness Aware Reinforcement Learning via Proximal Policy Optimization](https://mlsanity.com/paper/2502.03953/) (2025)
- [Online Fair Allocation of Perishable Resources](https://mlsanity.com/paper/2406.02402/) (2024)
- [Intuitions of Compromise: Utilitarianism vs. Contractualism](https://mlsanity.com/paper/2410.05496/) (2024)
- [Regularized Proportional Fairness Mechanism for Resource Allocation Without Money](https://mlsanity.com/paper/2501.01111/) (2025)
- [Multi-User Dueling Bandits: A Fair Approach using Nash Social Welfare](https://mlsanity.com/paper/2605.01961/) (2026)
- [Fair Stable Matching: A Nash Social Welfare Approach](https://mlsanity.com/paper/2609.02354/) (2026)

## Abstract (arXiv)

The fair division of resources is an important age-old problem that has led to a rich body of literature. At the center of this literature lies the question of whether there exist fair mechanisms despite strategic behavior of the agents. A fundamental objective function used for measuring fair outcomes is the Nash social welfare, defined as the geometric mean of the agent utilities. This objective function is maximized by widely known solution concepts such as Nash bargaining and the competitive equilibrium with equal incomes. In this work we focus on the question of (approximately) implementing the Nash social welfare. The starting point of our analysis is the Fisher market, a fundamental model of an economy, whose benchmark is precisely the (weighted) Nash social welfare. We begin by studying two extreme classes of valuations functions, namely perfect substitutes and perfect complements, and find that for perfect substitutes, the Fisher market mechanism has a constant approximation: at most 2 and at least e1e. However, for perfect complements, the Fisher market does not work well, its bound degrading linearly with the number of players. Strikingly, the Trading Post mechanism---an indirect market mechanism also known as the Shapley-Shubik game---has significantly better performance than the Fisher market on its own benchmark. Not only does Trading Post achieve an approximation of 2 for perfect substitutes, but this bound holds for all concave utilities and becomes arbitrarily close to optimal for Leontief utilities (perfect complements), where it reaches (1+ε) for every ε > 0. Moreover, all the Nash equilibria of the Trading Post mechanism are pure for all concave utilities and satisfy an important notion of fairness known as proportionality.