Network Creation with Homophilic Agents

1 Introduction

Networks play an eminent role in today's world. They are crucial for our energy supply (power grid networks), our information exchange (the Internet and the World Wide Web), and our social relationships (friendship networks, email exchange, or co-author networks). There exists an abundance of approaches to provide formal frameworks for modeling networks, see, for example, the books by Jackson [2010] and Newman [2018]. In many of these models, the nodes of the network correspond to agents that strategically create connections which is particularly suitable for our main focus of modeling social networks. One such stream of research considers variants of the Network Creation Game (NCG) as proposed by Fabrikant et al. [2003]. There, selfish agents create edges to form a network among themselves. Forming edges is costly and hence agents try to create only the most useful edges. On the other hand, the force that causes agents to form edges at all is well-connectivity within the network, captured by a desire to occupy a central position.

The NCG is a stylized model of social interaction, providing valuable insight to agents' decision processes when interacting with each other. However, it is important to refine the basic model to spotlight specific details of this decision making. In this sense, we study network creation under the additional assumption that agents are separated into various types that model ethnic groups or affiliations.

Our goal is to contribute a new perspective on the simple causes that lead to the segregation of a society, similar to Schelling's checkerboard model for residential segregation [Schelling, 1969; Schelling, 1971]. Therefore, our agents' cost functions have a bias towards the creation of relationships with agents of the same type. Specifically, we study two models based on two seemingly orthogonal treatments of other agents. In the first model, agents incur a fixed cost for every created edge and a variable cost that only depends on the number of edges towards sametype agents. In the second model, edges towards differenttype agents are initially more expensive but their cost drops with an inverse linear decay. Both models give a different point-of-view on the same underlying principle, namely homophily of agents, i.e., the tendency to form connections with like-minded people. This is often summarized with the proverb "birds of a feather flock together", a dominant intrinsic force repeatedly observed in the creation of social networks, see McPherson et al. [2001] for a survey on the extensive sociological research on homophily in social networks. While our first model expresses homophily explicitly by an increasing comfort among friends, the second model incorporates homophily indirectly by accounting for a decreasing effort of integration once first contact is established. The latter paradigm is closely related to the well-known effect in social sciences called the "contact hypothesis" which states that stereotypes and prejudices between ethnic groups can be weakened by intensified contact [Allport et al., 1954; Amir, 1969; Dovidio et al., 2003].

We measure the desirability of networks by means of stability. Since we consider social networks, we assume a bilateral model where two agents have to cooperate to connect. Consequently, we use pairwise stability [Jackson and Wolinsky, 1996] as solution concept, rather than, for instance, Nash stability which is more appropriate for unilateral models.

Interestingly, we find an almost identical structure of stable networks for both models. This hints at a robust structure of networks created under homophily incentives. Naturally, a very small edge cost causes extremely high connectivity.

For moderately small edge cost, we provide characterizations of stable networks which are all highly segregated. We interpret this as identifying a sweet spot of high sensitivity towards agent types. For larger edge cost, stability causes a large spectrum of networks to form with respect to segregation strength. We accompany this theoretical limitation with an average-case analysis by detailed simulations of a simple distributed dynamics, where agents perform improvements towards stable networks. It would be plausible if a generally high edge cost causes less distinction of agent types. While this is sometimes confirmed, we also identify contrasting tendencies towards extreme segregation. An important driver for the different behavior is the initial segregation level, indicating that segregation can be avoided by a high initial effort without constant further interaction.

2 RelatedWork

