# on_pareto_optimality_in_social_distance_games__fa51c192.pdf

On Pareto Optimality in Social Distance Games

Alkida Balliu Gran Sasso Science Institute, Italy. alkida.balliu@gssi.infn.it

Michele Flammini DISIM - University of L Aquila & Gran Sasso Science Institute, Italy. michele.flammini@univaq.it

Dennis Olivetti Gran Sasso Science Institute, Italy. dennis.olivetti@gssi.infn.it

We investigate Pareto stability in Social Distance Games, that are coalition forming games in which agents utilities are proportional to their harmonic centralities in the respective coalitions, i.e., to the average inverse distance from the other agents. Pareto optimal solutions have been already considered in the literature as outcomes arising from the strategic interaction of the agents. In particular, they are stable under the deviation of the grand coalition, as they do not permit a simultaneous deviation by all the agents making all of them weakly better off and some strictly better off. We first show that, while computing a Pareto stable solution maximizing the social welfare is NP-hard in bounded degree graphs, a 2min{Δ, n}-approximating one can be determined in polynomial time, where n is the number of agents and Δ the maximum node degree. We then determine asymptotically tight bounds on the Price of Pareto Optimality for several classes of social graphs arising from the following combinations: unbounded and bounded node degree, undirected and directed edges, unweighted and weighted edges.

1 Introduction Coalition forming games have been largely investigated in the scientific literature (Dr eze and Greenberg 1980; Bogomolnaia and Jackson 2002; Elkind and Wooldridge 2009; Olsen 2012). Hedonic games (HG) (Dr eze and Greenberg 1980) are coalition forming games in which the outcomes are coalitions and agents have preferences over these coalitions. HGs where agents are part of a social graph and utilities depend on agents centralities have also been studied (Mc Sweeney, Mehrotra, and Oh 2012; Elkind and Wooldridge 2009; Olsen 2012). Fractional Hedonic Games (FHGs) are a subclass of HGs in which each agent s utility is her average value for the members of her coalition (Aziz, Brandt, and Harrenstein 2014). Two remarkable centrality measures considered in this setting are degree and harmonic centrality. Among the various notions (degree, harmonic, closeness, betweenness, eigenvector, ...), harmonic centrality has been identified as one of the best indexes, as it is the unique one satisfying a set of desirable properties (Boldi and Vigna 2014). Harmonic centrality induces another important class of games related

Copyright c 2017, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

to FHGs, called Social Distance Games (SDGs) (Brˆanzei and Larson 2011). SDGs are a family of coalitional games where the agent utility is measured in terms of closeness to the other members of the coalition. They can be seen as an extension of FHGs in which agents not directly connected to an agent i in a given coalition still contribute to her utility according to a properly defined measure proportional to the inverse of their distances from i. More precisely, given a social graph G where nodes are agents and edges express preferences, the utility of agent i in a given coalition P is defined as u(i, P) = 1 |P | vj P \{vi} 1 d P (i,j), where d P (i, j) is the shortest path distance between i and j in the subgraph of G induced by P. If i and j are disconnected in P, then d P (i, j) = . Thus, the utility of an agent is given by her harmonic centrality divided by the size of the coalition, or in other words by the average inverse distance from all the other nodes in her coalition. Stable solutions in general induce suboptimal outcomes. In this respect, two measures of decrease of performance due to Nash dynamics are well established in the research community: the Price of Anarchy (Koutsoupias and Papadimitriou 1999) and the Price of Stability (Correa, Schulz, and Moses 2004; Anshelevich et al. 2008). As far as Pareto stability is concerned, an analogous measure has been defined in (Elkind, Fanelli, and Flammini 2016), called Price of Pareto Optimality (PPO for short), which represents the ratio between the optimal social welfare and the social welfare of the worst Pareto optimal outcome of that game. While the PPO is the analogue of the price of anarchy for Nash equilibria, a corresponding measure related to the price of stability is meaningless, since an optimal solution is also Pareto optimal. The various fundamental notions of stability such as core stability, Nash stability, Pareto stability and individual stability have been already investigated in the context of HGs and FHGs (Brandl, Brandt, and Strobel 2015; Aziz et al. 2015; Suryapratim, Hideo, and Tayfun 2001; Bogomolnaia and Jackson 2002; Brˆanzei and Larson 2009; Gairing and Savani 2010; Elkind, Fanelli, and Flammini 2016; Bil o et al. 2014; Bil o et al. 2015). Surprisingly, despite the privileged role of harmonic centrality with respect to the other centrality indices remarked in (Boldi and Vigna 2014) which elects it as the best centrality measure, to the best of our knowledge SDGs have been

Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17)

