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 Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Existence, Computation and Efficiency of Nash Stable Outcomes in Hedonic Skill Games
Authors: Laurent Gourvรจs, Gianpiero Monaco
JAIR 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In the weighted tasks setting, we show that deciding whether an instance of the game admits a Nash stable outcome is NP-complete. We then characterize the instances admitting a Nash stable outcome. This characterization relies on the fact that every agent holds (resp., every task requires) either a single skill or more than one skill. For these instances, the complexity of computing a Nash stable outcome is determined, together with the possibility that natural dynamics converge to a Nash stable outcome from any initial configuration. Our study is completed with a thorough analysis of the price of anarchy of instances always admitting a Nash stable outcome. |
| Researcher Affiliation | Academia | Laurent Gourv es EMAIL Universit e Paris-Dauphine, Universit e PSL, CNRS, LAMSADE, 75016, Paris, France Gianpiero Monaco EMAIL University of Chieti-Pescara, Italy |
| Pseudocode | Yes | Algorithm 1 Better response dynamics (BRD) Input: an initial state ฯ0 whose corresponding coalition structure contains at most q coalitions |
| Open Source Code | No | The text does not contain any explicit statement about open-source code release, a link to a code repository, or mention of code in supplementary materials for the methodology described in this paper. |
| Open Datasets | No | This paper is theoretical and does not conduct experiments using any specific dataset. The examples provided (e.g., Example 1, Example 2) are illustrative scenarios rather than open datasets for experimentation. |
| Dataset Splits | No | The paper is theoretical and does not involve experimental evaluation on datasets, thus no dataset splits are discussed or provided. |
| Hardware Specification | No | The paper is theoretical and focuses on algorithmic complexity and properties of games. It does not describe any experiments that would require specific hardware for execution. |
| Software Dependencies | No | The paper presents theoretical results and algorithms conceptually (e.g., Algorithm 1 pseudocode) but does not describe any implementation or experiments, and therefore does not list software dependencies with specific version numbers. |
| Experiment Setup | No | The paper is theoretical and does not include any experimental results or evaluations. Consequently, there is no experimental setup, hyperparameters, or training configurations described. |