Social Distance Games

1 Introduction

Game theory provides a rich mathematical framework for analysing interactions among self interested parties. Coalitional games study the dynamics of players that interact to accomplish more together than they would individually. The central questions in coalitional game theory are how the players should cooperate and how the payoffs should be divided among the members of a coalition.

In recent years there has been growing interest in the field and many new classes of games have been formalised. One of the main driving forces behind the development of new games was the emergence of the internet, with applications such as internet architecture, routing, peer-to-peer systems, and viral marketing. As Scott Shenker famously said, "The Internet is an equilibrium, we just need to identify the game" [Nisan et al., 2007]. Another important line of research that contributed to the development of coalitional games was inspired from social and economic networks ( [Easley and Kleinberg, 2010], [Jackson, 2008]). Social networks influence all aspects of everyday life, such as where people live, work, what music they listen to, and with whom they interact. Early work on social networks was done by Milgram in the 1960's and his experiments indicated that any two people in the world are connected by a path of average length six. This idea is also known as the six degrees of separation hypothesis. Since then, researchers observed that many natural networks, such as the web, biological networks, networks of scientific collaboration, exhibit the same properties as the web of human acquaintances. The emergence of online communities such as Facebook, MySpace, and LinkedIn has enabled a much more detailed analysis of real networks.

Research in network formation focuses on how the structure of the network influences the behaviour of the players, what type of equilibria arise, which players are influential, and which networks are efficient. The study of network formation games has in turn led to important theoretical concepts and new analysis tools.

In this paper we formulate a model of interaction on social networks using coalitional game theory and the notion of social distance. Our game captures the idea that social networks exhibit homophily, and so the agents prefer to maintain ties with other agents who are close to them. Using social distance games, we study the properties of efficient and stable networks, relate them to the underlying graphical structure of the game, and give an approximation algorithm for finding optimal social welfare. We use the stability gap to investigate the welfare of stable coalition structures, and propose two new solution concepts with improved welfare guarantees.

2 The Model

In this section we introduce social distance games and key concepts from the literature. We assume the reader is familiar with basic graph theoretic notions including shortest path, complete graph, and induced subgraph.

Our utility formulation is based on the concept of social distance, which is the number of hops required to reach one node to another, and has become famous since Milgram's study on six degrees of separation. The utility function reflects the principle of homophily, that similarity breeds connection and people tend to form communities with similar others [McPherson et al., 2001]. Homophily has been repeatedly observed in many real world networks, such as marriage, friendship, work, and voluntary organizations.

Definition 1. A social distance game is represented as a simple unweighted graph G = (N, E) where

• N = {x1 , . . . , xn} is the set of agents
• The utility of an agent xi in coalition C ⊆ N is

where dC(xi, xj) is the shortest path distance between xi and xj in the subgraph induced by coalition C on the graph G. If xi and xj are disconnected in C, then dC(xi, xj ) = ∞.

The inverse social distance can be viewed as the similarity of a player with the other members of the coalition, and it indicates the centrality of the player in that coalition.

A singleton agent always receives zero. To be consistent, we define the similarity of an agent to himself as zero, and so when computing the utility of an agent in a coalition C, we divide by the size of C.

Our utility formulation is a variant of closeness centrality, is well defined on disconnected sets, and normalized in the interval [0, 1]. Moreover, it is related to several other classical measures from network analysis, such as degree, closeness, betweenness, and eigenvector centrality [Gomez et al., 2003], all of which are used to determine how a node is embedded in the network. Our main goal is to understand the dynamics generated by homophily driven communities, and so this utility function has a number of desirable properties that reflect the sociable nature of the agents.

Property 1. An agent prefers direct connections over indirect ones.

In general, the agent prefers a connection by a factor inversely proportional with the distance to that connection.

Property 2. Adding a close connection positively affects an agent's utility.

Moreover, our improvement function reflects diminishing returns. An additional friend benefits everyone, but the added benefit depends on how many friends the agent already has.

Property 3. Adding a distant connection negatively affects an agent's utility.

Property 3 states that agents who want to be central in their coalition experience loss in social status because of distant connections.

Property 4. All things being equal, agents favour larger coalitions.

2.1 Background

Let a coalition structure, P, be a partition of the agents into disjoint coalitions. The set of agents, N, is known as the grand coalition, and we denote its size by |N| = n.

