Approximations for Indivisible Concave Allocations with Applications to Nash Welfare Maximization
Authors: Nathaniel Kell, Kevin Sun
AAAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we obtain both multiplicative and additive approximations in the offline setting for indivisible items. Our approximations depend on novel parameters that measure the local multiplicative/additive curvatures of each agent valuation, which we show correspond directly to the integrality gap of the natural assignment convex program of the problem. Furthermore, we extend our additive guarantees to obtain constant multiplicative approximations for Asymmetric Nash Welfare Maximization when agents have smooth valuations. |
| Researcher Affiliation | Academia | 1 Denison University 2 Elon University |
| Pseudocode | Yes | Algorithm 1 Multiplicative Algorithm for ICA, Algorithm 2 Weighted Bang-per-buck Algorithm (WBB) |
| Open Source Code | No | The paper does not provide any links to open-source code or statements about its availability. |
| Open Datasets | No | The paper is theoretical and does not use datasets for training. |
| Dataset Splits | No | The paper is theoretical and does not mention dataset splits for validation. |
| Hardware Specification | No | The paper is theoretical and does not mention any hardware specifications for running experiments. |
| Software Dependencies | No | The paper is theoretical and does not mention specific software dependencies with version numbers needed to replicate experiments. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with hyperparameters or training configurations. |