Additively Separable Hedonic Games with Social Context ^†

Abstract

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 social context additively separable hedonic games (SCASHGs). 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.

1. Introduction

In many economic, social and political situations, individuals carry out activities in groups rather than alone and on their own. In these scenarios, understanding the happiness of each member of the group becomes of crucial importance. As examples, the utility of an individual in a group sharing a resource depends both on the consumption level of the resource and on the identity of the members in the group; similarly, the utility for a party belonging to a political coalition depends both on the party trait and on the identity of its members. Moreover, another important issue is that of investigating the dynamics that regulates coalition formation.

Dréze and Greenberg [1] introduced hedonic games, in which players have preferences over the set of all possible player coalitions. In particular, the utility of a player only depends on the composition of the coalition (or group) she belongs to. Hedonic games constitute a framework for formally studying the stability and the evolution of the process of forming player coalitions. Given that they model natural behavioral dynamics of real-life situations, this class of games has received great interest in the literature: in economic, social and political environments, in fact, individuals perform activities in groups rather than by themselves. Consider, for instance, the following scenarios: a company has to assign its employees to different work teams so that they can profitably collaborate; in a social network, users want to form groups in which they can speak of and share common interests.

Additively separable hedonic games constitute a natural and succinctly representable class of hedonic games. In these games, each player has a value for any other player, and the utility of a coalition to a particular player is simply the sum of the values she assigns to the members of her coalition. Additive separability satisfies a number of desirable axiomatic properties [2] and are the non-transferable utility generalization of graph games studied by Deng and Papadimitriou [3]. While the standard model of additively separable hedonic games assumes that players are totally selfish, in this paper we are interested in analyzing the case in which players take into account also the happiness of their friends, therefore adding to the original model a sort of altruism. Coming back to the above described scenarios, it is likely that, among the corporate employees, several friendship relations exist, not necessarily between people able to profitably collaborate together. Moreover, social network users often include people coming from the same family; even if they are of different ages and therefore are expected to gladly belong to different groups, they are also interested in the happiness of their relatives. We call these games Social Context Additively Separable Hedonic Games (SCASHGs) and we believe that they are able to model in a more accurate way the phenomenon of coalition formation in many realistic scenarios. In fact, in SCASHGs the behavior of every player also depends on the happiness of her friends, as it is in the above described scenarios.

In SCASHGs, valuations are additive and each player i has a valuation $v_{ij}$ for any other player j, but there is a crucial difference with respect to the classical additively separable hedonic games: while in the classical model the utility of a coalition to a particular player is simply given by the sum of the valuations she assigns to the members of her coalition, in SCASHGs there is another additive term that contributes to form the utility of a player, that is equal to the sum of the valuations her friends assign to the members of their own coalitions (this contribution is multiplied by a given parameter $\alpha \in [0,1]$). In particular, for $\alpha =0$, SCASHGs are equivalent to the classical additively separable hedonic games (i.e., a totally selfish setting is considered), while for $\alpha =1$ a fully altruistic setting can be modeled.

In order to model the friendship relations, a SCASHG is also defined by a graph representing an underlying social network: nodes are players and an edge connecting two players expresses friendship between them. Arguably, as a first step in the study of SCASHGs, it is natural to consider symmetric friendship relations and therefore, in this paper, we focus on undirected graphs.

In Figure 1, for example, we can see that the utility of player 5 is equal to $v_{1,5}+v_{2,5}+\alpha (v_{1,5}+v_{2,5}+v_{3,4})=2+3+\alpha (2+3+1)$, where $2+3$ is the sum of valuations of the players in her coalition and $\alpha (2+3+1)$ is the sum of valuations her friends 1, 2 and 3 assign to the members of their own coalitions, multiplied by $\alpha$.

Our aim is to study the existence and performance of natural stable outcomes for SCASHGs. We will focus on Nash stable outcomes, i.e., outcomes in which no player can improve her utility by unilaterally changing her own coalition. In particular, we evaluate the performance of Nash outcomes for SCASHGs by means of the widely used notions of price of anarchy and price of stability: the former is defined as the ratio between the social optimum value and the social value of the worst stable outcome, while the latter is defined as the ratio between the social optimum value and the social value of the best stable outcome.

1.1. Our Results

First of all, we provide an exact potential function for SCASHGs, thus proving that these games always possess a pure Nash equilibrium and also that the convergence to Nash equilibria is guaranteed. In order to evaluate the performance of SCASHGs, we consider two social welfare functions. The first social function, $\overline{\mathsf{SW}}$, is given by the summation, for each player, of the values she assigns to the members of her coalition, while the second social function, denoted by $\mathsf{SW}$, is the summation of the players’ utilities (taking into account, for any player, also the contribution due to the valuations of her friends multiplied by $\alpha$). In fact, we evaluate, for both of them, the performance of the Nash outcomes by means of the notions of price of anarchy and price of stability ($\mathsf{PoA}$ and $\overline{\mathsf{PoA}}$ denote the price of anarchy with respect to $\mathsf{SW}$ and $\overline{\mathsf{SW}}$, respectively; analogously $\mathsf{PoS}$ and $\overline{\mathsf{PoS}}$ denote the price of stability with respect to $\mathsf{SW}$ and $\overline{\mathsf{SW}}$, respectively).

In presence of negative valuations, both $\mathsf{PoS}$ and $\overline{\mathsf{PoS}}$ (and therefore also $\mathsf{PoA}$ and $\overline{\mathsf{PoA}}$) can be unbounded. Furthermore, in some cases we are able to provide instances in which the social value of any equilibrium $\mathcal{C}$ is negative while the optimal solution lead to a positive outcome.

We subsequently turn our attention to the case of non-negative valuations and prove that the price of anarchy is $\Theta (n)$, while the price of stability is 1.

1.2. Related Work

