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; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1]
Maximin Share Guarantees for Few Agents with Subadditive Valuations
Authors: George Christodoulou, Vasilis Christoforidis, Symeon Mastrakoulis, Alkmini Sgouritsa
IJCAI 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the problem of fairly allocating a set of indivisible items among a set of agents. We consider the notion of (approximate) maximin share (MMS) and we provide an improved lower bound of 1/2 (which is tight) for the case of subadditive valuations when the number of agents is at most four. We also provide a tight lower bound for the case of multiple agents, when they are equipped with one of two possible types of valuations. Moreover, we propose a new model that extends previously studied models in the area of fair division, which will hopefully give rise to further research. We demonstrate the usefulness of this model by employing it as a technical tool to derive our main result, and we provide a thorough analysis for this model for the case of three agents. Finally, we provide an improved impossibility result for the case of three submodular agents. |
| Researcher Affiliation | Academia | George Christodoulou1,2 , Vasilis Christoforidis1,2 , Symeon Mastrakoulis1,2 and Alkmini Sgouritsa1,3 1 Archimedes, Athena Research Center 2 Aristotle University of Thessaloniki 3 Athens University of Economics and Business EMAIL, EMAIL, |
| Pseudocode | No | The paper describes mathematical concepts, definitions, observations, lemmas, and theorems. It does not include any sections or figures explicitly labeled as 'Pseudocode' or 'Algorithm', nor does it present any structured code-like procedures. |
| Open Source Code | No | The paper does not contain any explicit statement about releasing code, nor does it provide any links to source code repositories for the methodology described. |
| Open Datasets | No | The paper is theoretical and focuses on mathematical proofs and the existence of allocations for indivisible items. It does not mention or use any specific datasets, public or otherwise. |
| Dataset Splits | No | The paper is theoretical and does not involve experiments on datasets, therefore no dataset split information is provided. |
| Hardware Specification | No | The paper describes theoretical results and mathematical proofs, and does not conduct experiments that would require specific hardware. Therefore, no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and focuses on mathematical proofs, not on practical implementations or experiments. Consequently, there are no mentions of specific software dependencies or their version numbers. |
| Experiment Setup | No | The paper presents theoretical research, including lemmas, theorems, and proofs related to fair allocation problems. It does not describe any experimental setup, hyperparameters, or training configurations. |