AAAI

Association for the Advancement of Artificial Intelligence

Home > Proceedings / Proceedings of the AAAI Conference on Artificial Intelligence, 36 > No. 5: AAAI-22 Technical Tracks 5

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


Proceedings:

No. 5: AAAI-22 Technical Tracks 5

Volume

Issue:

Proceedings of the AAAI Conference on Artificial Intelligence, 36

Track:

AAAI Technical Track on Game Theory and Economic Paradigms

Downloads:

Download PDF

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.

DOI:

10.1609/aaai.v36i5.20402


AAAI

Proceedings of the AAAI Conference on Artificial Intelligence, 36