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, Ernest van Wijland

AAAI 2022 pp. 4760-4767

doi:10.1609/AAAI.V36I5.20402 /aaai/2022/akrami2022aaai-maximizing/

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.

PDF AAAI Semantic Scholar

Cite

Text

Akrami et al. "Maximizing Nash Social Welfare in 2-Value Instances." AAAI Conference on Artificial Intelligence, 2022. doi:10.1609/AAAI.V36I5.20402

Markdown

[Akrami et al. "Maximizing Nash Social Welfare in 2-Value Instances." AAAI Conference on Artificial Intelligence, 2022.](https://mlanthology.org/aaai/2022/akrami2022aaai-maximizing/) doi:10.1609/AAAI.V36I5.20402

BibTeX

@inproceedings{akrami2022aaai-maximizing,
  title     = {{Maximizing Nash Social Welfare in 2-Value Instances}},
  author    = {Akrami, Hannaneh and Chaudhury, Bhaskar Ray and Hoefer, Martin and Mehlhorn, Kurt and Schmalhofer, Marco and Shahkarami, Golnoosh and Varricchio, Giovanna and Vermande, Quentin and van Wijland, Ernest},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2022},
  pages     = {4760-4767},
  doi       = {10.1609/AAAI.V36I5.20402},
  url       = {https://mlanthology.org/aaai/2022/akrami2022aaai-maximizing/}
}