Maximizing Nash Social Welfare in 2-Value Instances
Authors: Hannaneh Akrami, Bhaskar Ray Chaudhury, Martin Hoefer, Kurt Mehlhorn, Marco Schmalhofer, Golnoosh Shahkarami, Giovanna Varricchio, Quentin Vermande, Ernest van Wijland4760-4767
AAAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this work, we design an algorithm to compute an optimal allocation in polynomial time if p divides q, i.e., when p = 1 and q N after appropriate scaling. The problem is NP-hard whenever p and q are coprime and p 3. 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. |
| Researcher Affiliation | Academia | 1 Max Planck Institute for Informatics, Graduiertenschule Informatik, Universit at des Saarlandes 2 University of Illinois, Urbana-Champaign, Department of Computer Science 3 Goethe University Frankfurt, Institute for Computer Science 4 Max Planck Institute for Informatics, Universit at des Saarlandes 5 Ecole Normale Sup erieure, Paris |
| Pseudocode | Yes | Algorithm 1: Algorithm TWOVALUEAPPROX; Algorithm 2: Algorithm BALANCE |
| Open Source Code | No | The paper does not provide any statement or link indicating that the source code for the described methodology is publicly available. |
| Open Datasets | No | The paper is theoretical and does not describe experiments using datasets. Therefore, it does not provide information about public or open datasets. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical data or experiments, so it does not discuss training, validation, or test splits. |
| Hardware Specification | No | The paper describes theoretical algorithms and proofs. It does not mention any specific hardware used for running experiments. |
| Software Dependencies | No | The paper describes theoretical algorithms and mathematical proofs. It does not mention specific software, libraries, or their version numbers that would be used for implementation or experimentation. |
| Experiment Setup | No | The paper is theoretical, focusing on algorithm design and proofs. It does not describe an experimental setup with hyperparameters or training configurations. |