AAAI 2022technical21 citations
Maximizing Nash Social Welfare in 2-Value Instances
Hannaneh Akrami, Bhaskar Ray Chaudhury, Martin Hoefer, Kurt Mehlhorn, Marco Schmalhofer, Golnoosh Shahkarami, Giovanna Varricchio, Quentin Vermande
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 for every good is either p or q, where p and q are integers and p2. 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.
BibTeX
@inproceedings{aaai2022_maximizingnashso,
title = {Maximizing Nash Social Welfare in 2-Value Instances},
author = {Hannaneh Akrami and Bhaskar Ray Chaudhury and Martin Hoefer and Kurt Mehlhorn and Marco Schmalhofer and Golnoosh Shahkarami and Giovanna Varricchio and Quentin Vermande and Ernest van Wijland},
booktitle = {AAAI 2022},
year = {2022}
}