investigated only in the context of core stability (Brˆanzei and Larson 2011). In this paper, we investigate Pareto stability in SDGs.

Related Work Pareto optimality in coalition formation games has been considered in (Aziz, Brandt, and Harrenstein 2013), where the authors proved that computing and verifying Pareto optimal partitions in Hedonic Games is intractable and gave some conditions to achieve tractablity. Pareto optimality has also been recently pointed out as a reasonable stability concept in coalition games in (Elkind, Fanelli, and Flammini 2016). In fact, Pareto optimality induces stable solutions, in the sense that agents feel satisfied by the fact that there is no other solution in which none of them is worse off, and some strictly improve. In other words, Pareto optimal solutions are resilient versus a simultaneous deviation of the grand coalition. Elkind et al. focused on Pareto stability in Hedonic Games. They explicitly defined the Price of Pareto Optimality (PPO) and estimated it in different classes of HGs: Additively Separable Hedonic Games, Fractional Hedonic Games, Modified Fractional Hedonic Games. Social Distance Games have been investigated and introduced in (Brˆanzei and Larson 2011). In particular, it has been proved that the price of anarchy in this context is Θ( n), and that the diameter of stable coalitions is upper bounded by a constant factor of 14. Thus, core stable partitions divide agents into small world coalitions. Moreover, it is shown that finding an optimal solution is NP-hard, while a 2-approximation can be achieved by decomposing the graph into diameter two subgraphs.

Our Contribution In this paper we investigate Pareto stability in Social Distance Games. We show that, while finding a Pareto optimal solution maximizing the social welfare is NP-hard in bounded degree graphs, a 2min{Δ, n}- approximating one can be determined in polynomial time, where n is the number of agents and Δ the maximum node degree. We then provide asymptotically tight bounds on the PPO for several classes of social graphs, and in particular for all the following combinations: unbounded and bounded node degree, undirected and directed edges, unweighted and weighted edges (see Tables 1 and 2). All the bounds are asymptotically tight, with the unique exception of weighted bounded degree undirected graphs.

Undirected Unweighted Weighted General Θ(n) Θ(n W) Δ-bounded Θ(Δ) Ω(ΔW), O(min{n W, ΔW 2})

Table 1: PPO bounds for undirected graphs, Δ-bounded stands for max degree Δ and W is the max edge weight.

1.1 Definitions and Notation We consider coalition formation games characterized by a finite set of agents V = {1, . . . , n} and an underlying so-

Directed Unweighted Weighted General Θ(n) Θ(n W) (1, 1) bounded Θ( n log n) Θ( n W W +log n + W) (Δ, 1) bounded Θ( n log logΔ n) Θ( n W log logΔ n)

Table 2: PPO bounds for undirected graphs, (Δi, Δo) bounded stands for max in-degree Δi and max out-degree Δo, W is the max edge weight.

cial relationship weighted directed graph G = (V, E, w), where nodes represent agents and arcs (i, j) E of weight w(i, j) the degree of preference or friendship that agent i has for agent j. Without loss of generality we assume that 1 w(i, j) W for every arc (i, j) E, W 1. We say that G is unweighted and write G = (V, E) if w(i, j) = 1 for every (i, j) E, otherwise we say that G is weighted. Moreover, we say that G is undirected if G is symmetric, that is if (i, j) E if and only if (j, i) E and w(i, j) = w(j, i) for all (i, j) E. In such a case we denote each pair of opposite arcs (i, j) and (j, i) simply as the edge {i, j}. A coalition is a non-empty subset of V . The set of all agents V is called the grand coalition; a coalition of size 1 is called a singleton coalition and its node isolated or a singleton; a coalition containing at least two agents is called a proper coalition. Given a coalition P, we denote by G(P) the subgraph of G induced by the agents in P. In the following, for the sake of simplicity, we will often identify G(P) directly with the corresponding coalition P and an agent with its node in G. A solution or outcome of the game is a partition P = {P1, . . . , Pk} of the nodes in k 1 coalitions. Given an agent i V , P(i) is the coalition P that contains i. Let μ(i, G ) be a node centrality measure of node i in a graph G = (V , E ). Two basic notions of centrality have been largely investigated in the literature, called degree centrality and harmonic centrality, respectively. In the former, μ(i, G ) is given by the node degree of i in G , while in the latter also nodes not directly connected to i contribute to her utility in an inverse manner with respect to their distances. Namely, μ(i, G ) =

