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].
Settling the Complexity of Popularity in Additively Separable and Fractional Hedonic Games
Authors: Martin Bullinger, Matan Gilboa
IJCAI 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We go further and settle the complexity of the existence problem concerning popularity in additively separable and fractional hedonic games by showing that it is Δp 2-complete in both cases. We are thus the first work that proves a completeness result of popularity for the second level of the polynomial hierarchy. |
| Researcher Affiliation | Academia | Martin Bullinger , Matan Gilboa University of Oxford EMAIL, EMAIL |
| Pseudocode | No | The paper describes reductions and proofs of complexity, but does not include any structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper refers to a technical report for detailed proofs but does not include any statement about releasing source code or provide a link to a code repository for the methodology described. |
| Open Datasets | No | This paper is theoretical in nature, focusing on complexity analysis of hedonic games, and therefore does not use or make available any datasets. |
| Dataset Splits | No | This paper is theoretical and does not conduct experiments involving datasets, thus there is no information regarding dataset splits. |
| Hardware Specification | No | This paper focuses on theoretical complexity results and does not describe any experiments that would require specific hardware specifications. |
| Software Dependencies | No | This paper is theoretical and does not detail any experimental implementation, thus no specific software dependencies with version numbers are provided. |
| Experiment Setup | No | This paper is theoretical and does not conduct experiments, therefore no experimental setup details such as hyperparameters or training configurations are provided. |