Improved Maximin Guarantees for Subadditive and Fractionally Subadditive Fair Allocation Problem
Authors: Masoud Seddighin, Saeed Seddighin5183-5190
AAAI 2022 | Conference PDF | Archive PDF | Plain Text | 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. |