Stable outcomes in modified fractional hedonic games

Abstract

In coalition formation games self-organized coalitions are created as a result of the strategic interactions of independent agents. In this paper we assume that for each couple of agents (i, j), weight $w_{i,j}=w_{j,i}$ reflects how much agents i and j benefit from belonging to the same coalition. We consider the (symmetric) modified fractional hedonic game, that is a coalition formation game in which agents’ utilities are such that the total benefit of agent i belonging to a coalition (given by the sum of $w_{i,j}$ over all other agents j belonging to the same coalition) is averaged over all the other members of that coalition, i.e., excluding herself. Modified fractional hedonic games constitute a class of succinctly representable hedonic games. We are interested in the scenario in which agents, individually or jointly, choose to form a new coalition or to join an existing one, until a stable outcome is reached. To this aim, we consider common stability notions leading to strong Nash stable outcomes, Nash stable outcomes or core stable outcomes: we study their existence, complexity and performance, both in the case of general weights and in the case of 0–1 weights. In particular, we completely characterize the existence of the considered stable outcomes and show many tight or asymptotically tight results on the performance of these natural stable outcomes for modified fractional hedonic games, also highlighting the differences with respect to the model of fractional hedonic games, in which the total benefit of an agent in a coalition is averaged over all members of that coalition, i.e., including herself.

1 Introduction

Teamwork, clustering and coalition formations have been important and widely investigated issues in multi-agent systems. In fact, in many economic, social and political situations, individuals carry out activities in groups rather than by themselves. In these scenarios, it is of crucial importance to consider the satisfaction of the members of the groups.

Hedonic games, introduced in [18], model the formation of coalitions of agents in multi-agent systems (see [6] for a nice survey on the topic). They are games in which agents have preferences over the set of all possible agent coalitions, and the utility of an agent depends on the composition of the coalition she belongs to. While the standard model of hedonic games assumes that agents’ preferences over coalitions are ordinal, there are several prominent classes of hedonic games where agents assign cardinal utilities to coalitions. Additively separable hedonic games constitute a natural and succinctly representable class of hedonic games. In this setting, each agent has a value for any other agent, and the utility of a coalition to a particular agent is simply the sum of the values she assigns to the members of her coalition. Additive separability satisfies a number of desirable axiomatic properties [3] and is the non-transferable utility generalization of graph games studied in [23]. Fractional hedonic games, introduced in [2], are similar to additively separable ones, with the difference that the utility of each agent is divided by the size of her coalition. Arguably, it is more natural to compute the average value of all other members of the coalition [25]. Various solution concepts, such as the core, the strict core, and various kinds of individual stability like Nash Equilibrium have been proposed to analyze these games (see the Sect. 1.1).

In this paper we deal with symmetric modified fractional hedonic games (MFHGs). MFHGs have been formally introduced in [25] and afterward studied in [31].

Fig. 1

a Example of a weighted undirected graph G that models a hedonic game. Notice that the grand coalition (i.e., the outcome in which all agents belong to the same coalition) is a Nash stable outcome (being neither core stable nor strong Nash stable because, for instance, agents 2 and 5 can improve their utility by jointly forming a new coalition). b A strong Nash stable outcome. c A core stable outcome (not being Nash stable because agent 1 can improve her utility by joining the coalition of agents 3 and 4)

An instance of (symmetric) MFHG (similarly to instances of other classes of hedonic games such as fractional hedonic games and additively separable hedonic games) can be effectively modeled by means of a weighted undirected graph $G=(N,E,w)$, where nodes in N represent the agents, and the weight $w(\{i,j\})$ of an edge $\{i,j\} \in E$ represents how much agents i and j benefit from belonging to the same coalition. In particular, if there is no edge between two nodes i and j it means that agents i and j have a benefit of zero from belonging to the same coalition, that is, if $\{i,j\} \notin E$ then $w(\{i,j\})=0$. See Fig. 1a for an example with five agents. This graphical representation provides an interesting angle on network clustering [2, 16, 38, 39]. The advantages of a graphical representation can be twofold: (a) First of all, from a descriptive point of view, there is a natural connection between some structural properties of the graph and interesting classes of hedonic games. To this respect, consider bipartite graphs: they naturally induce a hedonic game modeling a basic economic scenario in which each agent can be considered as a buyer or a seller; this scenario, referred to in [2, 15, 16] as Bakers and Millers, is such that individuals of the same type are competitors and those of different types can be seen as suppliers and purveyors in a market. Both types of players can freely choose the neighborhood where to set up their enterprises. Millers want to be situated in a neighborhood with as many purchasing bakers (relative to competing millers) as possible, so as to keep prices high for the wheat they produce. On the other hand, bakers aim at keeping the ratio of the number of millers to the number of bakers as high as possible, so as to keep the price of wheat down and that of bread up. It can be easily checked that this setting can be modeled by means of bipartite graphs in which in one side there are the nodes corresponding to Baker agents and in the other side the nodes corresponding to Miller agents. (b) Moreover, from a more practical and technical point of view, graphs techniques and result (e.g., the result of Theorem 2 derived in [30]) can be smartly exploited in order to obtain results for hedonic games.

We notice that a previous paper [37] considers a setting which is very close to MFHGs, however under different perspective. MFHGs model natural behavioral dynamics in social environments. Even when defined on undirected and unweighted graphs, they suitably model the above described basic economic scenario of Bakers and Millers. Moreover, MFHGs can model other realistic scenarios: (i) politicians may want to be in a party that maximizes the fraction of like-minded members; (ii) people may want to be with an as large as possible fraction of people of the same ethnic or social group.

In MFHGs, slightly differently than in fractional hedonic games, the utility of an agent i is given by the sum of all weights towards the other agents in the coalition she belongs to, divided by the size of the coalition minus 1, that indeed corresponds to the average value of all other members than i of the coalition. Despite this small difference, we will show that natural stable outcomes in MFHGs perform differently than in fractional hedonic games. Specifically, we adopt Nash stable, strong Nash stable and core stable outcomes. Informally, an outcome is Nash stable (or it is a Nash equilibrium) if no agent can improve her utility by unilaterally changing her own coalition; the grand coalition (i.e., the outcome in which all agents belong to the same coalition) is a Nash stable outcome for the example depicted in Fig. 1a. Moreover, an outcome is strong Nash stable if no subset of agents can cooperatively deviate in a way that benefits all of them; in Fig. 1b is shown a strong Nash stable outcome for the example instance in Fig. 1a. Finally, an outcome is in the core or is core stable, if there is no subset of agents T, whose members all prefer T with respect to the coalition in the outcome; in Fig. 1c is shown a core stable outcome for the example instance in Fig. 1a. We point out that strong Nash stable outcomes are resilient to a group of agents that can join any coalition and therefore represent a powerful solution concept. However, there are settings in which (one or more) agents are not allowed for to join an existent coalition without asking for permission from its members: in these settings the notion of core, where in a non-stable outcome a subset of T agents can only form a new coalition itself and cannot join an already non-empty coalition, appears to be more realistic.

Our aim is to study the existence, performance and computability of natural stable outcomes for MFHGs. In particular, we evaluate the performance of Nash, strong Nash, and core stable outcomes for MFHGs, by means of the widely used notions of price of anarchy (resp. strong price of anarchy and core price of anarchy), and price of stability (resp. strong price of stability and core price of stability), which are defined as the ratio between the social optimal value and the social value of the worst (resp. best) stable outcome.

1.1 Related work

Hedonic aspects in coalition formation problems have been first considered by Dréze and Greenberg [24], who analyzed them under a cooperative perspective. Bogomolnaia and Jackson [18] and Banerjee et al. [12] then defined hedonic games in their present form as a simple but very versatile model of coalition formation. Ballester [9] considers computational complexity issues related to hedonic games, and show that the core and the Nash stable outcomes have corresponding NP-complete decision problems for a variety of situations. Feldman et al. [26] investigate some interesting subclasses of hedonic games from a non-cooperative point of view, by characterizing Nash equilibria and providing upper and lower bounds on both the price of stability and the price of anarchy. It is worth noticing that in their model they do not have an underlying graph, but agents lie in a metric space with a distance function modeling their distance or similarity. Peters [38] considers graphical hedonic games where agents form the vertices of an undirected graph, and each agent’s utility function only depends on the actions taken by her neighbors (with general value functions). It is proved that, when agent graphs have bounded treewidth and bounded degrees, the problem of finding stable solutions, i.e., Nash equilibria, can be efficiently solved. Peters et al. [39] consider several classes of hedonic games and identify simple conditions on expressivity that are sufficient for the problem of checking whether a given game admits a stable outcome to be computationally hard.

The optimization problem of partitioning agents into coalitions so as to maximize the social welfare is a major research challenge in AI and it has been extensively investigated in the field of multi-agent systems under the name of Coalition Structure Generation (CSG). Several works characterize the computational complexity of finding optimal solutions, providing efficient algorithms, hardness results and suitable approximations under different assumptions or variants of the problem [5, 7, 8, 13, 21,22,23, 35, 40, 41, 43, 45, 46, 48, 49]. A survey of the different approaches in this setting is also available [42].

Table 1 Related results for additively separable hedonic games (ASHG)

