Quantifying Core Stability Relaxations in Hedonic Games
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917862541623296 |
|---|---|
| author | Demeulemeester, Tom Peters, Jannik |
| author_facet | Demeulemeester, Tom Peters, Jannik |
| contents | We study relationships between different relaxed notions of core stability in hedonic games, which are a class of coalition formation games. Our unified approach applies to a newly introduced family of hedonic games, called $α$-hedonic games, which contains previously studied variants such as fractional and additively separable hedonic games. In particular, we derive an upper bound on the maximum factor with which a blocking coalition of a certain size can improve upon an outcome in which no deviating coalition of size at most $q$ exists. Counterintuitively, we show that larger blocking coalitions might sometimes have lower improvement factors. We discuss the tightness conditions of our bound, as well as its implications on the price of anarchy of core relaxations. Our general result has direct implications for several well-studied classes of hedonic games, allowing us to prove two open conjectures by Fanelli et al. (2021) for fractional hedonic games. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_01666 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Quantifying Core Stability Relaxations in Hedonic Games Demeulemeester, Tom Peters, Jannik Computer Science and Game Theory Discrete Mathematics Combinatorics We study relationships between different relaxed notions of core stability in hedonic games, which are a class of coalition formation games. Our unified approach applies to a newly introduced family of hedonic games, called $α$-hedonic games, which contains previously studied variants such as fractional and additively separable hedonic games. In particular, we derive an upper bound on the maximum factor with which a blocking coalition of a certain size can improve upon an outcome in which no deviating coalition of size at most $q$ exists. Counterintuitively, we show that larger blocking coalitions might sometimes have lower improvement factors. We discuss the tightness conditions of our bound, as well as its implications on the price of anarchy of core relaxations. Our general result has direct implications for several well-studied classes of hedonic games, allowing us to prove two open conjectures by Fanelli et al. (2021) for fractional hedonic games. |
| title | Quantifying Core Stability Relaxations in Hedonic Games |
| topic | Computer Science and Game Theory Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2412.01666 |