Forming Probably Stable Communities with Limited Interactions
Authors: Ayumi Igarashi, Jakub Sliwinski, Yair Zick2053-2060
AAAI 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We analyze the relation between network structure, and one s capability to infer statistically stable (also known as PAC stable) player partitions from data. We show that when the interaction network is a forest, one can efficiently infer PAC stable coalition structures. Furthermore, when the underlying interaction graph is not a forest, efficient PAC stabilizability is no longer achievable. Thus, our results completely characterize when one can leverage the underlying graph structure in order to compute PAC stable outcomes for hedonic games. Finally, given an unknown underlying interaction network, we show that it is NP-hard to decide whether there exists a forest consistent with data samples from the network. |
| Researcher Affiliation | Academia | Ayumi Igarashi Kyushu University Fukuoka, Japan igarashi@agent.inf.kyushu-u.ac.jp Jakub Sliwinski ETH Zurich Zurich, Switzerland jsliwinski@ethz.ch Yair Zick National University of Singapore Singapore zick@comp.nus.edu.sg |
| Pseudocode | Yes | Algorithm 1 An algorithm finding a PAC stable outcome for forest-restricted games |
| Open Source Code | No | The paper does not provide any statement about releasing source code for the described methodology or a link to a code repository. |
| Open Datasets | No | The paper discusses 'samples drawn i.i.d. from a distribution D' for theoretical analysis but does not refer to a publicly available dataset used for training or empirical evaluation. |
| Dataset Splits | No | The paper does not provide specific details on training, validation, or test dataset splits. |
| Hardware Specification | No | The paper does not provide any specific details about the hardware used for computations or experiments. |
| Software Dependencies | No | The paper does not specify any software dependencies with version numbers (e.g., specific libraries, frameworks, or solvers). |
| Experiment Setup | No | The paper focuses on theoretical proofs and algorithm design, and thus does not provide specific experimental setup details such as hyperparameters, model initialization, or training configurations for empirical experiments. |