Hedonic games have been broadly studied in the literature. They have been first considered by Dréze and Greenberg [1], who analyze them under a cooperative perspective. Bogomolnaia and Jackson [4] and Banerjee et al. [5] then have defined hedonic games in their present form as a simple but very versatile model of coalition formation. Feldman et al. [6] 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. Peters and Elkind [7] 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.

Additively separable hedonic games have been first considered by Bogomolnaia and Jackson [4] who show that Nash stable outcomes are not guaranteed to exist for games with asymmetric valuations. However, for symmetric valuations, the existence of a Nash stable outcome is guaranteed by potential function argument [4]. Ballester [8] and Sung and Dimitrov [9] 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 [10] 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. [11] show that checking the existence of a core stable outcome is NP-hard even for symmetric valuations. Concerning the performance of Nash stable outcomes in additively separable hedonic games with symmetric valuations, it is easy to check that the price of anarchy is unbounded [12] 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).

Fractional hedonic games are close to additively separable ones. The difference is that the utility of each player is divided by the size of her coalition. They have been first considered by Aziz et al. [13] (see also [14]), who prove that the core can be empty for asymmetric valuations and that it is not empty for some special cases. Brandl et al. [15] also study the existence of core as well as individual stability in fractional hedonic games. Bilò et al. [16] consider Nash stable outcomes for fractional hedonic games and study their existence and complexity. Kaklamanis et al. [17] also consider Nash stable outcomes and provide some improved results on the price of stability. Carosi et al. [18] consider local core stability in fractional hedonic games with binary symmetric valuations and show that any local core dynamics converges, which implies that a local core stable coalition structure always exists. Finally, Aziz et al. [19] consider the computational complexity of computing welfare maximizing partitions (not necessarily Nash stable) for fractional hedonic games played on undirected graphs.

Modified fractional hedonic games are very similar to fractional hedonic ones. The difference is that the utility of each player is averaged over all the other members of that coalition (i.e., excluding herself). Olsen [20] is the first to consider these games and investigates computational issues about Nash stable outcomes. Monaco et al. [21,22] completely characterize the existence of fundamental stable outcomes and show tight results on their performance. Elkind et al. [23] study the set of Pareto optimal outcomes for modified fractional hedonic games with symmetric valuations.

From a different perspective, strategy proof mechanisms for additively separable hedonic and fractional hedonic games have been proposed in [24,25]. Moreover, Flammini et al. [26] consider the problem of maximizing the social welfare in additively separable and fractional hedonic games in the online setting. Hedonic games are being widely investigated also under different utility definitions: For instance, in [27,28], coalition formation games, in which player utilities are proportional to their harmonic centralities in the respective coalitions, are considered.

In our paper, we deal with selfish players having also a certain degree of altruism. To this respect, our work is related to social context games. These games have been introduced in [29] and are defined by an underlying game in strategic form, and a social context consisting of an undirected graph and an aggregation function. In [29], the authors consider resource selection games as the underlying game and they study the existence of pure strategy Nash equilibrium. Building on this model, Bilò et al. [30] investigate social context games in which the underlying games are linear congestion games and Shapley cost sharing games, while the aggregation functions are min, max and sum. Moreover, Anagnostopoulos et al. [31] study the effects of the altruistic behavior of players showing that the price of anarchy may increase as the players become more altruistic. They show that this increase is modest for congestion games and min-sum scheduling games, whereas it might be drastic for generalized second price auctions. The interests on altruistic players have been also modeled and studied by Hoefer and Skopalik [32]: they focus on the existence and complexity of pure Nash equilibria with altruistic players in atomic congestion games. Chen et al. [33] study the inefficiency of equilibria for several classes of games such as cost-sharing games, utility games and linear congestion games. Salehi-Abari and Boutilier [34] study social choice with empathetic preferences and their local empathetic model is related to the model presented in [35]. Finally, Brânzei and Larson [36] study social distance games. In these games a player’s opinion on her friends (players of distance one) has the highest weight while her opinion on players farther away counts less.

To the best of our knowledge, few papers deal with the notion of altruism in hedonic games. Nguyen et al. [35] define altruistic hedonic games where the satisfaction of players’ friends is taken into account according to three degrees of altruism, from being selfish first, over aggregating opinions of a player and her friends equally, to altruistically letting one’s friends decide first. They study both the axiomatic properties of these games and the computational complexity of problems related to common stability concepts. In [37], Umar and Mesbah model the problem of joint coalition formation and bandwidth allocation in ad hoc radio networks made of selfish/altruistic nodes as a hedonic coalition formation game with non-transferable utility. The authors study the computational complexity and convergence properties of the proposed hedonic algorithm under selfish and altruistic preferences, and present means to guarantee Nash stability.

Finally, it is also worth mentioning some related literature on network formation games, in which interestingly the considered games are shown to be potential games as in our paper: in [38], Badev deals with a setting in which the utility of the players is influenced by the friendship relations and vice-versa, while Kinateder and Merlino [39] study a network creation game in which benefits are shared among neighbors. Mele [40] proposes an empirical model of social network formation, combining strategic and random connections among players. Bourlès et al. [41] provide an interesting analysis of altruism in networks: agents are embedded in a fixed network and care about the well-being of their network neighbors, i.e., they may provide financial support to their poorer friends.

1.3. Paper Organization

The paper is organized as follows. In Section 2 we formally define social context additively separable hedonic games. The technical contributions of the paper are then presented in Section 3, Section 4 and Section 5 which address the existence of Nash outcomes, the results on the price of anarchy and those on the price of stability, respectively. Finally, in Section 6 we list some interesting open problems.

2. Model

For an integer $k>0$, denote by $\left[k\right]$ the set $\{1,\dots ,k\}$.