j V \{i} 1 d G (i,j), where d G (i, j) is the distance between i and j in G . The utility of an agent i V in a given coalition P is a suitable function of her node centrality μ(i, G(P)) (or simply μ(i, P)) in the subgraph G(P) induced by P. More precisely, u(i, P) = μ(i,P )

|P | . With abuse of notation we also denote the utility of i in a given solution P simply as u(i, P) instead of u(i, P(i)). According to the considered centrality measure, different classes of coalition formation games arise. Fractional Hedonic Games (FHG) defined in (Aziz, Brandt, and Harrenstein 2014) correspond to the degree centrality, while Social Distance Games (SDG) of (Brˆanzei and Larson 2011) to the harmonic centrality. We denote by SDG(G) (resp. FHG(G) the Social Distance Game (resp. Fractional Hedonic Game) instance induced by graph G. Although degree and harmonic centralities are strongly related, there can be substantial differences, even in a sim-

ple star graph G = (V, E) with V = {1, . . . , n}, E = {(1, i)|2 i n}. In fact, in FHG(G) each leaf has utility 1/n, while in SDG(G) each leaf has utility 1/2, that is comparable to the one in complete graphs. The social welfare of a partition P is defined as SW(P) = n i=1 u(i, P). A partition P is optimal if SW(P ) SW(P) for every other partition P. We say that P Pareto dominates P if u(i, P) u(i, P ) for every i V and u(i, P) > u(i, P ) for some i V . A partition P is Pareto optimal if there is no partition P that Pareto dominates P. Clearly an optimal partition is also Pareto optimal, but the opposite does not hold in general. We call a Pareto optimal solution stable, as it can be seen as an outcome of the game that is stable under the deviation of the grand coalition. More precisely, it does not allow a simultaneous deviation by all the agents that makes all agents weakly better off and some agents strictly better off. Let PO be the set of all Pareto optimal partitions and let P be an optimal partition.

Definition 1. Given a social graph G, the Price of Pareto Optimality (PPO) of G is defined as PPO(G) = max P PO SW (P )

SW (P) . Given a family of graphs G, the Price of Pareto Optimality of G is PPO(G) = max G G PPO(G).

In the following we will always implicitly assume that the social graph G is weakly connected, otherwise SDG(G) can be split in independent games defined on its weakly connected components. Starting from the above assumption, the following facts concerning SDGs will be often exploited in the next sections.

Fact 1. Let P be a stable partition for SDG(G). Then the following properties hold:

1. P must contain at least one proper coalition; 2. every proper coalition of P induces a weakly connected subgraph; 3. 1 2W SW(P) < n; moreover, if G is undirected, SW(P) 1 W ; 4. the isolated nodes in P form an independent set in G.

Proof. Properties 1, 2 and 4 can be easily checked, thus we focus only on the third property. P has at least a proper weakly connected coalition P (by properties 1, 2). Then, P contains at least |P| 1 arcs and since every arc (i, j) in P increases the utility of i at least by 1 W |P |, the overall social welfare of P, which is at least equal to the sum of the utilities of the agents in P, is at least (|P | 1)

W |P | 1 2W . Similarly, if G is undirected, then SW(P) 1 W holds by observing that an edge {i, j} increases at least by 1 W |P | the utilities both

of i and j, so that SW(P) 2(|P | 1)

W |P | 1 W . Moreover, in every case SW(P) < n, as every agent i is at distance at least 1 from all the other agents in P(i), so that her utility is u(i, P) |P(i)| 1

|P(i)| < 1.

Notice that Definition 1 is well posed, as for any stable solution SW(P) > 0 always holds. In the following we will denote by G (resp. G ) the family of all the unweighted undirected (resp. directed) graphs, by G(Δ) the family of the unweighted undirected graphs with maximum node degree bounded by Δ 1, by G (Δi, Δo) the family of the undirected graphs with in-degree bounded by Δi 1 and out-degree bounded by Δo 1. The corresponding families for weighted graphs with arc weights between 1 and W are denoted by GW , G W , GW (Δ) and G W (Δi, Δo). Again, we implicitly assume that all the graphs in such families are weakly connected.

2 Computational Complexity Results

As shown in (Brˆanzei and Larson 2011), determining an optimal solution P , i.e., maximizing SW(P ), is NP-hard. We now extend such a result to bounded degree graphs (due to space limitations the proof is omitted).

Theorem 1. The problem of determining an optimal solution for any G G(6) is NP-hard.

Notice that, since the optimum is also stable, this also implies the hardness of finding the best stable solution in bounded degree graphs. Stable solutions suitably approximating optimal ones can be determined according to the following algorithm:

P , X = V , G(X) subgraph induced by X, i = 1; while X = do

ui node of maximum degree in G(X); Nui set containing ui and its neighbors in G(X); P P {Nui}, X X \ Nui, i i + 1; G(X) subgraph induced by X; end

Theorem 2. Given any G G(Δ), Δ 1, the above algorithm constructs a r-approximating stable solution P with r = 2min{Δ, n}, i.e., with SW (P )

Proof. In the i-th iteration of the algorithm, once the node ui of maximum degree xi in the residual graph is selected, a new proper coalition Pi of size xi + 1 is formed, in which ui is called center. Such a coalition contributes xi

2 + xi xi+1 to the social welfare. Let then P be the solution determined by the algorithm, and P1, . . . , Pk be the proper coalitions in P. The formation of Pi in iteration i might leave some agents disconnected, that is alone in a singleton coalition, as their neighbors belong only to Pi or to the previously formed coalitions. Since centers are chosen in non-increasing degree, the number of disconnected agents created by Pi is at most xi(xi 1). The overall number of nodes that are in Pi or that are disconnected by Pi, that is belonging to Nui, is thus at most x2 i + 1. Since the sets Nui form a partition of V , we thus have that k i=1(x2 i + 1) = n. As the optimal social welfare is trivially upper bounded by n, it is enough to show that the algorithm achieves social

welfare is at least max n

2 , n 2Δ . By the above remarks,

SW(P) = k i=1( xi

2 + xi xi+1), subject to (x2 i + 1) = n. It is possible to show that SW(P) is minimized for k = 1, achieving a social welfare at least n 1/2 + n 1/( n 1 + 1) n/2. Considering also the degree bound, we have that k i=1( xi

2 + xi xi+1) is minimized when xi = Δ. In this case, the number of iterations is at least n/(Δ2 + 1) , hence SW(P) n Δ2+1( Δ

2 + Δ Δ+1) n 2Δ. As far as stability of the returned solution is concerned, notice that in any other solution the utility of the center xi with minimum i having a different coalition has a strictly smaller utility.

Notice that, if stability is not a concern, it is possible to efficiently determine a solution that could possibly be unstable, in which every agent has utility at least 1/2. We can obtain such a solution according to the following procedure. Consider each connected component P. We can construct a tree T spanning the nodes of P. Such a tree can be partitioned in stars by means of the following iterative process: i) if T is a star we are done; ii) if T is not a star consider the deepest leaves (starting from a given root node) that have a common parent and form a star with all such nodes, delete the star from the current tree T and iterate from step i). In this way, all the agents in the new subcoalitions identified by the stars have utility at least 1

