=Paper=
{{Paper
|id=Vol-2243/paper1
|storemode=property
|title=Hedonic Games with Social Context
|pdfUrl=https://ceur-ws.org/Vol-2243/paper1.pdf
|volume=Vol-2243
|authors=Gianpiero Monaco,Luca Moscardelli,Yllka Velaj
|dblpUrl=https://dblp.org/rec/conf/ictcs/MonacoMV18
}}
==Hedonic Games with Social Context==
https://ceur-ws.org/Vol-2243/paper1.pdf
Hedonic Games with Social Context
Gianpiero Monaco1 , Luca Moscardelli2 , and Yllka Velaj3
1
University of L’Aquila, L’Aquila 67100, Italy, gianpiero.monaco@univaq.it
2
University of Chieti-Pescara, Pescara 65127, Italy, luca.moscardelli@unich.it
3
CWI, Amsterdam 1098 XG, Netherlands, yllka.velaj@cwi.nl
Abstract. Hedonic games are coalition formation games in which coali-
tions are created as a result of the strategic interaction of independent
players. To this day, the literature on non-cooperative hedonic games has
considered totally selfish players; our aim is that of defining and study-
ing 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
hedonic games (SCHGs). We consider Nash equilibria of SCHGs, and
study their existence, convergence and performance with respect to the
classical notions of price of anarchy and price of stability. In particular,
we provide an exact potential function for SCHGs implying the existence
and convergence to Nash equilibria, and we prove tight or asymptotically
tight bounds on the price of anarchy and the price of stability of SCHGs.
Keywords: Coalition Formation; Hedonic Games; Nash Equilibrium; Price of
Anarchy; Price of Stability; Social Context
1 Introduction
An important issue in computer science is that of investigating the dynamics
that regulates clustering and coalition formation. Hedonic games, introduced by
Dréze and Greenberg [15], represent a framework for studying the formal aspects
of the formation of player coalitions. In these games, players have preferences
over the set of all possible player coalitions, and the utility of a player depends
on the composition of the coalition she belongs to.
Hedonic games are of great interest because they model natural behavioral
dynamics in social environments: in economic, social and political situation,
in fact, individuals carry out activities in groups rather than by themselves.
Politicians, for example, may want to be in a party that maximizes like-minded
members or, more in general, people may want to be with people of the same
ethnic or social group.
While the standard model of 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. We call these games Social
Context Hedonic Games (SCHGs); we believe that they provide a more realistic
model for hedonic games, because they capture the fact that the behavior of
players also depends on the happiness of their friends. To this aim, we consider
2 G. Monaco et al.
2 4 2 4 (i, j) vi,j
5 5 (1,3) 1
(2,5) 3
(1,5) 2
1 3 1 3 (3,4) 1
Fig. 1. A social network G, a coalition structure C and the non-null valuations vi,j .
an underlying social network represented by a graph, whose nodes are players
and in which an edge connecting two players expresses friendship between them.
Arguably, as a first step in the study of SCHGs, it is more natural to consider
symmetric friendship relations and therefore we focus on undirected graphs.
In SCHGs, valuations are additive and each player has a valuation v for any
other player, but differently from the classical hedonic games, the utility of a
coalition to a particular player is given not only by the sum of the valuations
she assigns to the members of her coalition, but also depends on the sum of the
valuations her friends assign to the members of their own coalitions (the latter
contribution is multiplied by a given parameter α ∈ [0, 1]). In particular, for
α = 0 we model classical hedonic games in the totally selfish setting and when
α = 1 we can model a fully altruistic setting. In Figure 1, for example, we can
see that the utility of player 5 is equal to v1,5 + v2,5 + α(v1,5 + v2,5 + v3,4 ) =
2 + 3 + α(2 + 3 + 1), where 2 + 3 is the sum of valuations of the players in her
coalition and α(2 + 3 + 1) is the sum of valuations her friends 1, 2 and 3 assign
to the members of their own coalitions, multiplied by α.
Our aim is to study the existence and performance of natural stable outcomes
for SCHGs. 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 SCHGs by means
of the widely used notions of price of anarchy and 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 Our Results
By providing an exact potential function for the SCHGs, we show that these
games always posses a pure Nash equilibrium and also that the convergence to
such stable outcomes is guaranteed. We consider two social welfare functions.
The first social function, 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 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 α). 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 (PoA
and PoA denote the price of anarchy with respect to SW and SW, respectively;
Hedonic Games with Social Context 3
analogously PoS and PoS denote the price of stability with respect to SW and
SW, respectively).
In presence of negative valuations, both PoS and PoS (and therefore also PoA
and PoA) can be unbounded. Furthermore, in some cases we are able to provide
instances in which the social value of any equilibrium 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 we prove that the price of anarchy is Θ(n), while the price of stability is 1.
1.2 Related Work
Social context games are introduced in [2]. These games are defined by an un-
derlying game in strategic form, and a social context consisting of an undi-
rected graph and an aggregation function. The authors consider resource selec-
tion games as the underlying game and they study the existence of pure strategy
Nash equilibrium. Building on this model, Bilò et al. [8] 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. [1] study the effects of the altruistic behaviour
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 modelled and
studied by Hoefer and Skopalik [19]: they focus on the existence and complexity
of pure Nash equilibria with altruistic agents in atomic congestion games. Chen
et al. [13] 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 [25] study social choice with empathetic preferences and their local
empathetic model is related to the model presented in [21]. Finally, Brânzei and
Larson [11] study social distance games. In these games a players opinion on
her friends (players of distance one) has the highest weight while her opinion on
players farther away counts less.
Several papers are devoted to the study of hedonic games. They are intro-
duced by Dréze and Greenberg [15], who analyze hedonic games under a coop-
erative perspective. Properties guaranteeing the existence of core allocations for
games with additively separable utility have been studied by Banerjee, Konishi
and Sönmez [7], while Bogomolnaia and Jackson [10] deal with several forms of
stable outcomes like the core, Nash and individual stability. Ballester [4] consid-
ers computational complexity issues related to hedonic games, and shows that
the core and the Nash stable outcomes have corresponding NP-complete decision
problems for a variety of situations, while Aziz et al. [3] study the computational
complexity of stable coalitions in additively separable hedonic games. Moreover,
Olsen [22] proves that the problem of deciding whether a Nash stable coalitions
exists in an additively separable hedonic game is NP-complete, as well as the
one of deciding whether a non-trivial Nash stable coalitions exists in an ad-
ditively separable hedonic game with non-negative and symmetric preferences
4 G. Monaco et al.
(i.e., unweighted undirected graphs). Feldman et al. [16] investigate some in-
teresting 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. In their model the agents lie in
a metric space with a distance function modeling their distance or ”similarity”.
Peters [23] 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). Moreover, hedonic
games have also been considered by Charikar et al. [12] and by Demaine et al.
[14] from a classical optimization point of view (i.e, without requiring stability
for the solutions) and by Flammini et al. in an online setting [17]. Peters et al.
[24] 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. From a different perspec-
tive, strategyproof mechanisms for additively separable hedonic and fractional
hedonic games have been proposed in [18], while stable outcomes for these games
and for modified fractional hedonic games are presented in [9] and [20]. Finally,
hedonic games are being widely investigated also under different utility defini-
tions. For instance, in [5, 6], 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, few papers deal with the notion of altruism
in hedonic games. Nguyen et al. [21] 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 ones friends decide first. They study both
the axiomatic properties of these games and the computational complexity of
problems related to common stability concepts. In [26], 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.
The paper is organized as follows. In Section 2 we formally define the hedo-
nic games with social context. The technical contributions of the paper are then
presented in Sections 3, 4 and 5 which address the existence of Nash outcomes,
the results on the price of anarchy and those on the price of stability, respec-
tively. Finally, in Section 6 we list some interesting open problems. Due to space
limitations, some proofs are omitted.
2 Model
For an integer k > 0, denote with [k] the set {1, . . . , k}.
We model a Social Context Hedonic Game by means of a valuation function
v, an undirected graph G = (N, E) and a given parameter α ∈ [0, 1]. We denote
Hedonic Games with Social Context 5
with n = |N | the number of nodes of G and with E the set of edges between the
nodes, that represent the friendship relation. v : N × N → R is the symmetric
valuation function. For the sake of convenience, we adopt the notation (i, j) and
vi,j to denote the pair {i, j} ∈ N × N and its valuation v({i, j}), respectively.
Given a symmetric valuation function v, an undirected graph G = (N, E) and
a value for α, the Social Context Hedonic Game induced by G, v and α, denoted
as G(G, v, α), is the game in which each node i ∈ N is associated with a player.
We assume that players are numbered from 1 to n and, for every i ∈ [n], each
player chooses to join a certain coalition among n candidate ones: the strategy
of player i is an integer j ∈ [n], meaning that player i is selecting candidate
coalition Cj . A coalition structure (also called outcome) is a partition of the set
of playersS into n coalitions C = {C1 , C2 , . . . , Cn } such that Cj ⊆ N for each
j ∈ [n], j∈[n] Cj = N and Ci ∩ Cj = ∅ for any i, j ∈ [n] with i 6= j. Notice
that, since the number of candidate coalitions is equal to the number of players
(nodes), some coalition may be empty. If i ∈ Cj , we say that player i is a member
of the coalition Cj . We denote by C(i) the coalition in C of which player i is a
member. In an outcome C, the utility of player i is defined as
X
ui (C) = ui (C) + α · uj (C),
(i,j)∈E
P
where, for every i ∈ [n], ui (C) = j∈C(i) vi,j .
Each player chooses the coalition she belongs to with the aim of maximizing
her utility. We denote by (C, i, j), the new coalition structure obtained from C
by moving player i from C(i) to Cj ; formally, (C, i, j) = C \ {C(i), Cj } ∪ {C(i) \
{i}, Cj ∪{i}}. A player deviates if she changes the coalition she belongs to. Given
an outcome C, an improving move (or simply a move) for player i is a deviation
to any coalition Cj that strictly increases her utility, i.e., ui ((C, i, j)) > ui (C).
Moreover, player i performs a best-response in coalition structure 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 Cj such that ui ((C, i, j)) > ui (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 moves, while a best-response dynamics
is a sequence of best-responses. A game has the finite improvement path prop-
erty 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 N(G(G, v, α)) the set of Nash stable outcomes
of G(G, v, α).
The social welfare ofPa coalition structure C is the summation of the players’
utilities, i.e., SW(C) = i∈N ui (C).
P
We define also a second social welfare function SW(C) = i∈N ui (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 G(G, v, α), an optimum coalition structure C ∗ (G(G, v, α)) (re-
spectively C ∗ (G(G, v, α))) is one that maximizes the social welfare SW (re-
6 G. Monaco et al.
spectively SW) of G(G, v, α). The price of anarchy of a social context hedo-
nic game G(G, v, α) is defined as the worst-case ratio between the social wel-
fare of a social optimum outcome and that of a Nash equilibrium. Formally,
∗
for any k = 1, . . . , n, PoA(G(G, v, α)) = maxC∈N(G(G,v,α)) SW(C SW(C)
(G(G,v,α)))
and
∗
PoA(G(G, v, α)) = maxC∈N(G(G,v,α)) SW(C SW(C)
(G(G,v,α)))
. Analogously, the price of
stability of G(G, v, α) is defined as the best-case ratio between the social wel-
fare of a social optimum outcome and that of a Nash equilibrium. Formally,
∗
for any k = 1, . . . , n, PoS(G(G, v, α)) = minC∈N(G(G,v,α)) SW(C SW(C)
(G(G,v,α)))
and
∗
PoS(G(G, v, α)) = minC∈N(G(G,v,α)) SW(C SW(C)
(G(G,v,α)))
.
3 Nash Stable Outcomes
In this section we consider Nash stable outcomes. We show that a stable outcome
is guaranteed to exist and also that the finite improvement path property holds
for SCHGs, because these games admit the potential function
1X
Φ(C) = ûi (C),
2
i∈N
0 0
P
with ûi (C) = j∈C(i) vi,j , where, for each pair of players (i, j), we define vi,j =
0
vi,j · (1 + α) if (i, j) ∈ E and vi,j = vi,j if (i, j) 6∈ E.
Thus, we can rewrite the potential function Φ(C) as
X X
Φ(C) = vi,j + α · vi,j .
j∈C(i) j∈C(i),(i,j)∈E
In the following theorem, we prove that Φ(C) is an exact potential function
for our game.
Theorem 1. Φ is a potential function for SCHGs.
Proof. Given two stable outcomes C and C 0 where C 0 is obtained form C after a
player i performs a move, we prove that the following holds:
Φ(C 0 ) − Φ(C) = ui (C 0 ) − ui (C). (1)
For the left hand side of Equation (1), by applying the definition of Φ, we obtain
that:
!
0 1 X 0
X 1X
Φ(C ) − Φ(C) = ûi (C ) − ûi (C) = (ûi (C 0 ) − ûi (C))
2 2
i∈N i∈N i∈N
1 X
0
X
0
= · 2 vi,j − vi,j
2
j∈C 0 (i) j∈C(i)
X X X X
= vi,j + α vi,j − vi,j − α vi,j .
j∈C 0 (i) j∈C 0 (i),(i,j)∈E j∈C(i) j∈C(i),(i,j)∈E
Hedonic Games with Social Context 7
In the right hand side we obtain that:
X X
ui (C 0 ) − ui (C) = ūi (C 0 ) + α ūj (C 0 ) − ūi (C) − α ūj (C)
(i,j)∈E (i,j)∈E
X
0 0
= ūi (C ) − ūi (C) + α (ūj (C ) − ūj (C))
(i,j)∈E
X X X X
= vi,j + α vi,j − vi,j − α vi,j .
j∈C 0 (i) j∈C 0 (i),(i,j)∈E j∈C(i) j∈C(i),(i,j)∈E
Hence, the proof follows. t
u
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.
The following result holds for both the social welfare functions SW and SW, even
when the social graph has no edges.
Theorem 2. For any α ∈ [0, 1], there exists a function v (also admitting nega-
tive valuations), such that PoA(G(G, v, α)) and PoA(G(G, v, α)) are unbounded,
where G = (N, ∅).
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 6, there exists a SCHG in which every Nash equilibrium C is such that
SW(C) is negative, while SW(C ∗ ) is positive. We now prove a similar result for
the social welfare function SW.
Theorem 3. For any α ∈ (0, 1], there exists a graph G and a function v (also
admitting negative valuations) inducing G(G, v, α), such that SW(C ∗ ) > 0 while
SW(C) < 0 for a Nash stable outcome C of G(G, v, α).
Given these negative results, in what follows we focus on the case in which
the valuation function does not assume negative values, i.e., vi,j ≥ 0 for any
i, j ∈ [n] with i 6= j.
In order to prove the upper bounds to PoA and PoA, we need some ad-
ditional notation and definitions. Given any outcome C, let δi (C) be the sum
of
P the valuations of player i toward her ¯friends P belonging to C(i), i.e δi (C) =
j∈C(i):(i,j)∈E v i,j , and, analogously, let δ i (C) = j∈C(i):(i,j)6∈E vi,j be the sum
of the valuations of player i toward players belonging to C(i) and not being
her friends. Finally, we denote by δimax the maximum valuation of player i, i.e.
δimax = maxj∈N vi,j .
The following theorems provide asymptotically matching upper and lower
bounds to PoA and PoA.
8 G. Monaco et al.
Theorem 4. For any α ∈ [0, 1], any graph G and any function v not admitting
negative valuations, PoA(G(G, v, α)) ≤ (n − 1)(1 + α) and PoA(G(G, v, α)) ≤
(n − 1)(1 + α).
Proof. Given a Nash stable outcome C, for every player i ∈ [n] it holds that
δi (C) + δ¯i (C) + αδi (C) ≥ δimax .
P
In fact, recall that ui (C) = ui (C) + α · (i,j)∈E uj (C), where, for every i ∈ [n],
ui (C) = j∈C(i) vi,j . By the definitions of δi (C) and δ¯i (C), ui (C) = δi (C) + δ¯i (C).
P
P
Moreover, let βi (C) = (i,j)∈E uj (C) − δi (C): it follows that ui (C) = δi (C) +
δ¯i (C) + α · (βi (C) + δi (C)). Notice that if player i changes her strategy by joining
the coalition containing player j such that vi,j = δimax , inducing in this way
a new coalition structure C 0 , we obtain ui (C 0 ) ≥ δimax + αβi (C), because the
contributions βi (C) of the friends of i not connected to player i in C(i) remain
unchanged in C 0 . Therefore, if δimax + αβi (C) > δi (C) + δ¯i (C) + α · (βi (C) + δi (C))
player i would increase her utility by changing her strategy: a contradiction to
the fact that C is Nash stable.
Moreover, it trivially holds that in all coalition structures, including the opti-
mal outcomes C ∗ and C ∗ , ui is at most (n−1)·δimax . Thus, ui (C ∗ ) ≤ (n−1)·δimax
and ui (C ∗ ) ≤ (n − 1) · δimax .
Therefore,
(n − 1) · i∈N δimax
P
SW(C ∗ )
≤ P .
SW(C) i∈N ui (C)
max
δi
Since ui (C) = δi (C) + δ¯i (C) ≥ (1+α) , we obtain that
(n − 1) · i∈N δimax
P
SW(C ∗ )
≤ P max = (n − 1)(1 + α).
SW(C) i∈N δi
1+α
Analogously, for the social welfare function SW, since ui (C ∗ ) ≤ (n − 1) · δimax
δimax
and ui (C ∗ ) ≥ (1+α) , by recalling the definition of ui , we obtain that
(n − 1)δimax + α j∈N :(i,j)∈E (n − 1)δjmax
P P
SW(C ∗ ) i∈N
≤ max 1
+ α j∈N :(i,j)∈E δjmax 1+α
P P
SW(C) i∈N δi
(n − 1) i∈N δimax + α j∈N :(i,j)∈E δjmax
P P
= P max 1
+ α j∈N :(i,j)∈E δjmax 1+α
P
i∈N δi
≤ (n − 1)(1 + α),
thus proving the claim. t
u
We now focus on the lower bound to PoA and PoA.
Theorem 5. For every even positive integer n and every α ∈ [0, 1], there exist a
graph G with n vertices and a valuation function v such that PoA(G(G, v, α)) ≥
(1 + α) n2 − α and PoA(G(G, v, α)) ≥ (1 + α) n2 − α.
Hedonic Games with Social Context 9
n−1 n
n−3 n−2
A .. .. B
. .
3 4
1 2
Fig. 2. The bipartite graph G.
Proof. Consider the bipartite graph G = (A ∪ B, E) with n vertices depicted in
Figure 2 (note that A = {1, 3, . . . , n − 1} and B = {2, 4, . . . , n}), and let v the
valuation function in which
1
– vi,j = vj,i = 1+α for every (i, j) ∈ E;
– vi,j = vj,i = 1 for all pairs (i, j) 6∈ E such that i ∈ A and j ∈ B;
– vi,j = 0 for all remaining pairs.
On the one hand, as it can be easily checked, the grand coalition C o is such
that, for every i ∈ [n], ui (C o ) = n2 − 1 + 1+α 1
. Therefore, the optimal outcome
C is such that SW(C ) ≥ n 2 − 1 + 1+α and the optimal outcome C ∗ is such
n 1
∗ ∗
that SW(C ∗ ) ≥ n(1 + α) n2 − 1 + 1+α 1
.
On the other hand, the coalition structure C in which there are n2 non-empty
coalitions {i, i + 1} for i = 1, 3, . . . , n − 1 is a Nash stable outcome; in fact, for
1 1 1
every i ∈ A, ui (C) = 1+α and ui (C) = 1+α + α · 1+α = 1, while a deviation of
player i to another non-empty candidate coalition would induce a new coalition
structure C 0 such that ui (C 0 ) = 1 + α · 0 = 1, because for player i + 1 connected
in G to player i it holds ui+1 (C 0 ) = 0. Moreover, a deviation of player i to an
empty candidate coalition would induce a new coalition structure C 00 such that
ui (C 00 ) = 0, again because for player i + 1 connected in G to player i it holds
ui+1 (C 00 ) = 0. A completely symmetric argument holds for every player i ∈ B.
It follows that
n n2 − 1 + 1+α 1
SW(C ∗ ) n
≥ 1
= (1 + α) − α.
SW(C) n 1+α
2
Analogously, for the social welfare function SW, it holds that
n n2 − 1 + 1+α
1
SW(C ∗ ) (1 + α) n
≥ = (1 + α) − α.
SW(C) n 1
+ α 2
1+α 1+α
t
u
10 G. Monaco et al.
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 func-
tions SW and SW, the grand coalition is at the same time an optimal solution
and a Nash stable outcome, thus implying that PoS = 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 SW, there exists a SCHG in which every Nash
equilibrium C is such that SW(C) is negative, while SW(C ∗ ) is positive.
Theorem 6. For any α ∈ (0, 1], there exists a graph G and a function v (admit-
ting also negative valuations) inducing G(G, v, α), such that SW(C ∗ ) > 0 while
SW(C) < 0 for every Nash stable outcome C of G(G, v, α).
Proof. Let us consider the graph G depicted in Figure 3 and the valuation func-
tion v whose non-null values are listed in Figure 3, and in which < α is an
arbitrary positive parameter.
Now we want to show that in every Nash stable outcome C players 1, 2 and
3 belong to the same coalition.
First of all, notice that, for any i ≥ 4, vi,j = 0 for any j ∈ [n]; it follows
that it is possible to discard players 4, . . . , 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 + α 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 α to 2α − 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 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 u1 (C) = u3 (C) = 2α − and u2 (C) = 2 − 2α.
Moreover, since u3 (C) = −, it follows that for any i ≥ 4, ui (C) = −α.
3
n−3 .. (i, j) vi,j
.
2 (1,2) 1
(1,3) −1 −
1 (2,3) 1
Fig. 3. Graph G and valuations vi,j .
Hedonic Games with Social Context 11
Therefore,
SW(C) = 2(2α − ) + 2 − 2α − (n − 3)α < 0
for n going to infinite.
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. t
u
Now we focus our attention on the SW social welfare function and we show
that PoS is unbounded for α tending to 1.
Theorem 7. Given any M > 0, there exist a value of α, a graph G and a
function v (admitting also negative valuations) such that PoS(G(G, v, α)) > M .
6 Open Problems
Our work leads to many future research directions. It would be interesting to
analyze if it is possible to decrease the price of anarchy by restricting to par-
ticular classes of graphs, as well as to study different stability notions such as
strong Nash outcomes and core stable outcomes. Moreover, the problem in which
valuations can be different from zero only between players i, j for which edge
(i, j) ∈ E (and not for all pair of players) is worth studying. Finally, it would be
interesting to study the fractional version of hedonic games, in which the utility
of a player is divided by the number of players in the coalition she belongs to.
References
1. A. Anagnostopoulos, L. Becchetti, B. de Keijzer, and G. Schäfer. Inefficiency of
games with social context. Theory of Computing Systems, 57(3):782–804, 2015.
2. I. Ashlagi, P. Krysta, and M. Tennenholtz. Social context games. In Internet and
Network Economics, pages 675–683, 2008.
3. H. Aziz, F. Brandt, and H. G. Seedig. Stable partitions in additively separable
hedonic games. In Proc. 10th Int. Conf. on Autonomous Agents and Multiagent
Systems (AAMAS), pages 183–190, 2011.
4. C. Ballester. Np-completeness in hedonic games. Games and Economic Behavior,
49(1):1–30, 2004.
5. A. Balliu, M. Flammini, G. Melideo, and D. Olivetti. Nash stability in social
distance games. In Proc. 31st AAAI Conf. on Artificial Intelligence (AAAI), pages
342–348, 2017.
6. A. Balliu, M. Flammini, and D. Olivetti. On pareto optimality in social distance
games. In Proc. 31st AAAI Conf. on Artificial Intelligence (AAAI), pages 349–355,
2017.
7. S. Banerjee, H. Konishi, and T. Sönmez. Core in a simple coalition formation
game. Social Choice and Welfare, 18:135–153, 2001.
8. V. Bilò, A. Celi, M. Flammini, and V. Gallotti. Social context congestion games.
In Structural Information and Communication Complexity, pages 282–293, 2011.
12 G. Monaco et al.
9. V. Bilò, A. Fanelli, M. Flammini, G. Monaco, and L. Moscardelli. Nash stable out-
comes in fractional hedonic games: Existence, efficiency and computation. Journal
of Artificial Intelligence Research, 62:315–371, 2018.
10. A. Bogomolnaia and M. O. Jackson. The stability of hedonic coalition structures.
Games and Economic Behavior, 38:201–230, 2002.
11. S. Brânzei and K. Larson. Social distance games. In The 10th Int. Conf. on
Autonomous Agents and Multiagent Systems - Volume 3, AAMAS, pages 1281–
1282, 2011.
12. M. Charikar, V. Guruswami, and A. Wirth. Clustering with qualitative informa-
tion. Journal of Computer and System Sciences, 71(3):360–383, 2005.
13. P.-A. Chen, B. de Keijzer, D. Kempe, and G. Schäfer. The robust price of anarchy
of altruistic games. In Proc. 7th Int. Conf. on Internet and Network Economics,
WINE’11, pages 383–390, 2011.
14. E. D. Demaine, D. Emanuel, A. Fiat, and N. Immorlica. Correlation clustering in
general weighted graphs. Theoretical Computer Science, 361(2-3):172–187, 2006.
15. J. H. Dréze and J. Greenberg. Hedonic coalitions: optimality and stability. Econo-
metrica, 48:987–1003, 1980.
16. M. Feldman, L. Lewin-Eytan, and J. S. Naor. Hedonic clustering games. ACM
Transactions on Parallel Computing, 2(1):4:1–4:48, 2015.
17. M. Flammini, G. Monaco, L. Moscardelli, M. Shalom, and S. Zaks. Online coalition
structure generation in graph games. In Proc. 17th Int. Conf. on Autonomous
Agents and Multiagent Systems (AAMAS), pages 1353–1361, 2018.
18. M. Flammini, G. Monaco, and Q. Zhang. Strategyproof mechanisms for additively
separable hedonic games and fractional hedonic games. In Proc. 15th Workshop
on Approximation and Online Algorithms (WAOA), pages 301–316, 2017.
19. M. Hoefer and A. Skopalik. Altruism in atomic congestion games. ACM Trans.
Econ. Comput., 1(4):21:1–21:21, 2013.
20. G. Monaco, L. Moscardelli, and Y. Velaj. Stable outcomes in modified fractional
hedonic games. In Proceedings of the 17th International Conference on Autonomous
Agents and MultiAgent Systems, AAMAS, pages 937–945, 2018.
21. N.-T. Nguyen, A. Rey, L. Rey, J. Rothe, and L. Schend. Altruistic hedonic games.
In Proc. 15th Int. Conf. on Autonomous Agents and Multiagent Systems, AAMAS,
pages 251–259, 2016.
22. M. Olsen. Nash stability in additively separable hedonic games and community
structures. Theory of Computing Systems, 45(4):917–925, 2009.
23. D. Peters. Graphical hedonic games of bounded treewidth. In Proc. of The 30th
AAAI Conf. on Artificial Intelligence (AAAI), pages 586–593, 2016.
24. D. Peters and E. Elkind. Simple causes of complexity in hedonic games. In Proc.
24th Int. Joint Conf. on Artificial Intelligence (IJCAI), pages 617–623, 2015.
25. A. Salehi-Abari and C. Boutilier. Empathetic social choice on social networks. In
Proc. 13th Int. Conf. on Autonomous Agents and Multi-agent Systems, AAMAS,
pages 693–700, 2014.
26. R. Umar and W. Mesbah. Throughput-efficient coalition formation of self-
ish/altruistic nodes in ad hoc networks: A hedonic game approach. Telecommun.
Syst., 67(1):95–111, Jan. 2018.