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..
Hedonic Coalition Formation in Networks
Authors: Martin Hoefer, Daniel Vaz, Lisa Wagner
AAAI 2015 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We analyze the effects of network-based visibility and structure on the convergence of coalition formation processes to stable states. Our main result is a tight characterization of the structures based on which dynamic coalition formation can stabilize quickly. Maybe surprisingly, polynomial-time convergence can be achieved if and only if coalition formation is based on complete or star graphs. Theorem 1 below shows that if every formation graph G G is a clique, then there are always short paths to stability , i.e., polynomial-time sequences of improvement steps to stable states. Theorem 2 proves the existence of short paths to stability if every formation graph is a star. In contrast, for every other graph structure G we provide in Theorem 3 an instance with n agents, G = {G}, m = Θ(n) possible coalitions and an initial state such that the unique sequence of improvement steps based on formation graph G has length 2Θ(n). |
| Researcher Affiliation | Academia | Martin Hoefer Max-Planck-Institut f ur Informatik Saarland University Saarbr ucken, Germany EMAIL Daniel Vaz Max-Planck-Institut f ur Informatik Saarland University Saarbr ucken, Germany EMAIL Lisa Wagner Dept. of Computer Science RWTH Aachen University Aachen, Germany EMAIL |
| Pseudocode | No | The paper does not contain any pseudocode or clearly labeled algorithm blocks. |
| Open Source Code | No | The paper does not provide any statements about open-source code being released or links to a code repository. |
| Open Datasets | No | This is a theoretical paper that does not involve empirical experiments with datasets. Therefore, no information on dataset availability is present. |
| Dataset Splits | No | This is a theoretical paper that does not involve empirical experiments with datasets. Therefore, no information on training/validation/test splits is present. |
| Hardware Specification | No | This is a theoretical paper that does not involve empirical experiments. Therefore, no hardware specifications are mentioned. |
| Software Dependencies | No | This is a theoretical paper that does not involve empirical experiments. Therefore, no software dependencies with version numbers are mentioned. |
| Experiment Setup | No | This is a theoretical paper that does not involve empirical experiments. Therefore, no experimental setup details such as hyperparameters or training settings are provided. |