Concerning additively separable hedonic games, Bogomolnaia and Jackson [18] first noticed that Nash stable outcomes are not guaranteed to exist for games played on directed graphs, and Ballester [9] and Sung and Dimitrov [47] show that the problem of checking whether an instance admit a Nash stable outcome is NP-complete and NP-complete in the strong sense, respectively. Olsen [36] proves that the problem of deciding whether a non-trivial Nash stable coalition exists in additively separable hedonic games with non-negative and symmetric preferences is NP-complete. Aziz et al. [3] prove that checking the existence of a core stable outcome is NP-hard even for undirected graphs. Since a strong Nash stable outcome is also core stable, this last result implies that strong Nash stable outcomes are not guaranteed to exist for symmetric valuations. However, the existence of a Nash stable outcome is guaranteed by potential function argument [18], also showing that the price of stability is equal to 1. As far as concern the performance of Nash stable outcomes in symmetric separable hedonic games, it is easy to check that the price of anarchy is unbounded [17] and that the price of stability is 1 since an optimal outcome is always Nash Stable (it can be easily proved by using the potential function). We notice that, if the weights are all positive, the grand coalition is optimum and strong stable and thus also core and Nash stable, even for games played on directed graphs. Finally, in [32], the authors consider additively separable hedonic games with social context where agents also care about the happiness of their friends. They provide a potential function for these games implying the existence and convergence to Nash equilibria, and prove tight or asymptotically tight bounds on the price of anarchy and the price of stability. Table 1 summarizes the main results about additively separable hedonic games.

Fractional hedonic games have been introduced by Aziz et al. [2] (see also [1]). They prove that the core can be empty for games played on general directed graphs and that it is not empty for games played on some classes of undirected and unweighted graphs (that is, graphs with degree at most 2, multipartite complete graphs, bipartite graphs admitting a perfect matching and regular bipartite graphs). Brandl et al. [19] study the existence of core and individual stability in fractional hedonic games and the computational complexity of deciding whether a core and individual stable partition exist in a given fractional hedonic game. In particular, they show that core stable and Nash stable outcomes may not exist even for unweighted undirected graphs and undirected graphs, respectively. Bilò et al. [14] consider Nash stable outcomes for fractional hedonic games played on undirected graphs and study their existence, complexity and performance for general and specific graph topologies. In particular, they first notice that Nash stable outcomes always exist only when the weights are all positive (in this case the grand coalition is Nash stable), and study the performance of Nash stable outcomes. They show that the price of anarchy is $\varTheta (n)$ (where n is the number of agents), and that, for unweighted undirected graphs, the problem of computing a Nash stable outcome of maximum social welfare is NP-hard, as well as the problem of computing an optimal (not necessarily stable) outcome. Furthermore, the same authors in [15] consider unweighted undirected graphs and show that 2-Strong Nash outcomes, that is, an outcome such that no pair of agents can improve their utility by simultaneously changing their own coalition, are not always guaranteed. Clearly, this last result implies that strong Nash stable outcomes are not guaranteed to exist even for fractional hedonic games played on unweighted undirected graphs. They also provide upper and lower bounds on the price of stability for games played on different unweighted undirected graphs topologies. It is remarkable the almost tight bound (up to a 0.026 additive factor) for bipartite graphs, and the polynomial time algorithm that computes an optimum that is also Nash stable for unweighted tree graphs. Kaklamanis et al. [31] provide some improved results on the price of stability. Recently, Carosi et al. [20] consider local core stability in fractional hedonic games played on unweighted undirected graphs. Specifically, they assume that the edges of the input graph model social connection (i.e., acquaintance) among agents and consider the simple setting where an agent values 1 all and only her acquaintances. A coalition structure is in the local core if there is no subset of agents which induces a clique in the graph, and such that all agents can improve their utility by forming a new coalition together. The authors show that any local core dynamics converges, which implies that a local core stable coalition structure always exists. Moreover, they provide tight bounds on the core price of anarchy and almost tight bound on the core price of stability. Finally, Aziz et al. [4] consider the computational complexity of computing welfare maximizing partitions (not necessarily Nash stable) for fractional hedonic games played on undirected graphs. We point out that fractional hedonic games played on unweighted undirected graphs model realistic economic scenarios referred to in [2, 15, 16] as Bakers and Millers. Table 2 summarizes the main results about fractional hedonic games.

From a different perspective, strategyproof mechanisms for additively separable hedonic and fractional hedonic games have been proposed in [28, 50]. Moreover, Flammini et al. consider the problem of maximizing the social welfare in additively separable and fractional hedonic games in the online setting [27].

Table 2 Related results for Fractional Hedonic Games (FHG)

Hedonic games are being widely investigated also under different utility definitions: For instance, in [10, 11], coalition formation games, in which agent utilities are proportional to their harmonic centralities in the respective coalitions, are considered.

To the best of our knowledge, only few papers have dealt with stable outcomes for MFHGs. Olsen [37] considers unweighted undirected connected graphs and investigates computational issues concerning the problem of deciding whether a Nash stable outcome (different from the trivial one where all the agents are in the same coalition) exists and, if the answer is yes, the problem of computing it. On the one hand, the author proves that a Nash stable outcome exists if and only if the graph contains at least 4 nodes and it is not isomorphic to a star. In this case, he proves that it can be computed in polynomial time. On the other hand, it is shown that the problem becomes NP-hard when we also require that a coalition must contain a given subset of the agents. Kaklamanis et al. [31] show that the price of stability is 1 for unweighted undirected graphs. Finally, Elkind et al. [25] study the set of Pareto optimal outcomes for MFHGs played on undirected graphs.

1.2 Our results

In this paper we consider symmetric MFHGs. Some preliminary results and open problems concerning the asymmetric case are discussed in Sect. 6.

We start by dealing with strong Nash stable outcomes. We first prove that there exists a simple graph (i.e., a path of three nodes) with positive edge weights that admits no strong Nash stable outcome. Therefore we focus on unweighted graphs, and present a polynomial time algorithm that computes an optimum outcome that can be transformed (still in polynomial time) in a strong Nash stable one with the same social welfare, implying that strong Nash stable outcomes always exist and that the strong price of stability is 1. We further prove that the strong price of anarchy is exactly 2. In particular, we are able to show that, even for jointly cooperative deviations of at most 2 agents, the strong price of anarchy is at most 2 (we emphasize that, as we will describe in the next paragraph, the price of anarchy for Nash stable outcomes that are resistant to deviations of one agent grows linearly with the number of agents), while it is at least 2 for jointly cooperative deviations of any subsets of agents.

We subsequently turn our attention to Nash stable outcomes. We notice that Nash stable outcomes are guaranteed to exist only if edge weights are non-negative. In a similar way as in [14], we prove that the price of anarchy is $\varOmega (n)$, where n is the number of agents, even for unweighted paths, and that it is at most $n-1$ for the more general case of non-negative edge-weighted graphs, thus giving an asymptotically tight characterization. We also prove a matching lower bound of $\varOmega (n)$ to the price of stability.

We finally consider strict core and core stable outcomes. We first show that the strict core could be empty even for unweighted graphs. We then prove that core stable outcomes always exist, and in particular that an outcome that is core stable can be computed in polynomial time, even in the presence of negative weights, i.e., for general undirected weighted graphs. We then establish that the core price of stability is 2. We further show that the core price of anarchy is at most 4. We also provide a tight analysis for unweighted graphs. We summarize our results in Table 3.

Table 3 Main results presented in the paper

In the next subsection we emphasize the differences between MFHGs and fractional hedonic games.

1.3 Main differences between MFHGs and fractional hedonic games

Roughly speaking, we say that an outcome is a k-strong Nash stable outcome if no subset of at most k agents can jointly change their strategies in a way that all of the k agents strictly improve their utility. It is easy to see that, for any $k,k' \ge 2$, such that $k' \ge k$, a $k'$-strong Nash stable outcome is also a k-strong Nash stable outcome. It is known that 2-strong Nash stable outcomes are not guaranteed to exist for fractional hedonic games, even for unweighted undirected graphs [15]. Clearly, this implies that k-strong Nash stable outcomes are not guaranteed to exist for any $k \ge 2$. In this paper we show that for MFHGs played on unweighted undirected graphs, k-strong Nash stable outcomes always exist and can be computed in polynomial time, for any $1 \le k \le n$, where n is the number of agents, and provide a tight analysis on the strong price of anarchy and stability.

For both MFHGs and fractional hedonic games, Nash stable outcomes (or equivalently 1-strong Nash stable) are guaranteed to exist [14, 16] for undirected graphs with only positive weights, but not for general weights (i.e., with also negative weights); moreover, the price of stability grows linearly with the number of agents. For fractional hedonic games, it is known [15] that the price of stability is greater than 1 even for bipartite undirected unweighted graphs. Moreover, the problem of computing an optimum outcome is NP-hard for fractional hedonic games played on unweighted undirected graphs. For MFHGs played on unweighted undirected graphs, we show that it is possible to compute in polynomial time a strong Nash stable outcome that is also optimum, which implies that the strong price of stability is 1.

Finally, it is known that the core can be empty even for fractional hedonic games played on general unweighted undirected graphs and that it is NP-hard deciding the existence [19]. The nonemptiness of the core is guaranteed only for fractional hedonic games played on some specific classes of unweighted undirected graphs, that is, graphs with degree at most 2, multipartite complete graphs, bipartite graphs admitting a perfect matching and regular bipartite graphs [2]. In this paper we show that for MFHGs the core is not empty for any undirected graph (this result was also observed in [1] for unweighted graphs), and that a core stable outcome can be computed in polynomial time. We further provide a tight and an almost tight analysis for the core price of stability and anarchy, respectively. We summarize similarities and differences between MFHGs and fractional hedonic games in Table 4.

Table 4 Main similarities and differences between MFHGs and Fractional hedonic games

2 Preliminaries

2.1 Model and definitions

For an integer $k>0$, denote with [k] the set $\{1,\ldots ,k\}$.

