We study the problem of allocating a set of indivisible goods among a set of agents with two-value additive valuations. In this setting, each good is valued either 1 or p=q for some fixed coprime numbers p, q ∈ N such that 1 ≤ q < p. Our goal is to find an allocation that maximizes the Nash social welfare (NSW), that is, 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 value 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 that produces a maximum NSW allocation for the half-integral case, that is, q = 2. Finally, we show it is NP-hard to compute an allocation with maximum NSW whenever q ≥ 3.
Maximizing Nash Social Welfare in Two-Value Instances: Delineating Tractability
Varricchio G.
;
2026-01-01
Abstract
We study the problem of allocating a set of indivisible goods among a set of agents with two-value additive valuations. In this setting, each good is valued either 1 or p=q for some fixed coprime numbers p, q ∈ N such that 1 ≤ q < p. Our goal is to find an allocation that maximizes the Nash social welfare (NSW), that is, 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 value 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 that produces a maximum NSW allocation for the half-integral case, that is, q = 2. Finally, we show it is NP-hard to compute an allocation with maximum NSW whenever q ≥ 3.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.


