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 ∈ N, p ≤ q. In this work, we design an algorithm to compute an optimal allocation in polynomial time if p divides q, i.e., when p = 1 and q ∈ N after appropriate scaling. The problem is NP-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 APX-hard, with a lower bound of 1.000015 achieved at p/q = 4/5.
Maximizing Nash Social Welfare in 2-Value Instances
Varricchio G.;
2022-01-01
Abstract
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 ∈ N, p ≤ q. In this work, we design an algorithm to compute an optimal allocation in polynomial time if p divides q, i.e., when p = 1 and q ∈ N after appropriate scaling. The problem is NP-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 APX-hard, with a lower bound of 1.000015 achieved at p/q = 4/5.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
