Existence, Computation and Efficiency of Nash Stable Outcomes in Hedonic Skill Games
Authors: Laurent Gourvès, Gianpiero Monaco
JAIR 2025 | Venue PDF | Archive PDF | Plain Text | 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. |