Definition 2. The social welfare of coalition structure P = (C1 , . . . ,Ck) is

Denote the utility of agent xi in partition P as u(xi, P ) or, when the context is clear, as u(xi). Figure 1 is an example of a social distance game.

The main notion of stability that we study in this paper is the core solution concept.

Definition 3. A coalition structure P = (C1 , . . . ,Ck) is in the core if there is no coalition B ⊆ N such that ∀x ∈ B, u(x,B) ≥ u(x, P ) and for some y ∈ B the inequality is strict: u(y,B) > u(y, P ). If all the inequalities are strict then P is in the weak core.

If coalition structure P is in the core, then P is resistant against group deviations. No coalition can deviate and improve the utility of at least one member, while not degrading the other ones. If B exists, then it is called a blocking coalition.

Finally, we introduce the graph theoretic notion of diameter on simple graphs.

Definition 4. The diameter of a graph G is the longest shortest path between any two vertices of G.

We assume coalitions are connected, since a disconnected coalition can improve everyone's utility by splitting into its connected components, and that the input graph is connected, since disconnected graphs can be analyzed componentwise. We emphasize a coalition is defined on the subgraph it induces on the original graph.

3 Social Welfare

We are interested in understanding the properties of social welfare maximising structures in social distance games. These structures can be viewed as the best outcomes for the society overall. The next properties follow immediately from the definition of the model.

Property 5. On complete graphs, the grand coalition is the only welfare maximising coalition structure.

Property 6. The welfare of any coalition structure is bounded by n - 1.

Note that the upper bound is only attained by the grand coalition on complete graphs.

From Property 5, the grand coalition is welfaremaximising on complete graphs. However, the grand coalition is still welfare maximising on complete bipartite graphs (such as a star), which can be significantly sparser. In addition, complete bipartite graphs have diameter two, and thus the grand coalition is both optimal and gives utility at least 1/2 to each agent.

3.1 An Approximation of Optimal Welfare

Finding the optimal welfare partition can be shown to be NPhard on social distance games via a reduction from Partition into Triangles. In this section we give an algorithm to approximate optimal welfare within a factor of two. The algorithm decomposes the graph into connected components, such that each component has diameter less than or equal to two, and no component is a singleton. We call this type of partition a diameter two decomposition of the graph.

Theorem 1. Diameter two decompositions guarantee to each agent utility at least 1/2.

Proof. Let G be a graph, P a diameter two decomposition of G, C a coalition in P, and xi ∈ C an agent. Let a and b the number of agents in distance one and two from xi, respectively. The diameter of C is at most two, hence |C| = a + b + 1. The utility of xi in C is:

C is not a singleton, thus xi has at least one direct neighbour in C, and so a ≥ 1. Using Equation 1, we get u(xi) ≥ 1/2.

The diameter two decomposition is an approximation of optimal welfare that satisfies at the same time a notion of fairness: every agent is guaranteed to receive more than half of their best possible value. In general, welfare maximising and core stable partitions do not necessarily ensure that every agent receives at least 1/2.

Algorithm 1 Fair Approximation of Optimal Welfare

1: T ←Minimum-Spanning-Tree(G); 2: k ← 1; 3: while |T| ≥ 2 do 4: xk ←Deepest-Leaf(T); 5: Ck ← {Parent(xk)}; 6: for all y ∈ Children(Parent(xk)) do 7: Ck ←Ck ∪ {y}; 8: end for 9: // Remove vertices Ck and their edges from T 10: T ← T -Ck; 11: k ← k + 1; 12: end while 13: // If the root is left, add it to the current coalition 14: if |T| = 1 then 15: Ck ←Ck ∪ {Root(T )}; 16: end if 17: return (C1 , . . . , Ck);

Algorithm 1 finds a diameter two decomposition of the graph. Let T be a minimum spanning tree of G. Iteratively remove stars from T, starting from the bottom leaves. In each iteration i, let xi be a leaf of maximum depth. Place xi and Parent(xi), the parent of xi, in the same coalition Ci, together with all the direct children of Parent(xi). The tree remains connected after each such removal, since otherwise there must have been a leaf of greater depth than xi. In the last iteration, k, there may be only one node left, namely Root(T ), the root of the tree. In that case, add Root(T ) to coalition Ck. Note that Root(T ) is still distance at most two from all the nodes in Ck. The algorithm has runtime O(n).

