Nash Stable Outcomes in Fractional Hedonic Games: Existence, Efficiency and Computation
Authors: Vittorio Bilò, Angelo Fanelli, Michele Flammini, Gianpiero Monaco, Luca Moscardelli
JAIR 2018 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We provide existence, efficiency and complexity results for games played on both general and specific graph topologies. As to the efficiency results, we mainly study the quality of the best Nash stable outcome and refer to the ratio between the social welfare of an optimal coalition structure and the one of such an equilibrium as to the price of stability. ... We provide upper and lower bounds on the price of stability for different topologies, both in case of weighted and unweighted edges. ... As to the computation of Nash stable coalition structures, we first show that the class of fractional hedonic games does not possess the finite improvement path property... Moreover, we prove that the problems of computing a best Nash stable coalition structure and an optimal one (not necessarily stable) are NP-hard (Theorem 14). On the positive side, we design a polynomial time algorithm which returns a stable outcome approximating the social welfare of the optimal coalition structure by a factor of 18/7 (Theorem 15) for unweighted triangle-free graphs and by a factor of 2 for unweighted bipartite graphs (Theorem 16). For unweighted trees, we design a polynomial time algorithm computing an optimal coalition structure that is also Nash stable (Theorem 17). |
| Researcher Affiliation | Academia | Vittorio Bil o EMAIL Department of Mathematics and Physics University of Salento Lecce, Italy Angelo Fanelli EMAIL CNRS, (UMR-6211) Caen, France Michele Flammini EMAIL GSSI Institute & Department of Information Engineering Computer Science and Mathematics University of L Aquila L Aquila, Italy Gianpiero Monaco EMAIL Department of Information Engineering Computer Science and Mathematics University of L Aquila L Aquila, Italy Luca Moscardelli EMAIL Department of Economic Studies University of Chieti-Pescara Pescara, Italy |
| Pseudocode | Yes | Algorithm 1 1: C = (C1, . . . , Cn) with Ci = for each i [n] 2: Compute a maximum matching M for G ... (lines of algorithm) 23: return e C Algorithm 2 Social optimum 1: procedure Opt CS(G = (N, E)) // G is a tree 2: Fix a root s N ... (lines of algorithm) 15: end procedure |
| Open Source Code | No | The paper does not contain any explicit statement about releasing source code for the described methodology, nor does it provide a link to a code repository. |
| Open Datasets | No | The paper does not use or refer to any specific publicly available datasets. It focuses on theoretical analysis of 'fractional hedonic games' played on abstract graph topologies (e.g., 'unweighted triangle-free graphs', 'unweighted bipartite graphs', 'unweighted trees'). |
| Dataset Splits | No | The paper does not involve experiments on datasets, therefore, there is no mention of dataset splits for training, validation, or testing. |
| Hardware Specification | No | This paper is theoretical in nature, focusing on mathematical proofs, algorithmic design, and complexity analysis. It does not describe any experimental setup or specific hardware used for computations. |
| Software Dependencies | No | This paper is theoretical, analyzing algorithmic properties and complexity. It does not mention any specific software libraries, tools, or version numbers that would be required to reproduce experimental results. |
| Experiment Setup | No | This paper is theoretical, presenting mathematical analysis, proofs, and algorithms. It does not describe any empirical experiments, and therefore, no experimental setup details, hyperparameters, or training configurations are provided. |