2. Notice also that this guarantees the existence of a stable solution, dominating the above one, that is a 2 approximation of the optimal one and guarantees a nice level of fairness, that is in which all the agents have utility at least 1/2. However, its determination in polynomial time remains an open question. As a final remark, although we can achieve a 2min{Δ, n}-approximating stable solution, as we will see, if agents are allowed to freely form their coalitions, they can end up in stable solutions achieving a worse approximation.

3 Undirected Graphs In this section we provide an asymptotically tight bound of Θ(Δ) on the PPO for the family of the bounded degree graphs G(Δ) for any Δ 1, showing that the maximum degree Δ is the crucial parameter in determining the price of Pareto optimality of SDGs. Notice that this also gives a corresponding Θ(n) result for general undirected graphs, just considering Δ = n 1 and observing that G = G(Δ). Let us first introduce some useful lemmas.

Lemma 1. Given G G(Δ) and a stable solution P for G, in every proper coalition P of P there exists at least one agent i having utility u(i, P) 1

Proof. If every node of a given coalition P has utility < 1

2, then P is not be stable, as it is possible to obtain a strictly dominating solution by using the 2 approximation algorithm shown before, that guarantees utility at least 1

2 to each node of the coalition.

Let i be an agent with utility at least 1/2. We suitably bound agent utilities according to their distances from i.