We model Social Context Additively Separable Hedonic Games (SCASHGs) by means of a valuation function v, an undirected graph $G=(N,E)$ and a given parameter $\alpha \in [0,1]$. We denote with $n=\left|N\right|$ the number of nodes of G and with E the set of edges between the nodes, which represent the friendship relation. $v:N\times N\to \mathcal{R}$ is the symmetric valuation function. We do not require any dependence between v and H, thus allowing for two friends to have a mutual negative valuation (as it is in the scenario described in the Introduction, in which, among the corporate employees, several friendship relations may exist, not necessarily between people able to profitably collaborate together). Nevertheless, all obtained results also hold for the special notable case in which the valuations between friends have to be positive: all positive results clearly hold also in this specific setting, while all remaining ones (given in Proposition 1, Theorem 2, Theorem 5 and Theorem 6) exploit constructions in which negative valuations exist only between players not connected by an edge in graph G. For the sake of convenience, we adopt the notation $(i,j)$ and $v_{i,j}$ to denote the pair $\{i,j\}\in N\times N$ and its valuation $v(\{i,j\})$, respectively.

Given a symmetric valuation function v, an undirected graph $G=(N,E)$ and a value for $\alpha$, the Social Context Additively Separable Hedonic Game induced by G, v and $\alpha$, denoted as $\mathcal{G}(G,v,\alpha )$, is the game in which each node $i\in N$ is associated with a player. We assume that players are numbered from 1 to n and, for every $i\in \left[n\right]$, each player chooses to join a certain coalition among n candidate ones: the strategy ${\sigma }_i$ of player i is an integer $j\in \left[n\right]$, meaning that player i is selecting candidate coalition $C_j$.

A strategy profile $({\sigma }_1,\dots ,{\sigma }_n)$ directly induces an outcome $\mathcal{C}=\{C_1,C_2,\dots ,C_n\}$, in which, for any $j\in \left[n\right]$, $C_j=\left\{i\right|{\sigma }_i=j\}$. In turn, an outcome $\mathcal{C}=\{C_1,C_2,\dots ,C_n\}$ naturally induces a coalition structure, i.e., a partition of the set of players into $k\le n$ coalitions $C_{h_1},\dots ,C_{h_k}$ such that, for any $j\in \left[k\right]$, $C_{h_j}\ne \varnothing$ (i.e., empty candidate coalitions are excluded from the partition), ${\bigcup }_{j\in \left[k\right]}{C}_{h_j}=N$ and $C_{h_i}\cap C_{h_j}=\varnothing$ for any $i,j\in \left[k\right]$ with $i\ne j$. For the sake of brevity, we denote by $\mathcal{C}$ also the coalition structure induced by $\mathcal{C}$. If $i\in C_j$, we say that player i is a member of the coalition $C_j$. We denote by $\mathcal{C}(i)$ the coalition in $\mathcal{C}$ of which player i is a member. In an outcome $\mathcal{C}$, the utility of player i is defined as

$$u_i(\mathcal{C})=\overline{u_i}(\mathcal{C})+\alpha ·\sum _{(i,j)\in E}\overline{u_j}(\mathcal{C}),$$

where, for every $i\in \left[n\right]$, $\overline{u_i}(\mathcal{C})={\sum }_{j\in \mathcal{C}(i)}{v}_{i,j}$.

Each player 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 player 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 \left\{i\right\},C_j\cup \left\{i\right\}\}$. A player deviates if she changes the coalition she belongs to. Given an outcome $\mathcal{C}$, an improving move (or simply a move) for player 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, player i performs a best-response in coalition structure $\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})$. A player is stable if she cannot perform a move. An outcome is (pure) Nash stable (or a Nash equilibrium) if every player is stable. An improving dynamics, or simply a dynamics, is a sequence of improving 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 $\mathsf{N}(\mathcal{G}(G,v,\alpha ))$ the set of Nash stable outcomes of $\mathcal{G}(G,v,\alpha )$.

The social welfare of a coalition structure $\mathcal{C}$ is the summation of the players’ utilities, i.e., $\mathsf{SW}(\mathcal{C})={\sum }_{i\in N}{u}_i(\mathcal{C})$.

We define also a second social welfare function $\overline{\mathsf{SW}}(\mathcal{C})={\sum }_{i\in N}\overline{u_i}(\mathcal{C})$ which is given by the summation, for each player, of the valuations she assigns to the members of her coalition (without considering her friends’ utilities).

Given a game $\mathcal{G}(G,v,\alpha )$, an optimum coalition structure ${\mathcal{C}}^{*}(\mathcal{G}(G,v,\alpha ))$ (respectively $\overline{{\mathcal{C}}^{*}}(\mathcal{G}(G,v,\alpha ))$) is one that maximizes the social welfare $\mathsf{SW}$ (respectively $\overline{\mathsf{SW}})$ of $\mathcal{G}(G,v,\alpha )$. The price of anarchy of a social context additively separable hedonic game $\mathcal{G}(G,v,\alpha )$ is defined as the worst-case ratio between the social welfare of a socially optimum outcome and that of a Nash equilibrium. Formally,

$$\mathsf{PoA}(\mathcal{G}(G,v,\alpha ))=\underset{\mathcal{C}\in \mathsf{N}(\mathcal{G}(G,v,\alpha ))}{max}\frac{\mathsf{SW}({\mathcal{C}}^{*}(\mathcal{G}(G,v,\alpha )))}{\mathsf{SW}(\mathcal{C})},$$

and

$$\overline{\mathsf{PoA}}(\mathcal{G}(G,v,\alpha ))=\underset{\mathcal{C}\in \mathsf{N}(\mathcal{G}(G,v,\alpha ))}{max}\frac{\overline{\mathsf{SW}}(\overline{{\mathcal{C}}^{*}}(\mathcal{G}(G,v,\alpha )))}{\overline{\mathsf{SW}}(\mathcal{C})}.$$

