Maximizing Nash Social Welfare in 2-Value Instances

Authors

  • Hannaneh Akrami Max Planck Institute for Informatics Graduiertenschule Informatik, Universität des Saarlandes
  • Bhaskar Ray Chaudhury University of Illinois, Urbana-Champaign, Department of Computer Science
  • Martin Hoefer Goethe University Frankfurt, Institute for Computer Science
  • Kurt Mehlhorn Max Planck Institute for Informatics, Universität des Saarlandes
  • Marco Schmalhofer Goethe University Frankfurt, Institute for Computer Science
  • Golnoosh Shahkarami Max Planck Institute for Informatics Graduiertenschule Informatik, Universität des Saarlandes
  • Giovanna Varricchio Goethe University Frankfurt, Institute for Computer Science
  • Quentin Vermande École Normale Supérieure, Paris
  • Ernest van Wijland École Normale Supérieure, Paris

DOI:

https://doi.org/10.1609/aaai.v36i5.20402

Keywords:

Game Theory And Economic Paradigms (GTEP)

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.
AAAI-22 Proceedings Cover

Downloads

Published

2022-06-28

How to Cite

Akrami, H., Chaudhury, B. R., Hoefer, M., Mehlhorn, K., Schmalhofer, M., Shahkarami, G., Varricchio, G., Vermande, Q., & Wijland, E. van. (2022). Maximizing Nash Social Welfare in 2-Value Instances. Proceedings of the AAAI Conference on Artificial Intelligence, 36(5), 4760-4767. https://doi.org/10.1609/aaai.v36i5.20402

Issue

Vol. 36 No. 5: AAAI-22 Technical Tracks 5

Section

AAAI Technical Track on Game Theory and Economic Paradigms