We model a coalition formation game by means of a undirected graph. For an undirected edge-weighted graph $G=(N,E,w)$, denote with $n=|N|$ the number of its nodes. For the sake of convenience, we adopt the notation (i, j) and $w_{i,j}$ to denote the edge $\{i,j\}\in E$ and its weight $w(\{i,j\})$, respectively. We assume that if $(i,j) \notin E$ then $w_{i,j}=0$. Say that G is unweighted if $w_{i,j}=1$ for each $(i,j)\in E$. We denote by $\delta ^{i}(G) = \sum _{j \in N: (i,j) \in E} w_{i,j}$, the sum of the weights of all the edges incident to i. Moreover, let $w^{i}_{max}(G)=\max _{j \in N: (i,j) \in E} w_{i,j}$ be the maximum edge-weight incident to i. We omit reference to G when G is clear from the context. Given a set of edges $X\subseteq E$, denote with $W(X)=\sum _{(i,j) \in X}w_{i,j}$ the total weight of edges in X. Given a subset of nodes $S \subseteq N$, $G_{S}=(S,E_{S})$ is the subgraph of G induced by the set S, i.e., $E_S = \{(i,j)\in E : i,j \in S\}$.

Given an undirected edge-weighted graph $G=(N,E,w)$, the modified fractional hedonic game induced by G, denoted as $\mathcal {G}(G)$, is the game in which each node $i \in N$ is associated with an agent. We assume that agents are numbered from 1 to n and, for every $i \in [n]$, each agent chooses to join a certain coalition among n candidate ones: the strategy of agent i is an integer $j \in [n]$, meaning that agent i is selecting candidate coalition $C_j$. A strategy profile $(j_1,\ldots ,j_n)$ naturally induces a coalition structure (also called outcome or partition), that is a partition of the set of agents into $\ell \le n$ coalitions ${\mathcal {C}}=\{C_1,C_2,\ldots ,C_\ell \}$ such that $C_j \subseteq N$ for each $j\in [\ell ]$, $\bigcup _{j\in [\ell ]}C_j = N$, $C_i \cap C_j = \emptyset$ for any $i,j\in [\ell ]$ with $i\ne j$ and agents i and $i'$ belong to a same coalition $C \in {\mathcal {C}}$ if and only if $j_i=j_{i'}$. If $i \in C$, we say that agent i is a member of the coalition C. We denote by ${\mathcal {C}}(i)$ the coalition in ${\mathcal {C}}$ of which agent i is a member. In an outcome ${\mathcal {C}}$, the utility of agent i is defined as $u_i({\mathcal {C}})=\sum _{j\in {\mathcal {C}}(i)} \frac{w_{i,j}}{|{\mathcal {C}}(i)|-1}$ when $|{\mathcal {C}}(i)|>1$, and $u_i({\mathcal {C}})=0$ when ${\mathcal {C}}(i)=\{i\}$ (i.e., when the agent is alone in her coalition). We notice that, for any possible outcome ${\mathcal {C}}$, we have that $u_i({\mathcal {C}}) \le w^{i}_{max}$.

Each agent chooses the coalition she belongs to with the aim of maximizing her utility. We denote by $({\mathcal {C}}, i, j)$, the new coalition structure obtained from ${\mathcal {C}}$ by moving agent i from ${\mathcal {C}}(i)$ to $C_j$; formally, $({\mathcal {C}}, i, j) = {\mathcal {C}}\setminus \{{\mathcal {C}}(i),C_j\} \cup \{{\mathcal {C}}(i)\setminus \{i\}, C_j \cup \{i\}\}$. An agent deviates if she changes the coalition she belongs to. Given an outcome ${\mathcal {C}}$, an improving move (or simply a move) for agent i is a deviation to any coalition $C_j$ that strictly increases her utility, i.e., $u_i(({\mathcal {C}}, i, j)) > u_i({\mathcal {C}})$. Moreover, agent i performs a best-response in coalition ${\mathcal {C}}$ by choosing a coalition providing her the highest possible utility (notice that a best-response is also a move when there exists a coalition $C_j$ such that $u_i(({\mathcal {C}}, i, j)) > u_i({\mathcal {C}})$). An agent is stable if she cannot perform a move.

Definition 1

(Nash equilibrium) An outcome is (pure) Nash stable (or a Nash equilibrium) if every agent is stable.

An improvement dynamics, or simply a dynamics, is a sequence of moves, while a best-response dynamics is a sequence of best-responses. A game has the finite improvement path property if it does not admit an improvement dynamics of infinite length. Clearly, a game possessing the finite improvement path property always admits a Nash stable outcome. We denote with $\textsf {N} (\mathcal {G}(G))$ the set of Nash stable outcomes of $\mathcal {G}(G)$.

Definition 2

(k-strong Nash equilibrium) An outcome ${\mathcal {C}}$ is k-strong Nash stable (or a k-strong Nash equilibrium) if there is no ${\mathcal {C}}'$ obtained from ${\mathcal {C}}$, when a subset of at most k agents $K \subseteq N$ (with $|K| \le k$) jointly change (or deviate from) their strategies (not necessarily selecting the same candidate coalition), such that $u_i({\mathcal {C}}') > u_i({\mathcal {C}})$ for any $i \in K$, that is, after any joint collective deviation, there always exists an agent in the set of deviating ones who does not improve her utility.

We denote with ${k}{\textsf {-SN} }(\mathcal {G}(G))$ the set of k-strong Nash stable outcomes of $\mathcal {G}(G)$. We simply say that an outcome ${\mathcal {C}}$ is a strong Nash equilibrium if ${\mathcal {C}}$ is an n-strong Nash equilibrium, and denote the set of n-strong Nash stable outcomes of $\mathcal {G}(G)$ with $\textsf {SN} (\mathcal {G}(G))$. It is easy to see that, for any graph G and any $k\ge 2$, ${k}{\textsf {-SN} }(\mathcal {G}(G)) \subseteq {k-1}{\textsf {-SN} }(\mathcal {G}(G))$, while the vice versa does not in general hold. Clearly, ${1}{\textsf {-SN} }(\mathcal {G}(G))=\textsf {N} (\mathcal {G}(G))$. Analogously to the notion of Nash equilibrium, also for strong Nash equilibria it is possible to define a dynamics as a sequence of improving moves, where each move performed by agents in K leading from outcome ${\mathcal {C}}$ to outcome ${\mathcal {C}}'$ is such that all of them improve their utility, i.e. $u_i({\mathcal {C}}') > u_i({\mathcal {C}})$ for every $i \in K$.

We say that a coalition $T \subseteq N$strongly blocks an outcome ${\mathcal {C}}$, if each agent $i \in T$ strictly prefers T, i.e., strictly improve her utility with respect to her current coalition ${\mathcal {C}}(i)$.

Definition 3

(Core) An outcome that does not admit a strongly blocking coalition is called core stable and is said to be in the core.

We denote with $\textsf {{CR}} (\mathcal {G}(G))$ the core of $\mathcal {G}(G)$. Notice that, given any graph G, a strong Nash stable outcome is also in the core, and it is also a Nash equilibrium, i.e., $\textsf {SN} (\mathcal {G}(G)) \subseteq \textsf {N} (\mathcal {G}(G))$ and $\textsf {SN} (\mathcal {G}(G)) \subseteq \textsf {{CR}} (\mathcal {G}(G))$; moreover, as already outlined in the caption of Fig. 1, there is no relation between the sets of Nash stable and core stable outcomes, i.e., there are Nash stable outcomes not being core stable (consider the grand coalition in Fig. 1a) and, vice versa, there also exist core stable outcomes not being Nash stable (see Fig. 1c).

We say that a coalition $T \subseteq N$weakly blocks an outcome ${\mathcal {C}}$, if each agent $i \in T$ weakly prefers T, i.e., she does not worsen her utility with respect to her current coalition ${\mathcal {C}}(i)$, and there exists at least one agent $i \in T$ who strictly prefers T to her current coalition ${\mathcal {C}}(i)$.

Definition 4

(Strict core) An outcome that does not admit a weakly blocking coalition is called strict core stable and is said to be in the strict core.

We denote with $\textsf {SCR} (\mathcal {G}(G))$ the strict core of $\mathcal {G}(G)$. Notice that, given any graph G, a strict core stable outcome is also core stable, i.e., $\textsf {SCR} (\mathcal {G}(G)) \subseteq \textsf {{CR}} (\mathcal {G}(G))$.

The social welfare of a coalition structure ${\mathcal {C}}$ is the summation of the agents’ utilities, i.e.,

$$\begin{aligned} \textsf {SW} ({\mathcal {C}}) = \sum _{i \in N} u_i({\mathcal {C}}). \end{aligned}$$

We overload the social welfare function by applying it also to single coalitions to obtain their contribution to the social welfare, i.e., for any $i \in [n]$,

$$\begin{aligned} \textsf {SW} (C_i)=\sum _{j \in C_i} u_j({\mathcal {C}}) \text { so that } \textsf {SW} ({\mathcal {C}}) = \sum _{i \in [n]} \textsf {SW} (C_i). \end{aligned}$$

It is worth noticing that, equivalently, for any $i \in [n]$,

$$\begin{aligned} \textsf {SW} (C_i)=\frac{2W\left( E_{C_i}\right) }{|C_i|-1} \text { and } \textsf {SW} ({\mathcal {C}}) =\sum _{i \in [n]}\frac{2 W\left( E_{C_i}\right) }{|C_i|-1}. \end{aligned}$$