Analogously, the price of stability of $\mathcal{G}(G,v,\alpha )$ is defined as the best-case ratio between the social welfare of a socially optimum outcome and that of a Nash equilibrium. Formally,

$$\mathsf{PoS}(\mathcal{G}(G,v,\alpha ))=\underset{\mathcal{C}\in \mathsf{N}(\mathcal{G}(G,v,\alpha ))}{min}\frac{\mathsf{SW}({\mathcal{C}}^{*}(\mathcal{G}(G,v,\alpha )))}{\mathsf{SW}(\mathcal{C})},$$

and

$$\overline{\mathsf{PoS}}(\mathcal{G}(G,v,\alpha ))=\underset{\mathcal{C}\in \mathsf{N}(\mathcal{G}(G,v,\alpha ))}{min}\frac{\overline{\mathsf{SW}}(\overline{{\mathcal{C}}^{*}}(\mathcal{G}(G,v,\alpha )))}{\overline{\mathsf{SW}}(\mathcal{C})}.$$

3. Nash Stable Outcomes

In this section we consider Nash stable outcomes.

We first show that the social context radically modifies the notion of stability of additively separable hedonic games. To this aim, consider the instance whose graph G and valuations are depicted in Figure 2. On the one hand, the coalition structure $\{1,2\},\left\{3\right\}$ is Nash stable when $\alpha =0$ (i.e., without considering social effects): the utility of players $1,2,3$ are $3,3,0$, respectively. Player 1 is earning as much as possible, and therefore has no incentive to deviate; player 2 would obtain a utility of 2 by joining the coalition of player 3, while it would obtain a utility of 0 by going alone; player 3 would obtain a utility of $-6$ by joining the coalition of players 1 and 2. On the other hand, the same coalition structure is not Nash stable when $\alpha =1$, i.e., when considering the effect of social context. In fact, in this case the utility of player 2 is again $3+1·0=3$, while she would obtain a utility of $2+1·2=4$ by joining the same coalition of player 3. Interestingly, it is also possible to build an instance in which the converse does not hold: Consider the instance exploited in the proof of Theorem 2. Here, the grand coalition is Nash stable and is such that every player is getting a negative utility. If we do not consider social context effects on the player utilities, the grand coalition would not be Nash stable because every player would clearly prefer to form a new coalition alone, so getting utility 0.

We now show that a stable outcome is guaranteed to exist and also that the finite improvement path property holds for SCASHGs, because these games admit the potential function.

$$\mathsf{\Phi }(\mathcal{C})=\frac{1}{2}\sum _{i\in N}{\widehat{u}}_i(\mathcal{C}),$$

with ${\widehat{u}}_i(\mathcal{C})={\sum }_{j\in \mathcal{C}(i)}{v}_{i,j}^{\prime }$, where, for each pair of players $(i,j)$, we define $v_{i,j}^{\prime }=v_{i,j}·(1+\alpha )$ if $(i,j)\in E$ and $v_{i,j}^{\prime }=v_{i,j}$ if $(i,j)\notin E$.

Thus, we can rewrite the potential function $\mathsf{\Phi }(\mathcal{C})$ as

$$\mathsf{\Phi }(\mathcal{C})=\sum _{j\in \mathcal{C}(i)}{v}_{i,j}+\alpha ·\sum _{j\in \mathcal{C}(i),(i,j)\in E}{v}_{i,j}.$$

In the following theorem, we prove that $\mathsf{\Phi }(\mathcal{C})$ is an exact potential function for our game.

Theorem 1.

Φ is a potential function for SCASHGs.

Proof. 

Given two stable outcomes $\mathcal{C}$ and ${\mathcal{C}}^{\prime }$ where ${\mathcal{C}}^{\prime }$ is obtained from $\mathcal{C}$ after a player i performs a move, we prove that the following holds:

$$\mathsf{\Phi }({\mathcal{C}}^{\prime })-\mathsf{\Phi }(\mathcal{C})=u_i({\mathcal{C}}^{\prime })-u_i(\mathcal{C}).$$

(1)

For the left hand side of Equation (1), by applying the definition of $\mathsf{\Phi }$, we obtain that:

$$\begin{array}{cc}\hfill \mathsf{\Phi }({\mathcal{C}}^{\prime })-\mathsf{\Phi }(\mathcal{C})& =\frac{1}{2}\left(\sum _{j\in N}{\widehat{u}}_j({\mathcal{C}}^{\prime })-\sum _{j\in N}{\widehat{u}}_j(\mathcal{C})\right)=\frac{1}{2}\sum _{j\in N}\left({\widehat{u}}_j({\mathcal{C}}^{\prime })-{\widehat{u}}_j(\mathcal{C})\right)\hfill \\ \hfill & =\frac{1}{2}·2\left(\sum _{j\in {\mathcal{C}}^{\prime }(i)}{v}_{i,j}^{\prime }-\sum _{j\in \mathcal{C}(i)}{v}_{i,j}^{\prime }\right)\hfill \\ \hfill & =\sum _{j\in {\mathcal{C}}^{\prime }(i)}{v}_{i,j}+\alpha \sum _{j\in {\mathcal{C}}^{\prime }(i),(i,j)\in E}{v}_{i,j}-\sum _{j\in \mathcal{C}(i)}{v}_{i,j}-\alpha \sum _{j\in \mathcal{C}(i),(i,j)\in E}{v}_{i,j}.\hfill \end{array}$$

In the right hand side we obtain that:

