On Lower Bounds for Maximin Share Guarantees
Authors: Halvard Hummel
IJCAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We prove that for any integer c > 0, there exists a number of agents nc such that an MMS allocation exists for any instance with n nc agents and at most n + c items, where nc 0.6597c c! for allocation of goods and nc 0.7838c c! for chores. Furthermore, we show that for n = 3 agents, all instances with n + 6 goods have an MMS allocation. Our proofs of Theorems 1 and 3 build on two new structural properties of ordered instances. |
| Researcher Affiliation | Academia | Halvard Hummel Norwegian University of Science and Technology halvard.hummel@ntnu.no |
| Pseudocode | No | The paper does not contain structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any statement or link regarding the availability of open-source code for the described methodology. |
| Open Datasets | No | This is a theoretical paper and does not involve experiments with datasets. |
| Dataset Splits | No | This is a theoretical paper and does not involve experiments with dataset splits. |
| Hardware Specification | No | This is a theoretical paper and does not mention any specific hardware used for experiments. |
| Software Dependencies | No | This is a theoretical paper and does not mention any specific software dependencies with version numbers. |
| Experiment Setup | No | This is a theoretical paper and does not describe any experimental setup details such as hyperparameters or training settings. |