Corollary 1. The optimal welfare partition attains at least n/2, where n is the number of vertices.

4 The Core

Group stability is an important concept in coalitional games. No matter how many desirable properties a coalition structure satisfies, if there exist groups of agents that can deviate and improve their utility by doing so, then that configuration can be easily undermined. We investigate properties of the core in social distance games.

Property 7. On complete graphs, the grand coalition is the only core stable coalition structure.

There exist social distance games for which the core is empty, such as the game in Figure 1. The grand coalition is blocked by {1, 2, 4, 5}, partition ({0, 3}, {1, 2, 4, 5}) is blocked by {1, 2, 3, 4, 5}. Similar examples exist for the weak core. However, if the graph is a tree, the weak core always exists and can be found in polynomial time.

Theorem 2. Algorithm 1 returns a weak core partition when the graph is a tree.

4.1 Core Partitions are Small Worlds

A small world network is a graph in which most nodes can be reached from any other node using a small number of steps through intermediate nodes [Jackson, 2008]. Small worlds in classical random graphs have an average path length of O(ln(n)), while scale-free networks have a path length of O(ln(n)/ ln(ln(n))). Most real networks display the small world property, and examples range from genetic and neural networks to the world wide web [Barabasi and Oltvai, 2004]. In this model, core stable partitions divide the agents into small world coalitions, regardless of how wide the original graph was. We obtained an upper bound of 14 on the diameter of any coalition in the core. The tight bound is likely even lower.

Theorem 3. The diameter of any coalition belonging to a core partition is bounded by the constant 14.

Proof. Let C be a coalition belonging to a core partition. Denote |C| = c, D the diameter of C, and x0, y two agents with dC(x0 , y) = D. Divide C into sets (C0 = {x0}, C1 , . . . , CD), with Ci = {z ∈ C|dC(x0 , z) = i}, and define A = C0 ∪C1 ∪. . .∪C⌊ D4 ⌋ , B = C⌊ D4 ⌋+1 ∪. . .∪C⌊ D2 ⌋ , Γ = C⌊ D2 ⌋+1 ∪ . . . ∪ C⌊ 3D 4 ⌋ , and Δ= C⌊ 3D 4 ⌋+1 ∪ . . . ∪ CD, where |A| = α, |B| = β, |Γ| = γ, |Δ| = δ, and α + β + γ + δ = c.

Let x1 ∈ C1. Agent x0 is connected to all of C1, and so it is connected to x1. C is in the core, thus coalition {x0 , x1} is not blocking, and so at least one of x0, x1 obtains utility 1/2. Observe that agents x0 and x1 prefer B, Γ, and Δ to be small, because the agents in those sets are distant and contribute to decreasing x0 and x1's utility.

or equivalently,

Similarly, let xD ∈ CD. Agent xD can be directly connected only to agents in CD and CD-1. There must exist a path from x0 to xD that passes through CD-1, thus there is xD-1 ∈ CD-1 neighbour of xD. Then

Use D′ to get simplified (coarser) bounds:

or equivalently,

Summing Inequalities 2 and 3:

that is:

Finally, take the "perspective" of the middle agents. Let x⌊ D2 ⌋+1 ∈ C⌊ D2 ⌋+1 . There is a path from x⌊ D2 ⌋+1 to x0 that passes through C⌊ D2 ⌋ , thus there exists x⌊ D2 ⌋ ∈ C⌊ D2 ⌋ connected to x⌊ D2 ⌋+1 .

that is,

if and only if

Multiplying Inequalities 4 and 5, we get (D′ - 8)(D′ - 6) ≤ 43 D′ . Solving for integer D′ and taking into account that D ≥ 8, it follows that D′ ≤ 10, and so D ≤ 14.

5 Stability Gap

We observed from the empty core game in Figure 1 that maximum welfare partitions are not always stable, and from Figure 2 that stable partitions do not necessarily maximise welfare. We analyse the loss of welfare that comes from being in the core using the notion of stability gap [Brˆanzei and Larson, 2009]. The worst case and best case performance of a core member are measured by the minimum and maximum stability gap, respectively. The stability gap parallels the prices of anarchy and stability [Nisan et al., 2007] and is defined for games with non-empty cores.

Let P ∗ be a welfare maximising coalition structure and P C a member of the core. In the best case, P C is also a welfare maximiser. Since it is possible that no core member attains the welfare of P ∗ , the quantity

