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 [1].
Randomized and Deterministic Maximin-share Approximations for Fractionally Subadditive Valuations
Authors: Hannaneh Akrami, Kurt Mehlhorn, Masoud Seddighin, Golnoosh Shahkarami
NeurIPS 2023 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our results involve both deterministic and randomized allocations. On the deterministic side, we improve the best approximation guarantee for fractionally subadditive valuations to 3/13 = 0.230769. We develop new ideas on allocating large items in our allocation algorithm which might be of independent interest. Furthermore, we investigate randomized algorithms and the Best-of-both-worlds fairness guarantees. We propose a randomized allocation that is 1/4-MMS ex-ante and 1/8-MMS ex-post for XOS valuations. Moreover, we prove an upper bound of 3/4 on the ex-ante guarantee for this class of valuations.Both of our results are constructive; however, their running times are not polynomially bounded. |
| Researcher Affiliation | Academia | Hannaneh Akrami Max Planck Institute for Informatics Graduiertenschule Informatik Universität des Saarlandes EMAIL Kurt Mehlhorn Max Planck Institute for Informatics Universität des Saarlandes EMAIL Masoud Seddighin Tehran Institute for Advanced Studies EMAIL Golnoosh Shahkarami Max Planck Institute for Informatics Graduiertenschule Informatik Universität des Saarlandes EMAIL |
| Pseudocode | No | The paper describes algorithms through numbered steps within paragraphs, such as in Section 4 "we use the following algorithm: 1. While there exists an item bj with value at least 1/4 to an agent i, allocate bj to agent i and remove i and bj respectively from N and M. 2. For the remaining agents [n] and items proceed as follows... 3. Convert F into a randomized allocation using Lemma 4.2." However, these are not presented as formal "Pseudocode" or "Algorithm" blocks. |
| Open Source Code | No | No statement regarding the release of source code or links to a code repository are provided in the paper. |
| Open Datasets | No | The paper is theoretical and does not involve empirical studies with datasets. Therefore, no information about publicly available training datasets is provided. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical studies with datasets. Therefore, no information about training, validation, or test data splits is provided. |
| Hardware Specification | No | The paper is theoretical and does not conduct experiments, thus no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not describe any specific software dependencies with version numbers for implementation. |
| Experiment Setup | No | The paper is theoretical and does not describe empirical experiments or their setup, including hyperparameters or system-level training settings. |