Lemma 2. Given G G(Δ), a Pareto stable solution P and any proper coalition P of P, let i be an agent in P with utility at least 1

2. Then, every agent j P at distance t from i has utility at least 1 2(t+1).

Proof. Let j be a generic node in P at distance t from i, D be the diameter of P and nd be the number of nodes at distance d from i in P. Since all the nodes at distance d from i are at distance at most d + t from j, and i is at distance t

from j, u(j,P)

D d=1 nd d+t |P | D d=1 nd

D d=1 nd d+t D d=1 nd

d 1 t+1, that im-

plies u(j, P) u(i,P)

t+1 1 2(t+1).

As a consequence, the following lemma holds.

Lemma 3. Given a stable solution P and a proper coalition P of P, the overall utility of the nodes in P is at least |P |

Proof. By Lemma 1,

d 1+ D d=1 nd = u(i, P) 1 2, that is D d=1 nd

d > 1+ D d=1 nd 2 . Therefore, by applying Lemma 2, SW(P) 1

2 + D d=1(nd 1

4 1+ D d=1 nd 2 |P |

We are now able to prove the final theorem.

Theorem 3. PPO(G(Δ)) = Θ(Δ).

Proof. Consider any graph G G(Δ) and a stable partition P for G. Let I be the set of the isolated nodes in P, that is belonging to singleton coalitions, and P1, ...., Pk be the proper coalitions in P. By Lemma 3 the social welfare of P is SW(P) |P1|+...+|Pk|

8 . On the other hand, since every non isolated node can be adjacent to at most Δ 1 isolated nodes in I, |I| (Δ 1) (|P1| + . . . + |Pk|), so that by Fact 1 the social welfare of any optimal solution P is SW(P ) < |I| + |P1| + . . . + |Pk| Δ(|P1| + . . . + |Pk|). Therefore, SW (P )

SW (P) Δ(|P1|+...+|Pk|)

|P1|+...+|Pk|

In order to derive a corresponding lower bound, we observe that there exists a Δ-bounded degree graph G G(Δ) for which PPO(G) > 3 10Δ = Ω(Δ). Such a graph is depicted in Figure 1, the number of nodes is Δ + 2.

a) b) c) 1 2 3 1 2 3 1 2 3

Figure 1: PPO lower bound in undirected graphs: a) original graph, b) a Pareto stable solution, c) optimal solution.

4 Directed Graphs We now analyze the price of Pareto optimality of SDGs for the family G of the directed graphs. In the general case the following theorem holds.

Theorem 4. PPO( G ) = Θ(n).

Proof. The undirected lower bound of Ω(n) for the family of the undirected graphs G directly applies to directed graphs, as an undirected graph corresponds to a special case of directed graph, that is to a symmetric directed graph, so that G G . For what concerns the upper bound, by Fact 1, given any stable solution P and optimal partition P for a graph G G , SW (P )

SW (P) < n 1/2 = 2n.

Unfortunately, unlike the undirected case, the price of Pareto optimality can be very high even in the very restricted scenario of directed graphs with in-degree and out-degree bounded by 1.

Theorem 5. PPO( G (1, 1)) = Θ( n log n).

Proof. As far as the lower bound is concerned, notice that a connected (1, 1)-bounded degree directed graph G G (1, 1) can be either a ring or a path. In both cases, a stable solution is given by the partition Pg consisting only of the grand coalition. In fact, as every node has out-degree 1, any other partition P would yield a null utility to at least one node having non null utility in Pg, and thus would not dominate Pg. Since in Pg every node i can have at most one node at any given distance d, 1 d n 1, the achieved social welfare is SW(Pg) = n i=1 u(i, Pg) n n 1 d=1