measures the worst case ratio. We show the worst case bound for the stability gap of social distance games is Θ(√n). In order to get the bound, we use a few lemmas.

Lemma 1. If an agent has utility greater than 1/2 in a coalition, then all its direct neighbours from the same coalition have utility at least 1/4.

Lemma 2. If P is a partition in the core and x, y two agents adjacent in G, then at least one of x, y attains utility greater than or equal to 1/2 in P .

Corollary 2. The welfare of any non-singleton coalition in a core stable partition is at least 1/4 of the maximum possible for that coalition.

Theorem4. Let G = (N, E) be a game with nonempty core. Then Gapmin (G) is in worst case Θ(√n).

Proof. Let partition P ∗ be welfare maximising and P = (C1 , . . . , Ck, S1 , . . . , Ss) in the core, where ci ≥ 2, i = 1, k, and |Sj| = 1, j = 1, s. Let Ti, Di, and Fi denote the sets of agents in Ci with utilities strictly greater than 1/2, equal to 1/2, and strictly less than 1/2, respectively. Denote ti = |Ti|, di = |Di|, fi = |Fi|, and ci = |Ci|. The sets Ti, Di, and Fi are disjoint, Ti is non-empty, and Ti ∪Di ∪ Fi = Ci .

From Lemmas 1 and 2, each singleton Si can only be connected to agents in T1 , . . . , Tk. In addition, u(xij) ≤ ci-1 ci , ∀xij ∈ Ti ⊂ Ci. Thus each such xij can be connected (in G) to at most ci - 1 singletons, because otherwise xij and the singletons would form a blocking coalition. The number of singletons, s, satisfies the inequality: s ≤ ∑ki=1 ti(ci - 1). With Corollary 2 this gives:

Consider n fixed and find an upper bound for s, which in turn gives an upper bound for 4n n-s . Observe that each agent in coalition Ci has at most ci - 2 singletons connected to it, thus Ci has at most ci(ci - 2) singletons:

From s < n and s ≤ (n - s)2 , it follows that s ≤ n - √n + 1/2, and so:

To complete the proof, we give a Θ(√n) example. Let G be such that N = C ∪ S, C = {x1 , . . . , xc} is a clique, S = {y1 , . . . , ys} an independent set, with |C| = c and |S| = s. In addition, each agent y ∈ S is connected to exactly one x ∈ C, and each x ∈ C has exactly c - 2 direct neighbours in S, which we denote as S(x). Thus s = c(c - 2), and so n = c2 -c. Note that while n cannot be any integer, there are arbitrarily large n of this form. Solving for c gives

The optimal welfare partition, P ∗ , is such that each agent x ∈ C forms a coalition with its set S(x). Agent x has utility c-2 c-1 , while each agent in S(x) gets 1/2. Thus,

Partition P ∗ is not stable because C is blocking, but P = (C, {y1}, . . . , {ys}) is in the core. Each agent in C gets c-1 c , while everyone in S obtains zero:

Using Equation 6, Gapmin (G) = (c-2)c(c+1) 2(c-1)2 ≈ √n - 1 ∈ Θ(√n).

Better bounds for the gap can be obtained depending on the underlying graph model. Here we consider dense graphs, which are common in social networks, and show their stability gap is small.

Theorem 5. The stability gap of every graph with m edges, where

is at most 4 1-ε , where ε ∈ [0, 1].

Proof. For ε = 0, the inequality simply states that the number of edges is non-negative. For ε = 1, it requires that the graph is complete: m ≥ n(n-1) .

2 We observe that the singletons in the core form an independent set, since otherwise they could organize themselves into coalitions and improve their welfare by doing so. Let α be the the independence number of the graph. From the fact that a graph with independence number α has at most m ≤ (n2 ) - (α2 ) edges, it follows that α satisfies the inequality α ≤ 12 + √ 14 + n(n - 1) - 2m From Inequality 7, we get that α ≤ εn, and so any core configuration has at most εn singletons. From Corrolary 2, the welfare of the remaining (1 -ε)n agents is at least 1-ε 4 n, and so the gap is bounded as follows: Gapmin (G) < n (1-ε)n/4 = 4 1-ε .

The Erd˝os-R´enyi random graph model is perhaps the best known and widely studied method for generating random graphs [Diestel, 2005].

