Randomized and Deterministic Maximin-share Approximations for Fractionally Subadditive Valuations
Authors: Hannaneh Akrami, Kurt Mehlhorn, Masoud Seddighin, Golnoosh Shahkarami
NeurIPS 2023 | Conference PDF | Archive PDF | Plain Text | 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 hakrami@mpi-inf.mpg.de Kurt Mehlhorn Max Planck Institute for Informatics Universität des Saarlandes mehlhorn@mpi-inf.mpg.de Masoud Seddighin Tehran Institute for Advanced Studies m.seddighin@teias.institute Golnoosh Shahkarami Max Planck Institute for Informatics Graduiertenschule Informatik Universität des Saarlandes gshahkar@mpi-inf.mpg.de |
| 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. |