Maximizing Nash Social Welfare in Two-Value Instances: Delineating Tractability

Mathematics of Operations Research, vol. 51, pp. 853–876

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 [Formula: see text] for some fixed coprime numbers [Formula: see text] such that [Formula: see text]. 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, [Formula: see text]. We then exploit more involved techniques to get an algorithm that produces a maximum NSW allocation for the half-integral case, that is, [Formula: see text]. Finally, we show it is NP-hard to compute an allocation with maximum NSW whenever [Formula: see text]. Funding: M. Hoefer and G. Varricchio were supported by the DFG [Grant Ho 3831/5-1].

Authors 8

1. Hannaneh Akrami

   University of Bonn · Max Planck Institute for Informatics · Saarland University

   Affiliation as printed

   Max Planck Institute for Informatics, 66123 Saarbrücken, Germany; and Hertz Chair for Algorithms and Optimization, Bonn University, 53113 Bonn, Germany; and Universität des Saarlandes, 66123 Saarbrücken, Germany

   Max Planck Institute for Informatics and Graduirtenschule Informatik, Universität des Saarlandes, 66123 Saarbrücken, Germany

2. Martin Hoefer Aachen Department of Computer Science

   Goethe University Frankfurt · RWTH Aachen University

   Affiliation as printed

   Department of Computer Science, RWTH Aachen University, 52062 Aachen, Germany

   Institute for Computer Science, Goethe University Frankfurt, D-60325 Frankfurt, Germany

3. Kurt Mehlhorn

   Max Planck Institute for Informatics · Saarland University

   Affiliation as printed

   Max Planck Institute for Informatics, 66123 Saarbrücken, Germany; and Universität des Saarlandes, 66123 Saarbrücken, Germany

   Max Planck Institute for Informatics, Universität des Saarlandes, 66123 Saarbrücken, Germany

4. Marco Schmalhofer

   Goethe University Frankfurt

   Affiliation as printed

   Institute for Computer Science, Goethe University Frankfurt, 60629 Frankfurt am Main, Germany

   Institute for Computer Science, Goethe University Frankfurt, D-60325 Frankfurt, Germany

5. Golnoosh Shahkarami

   Max Planck Institute for Informatics · Saarland University

   Affiliation as printed

   Max Planck Institute for Informatics, 66123 Saarbrücken, Germany; and Saarbrücken Graduate School of Computer Science, Universität des Saarlandes, 66123 Saarbrücken, Germany

   Max Planck Institute for Informatics and Graduirtenschule Informatik, Universität des Saarlandes, 66123 Saarbrücken, Germany

6. Giovanna Varricchio

   University of Calabria

   Affiliation as printed

   Department of Mathematics and Computer Science, University of Calabria, 87036 Arcavacata, Italy

   Department of Mathematics and Computer Science, Universitá della Calabria, 87036 Rende, Italy

7. Quentin Vermande

   Institut national de recherche en sciences et technologies du numérique · Centre Inria d'Université Côte d'Azur

   Affiliation as printed

   INRIA Centre at Université Côte d’Azur, 06902 Sophia Antipolis, France

   Inria Centre at Université Côte d’Azur, 06103 Nice, France

8. Ernest van Wijland

   Université Paris Cité · École Normale Supérieure - PSL · Institut de Recherche en Informatique Fondamentale

   Affiliation as printed

   IRIF, Université Paris-Cité, 75006 Paris, France

   École Normale Supérieure, 75005 Paris, France