$$\begin{array}{cc}\hfill u_i({\mathcal{C}}^{\prime })-u_i(\mathcal{C})& ={\overline{u}}_i({\mathcal{C}}^{\prime })+\alpha \sum _{(i,j)\in E}{\overline{u}}_j({\mathcal{C}}^{\prime })-{\overline{u}}_i(\mathcal{C})-\alpha \sum _{(i,j)\in E}{\overline{u}}_j(\mathcal{C})\hfill \\ \hfill & ={\overline{u}}_i({\mathcal{C}}^{\prime })-{\overline{u}}_i(\mathcal{C})+\alpha \sum _{(i,j)\in E}\left({\overline{u}}_j({\mathcal{C}}^{\prime })-{\overline{u}}_j(\mathcal{C})\right)\hfill \\ \hfill & =\sum _{j\in {\mathcal{C}}^{\prime }(i)}{v}_{i,j}+\alpha \sum _{j\in {\mathcal{C}}^{\prime }(i),(i,j)\in E}{v}_{i,j}-\sum _{j\in \mathcal{C}(i)}{v}_{i,j}-\alpha \sum _{j\in \mathcal{C}(i),(i,j)\in E}{v}_{i,j}.\hfill \end{array}$$

Hence, the proof follows.  □

4. Price of Anarchy

In this section we evaluate the performance of Nash stable outcomes with respect to the notion of price of anarchy.

We first show that the price of anarchy is unbounded for general valuations. It is already known that the price of anarchy of additively separable hedonic games is unbounded [12]. The following proposition is an easy extension to our setting with social context. The following result holds for both the social welfare functions $\mathsf{SW}$ and $\overline{\mathsf{SW}}$.

Proposition 1.

For any $\alpha \in [0,1]$, there exists a function v (also admitting negative valuations), such that $\mathsf{PoA}(\mathcal{G}(G,v,\alpha ))$ and $\overline{\mathsf{PoA}}(\mathcal{G}(G,v,\alpha ))$ are unbounded, where $G=(N,\varnothing )$.

Proof. 

Let $v_{i,j}$ be the players’ valuations as shown in Figure 3, with $M\gg ϵ>0$. As $E=\varnothing$, we can easily note that the values of the two social welfare functions $\mathsf{SW}$ and $\overline{\mathsf{SW}}$ are equal for every coalition structure.

On the one hand, there exists outcome ${\mathcal{C}}^{\prime }=\{\left\{1\right\},\{2,3\},\left\{4\right\}\}$ with $\overline{\mathsf{SW}}({\mathcal{C}}^{\prime })=\mathsf{SW}({\mathcal{C}}^{\prime })=2$ and therefore $\overline{\mathsf{SW}}({\mathcal{C}}^{*})\ge 2$ and $\mathsf{SW}({\mathcal{C}}^{*})\ge 2$. On the other hand, it can be easily verified that outcome $\mathcal{C}=\left\{\right\{1,2\},\{3,4\left\}\right\}$ with $\overline{\mathsf{SW}}(\mathcal{C})=\mathsf{SW}(\mathcal{C})=4ϵ$ is a Nash equilibrium. Therefore, $\overline{\mathsf{PoA}}(\mathcal{G}(G,v,\alpha ))\ge \frac{1}{2ϵ}$ and $\mathsf{PoA}(\mathcal{G}(G,v,\alpha ))\ge \frac{1}{2ϵ}$, thus proving the claim for $ϵ$ tending to 0. □

For more involved social graphs, we are also able to show a stronger result, holding even for the case of the price of stability (analyzed in Section 5): by Theorem 5, there exists a SCASHG in which every Nash equilibrium $\mathcal{C}$ is such that $\mathsf{SW}(\mathcal{C})$ is negative, while $\mathsf{SW}({\mathcal{C}}^{*})$ is positive. We now prove a similar result for the social welfare function $\overline{\mathsf{SW}}$.

Theorem 2.

For any $\alpha \in (0,1]$, there exists a graph G and a function v (also admitting negative valuations) inducing $\mathcal{G}(G,v,\alpha )$, such that $\overline{\mathsf{SW}}({\mathcal{C}}^{*})>0$ while $\overline{\mathsf{SW}}(\mathcal{C})<0$ for a Nash stable outcome $\mathcal{C}$ of $\mathcal{G}(G,v,\alpha )$.

Proof. 

Let G be the social graph depicted in Figure 4 and let $v_{i,j}$ be the valuations as represented in Figure 4, with $ϵ$ such that $0<ϵ<2\alpha$.

On the one hand, coalition structure ${\mathcal{C}}^{\prime }=\{\{1,2,3\},\{4,5,6\}\}$ is such that $\overline{\mathsf{SW}}({\mathcal{C}}^{\prime })=4$, and therefore $\overline{\mathsf{SW}}({\mathcal{C}}^{*})\ge 4$.

On the other hand, a Nash equilibrium $\mathcal{C}$ is the grand coalition, in which all players are in the same coalition and, as can be easily checked, $\overline{\mathsf{SW}}(\mathcal{C})=-2ϵ$. Indeed, players $1,3,5$ and 6 have all the same utility $u_1(\mathcal{C})=-\alpha ϵ$ when they are in the grand coalition while, if any of them deviates, the best she can do is forming a new coalition alone, in which she would have utility $-\alpha (1+ϵ)<-\alpha ϵ$. Moreover, players 2 and 4 have the same utility $u_2(\mathcal{C})=-ϵ$ and if any of them deviates forming another coalition, her utility would become $-2\alpha <-ϵ$ for $ϵ<2\alpha$.  □

The above results can be interpreted as follows: having negative valuations towards some players can preclude the possibility to form a group with other players for which the valuation is positive, when the former and the latter are already together in the same group. It is worth noticing that such a situation also arises in the classical model of additively separable hedonic games (notice that in Proposition 1 the social graph is without edges). This phenomenon shows how, in social and economic scenarios, players having difficulties to collaborate with other ones can decrease the global quality of stable outcomes. Given these negative results, in what follows we focus on the case in which the valuation function does not assume negative values, i.e., $v_{i,j}\ge 0$ for any $i,j\in \left[n\right]$ with $i\ne j$.

