Research Repository

On the price of stability of some simple graph-based hedonic games

Kaklamanis, C and Kanellopoulos, P and Papaioannou, K and Patouchas, D (2021) 'On the price of stability of some simple graph-based hedonic games.' Theoretical Computer Science, 855. 1 - 15. ISSN 0304-3975

Hedonic games.pdf - Accepted Version
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (275kB) | Preview


We consider graph-based hedonic games such as simple symmetric fractional hedonic games and social distance games, where a group of utility maximizing players have hedonic preferences over the players' set, and wish to be partitioned into clusters so that they are grouped together with players they prefer. The players are nodes in a connected graph and their preferences are defined so that shorter graph distance implies higher preference. We are interested in Nash equilibria of such games, where no player has an incentive to unilaterally deviate to another cluster, and we focus on the notion of the price of stability. We present new and improved bounds on the price of stability for several graph classes, as well as for a slightly modified utility function.

Item Type: Article
Divisions: Faculty of Science and Health > Computer Science and Electronic Engineering, School of
Depositing User: Elements
Date Deposited: 23 Nov 2020 14:48
Last Modified: 13 Nov 2021 02:00

Actions (login required)

View Item View Item