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].
On a Simple Hedonic Game with Graph-Restricted Communication
Authors: Vittorio Bilò, Laurent Gourvès, Jérôme Monnot
JAIR 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the existence and computational complexity of both Nash stable and core stable partitions. Then, we provide tight or asymptotically tight bounds on their efficiency, measured in terms of the price of anarchy and the price of stability, under two natural social functions, namely, the number of agents who are not in a singleton coalition, and the number of coalitions. We also derive refined bounds for games in which the social graph is claw-free. Finally, we investigate the complexity of computing socially optimal partitions, as well as extreme Nash stable ones. |
| Researcher Affiliation | Academia | VITTORIO BILÒ, University of Salento, Italy LAURENT GOURVÈS, Université Paris-Dauphine, Université PSL, CNRS, LAMSADE, France JÉRÔME MONNOT, Université Paris-Dauphine, Université PSL, CNRS, LAMSADE, France |
| Pseudocode | Yes | Algorithm 1 Greedy Core Input: Game (𝐺, F ) where 𝐺= (𝑉, 𝐸) is a graph. Output: A core stable partition 𝜋. 1: while 𝑉 do 2: take 𝑖 𝑉maximizing the degree 𝑑𝐺(𝑖) 3: 𝜋(𝑖) 𝑁𝐺[𝑖] *𝑁𝐺[𝑖] is the closed neighbourhood of 𝑖* 4: 𝐺 𝐺[𝑉\ 𝑁𝐺[𝑖]] 5: end while 6: return 𝜋 |
| Open Source Code | No | The paper does not contain any explicit statement about releasing source code or provide a link to a code repository. |
| Open Datasets | No | This paper is theoretical, analyzing a game model and its properties. It does not conduct experiments on datasets, thus no dataset access information is provided. |
| Dataset Splits | No | This paper is theoretical and does not involve empirical experiments requiring dataset splits. |
| Hardware Specification | No | The paper focuses on theoretical analysis, proofs, and algorithms, without describing any experimental setup that would require specific hardware. |
| Software Dependencies | No | The paper is theoretical and does not describe implementation details or experimental setups that would require listing specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe any empirical experiments or their setup, thus no hyperparameter values or training configurations are provided. |