In order to prove the upper bounds to $\mathsf{PoA}$ and $\overline{\mathsf{PoA}}$, we need some additional notation and definitions. Given any outcome $\mathcal{C}$, let ${\delta }_i(\mathcal{C})$ be the sum of the valuations of player i toward her friends belonging to $\mathcal{C}(i)$, i.e ${\delta }_i(\mathcal{C})={\sum }_{j\in \mathcal{C}(i):(i,j)\in E}{v}_{i,j}$, and, analogously, let $\overline{{\delta }_i}(\mathcal{C})={\sum }_{j\in \mathcal{C}(i):(i,j)\notin E}{v}_{i,j}$ be the sum of the valuations of player i toward players belonging to $\mathcal{C}(i)$ and not being her friends. Finally, we denote by ${\delta }_i^{max}$ the maximum valuation of player i, i.e. ${\delta }_i^{max}={max}_{j\in N}{v}_{i,j}$.

The following theorems provide asymptotically matching upper and lower bounds to $\mathsf{PoA}$ and $\overline{\mathsf{PoA}}$.

Theorem 3.

For any $\alpha \in [0,1]$, any graph G and any function v not admitting negative valuations, $\overline{\mathsf{PoA}}(\mathcal{G}(G,v,\alpha ))\le (n-1)(1+\alpha )$ and $\mathsf{PoA}(\mathcal{G}(G,v,\alpha ))\le (n-1)(1+\alpha )$.

Proof. 

Given a Nash stable outcome $\mathcal{C}$, for every player $i\in \left[n\right]$ it holds that

$${\delta }_i(\mathcal{C})+\overline{{\delta }_i}(\mathcal{C})+\alpha {\delta }_i(\mathcal{C})\ge {\delta }_i^{max}.$$

(2)

To prove inequality 2, recall that $u_i(\mathcal{C})=\overline{u_i}(\mathcal{C})+\alpha ·{\sum }_{(i,j)\in E}\overline{u_j}(\mathcal{C})$, where, for every $i\in \left[n\right]$, $\overline{u_i}(\mathcal{C})={\sum }_{j\in \mathcal{C}(i)}{v}_{i,j}$. By the definitions of ${\delta }_i(\mathcal{C})$ and $\overline{{\delta }_i}(\mathcal{C})$, $\overline{u_i}(\mathcal{C})={\delta }_i(\mathcal{C})+\overline{{\delta }_i}(\mathcal{C})$. Moreover, let ${\beta }_i(\mathcal{C})={\sum }_{(i,j)\in E}\overline{u_j}(\mathcal{C})-{\delta }_i(\mathcal{C})$: it follows that $u_i(\mathcal{C})={\delta }_i(\mathcal{C})+\overline{{\delta }_i}(\mathcal{C})+\alpha ·({\beta }_i(\mathcal{C})+{\delta }_i(\mathcal{C}))$. Let j be the player such that $v_{i,j}={\delta }_i^{max}$. If j belongs in $\mathcal{C}$ to the same coalition of i, inequality 2 trivially holds. Otherwise, notice that if player i changes her strategy by joining the coalition containing player j, inducing in this way a new coalition structure ${\mathcal{C}}^{\prime }$, we obtain $u_i({\mathcal{C}}^{\prime })\ge {\delta }_i^{max}+\alpha {\beta }_i(\mathcal{C})$, because the contributions ${\beta }_i(\mathcal{C})$ of the friends of i not connected to player i in $\mathcal{C}(i)$ remain unchanged in ${\mathcal{C}}^{\prime }$. Therefore, if ${\delta }_i^{max}+\alpha {\beta }_i(\mathcal{C})>{\delta }_i(\mathcal{C})+\overline{{\delta }_i}(\mathcal{C})+\alpha ·({\beta }_i(\mathcal{C})+{\delta }_i(\mathcal{C}))$ player i would increase her utility by changing her strategy: a contradiction to the fact that $\mathcal{C}$ is Nash stable.

Moreover, it trivially holds that in all coalition structures, including the optimal outcomes ${\mathcal{C}}^{*}$ and $\overline{{\mathcal{C}}^{*}}$, $\overline{u_i}$ is at most $(n-1)·{\delta }_i^{max}$. Thus, $\overline{u_i}({\mathcal{C}}^{*})\le (n-1)·{\delta }_i^{max}$ and $\overline{u_i}(\overline{{\mathcal{C}}^{*}})\le (n-1)·{\delta }_i^{max}$.

Therefore,

$$\frac{\overline{\mathsf{SW}}(\overline{{\mathcal{C}}^{*}})}{\overline{\mathsf{SW}}(\mathcal{C})}\le \frac{(n-1)·{\sum }_{i\in N}{\delta }_i^{max}}{{\sum }_{i\in N}\overline{u_i}(\mathcal{C})}.$$

Since, by inequality 2, $\overline{u_i}(\mathcal{C})={\delta }_i(\mathcal{C})+\overline{{\delta }_i}(\mathcal{C})\ge \frac{{\delta }_i^{max}}{(1+\alpha )}$, we obtain that

$$\frac{\overline{\mathsf{SW}}(\overline{{\mathcal{C}}^{*}})}{\overline{\mathsf{SW}}(\mathcal{C})}\le \frac{(n-1)·{\sum }_{i\in N}{\delta }_i^{max}}{\frac{{\sum }_{i\in N}{\delta }_i^{max}}{1+\alpha }}=(n-1)(1+\alpha ).$$

Analogously, for the social welfare function $\mathsf{SW}$, since $\overline{u_i}({\mathcal{C}}^{*})\le (n-1)·{\delta }_i^{max}$ and $\overline{u_i}(\mathcal{C})\ge \frac{{\delta }_i^{max}}{(1+\alpha )}$, by recalling the definition of $u_i$, we obtain that

