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.
2026
game theory
Nash social welfare
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.11770/418177
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? 0
social impact