# Maximizing Nash Social Welfare in 2-Value Instances: Delineating Tractability

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Jul 2022.

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

- [Settling the Computational Complexity of Max-Min Allocation with Ternary Valuations](https://mlsanity.com/paper/2610.05237/) (2026)

## Abstract (arXiv)

We study the problem of allocating a set of indivisible goods among a set of agents with 2-value additive valuations. In this setting, each good is valued either 1 or p/q, for some fixed co-prime numbers p,q∈ mathbbN such that 1≤ q < p. Our goal is to find an allocation maximizing the Nash social welfare (NSW), i.e., the geometric mean of the valuations of the agents. In this work, we give a complete characterization of polynomial-time tractability of NSW maximization that solely depends on the values of q. We start by providing a rather simple polynomial-time algorithm to find a maximum NSW allocation when the valuation functions are integral, that is, q=1. We then exploit more involved techniques to get an algorithm producing a maximum NSW allocation for the half-integral case, that is, q=2. Finally, we show it is classNP-hard to compute an allocation with maximum NSW whenever q≥3.