$$\begin{array}{ccc}\hfill \frac{\mathsf{SW}({\mathcal{C}}^{*})}{\mathsf{SW}(\mathcal{C})}& \le & \frac{{\sum }_{i\in N}\left[(n-1){\delta }_i^{max}+\alpha {\sum }_{j\in N:(i,j)\in E}(n-1){\delta }_j^{max}\right]}{{\sum }_{i\in N}\left[{\delta }_i^{max}+\alpha {\sum }_{j\in N:(i,j)\in E}{\delta }_j^{max}\right]\frac{1}{1+\alpha }}\hfill \\ & =& \frac{(n-1){\sum }_{i\in N}\left[{\delta }_i^{max}+\alpha {\sum }_{j\in N:(i,j)\in E}{\delta }_j^{max}\right]}{{\sum }_{i\in N}\left[{\delta }_i^{max}+\alpha {\sum }_{j\in N:(i,j)\in E}{\delta }_j^{max}\right]\frac{1}{1+\alpha }}\hfill \\ & \le & (n-1)(1+\alpha ),\hfill \end{array}$$

thus proving the claim.  □

We now focus on the lower bound on $\mathsf{PoA}$ and $\overline{\mathsf{PoA}}$.

Theorem 4.

For every even positive integer n and every $\alpha \in [0,1]$, there exists a graph G with n vertices and a valuation function v (not admitting negative valuations) such that $\overline{\mathsf{PoA}}(\mathcal{G}(G,v,\alpha ))\ge (1+\alpha )\frac{n}{2}-\alpha$ and $\mathsf{PoA}(\mathcal{G}(G,v,\alpha ))\ge (1+\alpha )\frac{n}{2}-\alpha$.

Proof. 

Consider the bipartite graph $G=(A\cup B,E)$ with n vertices depicted in Figure 5 (note that $A=\{1,3,\dots ,n-1\}$ and $B=\{2,4,\dots ,n\}$), and let v be the valuation function such that

• $v_{i,j}=v_{j,i}=\frac{1}{1+\alpha }$ for every $(i,j)\in E$;
• $v_{i,j}=v_{j,i}=1$ for all pairs $(i,j)\notin E$ such that $i\in A$ and $j\in B$;
• $v_{i,j}=0$ for all remaining pairs.

On the one hand, as can be easily checked, the grand coalition ${\mathcal{C}}^o$ is such that, for every $i\in \left[n\right]$, $\overline{u_i}({\mathcal{C}}^o)=\frac{n}{2}-1+\frac{1}{1+\alpha }$. Therefore, the optimal outcome $\overline{{\mathcal{C}}^{*}}$ is such that $\overline{\mathsf{SW}}(\overline{{\mathcal{C}}^{*}})\ge n\left(\frac{n}{2}-1+\frac{1}{1+\alpha }\right)$ and the optimal outcome ${\mathcal{C}}^{*}$ is such that $\mathsf{SW}({\mathcal{C}}^{*})\ge n(1+\alpha )\left(\frac{n}{2}-1+\frac{1}{1+\alpha }\right)$.

On the other hand, the coalition structure $\mathcal{C}$ in which there are $\frac{n}{2}$ non-empty coalitions $\{i,i+1\}$ for $i=1,3,\dots ,n-1$ is a Nash stable outcome; in fact, for every $i\in A$, $\overline{u_i}(\mathcal{C})=\frac{1}{1+\alpha }$ and $u_i(\mathcal{C})=\frac{1}{1+\alpha }+\alpha ·\frac{1}{1+\alpha }=1$, while a deviation of player i to another non-empty candidate coalition would induce a new coalition structure ${\mathcal{C}}^{\prime }$ such that $u_i({\mathcal{C}}^{\prime })=1+\alpha ·0=1$, because for player $i+1$ connected in G to player i it holds $\overline{u_{i+1}}({\mathcal{C}}^{\prime })=0$. Moreover, a deviation of player i to an empty candidate coalition would induce a new coalition structure ${\mathcal{C}}^{\prime \prime }$ such that $u_i({\mathcal{C}}^{\prime \prime })=0$, again because for player $i+1$ connected in G to player i it holds $\overline{u_{i+1}}({\mathcal{C}}^{\prime \prime })=0$. A completely symmetric argument holds for every player $i\in B$.

It follows that

$$\frac{\overline{\mathsf{SW}}(\overline{{\mathcal{C}}^{*}})}{\overline{\mathsf{SW}}(\mathcal{C})}\ge \frac{n\left(\frac{n}{2}-1+\frac{1}{1+\alpha }\right)}{n\left(\frac{1}{1+\alpha }\right)}=(1+\alpha )\frac{n}{2}-\alpha .$$

Analogously, for the social welfare function $\mathsf{SW}$, it holds that

$$\frac{\mathsf{SW}({\mathcal{C}}^{*})}{\mathsf{SW}(\mathcal{C})}\ge \frac{n\left(\frac{n}{2}-1+\frac{1}{1+\alpha }\right)(1+\alpha )}{n\left(\frac{1}{1+\alpha }+\frac{\alpha }{1+\alpha }\right)}=(1+\alpha )\frac{n}{2}-\alpha .$$

□

5. Price of Stability

In this section we present our results on the price of stability. First of all, notice that, if all valuations are non-negative, with respect to both social welfare functions $\mathsf{SW}$ and $\overline{\mathsf{SW}}$, the grand coalition is at the same time an optimal solution and a Nash stable outcome, thus implying that $\mathsf{PoS}=\overline{\mathsf{PoS}}=1$.

Therefore, in the following we deal with the case of general valuations, i.e., we allow the valuation function to assume negative values. We first show that, for the social welfare function $\mathsf{SW}$, there exists a SCASHG in which every Nash equilibrium $\mathcal{C}$ is such that $\mathsf{SW}(\mathcal{C})$ is negative, while $\mathsf{SW}({\mathcal{C}}^{*})$ is positive.