In the original NCG the cost of every edge is alpha, where α is a parameter of the game that allows adjusting the tradeoff between the agents' cost for creating edges and their cost for the centrality in the network, e.g., the sum of distances to all other nodes. Stable networks always exist, in particular, for α < 1, only cliques are stable, whereas for 1 ≤ α < n stars, other trees and also non-tree networks can be stable [Mamageishvili et al., 2015]. Bilateral NCGs with uniform edge price have been introduced by [Corbo and Parkes, 2005]. Also variants of the NCG with non-uniform edge cost have been studied: a version where edges of differing quality can be bought [Cord-Landwehr et al., 2014], and NCGs where the edge cost depends on the node degrees [Chauhan et al., 2017], on the length of the edges in a geometric setting [Bil`o et al., 2019], or on the hop-distance of the endpoints [Bil`o et al., 2021]. The latter is motivated by social networks, and bilateral edge formation with pairwise stability as a solution concept is considered. The NCG variant by Meirom et al. [2014] features different types of agents and different but fixed edge costs for each agent type.

Closest to our work is the model proposed by Mart´ı and Zenou [2017] that is a variant of the connections model [Jackson and Wolinsky, 1996] with different types of agents. Similar to our model, the cost for maintaining an other-type connection depends on the homogeneity of the neighborhoods of the involved agents. In contrast to us, the cost for same-type edges is fixed and the distance cost is defined differently. The authors study the existence and structure of equilibria but do not investigate segregation quantitatively. The latter has been done by Henry et al. [2011] using a stochastic process that starts with a randomly drawn network with nodes of different types. Then edges are randomly rewired with a built-in bias toward favoring same-type edges. As the main result, the authors show that the network strongly segregates over time, even if the built-in bias is very low.

Residential segregation has recently received a lot of attention by a stream of research developing a gametheoretic framework based on Schelling's checkerboard model [Chauhan et al., 2018; Agarwal et al., 2021; Echzell et al., 2019; Bil`o et al., 2020; Kanellopoulos et al., 2021; Bullinger et al., 2021]. There, agents of several types strategically select positions on a given fixed network and they individually aim for having at least a τ-fraction of same-type neighbors, for some 0 < τ ≤ 1. Also hedonic diversity games [Bredereck et al., 2019; Boehmer and Elkind, 2020] are similar. These are coalition formation games where an agent's utility depends on the type distribution of her coalition.

3 Preliminaries andModel

We consider a set V = {1, . . . , n} of n agents partitioned into k ≥ 2 disjoint types. The set of types is denoted by T , and for every type T ∈ T , let VT be the set of agents of type T , i.e., V = ⋃T∈T VT and VT ∩ VT ′ = ∅ for T, T ′ ∈ T , with T ̸= T ′ . For an agent u ∈ V, we denote by T (u) her type, i.e., u ∈ VT (u). Given a type T ∈ T , then nT = |VT | denotes the number of agents of type T. We identify types with colors and we assume that there are specific types B and R of blue and red agents, respectively, which are associated with an agent type having the smallest and largest number of agents, respectively. Thus, for every type T ∈ T , we have nB ≤ nT ≤ nR. In particular, with exactly two agent types we have precisely a blue minority and a red majority type.

In a network creation game, agents will buy edges to eventually form a network, which is an undirected graph G = (V,E). Therefore, it is useful to introduce some common concepts and notation from graph theory. Consider an undirected graph G = (V, E) together with vertices u, v ∈ V. We denote the (potential) edge between u and v by uv (whether it is present or not). For two agents u, v ∈ V, the edge uv is called monochromatic if u and v are of the same type, and bichromatic, otherwise. If uv ∈ E, we use the notation G - uv = (V, E \ {uv}), otherwise we use G + uv = (V,E ∪ {uv}). Further, let NG(u) = {v ∈ V : uv ∈ E} denote the neighborhood of u in G, let degG(u) = |NG(u)| be the degree of u in G, i.e., the size of its neighborhood, and let dG(u, v) be the distance from u to v in G, i.e., the length of a shortest path from u to v in G. The diameter of G is defined as diam(G) = maxu,v∈V dG(u, v), i.e., the maximum length of any shortest path in G. Finally, a useful measure for the centrality of a vertex in a network is its distance to a set of vertices. Given a subset V ′ ⊆ V of vertices, let dG(u, V ′ ) = ∑v∈V ′ dG(u, v) denote the sum of distances from u to all vertices in V ′ . Also, given a subset of agents C ⊆ V, we denote by G[C] the subgraph of G induced by C, i.e., G[C] = (C, F ), where F = {uv ∈ E : u, v, ∈ C}.

