TY - JOUR
AU - Akrami, Hannaneh
AU - Chaudhury, Bhaskar Ray
AU - Hoefer, Martin
AU - Mehlhorn, Kurt
AU - Schmalhofer, Marco
AU - Shahkarami, Golnoosh
AU - Varricchio, Giovanna
AU - Vermande, Quentin
AU - Wijland, Ernest van
PY - 2022/06/28
Y2 - 2023/03/26
TI - Maximizing Nash Social Welfare in 2-Value Instances
JF - Proceedings of the AAAI Conference on Artificial Intelligence
JA - AAAI
VL - 36
IS - 5
SE - AAAI Technical Track on Game Theory and Economic Paradigms
DO - 10.1609/aaai.v36i5.20402
UR - https://ojs.aaai.org/index.php/AAAI/article/view/20402
SP - 4760-4767
AB - 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 for every good is either p or q, where p and q are integers and 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 is an integer after appropriate scaling. The problem is NP-hard whenever p and q are coprime and p>2. 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.
ER -