Additively Separable Hedonic Games with Social Context
In hedonic games, coalitions are created as a result of the strategic interaction of independent players. In particular, in additively separable hedonic games, every player has valuations for all other ones, and the utility for belonging to a coalition is given by the sum of the valuations for all o...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-09-01
|
| Series: | Games |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2073-4336/12/3/71 |
| _version_ | 1797519217915854848 |
|---|---|
| author | Gianpiero Monaco Luca Moscardelli Yllka Velaj |
| author_facet | Gianpiero Monaco Luca Moscardelli Yllka Velaj |
| author_sort | Gianpiero Monaco |
| collection | DOAJ |
| description | In hedonic games, coalitions are created as a result of the strategic interaction of independent players. In particular, in additively separable hedonic games, every player has valuations for all other ones, and the utility for belonging to a coalition is given by the sum of the valuations for all other players belonging to it. So far, non-cooperative hedonic games have been considered in the literature only with respect to totally selfish players. Starting from the fundamental class of additively separable hedonic games, we define and study a new model in which, given a social graph, players also care about the happiness of their friends: we call this class of games <i>social context additively separable hedonic games (SCASHGs)</i>. We focus on the fundamental stability notion of Nash equilibrium, and study the existence, convergence and performance of stable outcomes (with respect to the classical notions of price of anarchy and price of stability) in SCASHGs. In particular, we show that SCASHGs are potential games, and therefore Nash equilibria always exist and can be reached after a sequence of Nash moves of the players. Finally, we provide tight or asymptotically tight bounds on the price of anarchy and the price of stability of SCASHGs. |
| first_indexed | 2024-03-10T07:39:51Z |
| format | Article |
| id | doaj.art-9f847c42bf1945a2a0b9018fd2981978 |
| institution | Directory Open Access Journal |
| issn | 2073-4336 |
| language | English |
| last_indexed | 2024-03-10T07:39:51Z |
| publishDate | 2021-09-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Games |
| spelling | doaj.art-9f847c42bf1945a2a0b9018fd29819782023-11-22T13:11:04ZengMDPI AGGames2073-43362021-09-011237110.3390/g12030071Additively Separable Hedonic Games with Social ContextGianpiero Monaco0Luca Moscardelli1Yllka Velaj2Department of Information Engineering, Computer Science and Mathematics, University of L’Aquila, 67100 L’Aquila, ItalyDepartment of Economic Studies, University of Chieti-Pescara, Viale Pindaro 42, 65125 Pescara, ItalyFaculty of Computer Science, University of Vienna, 1090 Vienna, AustriaIn hedonic games, coalitions are created as a result of the strategic interaction of independent players. In particular, in additively separable hedonic games, every player has valuations for all other ones, and the utility for belonging to a coalition is given by the sum of the valuations for all other players belonging to it. So far, non-cooperative hedonic games have been considered in the literature only with respect to totally selfish players. Starting from the fundamental class of additively separable hedonic games, we define and study a new model in which, given a social graph, players also care about the happiness of their friends: we call this class of games <i>social context additively separable hedonic games (SCASHGs)</i>. We focus on the fundamental stability notion of Nash equilibrium, and study the existence, convergence and performance of stable outcomes (with respect to the classical notions of price of anarchy and price of stability) in SCASHGs. In particular, we show that SCASHGs are potential games, and therefore Nash equilibria always exist and can be reached after a sequence of Nash moves of the players. Finally, we provide tight or asymptotically tight bounds on the price of anarchy and the price of stability of SCASHGs.https://www.mdpi.com/2073-4336/12/3/71coalition formationhedonic gamesnash equilibriumprice of anarchyprice of stabilitysocial context |
| spellingShingle | Gianpiero Monaco Luca Moscardelli Yllka Velaj Additively Separable Hedonic Games with Social Context Games coalition formation hedonic games nash equilibrium price of anarchy price of stability social context |
| title | Additively Separable Hedonic Games with Social Context |
| title_full | Additively Separable Hedonic Games with Social Context |
| title_fullStr | Additively Separable Hedonic Games with Social Context |
| title_full_unstemmed | Additively Separable Hedonic Games with Social Context |
| title_short | Additively Separable Hedonic Games with Social Context |
| title_sort | additively separable hedonic games with social context |
| topic | coalition formation hedonic games nash equilibrium price of anarchy price of stability social context |
| url | https://www.mdpi.com/2073-4336/12/3/71 |
| work_keys_str_mv | AT gianpieromonaco additivelyseparablehedonicgameswithsocialcontext AT lucamoscardelli additivelyseparablehedonicgameswithsocialcontext AT yllkavelaj additivelyseparablehedonicgameswithsocialcontext |