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].
Improved Maximin Guarantees for Subadditive and Fractionally Subadditive Fair Allocation Problem
Authors: Masoud Seddighin, Saeed Seddighin5183-5190
AAAI 2022 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this work, we study the maximin share fairness notion for allocation of indivisible goods in the subadditive and fractionally subadditive settings. While previous work refutes the possibility of obtaining an allocation which is better than 1/2-MMS, the only positive result for the subadditive setting states that when the number of items is equal to m, there always exists an Ω(1/ log m)-MMS allocation. Since the number of items may be larger than the number of agents (n), such a bound can only imply a weak bound of Ω( 1 n log n)-MMS allocation in general. In this work, we improve this gap exponentially to an Ω( 1 log n log log n)-MMS guarantee. In addition to this, we prove that when the valuation functions are fractionally subadditive, a 1/4.6-MMS allocation is guaranteed to exist. This also improves upon the previous bound of 1/5-MMS guarantee for the fractionally subadditive setting. |
| Researcher Affiliation | Academia | Masoud Seddighin1, Saeed Seddighin2 1School of Computer Science, Institute for Research in Fundamental Sciences (IPM), P.O.Box: 19395 5746, Tehran, Iran. 2Toyota Technological Institute at Chicago, Illinois, US. |
| Pseudocode | Yes | Algorithm 1: Finding a multiallocation. Algorithm 2: Random Allocation Algorithm. |
| Open Source Code | No | The paper does not provide any concrete access to source code for the methodology described. It does not include a link to a repository or an explicit statement about code release. |
| Open Datasets | No | This paper is theoretical and does not conduct experiments with datasets. |
| Dataset Splits | No | This paper is theoretical and does not conduct experiments with datasets, so there are no data splits for validation. |
| Hardware Specification | No | This paper is theoretical and does not conduct experiments, therefore, no hardware specifications are provided. |
| Software Dependencies | No | This paper is theoretical and does not conduct experiments; thus, no software dependencies with version numbers are specified. |
| Experiment Setup | No | This paper is theoretical and does not conduct experiments, therefore, no experimental setup details like hyperparameters or training configurations are provided. |