# Maximizing Nash Social Welfare in 2-Value Instances

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Jul 2021.

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

- [Online Fair Division for Personalized 2-Value Instances](https://mlsanity.com/paper/2505.22174/) (2025)
- [Dividing Good and Better Items Among Agents with Bivalued Submodular Valuations](https://mlsanity.com/paper/2302.03087/) (2023)
- [Large-Scale Auto-bidding with Nash Equilibrium Constraints](https://mlsanity.com/paper/2503.10304/) (2025)
- [Probing EFX via PMMS: (Non-)Existence Results in Discrete Fair Division](https://mlsanity.com/paper/2507.14957/) (2025)
- [Settling the Computational Complexity of Max-Min Allocation with Ternary Valuations](https://mlsanity.com/paper/2610.05237/) (2026)

## Abstract (arXiv)

We consider the problem of maximizing the Nash social welfare when allocating a set G of indivisible goods to a set N of agents. We study instances, in which all agents have 2-value additive valuations: The value of every agent i ∈ N for every good j ∈ G is vij ∈ p,q, for p,q ∈ mathbbN, p ≤ q. Maybe surprisingly, we design an algorithm to compute an optimal allocation in polynomial time if p divides q, i.e., when p=1 and q ∈ mathbbN after appropriate scaling. The problem is classNP-hard whenever p and q are coprime and p ≥ 3. In terms of approximation, we present positive and negative results for general p and q. We show that our algorithm obtains an approximation ratio of at most 1.0345. Moreover, we prove that the problem is classAPX-hard, with a lower bound of 1.000015 achieved at p/q = 4/5.