Before formally defining our network creation model, we introduce some relevant special types of graphs. The graph Kn = (V,E) is called complete if E = {uv : u, v, ∈ V}, i.e., all possible edges are present. Further, Sn = (V,E) is called star if there exists u ∈ V such that E = {uv : v ∈ V \ {u}}. We also define networks for the special case of two types. Given two agents u ∈ VB and v ∈ VR, the network DSn = (V, E) is called double star if E = uv ∪ {uw: w ∈ VB} ∪ {vw : w ∈ VR} and DSXn = (V, E) is called double star with switched centers if E = uv ∪ {uw: w ∈ VR} ∪ {vw: w ∈ VB}. An undirected graph G is called complete, star, double star, or double star with exchanged centers if it is isomorphic to Kn, Sn, DSn, or DSXn, respectively (where isomorphisms have to preserve agent types).

Network Creation Games with Homophilic Agents. We study network creation within a cost-oriented bilateral model `a la Corbo and Parkes [2005], where the agent cost is separated into a neighborhood cost encompassing the cost of sponsoring edges and a distance cost encompassing the cost of the agents' centrality. In both of our models, a created network G has a distance cost for agent u of dG(u) := dG(u, V), i.e., the sum of agent u's distances to all other agents. The neighborhood cost is different in our two models and will be specified in the definition of our network creation games.

To model the cost dependency on the types of neighbors, we define the set of same-type agents in the neighborhood of agent u as FG(u) = VT ∩ NG(u), if u ∈ VT . The set of other-type neighbors is defined as EG(u) = NG(u) \ FG(u). We denote the cardinalities of these sets by fG(u) = |FG(u)| and eG(u) = |EG(u)|, respectively.

Now we define our network creation games. A network creation game with increasing comfort among friends (ICFNCG) with cost parameter α > 0 is a network creation game where the neighborhood cost is given by

i.e., there is a fixed cost of α for every edge and an additional cost that decreases with an increasing number of friends.

A network creation game with decreasing effort of integration (DEI-NCG) with cost parameter α > 0 is a network creation game where the neighborhood cost ist given by

Hence, there is a fixed edge cost of α for every edge to an agent in the neighborhood together with a harmonically decreasing additional cost for edges towards other-type agents. Note that the sum is empty for eG(u) = 0, and therefore, the game is identical to the single-type bilateral network creation game by Corbo and Parkes [2005] if k = 1.

For the neighborhood cost, we omit the superscript indicating the type of network creation game, whenever this is clear from the context. Also, for both of our models, we define the cost of an agent u as cG(u) = aG(u) + dG(u).

The cost functions mimic the two effects that we want to model, namely a general homophilic behavior via the ICFNCG and diminishing prejudices with intensified contact via the DEI-NCG. In both models, edge costs have a similar decay structure and identical range of [α, 2α]. In the ICF-NCG, the cost of edges is 2α for each edge if an agent has no friends, and the edge cost is approaching α when the number of neighboring friends is growing. In the DEI-NCG, the cost of edges to friends is always α and the variable cost only affects othertype agents, where we approach α with a harmonic decay starting at a cost of 2α for the first other-type agent.

Measures for Desirable Networks. We analyze networks by the incentives of agents to maintain the network in terms of stability and by the diversity of their neighborhood with respect to other agent types. Following Jackson and Wolinsky [1996], a network G = (V, E) is called pairwise stable if the following two properties hold:

• (i) for all agents u ∈ V and neighbors v ∈ NG(u), it holds that cG(u) ≤ cG-uv(u), i.e., no agent can benefit from unilaterally severing an edge, and
• (ii) for all agents u ∈ V and non-neighbors v /∈ NG(u), it holds that cG(u) ≤ cG+uv(u) or cG(v) ≤ cG+uv(v), i.e., no pair of agents can bilaterally create an edge such that the individual cost for both agents decreases.

Connectivity is an important aspect in network analysis. With multiple agent types, the internal connectivity per type deserves special consideration. Formally, a network G = (V,E) is called fully intra-connected if, for every pair u, v ∈ V of same-type agents, it holds that uv ∈ E. Further, G is fully connected if G is complete.

For the evaluation of diversity, we consider two segregation measures. Given a network G = (V, E), its local segregation, denoted by LS(G), is defined as the average fraction of agents of the same type, i.e., LS(G) = 1 |V| ∑u∈V fG(u) degG(u) . The global segregation, called GS(G), is the proportion of monochromatic edges, i.e., GS(G) = ∑u∈V fG(u) 2|E| . Note that

12

∑u∈V fG(u) is the number of monochromatic edges. 1

Finally, the minimum willingness to integrate of an agent can be evaluated by checking if she entertains any bichromatic edge. Therefore, we call an agent curious if she is part of a bichromatic edge. Similarly, a type of agents is called curious if it solely consists of curious agents. Note that this concept is related to the degree of integration, which is identical to the number of curious agents and has been studied in game-theoretic segregation models [Agarwal et al., 2021].

4 Increasing Comfort among Friends

In this section we perform our theoretical analysis of the ICFNCG. Unless explicitly stated otherwise, all statements hold for an arbitrary number of types. All missing proofs can be found in the full version of the paper [Bullinger et al., 2022].

We start by gathering some statements concerning structural properties and simple pairwise stable networks. Their proof follows by a careful analysis of the cost difference after the creation and deletion of edges.

Proposition 4.1. For the ICF-NCG the following hold:

1. If α < 67 , then every pairwise stable network is fully intra-connected.
2. If α < 43 , then diam(G) ≤ 2 for every pairwise stable network G. In particular, G contains a curious type.
3. Let α < 1, G a pairwise stable network, and C ⊆ V such that every agent in C is curious and C ⊆ VT for some type T ∈ T . Then, G[C] is a clique. In particular, every curious type of agents is fully intra-connected.
4. If α ≤ nB nB+1 , then the complete network Kn is pairwise stable. Moreover for α < min{ 6 7 , nB nB+1 }, Kn is the

1 LS and GS are (related to) standard measures in social sciences to capture the agents' exposure [Massey and Denton, 1988]. LS is used by [Paolillo and Lorenz, 2018] and GS is used in the simulation framework Netlogo [Wilensky, 1997] and by [Zhang, 2011].

unique pairwise stable network.

5. If α ≥ 1, then the star Sn is pairwise stable.

The uniqueness in Proposition 4.1(4) excludes the parameter range 67 ≤ α ≤ nB nB+1 , which can only happen for sufficiently many blue agents. In fact, there the uniqueness ceases to hold, as we show in the full version [Bullinger et al., 2022].

For the existence of stable networks, we still have to consider the intermediate parameter range nB nB+1 < α < 1. We provide the construction for two agent types. The general case is covered in the full version [Bullinger et al., 2022].

Proposition 4.2. In the ICF-NCG, there exists a pairwise stable network for every nB nB+1 ≤ α < 1.

Construction for two agent types. Consider an instance of the ICF-NCG and let nB nB+1 ≤ α < 1. We will define a stable network for α dependent on the threshold τ = nB(nB+1) nB(nB+1)+1 . Note that nB nB+1 < τ < 1, as nB(nB + 1) > nB.

We assume VB = {b1, . . . , bnB } and VR = {r1, . . . , rnR } and define the edge set of the graph G = (V, E) as follows:

• {xi, xj} ∈ E, for x ∈ {b, r}, i, j ∈ {1, . . . , nB},
• {ri, bi} ∈ E, for i ∈ {1, . . . , nB},
• {ri, rj} ∈ E, for i ∈ {1, . . . , nB} and j ∈ {nB + 1, . . . , nR},
• if α < τ, then {ri, rj} ∈ E, for i, j ∈ {nB + 1, . . . , nR}, and no further edges are in E;

otherwise, no further edges are in E.

The two cases for the network G are illustrated in Figure 1. They can be shown to be pairwise stable for their respective parameter range.

Interestingly, the stable networks constructed in the previous proof give an almost full characterization of stable networks for the considered range of edge costs when k = 2.

Theorem 4.3. Consider the ICF-NCG with parameter α and k = 2 agent types. Let nR nR+1 < α < 1 and assume that G is pairwise stable. Then, the blue agents are fully intraconnected, the bichromatic edges form a matching of size nB, and curious red agents are connected to all other red agents.

Proof sketch. Let nR nR+1 < α < 1 and assume that G is pairwise stable network in the ICF-NCG with cost parameter α. By Proposition 4.1(2), the diameter of G is bounded by 2 and there exists a curious type of agents. By Proposition 4.1(3), the curious type of agents forms a clique C and the curious agents of the other type form a clique as well.

Now, it can be shown that the bichromatic edges form a matching by proving that any agent incident to two such edges can sever one of them. Therefore, only a minority type can be a curious type and we can conclude that the blue agents are fully intra-connected and that the matching of bichromatic edges is of size nB. Showing that curious red agents maintain edges with non-curious red agents follows from another application of Proposition 4.1(2).

Example 4.4. The characterization encountered in Theorem 4.3 does not cover the whole range of Proposition 4.2. In fact, it does not hold for nB nB+1 ≤ α ≤ nR nR+1 . Hence, further pairwise stable networks exist. Assume that nR ≥ 2 and let r∗ ∈ VR. Consider the network G = (V, E), where E = {{v,w}: v,w ∈ VR}∪{{v,w}: v,w ∈ VB}∪{{v, r∗ }: v ∈ VB}, i.e., the network is fully intra-connected and there is a special agent r∗ to which all blue agents are connected. The structure of this network is depicted in Figure 2. It is straightforward to check that the network is pairwise stable. ◁

Until now, we set our focus on the existence of pairwise stable networks. In the remainder of the section, we want to consider the segregation of pairwise stable networks. First, Theorem4.3 yields very high segregation for nR nR+1 < α < 1.

Corollary 4.5. Consider the ICF-NCG with parameter α and k = 2 agent types. Let nR nR+1 < α < 1 and assume that G is pairwise stable. Then, GS(G) ≥ 1- 1n and LS(G) ≥ 1- 2n .

We know that segregation is low for sufficiently low parameter α, where cliques are (uniquely) pairwise stable. Then, there is a transition at α = nR nR+1 , where segregation is provably high regardless of further parameters like the distribution of agents into types. Once, the cost parameter increases to α ≥ 1, the picture becomes less clear. Stars can have very high and very low segregation.

Proposition 4.6. Consider the ICF-NCG with parameter α ≥ 1. Then, for every n ≥ 2, there exist pairwise stable networks G and G′ on n nodes such that GS(G) = LS(G) = 1 and GS(G′ ) = LS(G′ ) = 1 n-1 .

The networks in the previous proposition have the drawback that we need to fix the exact numbers of agents of each type to obtain the desired segregation. By contrast, for α ≥ 43 , the double star is always highly segregated.

Proposition 4.7. Consider the ICF-NCG with α ≥ 43 . Then, the double star DSn is a pairwise stable network with GS(DSn) = 1- 1 n-1 and LS(DSn) ≥ 1 - 2n .

5 Decreasing Effort of Integration

We consider the DEI-NCG. See the full version [Bullinger et al., 2022] for all omitted details. We start by collecting some results determining simple stable networks for sufficiently small and large values of α, respectively. Note that we implicitly assume the restriction to two agent types when considering the networks DSn and DSXn. All other statements hold for an arbitrary number of agent types.

Proposition 5.1. For the DEI-NCG the following holds:

1. If α < 12 , thenKn is the unique pairwise stable network.
2. If α < 1, then every pairwise stable network is fully intra-connected.
3. If α < 1, then every pairwise stable network G satisfies diam(G) ≤ 2.
4. The network Kn is pairwise stable if α ≤ n-nR n-nR+1 .
5. If α ≥ 1, then Sn and DSn are pairwise stable networks.
6. If α ≥ 4 3 , then DSXn is a pairwise stable network.

Proposition 5.1(2) and Proposition 5.1(3) imply that, for α < 1, every pairwise stable network consists of two monochromatic cliques and one type of agents is curious. Still, there are highly segregated pairwise stable networks. Also, note that the highly integrated clique investigated in Proposition 5.1(4) is not the unique stable network for α ≥ 12 , as the next example shows for the case k = 2.

Example 5.2. Assume k = 2 and 1 2 ≤ α ≤ nR nR+1 . Recall that nR is the size of the majority type of agents. In particular, this covers the case α ≤ nB nB+1 = n-nR n-nR+1 . Assume that nB ≥ 2 and let b∗ be some fixed blue agent, i.e., an agent from the minority type. Consider the network G = (V,E) with E = {vw: v, w ∈ R} ∪ {vw: v, w ∈ B} ∪ {vb∗ : v ∈ R}, i.e., the network is fully intra-connected and there is a special blue agent b∗ to which all red agents are connected. There are no further bichromatic edges. For an illustration of the network, see Figure 3. Pairwise stability of this network follows from straightforward computations. ◁

In the previous example, it was still possible to simultaneously have full intra-connectivity while there are agents entertaining several bichromatic edges. This is not possible anymore if we further increase α. In fact, we can even characterize all pairwise stable networks for nR nR+1 < α < 1 and k = 2.

Theorem 5.3. Let k = 2 in the DEI-NCG. Assume that nR nR+1 < α < 1 and consider a network G. Then, G is pairwise stable if and only if it is fully intra-connected and its bichromatic edges form a matching covering VB.

Proof sketch. Clearly, if k = 2 and nR = 1, then the unique stable network consists of a neighboring blue and red agent and the assertion is true. Thus, we may assume that nR ≥ 2. We show that the given conditions imply pairwise stability.

Therefore, assume that G is a fully intra-connected network such that the bichromatic edges form a matching covering one type of agents. Then, no edge can be severed because monochromatic edges only decrease the neighborhood cost by α < 1 while increasing the distance cost by 1. Also, bichromatic edges decrease the neighborhood cost by 2α < 2

while increasing the distance cost by 2. Finally, it is impossible to create another bichromatic edge. This edge would be the second bichromatic edge incident to its endpoint from the minority type of agents. This agent would only decrease her distance cost by 1 while increasing her neighborhood cost by 3 2 α ≥ 32 nR nR+1 ≥ 1, where we use nR ≥ 2 in the last step.

The second part of the above proof shows that the networks characterized in the theorem are even stable for 23 ≤ α < 1. Putting together Proposition 5.1, Example 5.2, and Theorem 5.3, we have proved the existence of pairwise stable networks for almost every DEI-NCG if k = 2 (except a limit case when nB = 1). By generalizing the encountered networks, we can show their existence for an arbitrary number of types. The generalization of the network in Example 5.2 is straightforward, maintaining the property that there exists one specific agent entertaining all bichromatic edges. However, the generalization of the network in Theorem 5.3 is a bit disguised. We define the network by providing an efficient algorithm. This algorithm initially considers a fully intraconnected network and adds edges by having agents create bichromatic edges via specific better responses. In the special case of k = 2, this results precisely in the matchings encountered in Theorem 5.3 (see the full version for details).

Theorem 5.4. In the DEI-NCG pairwise stable networks always exist.

Finally, we want to consider the segregation of pairwise stable networks in the DEI-NCG. Clearly, segregation only depends on the networks, not on the type of NCG. Hence, we transfer from the investigation of ICF-NCGs that cliques provide low segregation for small α, stars provide high or low segregation for high α, but require a specific distribution of agents into types. Independently of this distribution, double stars provide high segregation and it is clear that GS(DSXn) = LS(DSXn) = 0. Finally, for an intermediate range of α, high segregation is inevitable.

Corollary 5.5. Let k = 2 and nR nR+1 < α < 1. Then, every pairwise stable network G in the DEI-NCG with parameter α satisfies GS(G) ≥ 1 - 2n and LS(G) ≥ 1 - 2n .

6 Experimental Analysis

While our theoretical results indicate a clear structure of stable networks for α ≤ 1, there is a broad range of possibilities for larger α. Therefore, we support the theoretical findings for α > 1 by a detailed experimental analysis 2 . To this end, we simulate a simple dynamic process based on distributed and strategic edge creation and deletion over time, incentivized by optimizing the cost functions of our two models.

The dynamics start with sparse initial networks (spanning tree or grid) and distribute agents of two equally-sized types such that the segregation of the initial network is very low or high. In each step, one agent is activated uniformly at random and can either create or delete an edge, performing a best response with respect to the cost function under consideration. In particular, we study also an add-only variant of the model, where agents can only create edges. This dynamics is particularly natural when modeling social networks, as confirmed by the observation that many real-world social networks get denser over time [Leskovec et al., 2005]. The dynamics proceed until the consideration of no agent changes the network.

2 The source code for the experiments can be found at https://github.com/melnan/HomophilicNCG

See [Bullinger et al., 2022] for a detailed discussion of our experimental setup and further results. An exemplary consideration of the dynamics based on the cost function of the DEI-NCG can be found in Figure 4 and Figure 5 for the general and add-only version, respectively. 3 Interestingly, the results for the ICF-NCG are qualitatively the same, regardless of measuring segregation with the local or global segregation measure. The experiments indicate that the segregation strength is proportional to α, with low segregation for low α, despite the theoretical necessity of high segregation for α close to 1. 4 Moreover, except for high α, the initial agent distribution influences the segregation, with more observed segregation for segregated initial states. The structure of the initial network seems less important for the qualitative behavior. Interestingly, the add-only version displays a similar behavior for low α, but the behavior changes drastically for moderately high α. Instead of high segregation, we find that initially integrated networks converge to only moderately segregated states, whereas this is not true for initially segregated networks, suggesting an escape route from segregation.

3 As discussed in the full version, for computational efficiency, we consider convergence to 1.01-approximate pairwise stable states which is qualitatively similar to pairwise stability. Also, note that "random" means that the initial agent distribution is chosen uniformly at random, which implies low initial segregation.

4 The provably high segregation for α < 1 close to 1 is not contradicting the experimental results. Just before we reach a cost parameter of α, we hit the sweet spot where buying monochromatic edges is desirable while buying bichromatic edges is not.

7 Conclusion

We have investigated two network creation games that consider heterogeneous edge creation of agents acting according to homophily. Our main goal was to analyze segregation within reasonable networks measured by pairwise stability. Our results are summarized in Figure 6. Even though our two game models feature two seemingly orthogonal perspectives based on a direct and an indirect consideration of homophily, their qualitative behavior is surprisingly similar.

Clearly, stable networks are highly integrated for a very small edge cost, when agents can afford to buy all available edges. Once our cost parameter reaches the sweet spot where agents need to balance neighborhood and distance cost, there is provably high segregation, following from characterizations of stable networks. For slightly larger edge cost, our theoretical results cannot give a clear tendency of the segregation strength. In principle, both low and high segregation can be achieved by stable networks. Therefore, we performed an average-case analysis by running extensive simulation experiments. These experiments provide general tendencies about segregation contrasting the large theoretical spectrum for α ≥ 1. Most importantly, we observe low segregation under integrated initial conditions if edges cannot be deleted. This yields an escape route from segregation by a high initial investment establishing permanent integration.

Acknowledgements

This work was supported by the Deutsche Forschungsgemeinschaft (German Research Foundation) under grants BR 2312/11-2, BR 2312/12-1, and LE 3445/3-1.