1 d n = Hn 1 1 + ln n, where Hn is the n-th harmonic number. Assuming an even number n of agents, consider the solution constructed by selecting a perfect matching M in G and forming for each arc e in M a coalition containing the two endpoints of e. Since every coalition has an overall utility of 1/2, yielding an overall social welfare n/4, we obtain (SW(P ))/(SW(Pg)) (n/4)/(Hn), proving the lower bound. For what concerns the upper bound, consider any stable solution P and let P1, . . . Pk be the proper coalitions in P. By Fact 1, each Pj induces a weakly connected subgraph and thus it is a directed path or a directed cycle. Then, since at least |Pj|

2 nodes in Pj have one node at distance d for every fixed d such that 1 d |Pj|

2 , the overall utility

of Pj is at least ( |Pj|

2 )/|Pj| H|Pj |

4 . Now let

I be the set of the isolated nodes in P. Agents in I form an independent set in G (Fact 1), hence |I| k + 1. Then, SW(P) H|P1|

4 + . . . + H|Pk|

8 , and the claim follows by observing that the optimal social welfare is at most n/4.

An even worse result holds as soon as the maximum indegree increases, even if bounded by 2.

Lemma 4. For any Δ > 1, PPO( G (Δ, 1)) = Ω( n log logΔ n).

Figure 2: PPO lower bound in bounded directed graphs. (2a) Pareto stable (2b) optimal solution

Proof. Consider the directed tree in Figure 2. A stable solution is represented in Figure 2a and corresponds to the partition P with a coalition P containing all the nodes except the leaves, plus a singleton coalition for each leaf. In fact, consider any other partition P . Since every node has out-degree 1, if P has a coalition intersecting P and not containing P, at least a node with non null utility in P would have utility 0 in P . Moreover, if P has a coalition containing P and some leaves, all the nodes in P have strictly smaller utility in P . Thus P does not dominate P. Let then h be the height of the tree. Each node (except the leaves) has Δ children. This means that at level 1 we have Δ nodes, at the second level Δ2 nodes and so forth, so that the number of leaves, which is equal to the number of nodes in the previous level h 1 is Δh 1. Therefore, the total number of nodes is n = h 1 l=0 (Δ)l + Δh 1 Δh 1, so that h 1 + logΔ n.

Thus, the social welfare of P is SW(P)

h 1 l=1 Δl Hl n Δh 1

(n Δh 1)(1+ln h)

n Δh 1 = 1 + ln h < 2 + ln logΔ n, where for every integer l, l 1, Hl is the l-th harmonic number. Consider then the partition shown in Figure 2b, where the Δh 1 leaves achieve utility 1

2 and all the other nodes utility 0. Then, the optimal social welfare is at least Δh 1

2 n 6 , and we can conclude that the lower bound on the PPO in bounded degree directed graphs is Ω( n log logΔ n).

We now provide an asymptotically matching upper bound exploiting the following lemma, whose proof is omitted.

Lemma 5. Given any G G (Δ, 1), a stable solution P and a coalition Pj P, the overall utility of Pj is at least equal to the one of a Δ-ary complete directed tree Tj defined on the nodes in Pj.

Theorem 6. For any Δ > 1, PPO( G (Δ, 1)) = Θ( n log logΔ n).

Proof. By Lemma 4, it suffices to determine an asymptotically matching upper bound. To this aim, consider any stable solution P and let P1, . . . Pk be the proper coalitions in P. By the stability of P and Fact 1, every Pj is weakly connected. By Lemma 5, the overall utility of each Pj is at least equal to the one of the tree Tj in the claim, that is at least the overall utility reached by the at least |Pj|/2 nodes in the last 2 levels (recall that Δ 2), i.e., at least |Pj|Hh 1

2 ln logΔ |Pj|

2 . Let q be the number of isolated nodes in P. Then q + |P1|+. . .+|Pk| = n, and since by Fact 1 isolated nodes form an independent set in G and every non isolated node is adjacent to at most Δ isolated nodes, q Δ (|P1|+. . .+|Pk|), so that |P1| + . . . + |Pk| = n q n Δ (|P1| + . . . + |Pk|), i.e. |P1| + . . . + |Pk| n Δ+1. Finally, SW(P)

ln logΔ |P1|

2 + . . . + ln logΔ |Pk|

2 ln logΔ(|P1|+...+|Pk|)

