Finding and Recognizing Popular Coalition Structures
Authors: Felix Brandt, Martin Bullinger
JAIR 2022 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we study popularity, strong popularity, and mixed popularity... We study the computational complexity of popular, strongly popular, and mixed popular partitions in a variety of hedonic coalition formation settings... Generalizing earlier results by Kavitha et al. (2011), we show how mixed popular partitions in roommate games can be computed in polynomial time via linear programming and a separation oracle... We provide the first negative computational results for mixed popular partitions and strongly popular partitions by showing that finding these partitions in flatmate games is NP-hard. Moreover, it turns out, that verifying whether a given partition is popular, strongly popular, or mixed popular in flatmate games is co NP-complete. |
| Researcher Affiliation | Academia | Felix Brandt EMAIL Martin Bullinger EMAIL Technical University of Munich, Boltzmannstr 3, 85748 Munich, Germany |
| Pseudocode | No | The paper discusses various algorithms and reductions (e.g., 'LP-based algorithm', 'Ellipsoid method', 'hardness reductions') but does not present any structured pseudocode or algorithm blocks within its content. |
| Open Source Code | No | The paper does not contain any explicit statements about releasing source code, providing links to code repositories, or including code in supplementary materials for the described methodologies. |
| Open Datasets | No | The paper focuses on theoretical computational complexity results in game theory settings (hedonic games, roommate games) and does not involve experimental evaluation on datasets. Therefore, it does not refer to any open or publicly available datasets. |
| Dataset Splits | No | As a theoretical paper, no empirical experiments are conducted using datasets. Consequently, there is no mention of training/test/validation dataset splits. |
| Hardware Specification | No | The paper is theoretical, analyzing computational complexity and algorithmic properties. It does not describe any experimental setup or report on performance tests that would require specific hardware specifications. |
| Software Dependencies | No | The paper is theoretical, discussing algorithms and complexity, but does not provide specific details or version numbers for software dependencies or libraries used for implementation. |
| Experiment Setup | No | The paper is theoretical in nature, presenting proofs and complexity analysis rather than empirical experiments. Therefore, no experimental setup details, such as hyperparameters or system-level training settings, are provided. |