Given a game $\mathcal {G}(G)$, an optimum coalition structure ${\mathcal {C}}^*(\mathcal {G}(G))=(C^*_1,\ldots ,C^*_{\ell ^*})$ is one that maximizes the social welfare of $\mathcal {G}(G)$.

Definition 5

(Price of Anarchy) The price of anarchy (resp. strong price of anarchy and core price of anarchy) of a modified fractional hedonic game $\mathcal {G}(G)$ is defined as the worst-case ratio between the social welfare of a social optimum outcome and that of a Nash equilibrium (resp. strong Nash equilibrium and core).

Formally, for any $k=1,\dots ,n$,

$$\begin{aligned} \textsf {PoA} ({\mathcal {G}(G)}) = \max _{{\mathcal {C}}\in {\textsf {N} (\mathcal {G}(G))}} \frac{\textsf {SW} ({\mathcal {C}}^*(\mathcal {G}(G)))}{\textsf {SW} ({\mathcal {C}})}, \end{aligned}$$

respectively:

$$\begin{aligned} {k}{\textsf {-SPoA} }({\mathcal {G}(G)}) = \max _{{\mathcal {C}}\in {{k}{\textsf {-SN} }(\mathcal {G}(G))}} \frac{\textsf {SW} ({\mathcal {C}}^*(\mathcal {G}(G)))}{\textsf {SW} ({\mathcal {C}})}, \end{aligned}$$

and

$$\begin{aligned} \textsf {CPoA} ({\mathcal {G}(G)}) = \max _{{\mathcal {C}}\in {\textsf {{CR}} (\mathcal {G}(G))}} \frac{\textsf {SW} ({\mathcal {C}}^*(\mathcal {G}(G)))}{\textsf {SW} ({\mathcal {C}})}. \end{aligned}$$

Definition 6

(Price of stability) The price of stability (resp. strong price of stability and core price of stability) of $\mathcal {G}(G)$ is defined as the best-case ratio between the social welfare of a social optimum outcome and that of a Nash equilibrium (resp. strong Nash equilibrium and core).

Formally, for any $k=1,\dots ,n$,

$$\begin{aligned} \textsf {PoS} ({\mathcal {G}(G)}) = \min _{{\mathcal {C}}\in {\textsf {N} (\mathcal {G}(G))}} \frac{\textsf {SW} ({\mathcal {C}}^*(\mathcal {G}(G)))}{\textsf {SW} ({\mathcal {C}})}, \end{aligned}$$

respectively:

$$\begin{aligned} {k}{\textsf {-SPoS} }({\mathcal {G}(G)}) = \min _{{\mathcal {C}}\in {{k}{\textsf {-SN} }(\mathcal {G}(G))}} \frac{\textsf {SW} ({\mathcal {C}}^*(\mathcal {G}(G)))}{\textsf {SW} ({\mathcal {C}})}, \end{aligned}$$

and

$$\begin{aligned} \textsf {CPoS} ({\mathcal {G}(G)}) = \min _{{\mathcal {C}}\in {\textsf {{CR}} (\mathcal {G}(G))}} \frac{\textsf {SW} ({\mathcal {C}}^*(\mathcal {G}(G)))}{\textsf {SW} ({\mathcal {C}})}. \end{aligned}$$

Clearly, for any game $\mathcal {G}(G)$ it holds that $1 \le \textsf {PoS} ({\mathcal {G}(G)}) \le \textsf {PoA} ({\mathcal {G}(G)})$ (resp. $1 \le {k}{\textsf {-SPoS} }({\mathcal {G}(G)}) \le {k}{\textsf {-SPoA} }({\mathcal {G}(G)})$ and $1 \le \textsf {CPoS} ({\mathcal {G}(G)}) \le \textsf {CPoA} ({\mathcal {G}(G)})$).

2.2 General results

We are now ready to provide some general results that will be exploited in the remainder of the paper in order to show the main technical results of the paper. More specifically, we show that it is possible to compute in polynomial time an optimum outcome. To this aim, we first need an additional lemma.

Lemma 1

Given a coalition C with $|C|\ge 4$, there exists an edge $e=(i,j)$ belonging to $E_C$ such that

$$\begin{aligned} \textsf {SW} (\{i,j\})+ \textsf {SW} (C \setminus \{i,j\}) \ge \textsf {SW} (C). \end{aligned}$$

Proof

Let $m=|E_C|$ and $k=|C|$ be the number of edges and nodes in coalition C, respectively. Moreover, let $e=(i, j)$ be the edge minimizing $\varDelta =\delta ^i+\delta ^j$. Let us assume by contradiction that

$$\begin{aligned} \textsf {SW} (\{i,j\})+ \textsf {SW} (C \setminus \{i,j\})=2+\frac{2(m-\varDelta +1)}{k-3}< \frac{2m}{k-1}=\textsf {SW} (C). \end{aligned}$$

By simple calculations, we obtain that

$$\begin{aligned} \varDelta > \frac{k^2-3k+2+2m}{k-1}. \end{aligned}$$

(1)

We denote by $\delta _{max}$ and $\delta _{min}$ the maximum and the minimum degrees of nodes in $G_C$, respectively. We have

$$\begin{aligned} 2m&=\sum _{i\in C} \delta _i\ge (k-1)\delta _{min}+\delta _{max}. \end{aligned}$$

(2)

$$\begin{aligned} \varDelta&\le \delta _{max}+\delta _{min}. \end{aligned}$$

(3)

Substituting (2), (3), in (1), the following holds:

$$\begin{aligned} \varDelta> \frac{k^2-3k+2+2m}{k-1}&\ge \frac{k^2-3k+2+(k-1)\delta _{min}+\delta _{max}}{k-1}\\ \delta _{max}+\delta _{min}\ge \varDelta&> \frac{k^2-3k+2+(k-1)\delta _{min}+\delta _{max}}{k-1}\\ \left( \delta _{max}+\delta _{min}\right) (k-1)&> k^2-3k+2+(k-1)\delta _{min}+\delta _{max}\\ k\delta _{max}-\delta _{max}&>k^2-3k+2+\delta _{max}\\ (k-2)\delta _{max}&>(k-1)(k-2)\\ \delta _{max}&>(k-1): \end{aligned}$$

a contradiction, because the maximum degree of a node is at most $k-1$. $\square$

Let $K_1$, $K_2$ and $K_3$ be the unweighted cliques with 1, 2 and 3 nodes, respectively, i.e., $K_1$ is an isolated node, $K_2$ has 2 nodes and a unique edge and $K_3$ is a triangle with 3 edges. We say that a coalition being isomorphic to $K_1$, $K_2$ or $K_3$ is a basic coalition.

We are now ready to prove the following theorem, showing that it is possible to consider, without decreasing the social welfare of the outcome, only coalition structures formed by basic coalitions.

Theorem 1

For any coalition structure ${\mathcal {C}}$, there exists a coalition structure ${\mathcal {C}}'$ containing only basic coalitions and such that $\textsf {SW} ({\mathcal {C}}')\ge \textsf {SW} ({\mathcal {C}})$.

Fig. 2

Possible coalitions with three nodes

Proof

