Individually Stable Dynamics in Coalition Formation over Graphs
Authors: Angelo Fanelli, Laurent Gourvès, Ayumi Igarashi, Luca Moscardelli
AAAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We investigate the convergence of dynamics towards individually stable outcomes under the following perspective: what are the most general classes of preferences and graph topologies guaranteeing convergence? To this aim, on the one hand, we cover a hierarchy of preferences, ranging from the most general to a subcase of additively separable preferences, including individually rational and monotone cases. On the other hand, given that convergence may fail in graphs admitting a cycle even in our most restrictive preference class, we analyze acyclic graph topologies such as trees, paths, and stars. Our results are summarized in Table 1. The indicates that the dynamics are not guaranteed to converge, while indicates that the dynamics under individual stability notion converge. The paper contains multiple theorems and proof sketches (e.g., "Theorem 3.2. Under monotone preferences, the IS dynamics always converge on paths. Proof sketch.", "Theorem 5.2. In a graph hedonic game with LAS preferences over a tree the IS dynamics always converge. Proof sketch."), and analyzes algorithmic convergence properties through theoretical examples rather than empirical data analysis. |
| Researcher Affiliation | Academia | Angelo Fanelli1, Laurent Gourv es1, Ayumi Igarashi2, Luca Moscardelli3 1Universit e Paris-Dauphine, Universit e PSL, CNRS, LAMSADE, 75016, Paris, France, 2The University of Tokyo, Japan, 3University of Chieti-Pescara, Italy EMAIL, EMAIL, EMAIL, EMAIL |
| Pseudocode | Yes | Algorithm 1: IS dynamics Algorithm 2: IS dynamics for trees with labeling |
| Open Source Code | No | The paper does not contain any explicit statements about releasing source code, nor does it provide links to a code repository or mention code in supplementary materials. The work is theoretical. |
| Open Datasets | No | The paper is theoretical and focuses on graph hedonic games and their convergence properties, rather than using or analyzing specific datasets. Therefore, no datasets are mentioned as publicly available or otherwise. |
| Dataset Splits | No | The paper does not use any datasets for empirical evaluation. It is a theoretical work, so there is no mention of dataset splits. |
| Hardware Specification | No | The paper focuses on theoretical analysis of game dynamics and does not describe any experimental setup or hardware used for computation. |
| Software Dependencies | No | The paper presents theoretical work on game dynamics and does not describe any implementation details or software dependencies with version numbers. |
| Experiment Setup | No | The paper is purely theoretical, focusing on the convergence properties of game dynamics. It does not describe any experimental setup, hyperparameters, or training configurations. |