Complexity of Probabilistic Inference in Random Dichotomous Hedonic Games
Authors: Saar Cohen, Noa Agmon
AAAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We initiate the research on the computational complexity of computing the probability that coalitions and partitions are optimal or stable. While some cases admit efficient algorithms (e.g., agents approve only few coalitions), they become computationally hard (#P-hard) in their complementary scenario. We then investigate the distribution of coalitions in perfect partitions and their performance in majority games, where an agent approves coalitions in which the agent is friends with the majority of its members. When friendships independently form with a constant probability, we prove that the number of coalitions of size 3 converges in distribution to a Poisson random variable. |
| Researcher Affiliation | Academia | Saar Cohen, Noa Agmon Department of Computer Science, Bar-Ilan University, Israel saar30@gmail.com, agmon@cs.biu.ac.il |
| Pseudocode | Yes | Algorithm 1: Computing L(n, {qm}m [M]) |
| Open Source Code | No | The paper references supplementary material at 'https://u.cs.biu.ac.il/ agmon/ Cohen AAAI23-Sup.pdf' but does not explicitly state that this material contains the source code for the methodology described in the paper. It is a theoretical paper and does not mention any software implementation details for its proofs. |
| Open Datasets | No | The paper is theoretical and does not use or reference any datasets for training or empirical evaluation. The mention of 'random graphs' refers to theoretical constructs within the paper's mathematical models, not empirical datasets. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical data splits (training, validation, test). Therefore, no information about validation splits is provided. |
| Hardware Specification | No | The paper focuses on theoretical computational complexity and does not describe any specific hardware used for its research or computations. |
| Software Dependencies | No | The paper is theoretical and does not mention any specific software names with version numbers or other ancillary software details needed for replication. |
| Experiment Setup | No | The paper is theoretical and does not involve empirical experiments, thus no experimental setup details, hyperparameters, or training configurations are provided. |