Theorem 6. The expected stability gap of graphs generated under the Erd˝os-R´enyi G(n, p) graph model is bounded by 4 1-2 log(n)/n whenever p ≥ 1/2.

Proof. It is known that the expected independence number of G(n, 1/2) graphs is α ≤ 2 log(n), and in general, G(n, p) graphs have α ≤ 2 log(n) whenever p ≥ 1/2. Then the gap can be bounded as follows: Gapmin (G) < n (n-2 log(n))/4 = 4 1-2 log(n)/n .

6 Alternative Solution Concepts

From Theorem 4, the stability gap can be as high as Θ(√n). In this section we consider several variations of the core with improved social support.

6.1 Stability Threshold

Recall that an agent achieves his best possible utility in a coalition with his direct neighbours and no-one else. Moreover, the improvement function satisfies diminishing returns, and so the higher an agent's utility, the harder it is to improve it. The stability threshold is descriptive of situations where agents naturally stop seeking improvements once they achieved a minimum value. This is a well-known assumption observed experimentally as a form of bounded rationality: choosing outcomes which might not be optimal, but will make the agents sufficiently happy.

We analyse stability for a threshold of k/(k + 1), which is equivalent to an agent forming a coalition with k of his direct neighbours. In this case, there can be at most k1 singletons neighbouring any agent with utility at least 1/2 in the core, since otherwise the singletons can block with that agent.

Theorem 7. Let G = (N,E) be an induced subgraph game with nonempty core of threshold k/(k + 1). Then Gapmin (G) ≤ 4 if k = 1, and Gapmin (G) ≤ 2k if k ≥ 2.

6.2 The "NoMan Left Behind" Policy

From Corollary 2, the core guarantees average utility greater than 1/4 to every non-singleton coalition. Thus the reason for which the core welfare can be low is because there exist networks in which many agents are left alone in equilibrium.

Here we view the formation of core stable structures as a process that starts from the grand coalition and stabilizes through rounds of coalitions splitting and merging. While the search for equilibrium can begin from any partition, we observe that initializing with the grand coalition is natural in many situations. For example, at the beginning of any joint project, a group of people gather to work on it. However, as the project progresses, they may form subgroups based on the compatibilities and strength of social ties between them. We formulate a simple social rule that agents have to follow when merging or splitting coalitions. That is, whenever a new group forms, it cannot leave behind any agent working alone. We call this rule the "No Man Left Behind" policy. The "No Man Left Behind" code of conduct is well known in the army and refers to the fact that no soldier can be left alone in a mission or abandoned in case of injury.

Theorem 8. Let G be a game which is stable under the "No Man Left Behind" policy. Then Gapmin (G) < 4.

7 Discussion and RelatedWork

This paper is a step in the direction of understanding network interactions from the perspective of coalitional game theory. We formulated an intuitive mathematical model, analysed its welfare and stability properties, gave an approximation of the optimal welfare, and showed that core stable structures have small world characteristics. We studied the efficiency of the core and studied two solution concepts with improved welfare guarantees. This work can be extended in several ways. We would like to look at power indices and see how the degree and position of a node in the network are correlated with the welfare of that node in the equilibrium. It would be interesting to characterize the extent to which a node contributes to social welfare or to stabilizing the game, and to identify stabilizers in existent networks. It also remains to be determined whether stable structures are small worlds under general utility functions that reflect homophily.

Social distance games are a compact model that can be placed in the general context of hedonic games [Bogomolnaia and Jackson, 2002]. Alon et al. [Alon et al., 2010] propose a graph-based model and uncover the relationship between the existence of Nash equilibrium and the graph's diameter. Bloch and Jackson [Bloch and Jackson, 2004] analyse network formation games among players whose payoffs depend on the structure of the network, using the stability notions of Nash equilibrium and pairwise stability. In their formulation, players derive utility from forming links to other agents in the network, but have to pay explicitely for maintaining those links. Jackson and Wolinski [Jackson and Wolinski, 1996] study a model in which agents are researchers working on several common projects, and the utility of an agent is a function of the number of projects they collaborate on. Aadithya et al. [Aadithya et al., 2010] propose efficient algorithms for computing a Shapley value-based network centrality. Finally, there exists a rich body of literature investigating the small world phenomenon and the properties of the networks in which it occurs [Kleinberg, 2000].