Local core stability in simple symmetric fractional hedonic games

We initiate the study of local core stability in simple symmetric fractional hedonic games. The input is an unweighted undirected graph G where vertices are the agents and edges model social connection (i.e., acquaintance) among agents. We assume that if there is an edge between two agents then they value 1 each other otherwise they value 0 each other, i.e., we consider the simple setting where an agent values 1 all and only her acquaintances. A coalition structure is a partition of the agents into coalitions where the utility of an agent is equal to the number of agents inside her coalition that are valued 1 divided by the size of the coalition. A coalition structure is in the core if no subset of agents can strictly improve all their utility by forming a new coalition together. In [ 7] it is shown that simple symmetric fractional hedonic games may not admit a core stable coalition structure. However, the fact that the core is required to be resilient to deviations by any groups of agents could be sometimes unrealistic, especially in systems with large populations. In fact, it may be difficult that agents are able to coordinate each other in order to understand whether there is the possibility of deviating together. Motivated by the above considerations, we define a relaxation of the core, called local core. A coalition structure is in the local core if there is no subset of agents which (1) induces a clique in the graph G and (2) such that all agents can improve their utility by forming a new coalition together. We first show that any local core dynamics converges, which implies that a local core stable coalition structure always exists. We then study its performance with respect to the classic utilitarian social welfare and provide tight and almost tight bounds on the local core price of anarchy and stability, respectively.