Hedonic Coalition Formation in Networks
Authors: Martin Hoefer, Daniel Vaz, Lisa Wagner
AAAI 2015 | Conference PDF | Archive PDF | Plain Text | 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 mhoefer@mpi-inf.mpg.de Daniel Vaz Max-Planck-Institut f ur Informatik Saarland University Saarbr ucken, Germany ramosvaz@mpi-inf.mpg.de Lisa Wagner Dept. of Computer Science RWTH Aachen University Aachen, Germany lwagner@cs.rwth-aachen.de |
| 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. |