2026-08-06T04:24:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18575 2024-03-06T11:02:10Z ddc:004 open_access

Relaxed Core Stability for Hedonic Games with Size-Dependent Utilities Demeulemeester, Tom Peters, Jannik hedonic games core stability algorithmic game theory computational social choice We study relationships between different relaxed notions of core stability in hedonic games. In particular, we study (i) q-size core stable outcomes in which no deviating coalition of size at most q exists and (ii) k-improvement core stable outcomes in which no coalition can improve by a factor of more than k. For a large class of hedonic games, including fractional and additively separable hedonic games, we derive upper bounds on the maximum factor by which a coalition of a certain size can improve in a q-size core stable outcome. We further provide asymptotically tight lower bounds for a large class of hedonic games. Finally, our bounds allow us to confirm two conjectures by Fanelli et al. [Angelo Fanelli et al., 2021][IJCAI'21] for symmetric fractional hedonic games (S-FHGs): (i) every q-size core stable outcome in an S-FHG is also q/(q-1)-improvement core stable and (ii) the price of anarchy of q-size stability in S-FHGs is precisely 2q/q-1. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tom Demeulemeester and Jannik Peters 2023 Is Part Of LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2023.41 urn:nbn:de:0030-drops-185759 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.41 eng https://creativecommons.org/licenses/by/4.0/legalcode