2 ln logΔ n Δ+1 2 = Ω(log logΔ n). The claim then follows by observing that the social welfare of an optimal solution P is at most n, so that SW (P )

SW (P) = O n log logΔ n .

We now prove a counterintuitive property concerning SDGs in directed graphs. In particular, one might think that, as in undirected graphs, the worst case stable solution, that is yields the highest price of Pareto optimality, can be achieved when a large number of nodes remains isolated. The following lemma states that instead this is not the case, as the existence of such stable solutions immediately implies a lower PPO for the corresponding instances.

Theorem 7. Given any Δ > 1, a (Δ, 1)-bounded degree directed graph G G (Δ, 1) and a stable solution P having α n isolated nodes, 0 α < 1, the price of Pareto optimality of SDGs on G is PPO(G) = O (1 α) n ln logΔ n .

Proof. Consider any stable solution P for G. As shown in the previous theorem, SW(P) Ω(log logΔ n). In order to prove the claim, it is then sufficient to show that an optimal partition P for G has social welfare SW(P ) = O((1 α) n). Let P 1 , . . . , P k be the proper coalitions of P . If α 1

2 then the theorem trivially holds. Assume then α > 1

2. Let I (resp. N) be the set of the isolated (resp. non isolated) nodes in P. By Fact 1, nodes in I form an independent set, and since the node out-degree is at most 1, the number of nodes of in-degree 0 in I is at least |I| |N| = α n (1 α)n = (2α 1)n. Let I I be such a subset of the nodes in I of in-degree 0, and let Ij = I P j , 1 j k, be the subset of the nodes of I contained in coalition P j of P. Since no node in P j can reach any node in Ij, the over-

all utility of P j is at most |P j | (|P j | |Ij|) |P j | = |P j | |Ij|. Let

I0 = I \(I1 . . . Ik). Then, since P 1 . . . P k = V I0, SW(P ) k j=1(|P j | |Ij|) = n |I0| k j=1 |Ij| =

n k j=0 |Ij| = n |I | n (2α 1)n = 2(1 α)n = O((1 α)n), hence the claim.

5 Weighted Graphs Due to space limitations, in this section we briefly sketch how to extend our results to the weighted case. For general undirected bounded degree weighted graphs, an Ω(ΔW) lower bound can be obtained by extending the unweighted worst case instance in Figure 1, setting the weights of edges (2, 3) and (1, 2) to W and 1

2W +ϵ, ϵ < 3

4, respectively. As in the unweighted case, this result can be adapted to general graphs, showing a lower bound of Ω(n W). It is also possible to extend the unweighted case proof to show an upper bound of O(min{ΔW 2, n W}) when Δ > 1, which provides also an asymptotically matching result for general graphs. In the directed case, the proofs for unbounded degree weighted graphs can be suitably adapted to get a PPO of Θ(n W) in the general case. In fact, the lower bound of the undirected weighted case directly applies, as an undirected graph is a special case of directed graph, and the upper bound derives by applying Fact 1. For bounded degree graphs, the following theorem holds.

Theorem 8. PPO( G W (Δ, 1)) = Θ( n W W +log n + W) if Δ =

1 and PPO( G W (Δ, 1)) = Θ( n W log logΔ n) if Δ > 1.

Proof. (Sketch) The proof of the (1, 1) case is rather technical. The lower bound is given by a directed path in which arc weights are alternatively equal to 1 and W. For the upper bound, first of all the optimal social welfare can be suitably bounded by showing that, given any G G W (1, 1) and optimal partition P for G, SW(P )

e E 1 we , where we is the weight arc e E. Then, since every proper coalition Pi of a stable solution P induces a directed path or a directed cycle, it is possible to derive that u(Pi) =

e Ei 1 we ) W +log |Pi|

|Pi|W , where Ei is the set of the arcs of the subgraph induced by Pi. Finally, if P1, . . . , Pk are the proper coalitions of P, SW(P) = u(P1) + + u(Pk)

1 W k i=1 ci W +log |Pi|

|Pi| , where ci =

e Ei 1 we , and af-

ter some mathematical steps, SW(P) = Ω

e E 1 we n W W +log n +W