Consider any coalition C belonging to ${\mathcal {C}}$. In the following we show that either coalition C is basic, or the nodes in C can be partitioned in $h\ge 2$ basic coalitions $C'_1,\dots ,C'_h$ such that $\sum _{i=1}^h \textsf {SW} (C'_i) \ge \textsf {SW} (C)$. This statement proves the claim because we can consider and sum up over all coalitions C belonging to ${\mathcal {C}}$.

We prove the statement by induction on the number k of nodes in C.

The base of the induction is for $k\le 3$: For $k=1$ and $k=2$, C is already a basic coalition. For $k=3$, there are four possible configurations shown in Fig. 2. For configurations (a), (b) and (c), again C already is a basic coalition (or can be trivially divided in basic coalitions). For configuration (d), let $x_1, x_2, x_3$ be the 3 nodes in C; clearly, $\textsf {SW} (C)=2$. Consider coalitions $C'_1=\{x_1,x_2\}$ and $C'_2=\{x_3\}$. It is easy to check that $\textsf {SW} (C'_1)+\textsf {SW} (C'_2)=2=\textsf {SW} ({\mathcal {C}})$.

As to the induction step, given any $k\ge 4$, assume now that the statement holds for $1, \dots , k-1$; we want to show that it also holds for k.

By Lemma 1, we know that there exists an edge $e=(i,j)$ belonging to $E_C$ such that $\textsf {SW} (\{i,j\})+ \textsf {SW} (C \setminus \{i,j\}) \ge \textsf {SW} (C)$. Since $|C \setminus \{i,j\}|\le k-2$, by the induction hypothesis, coalition $C \setminus \{i,j\}$ can be decomposed in h basic coalitions $C''_1,\dots ,C''_h$ such that $\sum _{i=1}^h \textsf {SW} (C''_i) \ge \textsf {SW} (C \setminus \{i,j\})$. Therefore, given that also $\{i,j\}$ is a basic coalition, we have proven the induction step. $\square$

By Theorem 1, in order to compute an optimal solution for the coalition structure generation problem (i.e., an outcome maximizing the social welfare), it is possible to exploit a result from [30]:

Theorem 2

[30] Given an unweighted graph G, it is possible to compute in polynomial time a partition of the nodes of G in sets inducing subgraphs isomorphic to $K_1$, $K_2$ or $K_3$ (i.e., a coalition structure composed by basic coalitions) maximazing the number of nodes belonging to sets inducing subgraphs isomorphic to $K_2$ or $K_3$.

In fact, by combining Theorems 1 and 2, it is possible to prove the following result.

Theorem 3

Given an unweighted graph G, there exists a polynomial time algorithm for computing a coalition structure ${\mathcal {C}}^*$ maximizing the social welfare.

Proof

By Theorem 1, there must exist an optimal outcome ${\mathcal {C}}^*=(C^*_1,\dots ,C^*_{\ell ^*})$ in which, for all $i=1,\dots ,\ell ^*$, $C^*_i$ is a basic coalition. Notice that any node in a basic coalition isomorphic to $K_1$ does not contribute to the social welfare, while all nodes in other coalitions contribute 1 to $\textsf {SW} ({\mathcal {C}}^*)$. It follows that, in order to maximize the social welfare, the number of nodes belonging to coalitions isomorphic to $K_2$ or $K_3$ has to be maximized, and therefore the solution computed in Theorem 2 is optimal also for our problem. $\square$

3 Strong Nash stable outcomes

In this section we consider strong Nash stable outcomes. We start by showing that even the existence of 2-strong nash equilibria is not guaranteed for non-negative edge-weights graphs.

Theorem 4

There exists a graph G containing only non-negative edge-weights such that $\mathcal {G}(G)$ admits no 2-strong Nash stable outcome.

Fig. 3

The graph G used in Theorem 4

Proof

Let G be the graph of three nodes and two edges depicted in Fig. 3, where the weights are $w_{1,3}=1$ and $w_{1,2}=\epsilon$, where $\epsilon >0$ is a small positive value. First notice that, the grand coalition where all the agents belong to the same coalition is not a 2-strong Nash stable outcome since, for instance, the two agents 1, 3 would both get strictly higher utility if they belong to a different coalition containing only them. On the other hand, any outcome where agent 2 does not belong to the same coalition containing agent 1 is even not Nash stable (i.e., 1-strong Nash stable), since agent 2 would get utility zero but she can improve her utility by selecting the coalition containing the agent 1. Hence, the claim follows. $\square$

Given the above negative result, in the remainder of this section we focus on unweighted graphs.

3.1 Strong price of stability

In this subsection we show that the strong price of stability is 1 for unweighted graphs. More specifically, given that (by Theorem 3) it is possible to compute in polynomial time an optimum outcome, we show that it can be transformed, still in polynomial time, into a strong Nash outcome with the same social value.

In [31] the authors show that the price of stability of modified unweighted fractional hedonic games is 1, without considering complexity issues. The different characterization of the optimum done in Theorem 1 allows us to first compute in polynomial time an outcome that maximizes the social welfare (done in Theorem 3) and then to transform this optimal outcome into a strong Nash without worsening its social welfare, again by a polynomial time transformation. The following theorem completes this picture by providing a polynomial time algorithm for transforming an optimal outcome into a strong Nash with the same social welfare, thus also proving that the strong price of stability is 1.

Theorem 5

Given an unweighted graph G, it is possible to compute in polynomial time an outcome ${\mathcal {C}}\in \textsf {SN} (\mathcal {G}(G))$ and such that $\textsf {SW} ({\mathcal {C}})=\textsf {SW} ({\mathcal {C}}^*)$.

Proof

Let ${\mathcal {C}}^*$ be the optimal outcome computed in polynomial time by Theorem 3. Let $N'\subseteq N$ the set of agents belonging in ${\mathcal {C}}^*$ to coalitions isomorphic to $K_2$ or $K_3$. Notice that $\textsf {SW} ({\mathcal {C}}^*) = |N'|$. No agent $i \in N'$ can have an incentive in changing her strategy (and thus can belong to any deviating subset of agents), because $u_i({\mathcal {C}})=1$ and a node can gain at most 1 in any outcome. Therefore, if $N'=N$, then ${\mathcal {C}}^*$ is also a strong Nash equilibrium and the claim directly follows.

In order to complete the proof, it is sufficient to (i) show the existence of a dynamics involving only the set of agents $K \subseteq N''$, where $N''= N \setminus N'$, and leading to a strong Nash outcome ${\mathcal {C}}$; (ii) providing a polynomial time algorithm for computing ${\mathcal {C}}$.

For any $h=1,2,3$, let ${\mathcal {C}}^*_h \subseteq {\mathcal {C}}^*$ be the set containing all coalitions of ${\mathcal {C}}^*$ isomorphic to $K_h$. We first provide some useful properties of nodes in $N''$:

• (P1) For any couple of distinct nodes $i,j \in N''$, $(i,j) \not \in E$, because otherwise the social welfare of ${\mathcal {C}}^*$ could be improved by putting i and j in the same coalition: a contradiction to the optimality of ${\mathcal {C}}^*$.

• (P2) For any $i \in N''$ and any vertex j belonging to a coalition in ${\mathcal {C}}^*_3$, $(i,j) \not \in E$, because otherwise the social welfare of ${\mathcal {C}}^*$ could be improved by removing j from her current coalition and putting her in the same coalition of i: a contradiction to the optimality of ${\mathcal {C}}^*$ (see Fig. 4).

• (P3) For any couple of distinct nodes $i,j \in N''$ and any coalition $\{i',j'\} \in {\mathcal {C}}^*_2$, if there exists an edge connecting node i to a node in $\{i',j'\}$ (assume without loss of generality to node $i'$, i.e. assume that $(i,i') \in E$), then $(j,j') \not \in E$, because otherwise the social welfare of ${\mathcal {C}}^*$ could be improved by removing $i'$ and $j'$ from their current coalition and putting them in the same coalition of i and j, respectively: a contradiction to the optimality of ${\mathcal {C}}^*$ (see Fig. 5).

• (P4) For any couple of distinct nodes $i,j \in N''$ and any couple of coalitions $\{i',j'\},\{i'',j''\}\in {\mathcal {C}}^*_2$, if there exist an edge connecting node i to a node in $\{i',j'\}$ (assume without loss of generality to node $i'$, i.e. assume that $(i,i') \in E$), and another edge connecting node j to a node in $\{i'',j''\}$ (assume without loss of generality to node $i''$, i.e. assume that $(j,i'') \in E$), then $(j',j'') \not \in E$, because otherwise the social welfare of ${\mathcal {C}}^*$ could be improved by removing $i'$, $i''$ and $j'$ from their current coalition and putting them in the same coalition of i, j and $j''$, respectively: a contradiction to the optimality of ${\mathcal {C}}^*$ (see Fig. 6).

Fig. 4

Proof of (P2)

Fig. 5

Proof of (P3)

Fig. 6

Proof of (P4)

In order to show the existence of a dynamics leading to a strong Nash outcome, first of all, consider an initial dynamics, ending in outcome ${\mathcal {C}}^0$, in which every agent in $i \in N''$ unilaterally moves in order to increase her utility (that in ${\mathcal {C}}^*$ is 0). By properties (P1) and (P2) it follows that, for any $i \in N''$, i selects a coalition in ${\mathcal {C}}^*_2$ and by property (P3) it follows that after this initial dynamics, all coalitions in ${\mathcal {C}}^0 \setminus {\mathcal {C}}^*$ (i.e., all coalitions modified by this initial dynamics) are isomorphic to star graphs, i.e. only one node has degree greater than 1.

Consider now a sequence of improving moves performed by any subset of agents $K \subseteq N$ and such that for any $i \in K$, agent i improves her utility after this move. For any $t \ge 1$, let ${\mathcal {C}}^t$ be the outcome reached after the t-th move of this dynamics and $K^t$ be the set of moving agents. We want to show that this dynamics converges, i.e., that a strong Nash equilibrium is eventually reached.

By properties (P3) and (P4) it follows that:

• (P5) For any coalition in ${\mathcal {C}}^*_2$, there exists an agent that will always have utility 1 during any dynamics; let ${\bar{N}} \subseteq N$ the set containing these nodes. Clearly, every agent in ${\bar{N}}$, as well as all nodes belonging to coalitions in ${\mathcal {C}}^*_3$, will never belong to a subset of nodes performing an improving move and therefore will always remain in the same coalition she belongs in ${\mathcal {C}}^*$.

• (P6) For any $t\ge 1$, and any agent $i \in K^t$ (potentially i could be an agent of a coalition in ${\mathcal {C}}^*_1$ or also an agent of a coalition in ${\mathcal {C}}^*_2$ not belonging to ${\bar{N}}$), ${\mathcal {C}}^t(i)$ is such that there exists a unique $j \in {\mathcal {C}}^t(i) \cap {\bar{N}}$ and i will have a unique edge in ${\mathcal {C}}^t(i)$ connecting her to j.

By properties (P5) and (P6), the only nodes participating in the dynamics are nodes either belonging to coalitions in ${\mathcal {C}}^*_1$ or belonging to coalitions in ${\mathcal {C}}^*_2$ but not belonging to ${\bar{N}}$; let $\bar{\bar{N}}$ be the set of these nodes, i.e., for any $t>1$, $K^t \subseteq \bar{\bar{N}}$.

In order to obtain a strong Nash equilibrium, we notice that the “residual” game played by agents in $\bar{\bar{N}}$ is equivalent to a singleton congestion game with identical latency functions (SCGI), in which we also have a set of resources (i.e. a strong Nash equilibrium in this new game is also a strong Nash equilibrium in our game and vice versa).

Congestion games, introduced by Rosenthal [44] in 1973, constitute a well-known class of non-cooperative games in which a set of resources R is available to the agents and the strategy set of each agent i can be any $\varSigma _i\subseteq 2^R$. The cost of each resource $j\in R$ (usually called the latency of j) is given by a function $f_j$ of the number of agents using j and the latency experienced by each agent i is the sum of the latencies of all the resources used by i.

In an SCGI, agent’s strategy consists of a single resource. The delay of a resource is given by the number of agents choosing it. Therefore, the cost that each agent aims at minimizing is the delay of her selected resource. In particular, the set of agents is $\bar{\bar{N}}$ and the set of resources is ${\bar{N}}$. In fact, in our “residual” game every agent aims at minimizing the cardinality of the star coalition she belongs to. In [29] it has been shown how to compute in polynomial time a strong Nash equilibrium for a class of congestion games including the one of SCGI.

Let us call ${\mathcal {C}}$ the obtained strong Nash equilibrium. It remains to show that $\textsf {SW} ({\mathcal {C}})=\textsf {SW} ({\mathcal {C}}^*)$. Observe that the difference between ${\mathcal {C}}$ and ${\mathcal {C}}^*$ is that some coalitions belonging to ${\mathcal {C}}^*$ isomorphic to $K_2$ becomes a coalition isomorphic to a star graph in ${\mathcal {C}}$, and that some coalitions belonging to ${\mathcal {C}}^*$ isomorphic to $K_1$ disappears in ${\mathcal {C}}$. The claim follows by noticing that the contribution to the social welfare of a coalition isomorphic to $K_1$ is zero, and that the contribution to the social welfare of a coalition isomorphic to $K_2$ (whose value is 2) is the same as the one of a coalition isomorphic to a star graph. $\square$

As a direct consequence of Theorem 5, the following corollary holds.

Corollary 1

For any unweighted graph G and any $k=1,\dots ,n$,

$$\begin{aligned} {k}{\textsf {-SPoS} }(\mathcal {G}(G))=1. \end{aligned}$$

3.2 Strong price of anarchy

In this subsection we study the strong price of anarchy for unweighted graphs.

Theorem 6

Given any $\epsilon >0$, there exists an unweighted graph G such that ${n}{\textsf {-SPoA} }(\mathcal {G}(G))\ge 2-\epsilon$.

Fig. 7

The graph G used in Theorem 6

Proof

Let us consider the graph G depicted in Fig. 7. The number of nodes in G is $n=2k+1$. Specifically, we have k agents $\{1,\ldots ,k\}$ in the first (upper) layer, other k agents $\{k+1,\ldots ,2k\}$ in the second layer, and a last agent in the last layer. Moreover, the k nodes in the upper layer form a clique. We first notice that the optimum solution OPT has social welfare at least $\textsf {SW} (OPT)\ge 2k$. In fact, the coalitions structure composed by k non-empty coalitions corresponding to the k matchings between agents of the first and second layer, i.e., for any $j=1,\ldots ,k$, $C_j=\{j,k+j\}$, has social welfare exactly 2k. A strong Nash stable outcome is given by the coalition structure ${\mathcal {C}}$ composed by two coalitions ${\mathcal {C}}=\{C_1, C_2\}$, where $C_1$ contains all the agents of the clique, while $C_2$ contains all the other agents. Indeed, on the one hand, all the agents belonging to the coalition $C_1$ and the agent of the last layer belonging to $C_2$ get utility 1 that is the maximum one they can hope for, which means that they do not have any interest on deviating from ${\mathcal {C}}$. Therefore, suppose by contradiction that ${\mathcal {C}}$ is not strong Nash stable, then the set of deviating agents must be a subset of the agents of the second layer belonging to the coalition $C_2$. However, by using the fact that $|C_2| = |C_1|+1$, it is easy to see any subset of agents of the second layer of $C_2$ cannot jointly deviate and all get higher utility with respect to ${\mathcal {C}}$. It follows that ${\mathcal {C}}$ is a strong Nash stable outcome. Since $\textsf {SW} ({\mathcal {C}})=k+2$, it follows that ${n}{\textsf {-SPoA} } \ge \frac{2k}{k+2}$, and the theorem holds by taking a sufficiently large k. $\square$

Theorem 7

For any unweighted graph G, ${2}{\textsf {-SPoA} }(\mathcal {G}(G))\le 2$.

Proof

Let ${\mathcal {C}}^*$ the optimal solution computed by Theorem 3, in which all coalitions are basic ones.

Consider any 2-strong Nash equilibrium ${\mathcal {C}}$.

For any coalition $C^*=\{i,j\}$ of ${\mathcal {C}}^*$ isomorphic to $K_2$, on the one hand we have that $\textsf {SW} (C^*)=2$. On the other hand, since ${\mathcal {C}}$ is a 2-strong Nash stable outcome, $u_i({\mathcal {C}})=1$ or $u_j({\mathcal {C}})=1$, because otherwise i and j could jointly perform an improving move. Thus, $u_i({\mathcal {C}}) + u_j({\mathcal {C}})\ge 1$, whereas $u_i({\mathcal {C}}^*) + u_j({\mathcal {C}}^*) =2$.

For any coalition $C^*=\{i,j,k\}$ of ${\mathcal {C}}^*$ isomorphic to $K_3$, on the one hand we have that $\textsf {SW} (C^*)=3$. On the other hand, since ${\mathcal {C}}$ is a 2-strong Nash stable outcome, at least 2 agents among i, j, k must have utility 1 in ${\mathcal {C}}$, because otherwise there would exist two agents aiming at jointly perform an improving move: a contradiction to the 2-strong Nash stability of ${\mathcal {C}}$. Thus, $u_i({\mathcal {C}}) + u_j({\mathcal {C}})+ u_k({\mathcal {C}}) \ge 2$, whereas $u_i({\mathcal {C}}^*) + u_j({\mathcal {C}}^*)+ u_k({\mathcal {C}}^*) =3$.

For any $h=1,2,3$, let $N_h \subseteq N$ be such that for any $j \in N_h$, $C^*_j$is isomorphic to $K_h$. Since agents being in coalitions of ${\mathcal {C}}^*$ isomorphic to $K_1$ do not contribute to $\textsf {SW} ({\mathcal {C}}^*)$, we obtain

$$\begin{aligned} \frac{\textsf {SW} ({\mathcal {C}}^*)}{\textsf {SW} ({\mathcal {C}})}\le & {} \frac{\sum _{j \in N_2} \textsf {SW} (C_j^*) + \sum _{j \in N_3} \textsf {SW} (C^*_j)}{\sum _{j \in N_2} \sum _{i \in C^*_j}{u_i({\mathcal {C}})} + \sum _{j \in N_3} \sum _{i \in C^*_j}{u_i({\mathcal {C}})}}\\\le & {} \frac{\sum _{j \in N_2} \textsf {SW} (C_j^*) + \sum _{j \in N_3} \textsf {SW} (C^*_j)}{\sum _{j \in N_2} \frac{1}{2} \textsf {SW} (C^*_j) + \sum _{j \in N_3} \frac{2}{3}\textsf {SW} (C^*_j)}\\\le & {} \frac{\sum _{j \in N_2} \textsf {SW} (C_j^*) + \sum _{j \in N_3} \textsf {SW} (C^*_j)}{\frac{1}{2}\left( \sum _{j \in N_2} \textsf {SW} (C^*_j) + \sum _{j \in N_3} \textsf {SW} (C^*_j)\right) }=2. \end{aligned}$$

$\square$

From Theorems 6 and 7, we immediately get the following result.

Corollary 2

The strong price of anarchy for unweighted graphs is 2.

4 Nash stable outcomes

In this section we consider Nash stable outcomes. We start by showing that there exists a graph G containing negative edge-weights such that the game induced by G admits no Nash stable outcome. This result is very similar to Lemma 1 of [14].

Theorem 8

There exists a graph G containing edges with negative weights such that ${\mathcal {G}(G)}$ admits no Nash stable outcome.

Fig. 8

The graph G used in Theorem 8

Proof

Let G be the graph in Fig. 8 and fix a Nash stable outcome ${\mathcal {C}}$. It is easy to see that, for $-M$ small enough, agents 1 and 3 cannot belong to the same coalition. By contrast, agents 2 and 4 must belong to the same coalition since otherwise the utility of agent 4 would be zero. Let $C_j$ be the coalition containing agents 2 and 4. If $C_j=\{2, 4\}$, then agent 1 wants to join the coalition and improve her utility from zero to $10/2=5$ thus contradicting the fact that ${\mathcal {C}}$ is Nash stable. If $C_j\supset \{2, 4\}$, then, since agents 1 and 3 cannot belong to the same coalition, it must be $|C_j|= 3$. Moreover, there exists a coalition $C_i$ containing exactly one of the two agents 1 and 3. Hence, we get the utility of agent 2 in ${\mathcal {C}}$ is $11/2< 10$, while 10 is the utility in joining coalition $C_i$, which rises again a contradiction. Since all possibilities for $C_j$ have been considered, it follows that a Nash stable outcome cannot exist. $\square$

We further show that there exists a dynamic of infinite length for games played on unweighted graphs.

Theorem 9

There exists an unweighted graph G such that ${\mathcal {G}(G)}$ does not possess the finite improvement path property, even under best-response dynamics.

Fig. 9

The graph G used in Theorem 9

Proof

Let us consider the game induced by be the graph G depicted in Fig. 9. Let us analyze the dynamics that starts from the coalitions structure ${\mathcal {C}}=\{\{1,\dots ,7\}, \{8\}\}$, where agents $\{1,\dots ,7\}$ are together in a coalition, and agent 8 is alone in another one. It is not difficult to check that, if the agents perform their unique (best) improving moves in the following exact ordering 6, 1, 7, 2, 3, 4, 6, 1, 7, 4, 3, 2, we get back to the starting coalitions structure ${\mathcal {C}}$.

$\square$

Despite the above negative results, it is easy to see that, if a graph G does not contain negative edge-weights, then the game induced by G admits a Nash equilibrium, that is the outcome where all the agents are in the same coalition. Therefore, in the next subsections we characterize the efficiency of Nash stable outcomes in modified fractional hedonic games played on general graphs with non-negative edge-weights.

4.1 Price of anarchy

We first show that the price of anarchy grows linearly with the number of agents, even for the special case of unweighted paths.

Theorem 10

There exists an unweighted path G such that $\textsf {PoA} (\mathcal {G}(G)) = \varOmega (n)$.

Proof

Let G be an unweighted simple path with an even number n of nodes. Notice that, since in this setting the utility of an agent in any outcome is at most 1, the optimum solution is given by a perfect matching, that is, $\textsf {SW} (OPT) = n$. However, when all the nodes are in the same coalition, we obtain a Nash stable outcome ${\mathcal {C}}$ such that $\textsf {SW} ({\mathcal {C}})= \frac{2*(n-2)+2}{n-1}$. Hence, the claim follows. $\square$

We are able to show an asymptotically matching upper bound, holding for weighted (positive) graphs.

Theorem 11

For any weighted graph with non-negative edge-weights G,

$$\begin{aligned} \textsf {PoA} (\mathcal {G}(G))\le n-1. \end{aligned}$$

Proof

We notice that in any Nash equilibrium ${\mathcal {C}}$, any agent i has utility $u_i({\mathcal {C}}) \ge \frac{w^{i}_{max}}{n-1}$, since agent i can always join the coalition containing the agent j, where $j=\text {arg}\max _{z \in N} w_{i,z}$. On the other hand, in the optimal outcome OPT, we have that any agent i has utility such that $u_i(OPT)\le \frac{(|OPT(i)|-1)*w^{i}_{max}}{|OPT(i)|-1} = w^{i}_{max}$. Hence, by summing over all agents, the theorem follows. $\square$

4.2 Price of stability

On the one hand, since we have proved in Corollary 1 that, for the setting of unweighted graphs, the strong price of stability is 1, it directly follows that also the price of stability is 1 in this setting, because any strong Nash equilibrium is also a Nash equilibrium.

On the other hand, in the weighted case, given the upper bound to the price of anarchy provided in Theorem 11, the following theorem shows an asymptotically matching lower bound to the price of stability.

Theorem 12

There exists a weighted star G with non-negative edge weights such that $\textsf {PoS} (\mathcal {G}(G))= \varOmega (n)$.

Fig. 10

The star graph G used in Theorem 12

Proof

Let G be a star with n nodes centered in node 1 as depicted in Fig. 10. The weights of the edges are such that there exists a leaf node 2 such that $w_{1,2}=1$, while for all the other leaf nodes $i \ne 1,2$ we have $w_{1,i}=\epsilon$, for an arbitrarily small $\epsilon >0$, (for instance $0< \epsilon < \frac{1}{n}$).

Notice that the grand coalition (i.e., the outcome in which all agents belong to the same coalition) is the unique Nash stable outcome and has social welfare equal to $\frac{2+2(n-2)\epsilon }{n-1}$. In fact, in any Nash equilibrium, all the leafs must be in the coalition together with the center 1. On the other hand, the coalition containing only agents 1 and 2 yields a social value of 2, and thus the theorem follows. $\square$

5 Core stable outcomes

In this section we consider the strict core and the core of MFHGs. We first show that the strict core of $\mathcal {G}(G)$ could be empty, even if G is unweighted.

Theorem 13

There exists an unweighted graph G such that $\textsf {SCR} (\mathcal {G}(G))=\emptyset$.

Proof

Let G be a path with $n=3$ nodes $\{1, 2, 3\}$.

If ${\mathcal {C}}=\{\{1\},\{2\}, \{3\}\}$, $C=\{1,2\}$ is a blocking coalition. In fact, moving from their coalition in ${\mathcal {C}}$ to coalition C, both agents 2 and 3 increase their utility form 0 to 1.

If ${\mathcal {C}}=\{\{1, 2\}, \{3\}\}$, $C=\{2,3\}$ is a weakly blocking coalition. In fact, moving from their coalition in ${\mathcal {C}}$ to coalition C, agent 3 increases her utility form 0 to 1 and agent 2 does not change her utility. The case ${\mathcal {C}}=\{\{ 1\}, \{2, 3\}\}$ is symmetric.

Finally, if ${\mathcal {C}}=\{\{1, 2, 3\}\}$, $C=\{1,2\}$ is a weakly blocking coalition. In fact, moving from their coalition in ${\mathcal {C}}$ to coalition C, agent 1 increases her utility form $\frac{1}{2}$ to 1 and agent 2 does not change her utility.

Since all possibilities for ${\mathcal {C}}$ have been considered, it follows that a strict core stable coalition does not exist. $\square$

Given the negative result of Theorem 13 concerning the strict core of modified fractional hedonic games, in the following we focus on the core of these games.

We first show that for any graph G, the core of the game $\mathcal {G}(G)$ is not empty, and that a core stable outcome approximating the optimal social welfare by a factor of 2 can be computed in polynomial time.

Theorem 14

Given any graph $G=(N,E,w)$, there exists a polynomial time algorithm for computing a core stable coalition structure ${\mathcal {C}}$ such that $\textsf {SW} ({\mathcal {C}}) \ge \frac{1}{2} \textsf {SW} ({\mathcal {C}}^*(\mathcal {G}(G)))$ and all coalitions in ${\mathcal {C}}$ are of cardinality at most 2.

Proof

Consider the following algorithm, working in phases $t=1,2,\dots$. Let $G^0=(N^0,E^0,w)$ be the subgraph of G such that $N^0 = N$ and $E^0=\{e \in E: w(e)\ge 0\}$, that is, $G^0$ has the same vertices as G and only contains the edges of G of non-negative weight. For any $t\ge 1$, let $G^t=(N^t, E^t, w)$ be the graph obtained after phase t. In any phase $t \ge 1$, a new coalition isomorphic to $K_2$ is added to ${\mathcal {C}}$ as follows: Let $e^{t-1}=\{i,j\}$ be an edge in $E^{t-1}$ of maximum weight $w_{i,j}=\max _{e \in E^{t-1}}w_e$. We add to ${\mathcal {C}}$ the coalition formed by i and j, i.e., ${\mathcal {C}}= {\mathcal {C}}\cup \{i,j\}$. Moreover, let $G^t$ such that $N^t = N^{t-1} \setminus \{i,j\}$ and $E^t \subset E^{t-1}$ the subset of edges of $G^0$ induced by nodes $N^t$.

When $E^t=\emptyset$, the algorithm ends returning ${\mathcal {C}}\cup \{ \{i\}|i \in N^t\}$. Since at each phase at least an edge is removed from the graph, the algorithms terminates in at most |E| phases returning an outcome with all coalitions of cardinality at most 2.

We first show that ${\mathcal {C}}$ is a core stable outcome of $\mathcal {G}(G)$. Remind that, for any possible outcome, $u_i({\mathcal {C}}) \le w^{i}_{max}$. Therefore, in the outcome ${\mathcal {C}}$, agents i and j selected at phase $t=1$ are achieving the maximum utility they can hope for. It implies that such agents cannot belong to any strongly blocking coalition. The proof continues by induction as follows. Suppose that all the agents selected until phase q, i.e., agents belonging to $N \setminus N^q$, cannot belong to any strongly blocking coalition, then agents $i_{q+1}$ and $j_{q+1}$ selected in the phase $q+1$ cannot belong to any strongly blocking coalition as well. In fact, suppose that such agents have a certain utility x in the coalition ${\mathcal {C}}$. For the inductive hypothesis we have that they can create a strongly blocking coalition only with agents belonging to $N^{q+1}$. However, since the edge $(i_{q+1},j_{q+1})$ has the maximum weights in $G^{q+1}$, it implies that they cannot get utility greater than x. Finally, for the agents that are not matched, i.e., agents that are alone in a coalition, since they form and independent set, they cannot form a strongly blocking coalition, and this finishes the proof.

It remains to show that $\textsf {SW} ({\mathcal {C}}) \ge \frac{1}{2} \textsf {SW} ({\mathcal {C}}^*(\mathcal {G}(G)))$. First of all notice that in any phase t, a coalition contributing $2 w_{e^{t-1}}$ to the social welfare is added to ${\mathcal {C}}$; we thus obtain that

$$\begin{aligned} \textsf {SW} ({\mathcal {C}}) = \sum _{t \ge 1} 2 w_{e^{t-1}}. \end{aligned}$$

For any $e \in E$, let $f(e,i) \in \{0,1,2\}$ be the number of endpoints of e belonging to coalition $C^*_i$. It is possible to bound $\textsf {SW} ({\mathcal {C}}^*(\mathcal {G}(G)))$ as follows:

$$\begin{aligned} \textsf {SW} ({\mathcal {C}}^*)= & {} \sum _{C^*_i \in {\mathcal {C}}^*} \textsf {SW} (C^*_i)\nonumber \\= & {} \sum _{C^*_i \in {\mathcal {C}}^*} \sum _{t \ge 1} \sum _{e \in E_{C^*_i} \cap (E^{t} \setminus E^{t-1})} \frac{2 w_e}{|C^*_i-1|}\nonumber \\\le & {} \sum _{C^*_i \in {\mathcal {C}}^*} \sum _{t \ge 1} \frac{2 f(e^{t-1},i) w_{e^{t-1}} (|C^*_i-1|)}{|C^*_i-1|} \end{aligned}$$

(4)

$$\begin{aligned}= & {} \sum _{t \ge 1} \sum _{C^*_i \in {\mathcal {C}}^*} 2 f(e^{t-1},i) w_{e^{t-1}}\nonumber \\= & {} \sum _{t \ge 1} 4 w_{e^{t-1}}, \end{aligned}$$

(5)

where inequality 4 holds because $w_{e^{t-1}}=\max _{e \in E^{t-1}}w_e$ and every endpoint of $e^{t-1}$ belonging to $C^*_i$ can have at most $|C^*_i-1|$ adjacent edges (notice that all edges in $E^{t} \setminus E^{t-1}$ are adjacent to an endpoint of $e^{t-1}$), and equality 5 holds because, given that $C^*_1,\ldots ,C^*_{\ell ^*}$ are a partition of N, it follows by definition of f that $\sum _{C^*_i \in {\mathcal {C}}^*}f(e^{t-1},i)=2$. Therefore,

$$\begin{aligned} \frac{\textsf {SW} ({\mathcal {C}}^*(\mathcal {G}(G)))}{\textsf {SW} ({\mathcal {C}})} \le \frac{\sum _{t \ge 1} 4 w_{e^{t-1}}}{\sum _{t\ge 1} 2 w_{e^{t-1}}} = 2. \end{aligned}$$

$\square$

As a direct consequence of Theorem 14, the following corollary holds.

Corollary 3

For any graph G, $\textsf {CPoS} (\mathcal {G}(G)) \le 2$.

Fig. 11

The graph G used in Theorem 15

We now show a matching lower bound on the $\textsf {CPoS}$ for the case of weighted graphs.

Theorem 15

For any $\epsilon >0$, there exists a weighted graph G such that

$$\begin{aligned} \textsf {CPoS} (\mathcal {G}(G)) \ge 2-\epsilon . \end{aligned}$$

Proof

Consider the graph G represented in Fig. 11.

On the one hand, it is easy to check that the only core stable coalition ${\mathcal {C}}$ is the one where the two central agents 2 and 3 are together in the same coalition, while agent 1, as well as agent 4, is alone in different coalitions, i.e., ${\mathcal {C}}=\{\{1\},\{2, 3\},\{4\}\}$. Notice that $\textsf {SW} ({\mathcal {C}})=2\left( 1+\frac{\epsilon }{2}\right)$. On the other hand, the outcome ${\mathcal {C}}'=\{\{1, 2\},\{3, 4\}\}$ has a social welfare equal to 4, and therefore $\textsf {SW} ({\mathcal {C}}^*)\ge 4$. It follows that $\textsf {CPoS} (\mathcal {G}(G)) \ge \frac{4}{2\left( 1+\frac{\epsilon }{2}\right) }\ge 2-\epsilon$. $\square$

For unweighted graphs, it is easy to see that the optimum outcome produced in Theorem 5 is also core stable, and therefore the following proposition holds:

Proposition 1

For any unweighted graph G, $\textsf {CPoS} (\mathcal {G}(G))=1$.

We are also able to prove a constant upper bound to the core price of anarchy.

Theorem 16

For any graph G, $\textsf {CPoA} (\mathcal {G}(G))\le 4$.

Proof

Let ${\mathcal {C}}'$ be the solution computed by Theorem 14, in which all coalitions have cardinality at most 2.

Consider any core stable outcome ${\mathcal {C}}$.

For any coalition $C'=\{i,j\}$ of ${\mathcal {C}}'$ isomorphic to $K_2$, on the one hand we have that $\textsf {SW} (C')=2$. On the other hand, since ${\mathcal {C}}$ is a core stable outcome, $u_i({\mathcal {C}})=1$ or $u_j({\mathcal {C}})=1$, because otherwise coalition $\{i,j\}$ would strongly block outcome ${\mathcal {C}}$. Thus, $u_i({\mathcal {C}}) + u_j({\mathcal {C}})\ge 1$, whereas $u_i({\mathcal {C}}') + u_j({\mathcal {C}}') =2$.

Let $N' \subseteq N$ be such that for any $j \in N'$, $C'_j$ is isomorphic to $K_2$. Since agents being in all other coalitions of ${\mathcal {C}}'$ do not contribute to $\textsf {SW} ({\mathcal {C}}')$, we obtain

$$\begin{aligned} \frac{\textsf {SW} ({\mathcal {C}}')}{\textsf {SW} ({\mathcal {C}})}\le & {} \frac{\sum _{j \in N'} \textsf {SW} (C'_j)}{\sum _{j \in N'} \sum _{i \in C'_j}{u_i({\mathcal {C}})}}\\\le & {} \frac{\sum _{j \in N_2} \textsf {SW} (C'_j) }{\sum _{j \in N_2} \frac{1}{2} \textsf {SW} (C'_j) }=2. \end{aligned}$$

The claim follows because, by Theorem 14, $\textsf {SW} ({\mathcal {C}}^*(\mathcal {G}(G))) \le 2 \cdot \textsf {SW} ({\mathcal {C}}')$. $\square$

For unweighted graphs we get the following tight characterization on the core price of anarchy.

Proposition 2

For any unweighted graph G, $\textsf {CPoA} (\mathcal {G}(G))=2$.

Proof

For the lower bound, it is easy to see that, given an unweighted path of four nodes 1, 2, 3, 4, the outcome ${\mathcal {C}}=\{\{1\}, \{2,3\}, \{4\}\}$ is core stable and has social welfare 2, while the optimum outcome ${\mathcal {C}}^*=\{\{1,2\},\{3,4\}\}$ has social welfare 4. A matching upper bound can be obtained by exploiting the same arguments used in the proof of Theorem 7. $\square$

6 Conclusions

In this paper we have considered strong Nash stable, Nash Stable, and core stable outcomes for symmetric modified fractional hedonic games, a natural class of succinctly representable hedonic games. We have shown conditions under which the existence of these natural stable outcomes is guaranteed and have provided polynomial time algorithms for computing them. We have further analyzed the performances of Nash stable, strong Nash Stable and core stable outcomes, by means of the widely used notions of price of anarchy (resp. strong price of anarchy and core price of anarchy) and price of stability (resp. strong price of stability and core price of stability): in this respect, we have shown tight (resp. asymptotically tight and almost tight) bounds on the performance of strong Nash stable (resp. Nash stable and core stable) outcomes.

If we put our paper in the context of the related work on additively separable hedonic games and fractional hedonic games (see the Related Work subsection for a comprehensive view of these results), it is worth noticing that there are several somewhat surprising results. In fact, as already remarked in Sect. 1.3, the small disparity (in the denominator of the agent utility definition) differentiating MFHGs from the classical fractional ones yields a different behavior of stable outcomes:

• for MFHGs, the existence of k-strong Nash stable outcomes (for any k) in the case of unweighted undirected graphs is guaranteed, whilst in fractional (unweighted undirected) hedonic games they are not guaranteed to exist even for $k=2$;

• for MFHGs played on unweighted undirected graphs, it is possible to compute in polynomial time a strong Nash stable outcome that is also optimum, and therefore the strong price of stability is 1, whilst for the corresponding fractional hedonic games the problem of computing an optimum outcome is NP-hard and the price of stability is greater than 1.

• for MFHGs, the core is not empty for any undirected graph and a core stable outcome can be computed in polynomial time, whilst for the corresponding fractional hedonic games the core may be empty and it is NP-hard deciding the existence.

Moreover, some other results are similar to the ones obtained for fractional hedonic games, and at the same time they substantially differ from the ones holding for the class of additively separable games (in which the utility of an agent has the denominator equal to 1). In fact, on the one hand, for both MFHGs and fractional hedonic games, Nash stable outcomes are guaranteed to exist for undirected graphs with only positive weights, but not for general weights; moreover, the price of stability grows linearly with the number of agents. On the other hand, for additively separable hedonic games, the existence of a Nash stable outcome in undirected graphs is guaranteed by a potential function argument also showing that the price of stability is equal to 1.

It could be worth trying to extend our results to the more general setting of asymmetric modified fractional hedonic games, in which the underlying graph is directed. To this respect, on the one hand, if all weights are positive, the grand coalition is Nash stable and therefore Nash equilibria are always guaranteed to exist and the same proof as the one of Theorem 11 shows that the price of anarchy is at most $n-1$, while the lower bound holding for the more specific case of undirected graph clearly applies to this more general setting. On the other hand, i.e., if also negative weights are allowed, the non existence of Nash stable outcomes proved in Theorem 8 directly implies the non existence of Nash stable outcomes for this more general setting. Moreover, if we turn our attention to strong Nash stable outcomes, the simple graph depicted in Fig. 12 shows that no 2-strong Nash stable outcome is guaranteed to exist even when considering unweighted graphs. In fact, agent 3 is stable only when is in the same coalition of agent 2, while agents 1 and 2 aim at staying together without other agents.

Fig. 12

The directed graph not admitting any 2-strong Nash stable outcome

Finally, the existence and the analysis of efficiency of core stable outcomes constitute an interesting open research direction.

There are other open problems suggested by our work. First of all, it would be nice to close the gap between the lower bound of 2 for the core price of stability and the upper bound of 4 for the core price of anarchy, and to study the complexity of computing an optimal outcome when the graph is weighted.

It would also be interesting to adopt different social welfare than the one considered in this paper. An example could be that of maximizing the minimum utility among the agents. A first step along this direction has been recently pursued in [34].

Finally, another research direction could be that of designing truthful mechanisms for MFHGs that perform well, for instance, with respect to the sum of the agents’ utility or the minimum utility among the agents.