Theorem 5.

For any $\alpha \in (0,1]$, there exists a graph G and a function v (admitting also negative valuations) inducing $\mathcal{G}(G,v,\alpha )$, such that $\mathsf{SW}({\mathcal{C}}^{*})>0$ while $\mathsf{SW}(\mathcal{C})<0$ for every Nash stable outcome $\mathcal{C}$ of $\mathcal{G}(G,v,\alpha )$.

Proof. 

Let us consider the graph G depicted in Figure 6 and the valuation function v whose non-null values are listed in Figure 6, and in which $ϵ<\alpha$ is an arbitrary positive parameter.

Now we want to show that in every Nash stable outcome $\mathcal{C}$ players 1, 2 and 3 belong to the same coalition.

First of all, notice that, for any $i\ge 4$, $v_{i,j}=0$ for any $j\in \left[n\right]$; it follows that it is possible to discard players $4,\dots ,n$ in the following discussion. The outcome in which players 1, 2 and 3 belong to three different coalitions is not Nash stable because, for instance, player 1 would increase her utility from 0 to $1+\alpha$ by joining the coalition of player 2. The outcome in which players 1 and 2 are in a coalition and player 3 in another one is not Nash stable because player 3 would increase her utility from $\alpha$ to $2\alpha -ϵ$ by joining the coalition of players 1 and 2 (notice that a symmetric argument holds for the outcome in which players 2 and 3 are in a coalition and player 1 in another one). Finally, the outcome in which players 1 and 3 are in a coalition and player 2 in another one is not Nash stable because, for instance, player 1 would increase her utility from $-1-ϵ$ to 0 by forming alone a new coalition. It follows that in any Nash equilibrium $\mathcal{C}$ (recall that by Theorem 1 a Nash equilibrium always exists) players 1, 2 and 3 belong to the same coalition.

It can be easily verified that $u_1(\mathcal{C})=u_3(\mathcal{C})=2\alpha -ϵ$ and $u_2(\mathcal{C})=2-2\alpha ϵ$. Moreover, since ${\overline{u}}_3(\mathcal{C})=-ϵ$, it follows that for any $i\ge 4$, $u_i(\mathcal{C})=-\alpha ϵ$.

Therefore,

$$\mathsf{SW}(\mathcal{C})=2(2\alpha -ϵ)+2-2\alpha ϵ-(n-3)\alpha ϵ<0$$

for n approaching infinity.

In order to complete the proof, it is sufficient to note that there exists a coalition structure (for instance the one in which players 1 and 2 belong to the same coalition and all other players are alone in different coalitions) with positive social welfare.  □

Now we focus our attention on the $\overline{\mathsf{SW}}$ social welfare function and we show that $\overline{\mathsf{PoS}}$ is unbounded for $\alpha$ tending to 1.

Theorem 6.

Given any $M>0$, there exist a value of α, a graph G and a function v (admitting also negative valuations) such that $\overline{\mathsf{PoS}}(\mathcal{G}(G,v,\alpha ))>M$.

Proof. 

Let us consider the graph G depicted in Figure 7 and the valuation function v whose non-null values are listed in Figure 7, and in which $\alpha \in \left(\frac{M-1}{M},1\right]$ and $ϵ<\alpha$.

By exploiting the same arguments used in the proof of Theorem 5, it is possible to show that the unique Nash stable outcome $\mathcal{C}$ is given by the grand coalition.

It can be easily verified that $\overline{u_1}(\mathcal{C})=\overline{u_3}(\mathcal{C})=-ϵ$ and $\overline{u_2}(\mathcal{C})=2$. Therefore, $\overline{\mathsf{SW}}(\mathcal{C})=2-2ϵ$.

Moreover, there exists coalition structure ${\mathcal{C}}^{\prime }=\{\{1,2\},\left\{3\right\}\}$ with social welfare $\overline{\mathsf{SW}}({\mathcal{C}}^{\prime })=2$. Thus, it holds that $\overline{\mathsf{SW}}(\overline{{\mathcal{C}}^{*}})\ge 2$.

Therefore, for any $M>0$,

$$\frac{\overline{\mathsf{SW}}(\overline{{\mathcal{C}}^{*}})}{\overline{\mathsf{SW}}(\mathcal{C})}\ge \frac{2}{2-2ϵ}\ge M$$

for $ϵ\ge \frac{M-1}{M}$. Since $\alpha \in \left(\frac{M-1}{M},1\right]$, it is possible to choose $ϵ$ such that $\frac{M-1}{M}\le ϵ<\alpha$ and the claim follows.  □

6. Open Problems

Starting from the fundamental class of additively separable hedonic games, we have defined and studied a new model in which, given a social graph, players also care about the happiness of their friends. Our work leads to many future research directions.

First of all, it would be interesting to study particular significant classes of graph topologies, in order to obtain a reduced price of anarchy. Moreover, the study of other stability notions such as strong Nash outcomes and core stable outcomes also deserves further investigation.

This is a first study toward the understanding of social effects in hedonic games. Several research directions (or their combinations) can be pursued along this line:

• the problem in which valuations can be different from zero only between players $i,j$ for which edge $(i,j)$ belongs to the social graph (and not for all pairs of players);
• the setting in which the valuations are not symmetric;
• the problem in which an edge-weighted social graph is considered, with the weights denoting how important is a player for another one;
• different combinations of the classical utilities of the friends, that in this first work have been combined in an additive way;
• the problem defined with player-specific parameters ${\alpha }_1,\dots ,{\alpha }_n$, in which every player has a different degree of altruism.

Finally, it would be interesting to study social context games in the setting of fractional hedonic games in which the utility of a player (according to the current model of additively separable hedonic games) is divided by the number of players in the coalition she belongs to, and modified fractional hedonic games in which the utility of a player is averaged over all other members of that coalition, that is, excluding herself.