The lower bound for the (Δ, 1)-bounded case with Δ > 1 is given by the same construction of Figure 2, letting all the weights of the arcs outgoing from the leaves be equal to 1, while all the others equal to W. An asymptotically matching upper bound comes strictly mimicking the corresponding proof of the unweighted case.

6 Conclusions and Open Questions We investigated the price of Pareto optimality SDGs, proving asymptotically tight bounds for several topologies. An interesting open question concerns the determination of the PPO for the family of the directed graphs with inand out-degree bounded by Δ. In the unweighted case it would be nice to determine the minimum value of Δ leading to the worst possible Ω(n) lower bound on the PPO, and similarly to Ω(n W) in the weighted case. Finally, it would be nice to see if we can achieve a constant factor approximation of the stable optimal solution in general graphs.

References Anshelevich, E.; Dasgupta, A.; Kleinberg, J. M.; Tardos, E.; Wexler, T.; and Roughgarden, T. 2008. The price of stability for network design with fair cost allocation. Society for Industrial and Applied Mathematics (SIAM) Journal of Computing 38(4):1602 1623. Aziz, H.; Gaspers, S.; Gudmundsson, J.; Mestre, J.; and T aubig, H. 2015. Welfare maximization in fractional hedonic games. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 15), Buenos Aires, Argentina, July 25-31, 2015, 461 467. Aziz, H.; Brandt, F.; and Harrenstein, P. 2013. Pareto optimality in coalition formation. Games and Economic Behavior 82:562 581. Aziz, H.; Brandt, F.; and Harrenstein, P. 2014. Fractional hedonic games. In International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 5 12. Bil o, V.; Fanelli, A.; Flammini, M.; Monaco, G.; and Moscardelli, L. 2014. Nash stability in fractional hedonic games. In Web and Internet Economics - 10th International Conference, (WINE), 486 491. Bil o, V.; Fanelli, A.; Flammini, M.; Monaco, G.; and Moscardelli, L. 2015. On the price of stability of fractional hedonic games. In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems (AAMAS). Bogomolnaia, A., and Jackson, M. O. 2002. The stability of hedonic coalition structures. Games and Economic Behavior 38(2):201 230. Boldi, P., and Vigna, S. 2014. Axioms for centrality. Internet Mathematics 10(3-4):222 262. Brandl, F.; Brandt, F.; and Strobel, M. 2015. Fractional hedonic games: Individual and group stability. In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems (AAMAS 15), Istanbul, Turkey, May 4-8, 2015, 1219 1227. Brˆanzei, S., and Larson, K. 2009. Coalitional affinity games. In Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems (AAMAS). International Foundation for Autonomous Agents and Multiagent Systems. Brˆanzei, S., and Larson, K. 2011. Social distance games. In 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), Taipei, Taiwan, May 26, 2011, Volume 1-3, 1281 1282. Correa, J. R.; Schulz, A. S.; and Moses, N. E. S. 2004. Selfish routing in capacitated networks. Mathematics of Operations Research 29(4):961 976. Dr eze, J. H., and Greenberg, J. 1980. Hedonic coalitions: Optimality and stability. Econometrica 48(4):987 1003. Elkind, E., and Wooldridge, M. 2009. Hedonic coalition nets. In 8th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), 417 424. Elkind, E.; Fanelli, A.; and Flammini, M. 2016. Price of Pareto optimality in hedonic games. In Proceedings of the

Thirtieth AAAI Conference on Artificial Intelligence, 475 481. Gairing, M., and Savani, R. 2010. Computing stable outcomes in hedonic games. In Third International Symposium on Algorithmic Game Theory (SAGT), 174 185. Koutsoupias, E., and Papadimitriou, C. H. 1999. Worstcase equilibria. In 16th Annual Symposium on Theoretical Aspects of Computer Science, Trier, Germany, March 46, 1999, Proceedings. Lecture Notes in Computer Science 1563, 404 413. Springer. Mc Sweeney, P. J.; Mehrotra, K.; and Oh, J. C. 2012. A game theoretic framework for community detection. In International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2012, Istanbul, Turkey, 26-29 August 2012, 227 234. Olsen, M. 2012. On defining and computing communities. In Eighteenth Computing: The Australasian Theory Symposium (CATS), 97 102. Suryapratim, B.; Hideo, K.; and Tayfun, S. 2001. Core in a simple coalition formation game. Social Choice and Welfare 18(1):135 153.