Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
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 | Venue PDF | 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. |