Int J Game Theory DOI 10.1007/s00182-015-0526-2 ORIGINAL PAPER

House exchange and residential segregation in networks Zhiwei Cui1 · Yan-An Hwang2

Accepted: 24 December 2015 © Springer-Verlag Berlin Heidelberg 2016

Abstract This paper considers a Schelling model in an arbitrary fixed network where there are no vacant houses. Agents have preferences either for segregation or for mixed neighborhoods. Utility is non-transferable. Two agents exchange houses when the trade is mutually beneficial. We find that an allocation is stable when for two agents of opposite-color each black (white) agent has a higher proportion of neighbors who are black (white). This result holds irrespective of agents’ preferences. When all members of both groups prefer mixed neighborhoods, an allocation is also stable provided that if an agent belongs to the minority (majority), then any neighbor of opposite-color is in a smaller minority (larger majority). Keywords Schelling model · Networks · Stable allocations · Internal cohesion · Counterpart partition JEL Classification

C71 · D51 · J15

We thank the editor and two anonymous referees for suggesting ways to improve the substance and exposition of this paper. Part of this work was undertaken while Zhiwei Cui was visiting the Department of Applied Mathematics at National Dong Hwa University, whose hospitality is greatly acknowledged. This work was financially supported by the National Science Foundation of China (No. 61202425) and the Fundamental Research Funds for the Central Universities (YWF-13-D2-JC-11, YWF-14-JGXY-016).

B

Zhiwei Cui [email protected] Yan-An Hwang [email protected]

1

School of Economics and Management, Beihang University, Beijing 100191, People’s Republic of China

2

Department of Applied Mathematics, National Dong Hwa University, Hualien 97401, Taiwan

123

Z. Cui, Y.-A. Hwang

1 Introduction Residential segregation in cities is one of the most important and interesting issues in the field of public economics.1 It is generally regarded as a social problem having adverse effects especially on ethnic minorities and consequently has a significant impact on public policy.2 Since the seminal and influential work of Schelling (1969, 1971, 1978), a considerable amount of effort has been devoted to individual choice and residential segregation. By considering house exchange in an arbitrary fixed network, the present paper contributes to this strand of research. Formally, we consider a finite set of houses located within an arbitrary fixed network, which we refer to hereafter as a house distribution network. Individuals can be distinguished into a nonempty ethnic group of black agents and a nonempty ethnic group of white agents. The number of agents is equal to the number of houses. An allocation assigns one and only one house to each agent. Neighborhood is defined as the set of neighboring houses in the network. Agents only care about the ratio of samecolor neighbors; and for each ethnic group all members have the same preference. More specifically, agents have either a preference for segregation or a preference or mixed neighborhoods. Utility is non-transferable. Two distinct agents exchange their houses if both of them are improved and at least one of them is strictly improved after the trade. This paper aims to explore stable allocations where there is no incentive for agents to exchange their houses. The main results show that an allocation is stable when in comparison with any white agent, each black agent has a higher proportion of neighbors who are black. Equivalently, each white agent has a higher proportion of neighbors who are white than any black agent has. This result holds irrespective of agents’ preferences. When the members of both ethnic groups prefer mixed neighborhoods, an allocation is also stable provided that if an agent belongs to the minority (majority), then any neighbor of opposite-color is in a smaller minority (larger majority). Our work contributes to the literature on residential segregation. Following Schelling (1969, 1971), much of the literature assumes that agents live in artificial worlds where houses are distributed across specific networks, such as circles, checkerboard (or lattice) networks or networks consisting of complete components. The process of segregation (or integration) can then be analyzed using stochastic dynamical system theory (Grauwin et al. 2009, 2012; Pancs and Vriend 2007; Vinkovi´c and Kirman 2006; Young 1998; Zhang 2004a, b, 2011). A distinct paper is that of Fagiolo et al. (2007) where they use simulation to study a spatial proximity model for six different classes of networks. These include two-dimensional lattices with Von-Neumann neighborhoods, two-dimensional lattices with Moore neighborhoods, regular networks, random networks, small-world networks and scale-free networks. 1 Segregation also exists between followers of different religions, between men and women in an office canteen, between tourists and locals at a city square, between staff and students in a seminar room, between different nationalities at a conference dinner, between workers with different skills in different firms, or between different species occupying their own territory (Pancs and Vriend 2007; Schelling 1971). 2 In recent times, racial-ethnic segregation has declined in the United States, but income (or class) segre-

gation has grown (Massey et al. 2009).

123

House exchange and residential segregation in networks

However, the present paper assumes that houses are located within an arbitrary fixed network, rather than an artificial network, and conducts static analysis of stable allocations. The present work is also related to the literature on house exchange under the framework of cooperative game theory. The simple housing market was first introduced by Shapley and Scarf (1974). In it the market is modeled as a collection of objects, “houses”, each of which is owned by a single agent. Each agent has a preference over all houses and wants just one house. Since then, a large theoretical literature has emerged investigating house exchange (Abdulkadiroglu and Sonmez 1998; Ben-Shoham et al. 2004; Kandori et al. 2008; Miyagawa 2002; Roth 1982; Roth and Postlewaite 1977; Serrano and Volij 2008).3 In this strand of the literature, the concept of core is used to characterize stable allocations. However, no definitions of location or neighborhood are provided. As a complement, the present paper introduces the location of houses, partitions the society into two ethnic groups and explores the properties of stable allocations provided that only bilateral exchange is possible. The rest of the paper is organized as follows. Section 2 describes the basic building blocks of our model. Section 3 introduces two concepts of internal cohesion and counterpart partition. Section 4 analyzes stable allocations. Section 5 explores the robustness of the main findings with respect to changes in assumptions. Section 6 concludes.

2 Notations and basic model 2.1 Houses and distribution network Let H be a finite set of houses. For any two houses i, j ∈ H, the pairwise relationship between them is captured by a binary variable, gi j ∈ {0, 1}. gi j = g ji = 1 if houses i and j are  neighbors and gi j = 0 otherwise; conventionally, gii = 0. .  g = H, (gi j )i, j∈H defines an undirected graph, and is referred to as a house distribution network. For any i ∈ H, the neighborhood Ni (g) is the set of neighbors in g. . Formally, Ni (g) = { j ∈ H : gi j = 1}.4 Let ηi (g) be the cardinality of Ni (g). A house i is isolated if Ni (g) = ∅. Without loss of generality, it is assumed that no isolated houses exist. That is, ηi (g) ≥ 1 for any i ∈ H. A path in g connecting houses i 1 and i k is a set of distinct houses {i 1 , i 2 , . . . , i k−1 }∪  {i k } such that gi1 i2 = gi2 i3 = · · · = gik−1 ik = 1. For any subset H ⊆ H, the subgraph    H , (gi j )i, j∈H defines a component if no path exists that connects i and j for any 





i ∈ H and j ∈ H\H , whilst for any pair of distinct houses in H there is a path that 3 Important real-life examples of this model are the assignment of campus housing to students (Abdulkadiroglu and Sonmez 1999; Chen and Sonmez 2002, 2004; Sonmez and Unver 2005) and kidney exchange (Roth et al. 2004). 4 In the literature on residential segregation, the definition of neighborhood is different. Given that houses

are located in a checkerboard network or torus, a von Neumann neighborhood implies that each agent only considers the four adjacent agents as neighbors whilst a Moore neighborhood includes the eight surrounding agents as neighbors.

123

Z. Cui, Y.-A. Hwang

   connects them. A component H , (gi j )i, j∈H is complete if gi j = 1 for any pair of 

distinct houses i, j ∈ H . g is connected if it has a unique component. g is complete if the unique component is complete. g is a star if there exists a house i 0 ∈ H such that for any two distinct houses i and j, gi j = 1 if and only if i = i 0 or j = i 0 . 2.2 Agents, allocations and utility functions Let A denote the set of agents where |A| = |H|.5 A is partitioned into a nonempty ethnic group of black agents, A1 , and a nonempty ethnic group of white agents, A2 . Let a and b be typical elements of the set A. An allocation is a one-to-one function h : A → H such that for any pair of agents a and b, if h(a) = h(b), then a = b. Owing to the assumption that |A| = |H|, no vacant houses exist and each agent a holds one and only one house h(a).6 Let H denote the set of all possible allocations. Given an allocation, each agent has a utility level which depends only on the proportion of same-color neighbors. For simplicity assume that agents in the same group share a common utility function. Formally, given an allocation h ∈ H, for ethnic group Al , l = 1, 2, each member a’s utility is specified by   |Nh(a) (g) ∩ h(Al )| . πa (h) = u l ηh(a) (g)    . where for any subset of agents A ⊂ A, h(A ) = {i ∈ H : ∃b ∈ A such that h(b) = i}  is the set of houses allocated to agents in A and utility function u l : [0, 1] → R represents the preference of agents from Al for any proportion of same-color neighbors. It is assumed that u l (0) = 0 and u l ( p) ≥ 0 for any p ∈ [0, 1]. That is, u l ( p) ≥ u l (0) for any p ∈ [0, 1]. In other words, each agent regards being completely surrounded by different-color agents as the worst possible case. For any l = 1, 2, members of ethnic group Al are indifferent over neighborhoods if u l ( p) = 0 for any p ∈ [0, 1]. Members of Al have a weak preference for mixed neighborhoods if there exists p0 ∈ (0, 1) such that u l ( p0 ) ≥ u l ( p) for any p ∈ [0, 1]; members of Al have a preference for mixed neighborhoods if u l ( p0 ) > max{u l (0), u l (1)} = u l (1). Members of Al have a preference for segregation if u l (1) > u l ( p) for any p ∈ [0, 1). And, when members of Al have a preference for segregation, it is assumed that u l (·) is strictly increasing on [0, 1]. Consider the case where members of ethnic group Al , l = 1, 2, have a preference for mixed neighborhoods. It is assumed that (1)u l (·) is symmetric; formally, u l (0.5−δ) = u l (0.5 + δ) holds for any δ ∈ [0, 0.5] and (2) there exists pm ∈ (0, 0.5] such that u l (·) is strictly increasing on [0, pm ] and u l ( p) = u l ( p0 ) for any p ∈ [ pm , 1 − pm ]. The symmetry means that there is no difference in the preference of the proportion of samecolor neighbors being p and the proportion being (1 − p) for any p ∈ [0, 1]. If pm =

5 For any finite set S, |S| is the number of elements belonging to S. 6 Grauwin et al. (2012), Pancs and Vriend (2007), Schelling (1971) and Zhang (2004a) assume that there

are vacant houses; that is, |A| < |H| holds.

123

House exchange and residential segregation in networks

Fig. 1 Utility functions representing the preference for mixed neighborhoods: the left panel shows that pm = 0.5 whilst the right panel shows that pm = 0.4 < 0.5

0.5, members of Al prefer to reside in 50−50 % perfectly integrated neighborhoods; and, the preference is represented by a symmetric single-peaked utility function.7 If pm < 0.5, members of Al prefer to reside in neighborhoods where the proportion of same-color neighbors lies in [ pm , 1 − pm ]. In other words, members of Al are equally satisfied with any neighborhood except for that where the proportion of the minority is strictly less than pm . In this case, the preference is represented by a symmetric singleplateaued utility function. Figure 1 illustrates two utility functions. In each panel, the horizontal axis indicates the proportion of same-color neighbors whilst the vertical axis shows the level of utility.

2.3 Exchange and stable allocations 

Definition 1 (Exchange) Given an allocation h ∈ H, the allocation h results from   h by distinct agents a and b exchanging houses if h (b) = h(a), h (a) = h(b) and   h (c) = h(c) for any c ∈ A\{a, b}. The exchange is beneficial if πa (h ) ≥ πa (h),  πb (h ) ≥ πb (h) and there is at least one strict inequality. Given an allocation h ∈ H, for any two distinct agents a and b from the same group, there exists no allocation resulting from h by a and b beneficially exchanging houses. A natural question comes to our mind: is there an allocation where any two distinct agents are not motivated to exchange houses? If the answer turns out to be “Yes”, such an allocation is said to be stable.8 Definition 2 (Stable allocation) An allocation h ∈ H is stable if there exists no allocation resulting from h by agents a and b beneficially exchanging houses for any a ∈ A1 and b ∈ A2 . 7 Pancs and Vriend (2007) consider the symmetric single-peaked utility function where p = p = 0.5 m 0 and u l (·) is an increasing linear function on the interval [0, 0.5]. 8 This paper conducts static analysis and uses the cooperative game theory definition of “stable allocation”. Each stable allocation corresponds to a limit point of unperturbed dynamics for the stochastic dynamical theory framework (Young 1998; Zhang 2004b).

123

Z. Cui, Y.-A. Hwang

Fig. 2 An illustration of internal cohesion: in each panel the set of houses inhabited by white (black) agents is internally cohesive

3 Internal cohesion and counterpart partition In this section, we introduce two concepts, internal cohesion and counterpart partition, which are essential for the exploration of stable allocations. 3.1 Internal cohesion The notion of neighborhood can be extended as follows. Given the house distribution  network g, for any nonempty subset H ⊆ H, the neighborhood NH (g) is defined as   . NH (g) = { j ∈ H\H : ∃i ∈ H such that gi j = 1}. 



NH (g) consists of houses having a neighbor in H but not belonging to H . It is straightforward to see that    NH (g) = ∪i∈H Ni (g) \H . Definition 3 (Internal cohesion) Given a house distribution network g, the nonempty  subset of houses H ⊆ H is internally cohesive 9 if 



|N j (g) ∩ H | |Ni (g) ∩ H | ≤ min max j∈N  (g) η (g) ηi (g) j i∈H H where if NH (g) = ∅, the left-hand side of the inequality is defined to be zero. When  the inequality holds strictly, H is strictly internally cohesive. 



Given the internal cohesion of H , each element of H has a higher proportion   of neighbors from H than any house not belonging to H . Figure 2 illustrates three 10 examples of internally cohesive subsets. Each node represents a house, and two nodes 9 The naming follows the notion of p-cohesive groups in Morris (2000) where it is used to study contagion through a myopic best-response rule. A subset is p-cohesive if each element has at least a proportion p of neighbors within the subset. 10 In the literature on residential segregation, two kinds of neighborhoods are assumed: continuous neigh-

borhoods and bounded neighborhoods as illustrated by the left and middle panels of Fig. 2, respectively.

123

House exchange and residential segregation in networks

are linked if the corresponding houses are neighbors. A black (grey) node indicates that the corresponding house is allocated to a black (white) agent. The left panel shows that each agent lives in a 50−50 % perfectly integrated neighborhood. In the middle panel, each agent’s neighbors have the same color as himself; that is, there is residential segregation. In the right panel, some agents live in mixed neighborhoods while for some agents, all neighbors are of the same-color. In each panel, the houses allocated to white agents constitute an internally cohesive subset. Thus, internal cohesion is able to embody both (perfect) integration and residential segregation. Due to the symmetry of the distribution of different-color agents, in the left and middle panels of Fig. 2, the subset of houses allocated to black agents is also internally cohesive. In fact, this conclusion can be extended to more general cases as follows. The proof is provided in the Appendix. Proposition 1 Consider a house distribution network g. If the proper, nonempty subset   H ⊂ H is internally cohesive, then H\H is also internally cohesive. 



Given the internal cohesion of H , for any house i ∈ H , a higher proportion of   / H . In other words, compared with house neighbors belong to H than any element j ∈  j, a lower proportion of i’s neighbors belong to H\H . Proposition 1 can be extended as follows. The proof follows the same logic as the proof of Proposition 1, and we omit it here. Proposition 2 Consider a house distribution network g. If the proper, nonempty subset   H ⊂ H is strictly internally cohesive, then H\H is also strictly internally cohesive. The following proposition provides another property of internal cohesion. The proof is relegated to the Appendix. 

Proposition 3 Consider a house distribution network g. If the nonempty subset H ⊂   H is internally cohesive, then Ni (g) ∩ H = ∅ for any i ∈ H . 



Given the internal cohesion of H , for any house i ∈ H , if all of i’s neighbors are   from H\H , then a strictly higher proportion of house j’s neighbors belong to H than  i for any j ∈ Ni (g) (Ni (g) ⊆ NH (g)). This contradicts the internal cohesion of H . The following proposition concerns the existence of the (strictly) internally cohesive set. The proof is trivial, and we omit it here. Proposition 4 For any house distribution network g, H is strictly internally cohesive. 3.2 Counterpart partition Definition 4 (Counterpart partition) Consider a house distribution network g. The partition {H1 , H2 } of H is a counterpart partition if for any i ∈ H1 and j ∈ H2 , when gi j = 1, one of the following two inequalities holds:    |Ni (g) ∩ H1 | 1 |Ni (g) ∩ H1 | |N j (g) ∩ H2 | + 1 − − × ≤0 ηi (g) η j (g) ηi (g) 2     |N j (g) ∩ H2 | |Ni (g) ∩ H1 | + 1 |N j (g) ∩ H2 | 1 − − × ≤0 η j (g) ηi (g) η j (g) 2 

123

Z. Cui, Y.-A. Hwang

Fig. 3 An illustration of counterpart partition: in each panel, the set of houses allocated to black agents and the set of houses inhabited by white agents form a counterpart partition

and when one inequality holds with equality, the other inequality is also required. Assume that {H1 , H2 } is a counterpart partition where the first inequality holds with strict equality. Consider two neighboring houses i ∈ H1 and j ∈ H2 . Given that less (more) than half of i’s neighbors belonging to H1 , if i and j exchange locations, i has a lower (higher) proportion of neighbors from H2 . Figure 3 illustrates allocations where H1 = h(A1 ) and H2 = h(A2 ) form a counterpart partition of H. In the left panel, 1 |Ni (g) ∩ h(A1 )| = for any i ∈ h(A1 ) ηi (g) 3 |N j (g) ∩ h(A2 )| + 1 2 1 = < for any j ∈ Nh(A1 ) (g). η j (g) 9 3 Thus, the first inequality holds with strict equality. In the right panel, the first inequality also holds with strict equality. In the left panel of Fig. 3, neither h(A1 ) nor h(A2 ) is internally cohesive while in the right panel, both h(A1 ) and h(A2 ) are internally cohesive. And, in the right panel of Fig. 2, H1 = h(A1 ) and H2 = h(A2 ) fail to form a counterpart partition of H. Therefore, there is no relationship between the internal cohesion of h(A1 ) and h(A2 ) and {h(A1 ), h(A2 )} being a counterpart partition of H.

4 Main results In this section, we analyze stable allocations. First, we present two trivial results about the existence of stable allocations when the house distribution network is complete or is a star. Second, we offer sufficient conditions regarding stability of allocations when the house distribution network is of a more general architecture. 4.1 Existence of stable allocations When the house distribution network g is complete, each agent has an identical proportion of same-color neighbors in any allocation, and the level of utility is a constant. Therefore, for any allocation, there is no allocation resulting from it by two distinct agents beneficially exchanging houses. From this we have the following proposition.

123

House exchange and residential segregation in networks

Proposition 5 Any allocation h ∈ H is stable when the house distribution network g is complete. Consider the case where the network g is a star. Without loss of generality, assume that the central house is occupied by agent a0 ∈ A1 . Any two distinct agents who reside in locations of the periphery are not motivated to exchange houses since they have the common neighborhood {a0 }. When exchanging houses with b ∈ A2 , a0 moves to a house of the periphery with only one neighbor b, and his utility level is strictly decreased unless he is indifferent over neighborhoods provided that |A1 | ≥ 2. As a result, the following proposition can be obtained. Proposition 6 When the house distribution network g is a star, any allocation h ∈ H is stable provided that (1) members of neither ethnic group are indifferent over neighborhoods and (2) |Al | ≥ 2 for any l = 1, 2. 4.2 Analysis of stable allocations The following theorem shows that the (strict) internal cohesion of h(A1 ) and h(A2 ) can guarantee stability of the allocation h provided that members of one ethnic group have a preference for segregation.11 Theorem 1 Assume that members of one ethnic group Al , l = 1 or 2, have a preference for segregation. Then, (I) when members of the other ethnic group have a preference for segregation or are indifferent over neighborhoods, an allocation h ∈ H is stable if both h(A1 ) and h(A2 ) are internally cohesive; (II) when members of the other ethnic group have a preference for mixed neighborhoods, an allocation h ∈ H is stable if both h(A1 ) and h(A2 ) are strictly internally cohesive. Proof Without loss of generality, assume that members of ethnic group A1 have a preference for segregation. For the sake of space, we only prove Part (I). The proof of Part (II) follows the same logic, and we omit it here. Consider agents a ∈ A1 and  b ∈ A2 . Let h be the allocation resulting from h by a and b exchanging houses. We first study the case where h(b) ∈ h(A2 )\Nh(A1 ) (g). That is, all of h(b)’s neighbors are assigned to agents from A2 for the allocation h. Then, for the allocation  h , agent a’s utility is zero. Following from Proposition 3, 1 |Nh(a) (g) ∩ h(A1 )| ≥ > 0. ηh(a) (g) ηh(a) (g)  As a consequence, πa (h) ≥ u 1

1 ηh(a) (g)





> 0 = πa (h ).

11 Part (II) of Theorem 1 is independent of the assumption that the preference for mixed neighborhoods is

represented by a symmetric single-peaked or symmetric single-plateaued utility function.

123

Z. Cui, Y.-A. Hwang

Now we turn to the case where h(b) ∈ Nh(A1 ) (g). According to the relationship between h(a) and h(b), the remaining proof is divided into two subcases. If h(a) and h(b) are neighbors, it follows that 

|Nh  (a) (g) ∩ h (A1 )| ηh  (a) (g)

=

|Nh(b) (g) ∩ h(A1 )| − 1 . ηh(b) (g)

Combining with the internal cohesion of h(A1 ), |N j (g) ∩ h(A1 )| |Ni (g) ∩ h(A1 )| |Nh(a) (g) ∩ h(A1 )| ≥ min ≥ max i∈h(A1 ) j∈Nh(A1 ) (g) ηh(a) (g) ηi (g) η j (g) |Nh(b) (g) ∩ h(A1 )| |Nh(b) (g) ∩ h(A1 )| − 1 ≥ > . ηh(b) (g) ηh(b) (g) Note that u 1 (·) is strictly increasing on [0, 1]. Thus,  πa (h) = u 1

|Nh(a) (g) ∩ h(A1 )| ηh(a) (g)



 > u1

|Nh(b) (g) ∩ h(A1 )| − 1 ηh(b) (g)





= πa (h ).

When h(a) and h(b) are not neighbors, it follows that 

|Nh  (a) (g) ∩ h (A1 )| ηh  (a) (g)

=

|Nh(b) (g) ∩ h(A1 )| , ηh(b) (g)

=

|Nh(a) (g) ∩ h(A2 )| . ηh(a) (g)



|Nh  (b) (g) ∩ h (A2 )| ηh  (b) (g)

Note that both h(A1 ) and h(A2 ) are internally cohesive. Therefore, |Nh(a) (g) ∩ h(A1 )| |Nh(b) (g) ∩ h(A1 )| ≥ and ηh(a) (g) ηh(b) (g) |Nh(b) (g) ∩ h(A2 )| |Nh(a) (g) ∩ h(A2 )| ≥ . ηh(b) (g) ηh(a) (g) Following from the assumption concerning agents’ preferences, each agent’s utility cannot be strictly improved. In summary, there exists no allocation resulting from h by agents a and b beneficially exchanging houses.   Theorem 1 offers a sufficient condition for stable allocations when members of one ethnic group Al have a preference for segregation. The underlying intuition is simple. / Al , The strict internal cohesion of h(A1 ) and h(A2 ) implies for any a ∈ Al and b ∈ that compared with agent b, a strictly higher proportion of agent a’s neighbors are from Al . If agents a and b exchange houses, a’s utility level is strictly reduced. Thus, agent a has no incentive to exchange houses with agent b.

123

House exchange and residential segregation in networks

Fig. 4 Illustration of stable allocations given by Theorem 1 when members of both ethnic groups have a preference for segregation

For the torus with “Moore neighborhoods”, Fig. 4 illustrates stable allocations given that all members of both ethnic groups have a preference for segregation. In each panel, both h(A1 ) and h(A2 ) are internally cohesive. The left panel presents the paradigmatic pattern of residential segregation while in the right panel, each agent lives in a 50−50 % perfectly integrated neighborhood.12 The middle panel also shows residential segregation where houses allocated to white agents constitute “crossed strips”. And, the right panel of Fig. 2 exemplifies the existence of stable allocations provided that the house distribution network is not specified by one-dimensional circles, two-dimensional lattices or torus. Consider the left panel of Fig. 2 and the right panel of Fig. 4. Each agent lives in a 50−50 % perfectly integrated neighborhood. The set of houses occupied by black (white) agents is also internally cohesive. Following from Theorem 1, even if the members of both ethnic groups have a preference for segregation, they are not motivated to overturn 50−50 % perfectly integrated neighborhoods. Therefore, there may well be a conflict between individual rationality and social efficiency. The following theorem provides a necessary condition for stable allocations when members of both ethnic groups prefer segregation. Theorem 2 Assume that all members of both ethnic groups A1 and A2 have a preference for segregation. Consider a stable allocation h. Then, for any a ∈ A1 and b ∈ A2 , |Nh(b) (g) ∩ h(A1 )| − gh(a)h(b) |Nh(a) (g) ∩ h(A1 )| ≥ (1) ηh(a) (g) ηh(b) (g) or

|Nh(b) (g) ∩ h(A2 )| |Nh(a) (g) ∩ h(A2 )| − gh(a)h(b) ≥ . ηh(b) (g) ηh(a) (g)

(2)



Proof Let h denote the allocation resulting from h by agents a and b exchanging houses. Owing to stability of the allocation h, 



πa (h) ≥ πa (h ) or πb (h) ≥ πb (h ) 12 In the left and right panels, h(A ) and h(A ) form a counterpart partition of H while in the middle panel, 1 2

h(A1 ) and h(A2 ) do not form a counterpart partition of H.

123

Z. Cui, Y.-A. Hwang

and when one inequality holds with equality, the other inequality is also required. The preference specification implies that both u 1 and u 2 are strictly increasing on [0, 1]. Therefore, 

|Nh  (a) (g) ∩ h (A1 )| |Nh(a) (g) ∩ h(A1 )| ≥ or ηh(a) (g) ηh  (a) (g) 

|Nh  (b) (g) ∩ h (A2 )| |Nh(b) (g) ∩ h(A2 )| ≥ . ηh(b) (g) ηh  (b) (g) As in the proof of Theorem 1, 

|Nh  (a) (g) ∩ h (A1 )| ηh  (a) (g) and

=

|Nh(b) (g) ∩ h(A1 )| − gh(a)h(b) ηh(b) (g)

=

|Nh(a) (g) ∩ h(A2 )| − gh(a)h(b) . ηh(a) (g)



|Nh  (b) (g) ∩ h (A2 )| ηh  (b) (g)

By substituting these two equations into the above inequalities, the conclusion is provided.   When h(A1 ) and h(A2 ) are internally cohesive, both Inequality (1) and Inequality (2) hold. However, Theorem 2 shows that the stability of an allocation may not be enough to derive both inequalities. Consider the case where the house distribution network g is a star. Any allocation h ∈ H is stable provided that all members of both ethnic groups prefer segregation and |Al | ≥ 2 for any l = 1, 2. If the central house is resided in by agent a0 ∈ A1 , only Inequality (1) holds when it involves agents a0 and b ∈ A2 . In fact, neither h(A1 ) nor h(A2 ) is internally cohesive. The seminal work of Schelling (1969, 1971) conveys the idea that in the long run residential segregation will emerge even if agents prefer mixed neighborhoods. The middle panel of Fig. 2 and the left and middle panels of Fig. 4 show that the internal cohesion of h(A1 ) and h(A2 ) can lead to residential segregation. Therefore, an intriguing question is whether or not the internal cohesion of h(A1 ) and h(A2 ) is related to stability of the allocation h when members of both ethnic groups prefer mixed neighborhoods. The following theorem provides the answer. Theorem 3 Assume that utility functions u 1 (·) and u 2 (·) are either symmetric singlepeaked or symmetric single-plateaued. Then, an allocation h ∈ H is stable if h(A1 ) and h(A2 ) are internally cohesive. The following lemma shows that there is no beneficial exchange between two agents residing in non adjacent houses when all members of both ethnic groups prefer mixed neighborhoods. This lemma is essential for the proof of Theorems 3 and 4. The proof is given in the Appendix.

123

House exchange and residential segregation in networks

Lemma 1 Assume that u 1 (·) and u 2 (·) are either symmetric single-peaked or symmetric single-plateaued. Consider an allocation h ∈ H. For any a ∈ A1 and b ∈ A2 , if gh(a)h(b) = 0, no allocation exists resulting from h by agents a and b beneficially exchanging houses. Proof of Theorem 3 Consider a pair of distinct agents a ∈ A1 and b ∈ A2 . Let  h denote the allocation resulting from h by a and b exchanging houses. Owing to Lemma 1, it is sufficient to consider the case that gh(a)h(b) = 1. When agents a and b exchange houses, 

|Nh  (a) (g) ∩ h (A1 )| ηh  (a) (g)

=

|Nh(b) (g) ∩ h(A1 )| − 1 , ηh(b) (g)

=

|Nh(a) (g) ∩ h(A2 )| − 1 . ηh(a) (g)



|Nh  (b) (g) ∩ h (A2 )| ηh  (b) (g)

|Nh(b) (g) ∩ h(A1 )| , three possibilities are explored. ηh(b) (g) |Nh(b) (g) ∩ h(A1 )| |Nh(a) (g) ∩ h(A1 )| ≤ pm . If ≤ pm , First, we consider the case ηh(b) (g) ηh(a) (g) following from the assumption that u 1 (·) is monotonically increasing on [0, pm ], According to different values of

   |Nh(b) (g) ∩ h(A1 )| − 1 |Nh(b) (g) ∩ h(A1 )| < u1 πa (h ) = u 1 ηh(b) (g) ηh(b) (g)   |Nh(a) (g) ∩ h(A1 )| = πa (h) ≤ u1 ηh(a) (g) 



where the second inequality follows from the internal cohesion of h(A1 ). Therefore, |Nh(a) (g) ∩ h(A1 )| ≤ after the trade, agent a’s utility level is strictly reduced. If pm < ηh(a) (g) 1 − pm , agent a obtains the highest possible utility level for the allocation h. It follows |Nh(a) (g) ∩ h(A1 )|   > 1 − pm , when h results from h by a that πa (h ) < πa (h). If ηh(a) (g) and b beneficially exchanging houses, following from the symmetry of utility function u l (·), l = 1, 2, pm >

|Nh(a) (g) ∩ h(A2 )| |Nh(b) (g) ∩ h(A1 )| − 1 ≥ ηh(b) (g) ηh(a) (g)

pm >

|Nh(b) (g) ∩ h(A1 )| |Nh(a) (g) ∩ h(A2 )| − 1 ≥ . ηh(a) (g) ηh(b) (g)

and

It yields a contradiction.

123

Z. Cui, Y.-A. Hwang

Now we turn to the possibility pm < internal cohesion of h(A1 ),

|Nh(b) (g) ∩ h(A1 )| ≤ 1 − pm . Owing to the ηh(b) (g)

|Nh(b) (g) ∩ h(A1 )| |Nh(a) (g) ∩ h(A1 )| ≥ > pm . ηh(a) (g) ηh(b) (g) |Nh(a) (g) ∩ h(A1 )| ≤ 1 − pm , it is straightforward to see that the exchange is not ηh(a) (g) |Nh(a) (g) ∩ h(A1 )| > 1 − pm , beneficial. If ηh(a) (g) If

|Nh(a) (g) ∩ h(A2 )| − 1 |Nh(a) (g) ∩ h(A2 )| < < pm . ηh(a) (g) ηh(a) (g) Therefore, after the trade, agent b’s utility level is strictly reduced. |Nh(b) (g) ∩ h(A1 )| > 1 − pm . It is straightforward to Finally, we explore the case ηh(b) (g) see that pm >

|Nh(a) (g) ∩ h(A2 )| |Nh(a) (g) ∩ h(A2 )| − 1 |Nh(b) (g) ∩ h(A2 )| ≥ > ηh(b) (g) ηh(a) (g) ηh(a) (g)

where the second inequality follows from the internal cohesion of h(A2 ). Thus, after exchange, agent b’s utility level is strictly reduced. In summary, there is no allocation resulting from h by agents a and b beneficially   exchanging houses for any a ∈ A1 and b ∈ A2 . Theorem 3 shows that when all individuals prefer mixed neighborhoods, the internal cohesion of h(A1 ) and h(A2 ) can guarantee stability of the allocation h. The reasoning is as follows. Each agent has no motivation to move to a house when all of its neighbors are of different-color. Therefore, the exchange is beneficial only if two agents are from mixed neighborhoods or are surrounded by different-color neighbors. Consider the first possibility. When two agents are not neighbors, the exchange cannot be beneficial, because all individuals have the same preference for mixed neighborhoods. Now we turn to the case where agents a ∈ A1 and b ∈ A2 reside in neighboring houses. For agent b, let p denote the proportion of neighbors who are black. (1) If p < pm , given the internal cohesion of h(A1 ), to make the exchange beneficial, for agent a, the proportion of black neighbors must be strictly larger than 1 − pm . Then, through the exchange, either agent a or agent b moves to a more segregated neighborhood. (2) If p ∈ [ pm , 1 − pm ], owing to the internal cohesion of h(A1 ) and h(A2 ), for agent a, the proportion of black neighbors is not less than pm and is not larger than 1 − pm . Both agents receive the highest possible level of utility for the allocation h and the exchange cannot be beneficial. (3) If p > 1 − pm , following from the internal cohesion of h(A2 ), exchange brings agent b into a more segregated neighborhood. Proposition 3 also excludes this second possibility.

123

House exchange and residential segregation in networks

In the left panel of Fig. 3, for any black agent, most neighbors are white. Neither h(A1 ) nor h(A2 ) is internally cohesive. However, it is easy to check that the allocation illustrated by the left panel of Fig. 3 is stable when all individuals prefer mixed neighborhoods. The following theorem formally explores this possibility and offers another sufficient condition for stability of an allocation. Theorem 4 Assume that utility functions u 1 (·) and u 2 (·) are either symmetric singlepeaked or symmetric single-plateaued. Then, an allocation h ∈ H is stable when h(A1 ) and h(A2 ) form a counterpart partition of H. Before proceeding with the proof of Theorem 4, we provide the following lemma which gives a necessary condition for beneficial exchange of houses between two distinct agents when all members of both ethnic groups prefer mixed neighborhoods. The proof is shown in the Appendix. Lemma 2 Assume that u 1 (·) and u 2 (·) are either symmetric single-peaked or sym metric single-plateaued. Let h be the allocation resulting from h ∈ H by agents a and b exchanging houses for any a ∈ A1 and b ∈ A2 . Then, the exchange is beneficial only when     |Nh(a) (g) ∩ h(A1 )| |Nh  (a) (g) ∩ h (A1 )| |Nh(a) (g) ∩ h(A1 )| 1 + −1 × − ≥0 ηh(a) (g) ηh  (a) (g) ηh(a) (g) 2 (3) and 



    |Nh(b) (g) ∩ h(A2 )| |Nh  (b) (g) ∩ h (A2 )| |Nh(b) (g) ∩ h(A2 )| 1 + −1 × − ≥0 ηh(b) (g) ηh  (b) (g) ηh(b) (g) 2 (4) where there exists at least one strict inequality. 

Proof of Theorem 4 Consider a pair of distinct agents a ∈ A1 and b ∈ A2 . Let h be the allocation resulting from h by a and b exchanging houses. Owing to Lemma 1, it is sufficient for us to explore the case where gh(a)h(b) = 1. It follows that for agents a and b, 

|Nh  (a) (g) ∩ h (A1 )| ηh  (a) (g)

=

|Nh(b) (g) ∩ h(A1 )| − 1 , ηh(b) (g)

=

|Nh(a) (g) ∩ h(A2 )| − 1 . ηh(a) (g)



|Nh  (b) (g) ∩ h (A2 )| ηh



(b) (g)

123

Z. Cui, Y.-A. Hwang 

As an application of Lemma 2, the allocation h results from h by agents a and b beneficially exchanging houses only if 

 |Nh(a) (g) ∩ h(A1 )| |Nh(b) (g) ∩ h(A1 )| − 1 + −1 ηh(a) (g) ηh(b) (g)   |Nh(a) (g) ∩ h(A1 )| 1 × − ≥0 ηh(a) (g) 2

and 

 |Nh(b) (g) ∩ h(A2 )| |Nh(a) (g) ∩ h(A2 )| − 1 + −1 ηh(b) (g) ηh(a) (g)   |Nh(b) (g) ∩ h(A2 )| 1 − ≥0 × ηh(b) (g) 2

where there exists at least one strict inequality. Due to the assumption that h(A1 ) and   h(A2 ) form a counterpart partition of H, the above condition cannot hold. Theorem 4 says that the assumption that h(A1 ) and h(A2 ) form a counterpart partition of H can guarantee stability of the allocation h when members of both ethnic groups prefer for mixed neighborhoods. As in the proof above, consider the case where agents a ∈ A1 and b ∈ A2 are neighbors. When h(A1 ) and h(A2 ) form a counterpart partition where the first inequality holds with strict inequality, if agent a lives in a segregated neighborhood, then the exchange with agent b brings a into a more segregated neighborhood. There is no incentive for a and b to exchange houses. Remark 1 The assumption that h(A1 ) and h(A2 ) form a counterpart partition cannot guarantee stability of the allocation h provided that all members of A1 and A2 prefer segregation. Consider the allocation given by the left panel of Fig. 3. When a pair of distinct agents a ∈ A1 and b ∈ A2 are neighbors, the exchange between them brings each of them into a neighborhood containing a higher proportion of same-color neighbors and increases their utility levels. Therefore, the allocation is not stable. Assume that all members of both ethnic groups prefer mixed neighborhoods. Theorems 3 and 4 only present a sufficient condition for stability of an allocation. Consider the allocation of houses specified by Fig. 5. No two agents are motivated to exchange their houses when u 1 (·) and u 2 (·) are symmetric single-peaked or symmetric singleplateaued. On the other hand, for two “central” houses occupied by a ∈ A1 and b ∈ A2 , it is trivial to see that Fig. 5 A stable allocation illustrating that neither of the conditions in Theorems 3 and 4 is necessary

123

House exchange and residential segregation in networks

|Nh(a) (g) ∩ h(A1 )| 2 |Nh(b) (g) ∩ h(A2 )| 2 = and = . ηh(a) (g) 3 ηh(b) (g) 8 Neither h(A1 ) nor h(A2 ) is internally cohesive. And, h(A1 ) and h(A2 ) fail to form a counterpart partition of H.

5 Discussion of the assumptions In this section, we discuss the key assumptions underlying the main results, with regard to the absence of vacant houses and the non-transferability of utility. Due to space constraints, we do not present the different models in detail.13 5.1 The absence of vacant houses Throughout the analysis, we have maintained the assumption that there are no vacant houses. However, in the literature relating to the Schelling model, one frequently used assumption is that agents have an opportunity to move to vacant houses. An interesting question is to see what happens if we assume that there are vacant houses in our model. Assume that there are vacant houses; formally, |A| = |A1 | + |A2 | < |H|. Agents only care about the proportion of same-color neighbors. Owing to the existence of vacant houses, for any allocation h, given the internal cohesion of h(A1 ), h(A2 ) is not necessarily internally cohesive. Consider the case that all members of both ethnic groups have a preference for segregation. Assume that for an allocation h, both h(A1 ) and h(A2 ) are internally cohesive. When each black (white) agent moves to a vacant house or exchanges houses with an agent of different-color, the proportion of neighbors being black (white) is reduced. This agent’s utility level is reduced. Following the logic of the proof of Theorem 1, h is stable. Therefore, the internal cohesion of both h(A1 ) and h(A2 ) can guarantee stability of the allocation h. We now turn to the case where all members of both ethnic groups have a preference for mixed neighborhoods. Assume that the house distribution network g is a circle. Consider the allocation h illustrated by Fig. 6 where a blank node represents a vacant house. It is easy to verify that both h(A1 ) and h(A2 ) are internally cohesive. However, h is unstable. In fact, by moving to a vacant house, any “interior” agent can obtain the highest possible utility level rather than zero. Therefore, even if both h(A1 ) and h(A2 ) are (strictly) internally cohesive, h may be not stable. 5.2 The non-transferability of utility An important aspect of our model is that utility is not transferable across agents. The assumption of non-transferable utility (NTU) is extensively employed in the literature 13 We would like to thank two anonymous referees so much for pointing out these possibilities and encour-

aging this discussion.

123

Z. Cui, Y.-A. Hwang Fig. 6 Given the existence of vacant houses, insufficiency of internal cohesion when members of both groups prefer mixed neighborhoods

Fig. 7 Given the transferable utility, insufficiency of internal cohesion when members of both groups prefer mixed neighborhoods

on the Schelling’s model. However, it is a matter of technical importance to check whether or not the main results are robust to transferability of utility. Assume that agents’ utility is transferable. Without loss of generality, suppose that a house exchange between two distinct agents is beneficial if and only if after the trade, the sum of their utility levels is strictly increased. Consider the case that all members of both ethnic groups have a preference for segregation. Assume that for the allocation h, both h(A1 ) and h(A2 ) are internally cohesive. For any pair of agents from different ethnic groups, when exchanging houses, each of them has to move to the neighborhood with a lower proportion of same-color neighbors. The sum of their utility levels cannot be increased. The allocation h is stable. Thus, the internal cohesion of both h(A1 ) and h(A2 ) can guarantee stability of h. Now consider the case that all members of both ethnic groups prefer to reside in 50−50 % perfectly integrated neighborhoods; that is, pm = 0.5. Assume that the  network g is a torus with “Moore neighborhoods”. Consider allocations h and h illustrated by the left and right panels of Fig. 7, respectively. It is not a difficult task  to prove the internal cohesion of h(A1 ) and h(A2 ). h can result from h by a pair of black and white agents exchanging houses. Through the exchange, the proportion of same-color neighbors changes from 58 to 48 for black agent whilst the proportion of same-color neighbors changes from 38 to 28 for white agent. For these two agents, the sum of their utility levels can be strictly increased when both u 1 (·) and u 2 (·) are

123

House exchange and residential segregation in networks

strictly convex on [0, 0.5]. Consequently, the internal cohesion of h(A1 ) and h(A2 ) may not be enough to guarantee stability of the allocation h.

6 Conclusion This paper considers the Schelling model in an arbitrary fixed network where there are no vacant houses and provides sufficient conditions to guarantee stability of allocations. Agents have preferences either for segregation or for mixed neighborhoods; and utility is non-transferable. The exchange between two distinct agents is beneficial when their utility levels are increased and for one of them, utility is strictly improved. We show that an allocation is stable when in comparison with each white agent, each black agent has a higher proportion of neighbors who are black. Equivalently, this condition means that each white agent has a higher proportion of neighbors who are white than any black agent. This result holds irrespective of the preferences of agents. In addition, when all members of both ethnic groups prefer mixed neighborhoods, an allocation is also stable provided that if an agent belongs to the minority (majority), then any neighbor of opposite-color is in a smaller minority (larger majority). The analysis of this paper can be extended in a number of directions. First, it is desirable to conduct stochastic stability analysis and identify the most likely stable allocations. Second, the possibility that a coalition of any size may redistribute its members’ houses should be taken into account. Third, when agents have a preference for mixed neighborhoods, more general form of utility function, rather than the symmetric one, should be considered. All these extensions constitute interesting and important areas for future research.

7 Proofs 

Proof of Proposition 1 According to the specific values of min i∈H

|Ni (g) ∩ H | , the ηi (g)

proof is divided into two cases.  |Ni (g) ∩ H | = 1. Case I min ηi (g) i∈H    In this case, |Ni (g) ∩ H | = ηi (g) holds for any i ∈ H . That is, for any i ∈ H ,    Ni (g) ⊂ H . Therefore, gi j = 0 for any i ∈ H and j ∈ H\H . Following from the  assumption that gi j = g ji for any i, j ∈ H, we have that N j (g) ⊂ H\H for any  j ∈ H\H . As a result, 

min j∈H\H





|N j (g) ∩ (H\H )| |Ni (g) ∩ (H\H )| = 1 > 0 = max . i∈N η j (g) ηi (g)  (g) H\H 

Case II min i∈H

|Ni (g) ∩ H | < 1. ηi (g)

123

Z. Cui, Y.-A. Hwang

In this case, NH (g) = ∅ and NH\H (g) = ∅. First of all, we introduce a lemma to facilitate the proof. Lemma 3 Consider a house distribution network g. For any proper, nonempty subset  of houses H ⊂ H, if NH (g) = ∅, 



|Ni (g) ∩ H | |Ni (g) ∩ H | = min . i∈N η (g) ηi (g)  (g) i i∈H H\H min

The proof of this lemma is trivial. We omit it here.  We then verify that the subset H\H is internally cohesive as follows. 

|Ni (g) ∩ (H\H )| i∈N ηi (g)  (g) H\H max

=

 max

i∈N

H\H

 (g)

|Ni (g) ∩ H | |Ni (g) ∩ H | = 1 − min 1− i∈N ηi (g) ηi (g)  (g) H\H 





= 1 − min i∈H

|Ni (g) ∩ H | ηi (g)





|N j (g) ∩ H | = ≤ 1 − max j∈N  (g) η j (g) H

min

j∈N

H

 (g)

|N j (g) ∩ H | 1− η j (g) 





|N j (g) ∩ (H\H )| |N j (g) ∩ (H\H )| = min = min  j∈N η j (g) η j (g)  (g) j∈H\H H\(H\H ) 

where the “≤” inequality follows from the internal cohesion of H and the third and the last “=” inequalities are applications of Lemma 3.   

Proof of Proposition 3 Assume that there exists a house i 0 ∈ H such that Ni0 (g) ∩  H = ∅. Therefore, 

0 ≤ min i∈H



|Ni0 (g) ∩ H | |Ni (g) ∩ H | ≤ = 0. ηi (g) ηi0 (g)

(5)

On the other hand, according to the nonexistence of isolated houses, Ni0 (g) = ∅.   Combining this with Ni0 (g) ∩ H = ∅, both j ∈ H\H and j ∈ NH (g) hold for any j ∈ Ni0 (g). It follows that 

|N j (g) ∩ H | 1 1 ≥ max ≥ > 0. j∈N  (g) j∈Ni 0 (g) η j (g) η j (g) |H| − 1 H max

(6) 

Inequalities (5) and (6) yield a contradiction to the internal cohesion of H .

123

 

House exchange and residential segregation in networks

Proof of Lemma 1 Without losing generality, assume that each utility function u l (·),  l = 1, 2, is symmetric single-plateaued. That is, pm < 0.5. Let h denote the allocation resulting from h by agents a and b exchanging houses. Depending on the specific positions of houses h(a) and h(b), the proof is divided into two cases. Case I h(a) ∈ h(A1 )\Nh(A2 ) (g) or h(b) ∈ h(A2 )\Nh(A1 ) (g). It is sufficient to consider the situation h(a) ∈ h(A1 )\Nh(A2 ) (g). It follows that 

|Nh  (b) (g) ∩ h (A2 )| |Nh(a) (g) ∩ h(A1 )| = 1 and then = 0. ηh(a) (g) ηh  (b) (g) 

If h(b) ∈ h(A2 )\Nh(A1 ) (g), owing to the specification of u 1 and u 2 , πa (h) = πa (h ) =   0 and πb (h) = πb (h ) = 0. If h(b) ∈ Nh(A1 ) (g), πb (h) > 0 and πb (h ) = 0 hold. According to Definition 1, the exchange is not beneficial. Case II h(a) ∈ Nh(A2 ) (g), h(b) ∈ Nh(A1 ) (g) and gh(a)h(b) = 0. In this case, it follows that for agent a and agent b, 

|Nh  (a) (g) ∩ h (A1 )| ηh  (a) (g)

=

|Nh(b) (g) ∩ h(A1 )| , ηh(b) (g)

(7)

=

|Nh(a) (g) ∩ h(A2 )| . ηh(a) (g)

(8)



|Nh  (b) (g) ∩ h (A2 )| ηh  (b) (g)

|Nh(a) (g) ∩ h(A1 )| |Nh(b) (g) ∩ h(A2 )| ∈ [ pm , 1 − pm ] or ∈ [ pm , 1 − pm ], ηh(a) (g) ηh(b) (g) the exchange between agents a and b is not beneficial. It is sufficient to consider |Nh(a) (g) ∩ h(A1 )|  ∈ [ pm , 1 − pm ]. πa (h ) ≥ πa (h) implies that the situation ηh(a) (g) |Nh(b) (g) ∩ h(A1 )| ∈ [ pm , 1 − pm ]. It follows that ηh(b) (g) If

|Nh(b) (g) ∩ h(A1 )| |Nh(b) (g) ∩ h(A2 )| =1− ∈ [ pm , 1 − pm ]. ηh(b) (g) ηh(b) (g) Therefore, both agents a and b obtain the highest possible level of utility and have no incentive to exchange their houses. |Nh(a) (g) ∩ h(A1 )| ∈ / [ pm , 1 − pm ] and Now we turn to the situation ηh(a) (g) |Nh(b) (g) ∩ h(A2 )|  ∈ / [ pm , 1 − pm ]. If h results from h by agents a and b beneηh(b) (g) ficially exchanging houses,







|Nh(a) (g) ∩ h(A1 )| 1

|Nh  (a) (g) ∩ h (A1 )| 1



−

≥

−



ηh(a) (g) 2 ηh  (a) (g) 2

123

Z. Cui, Y.-A. Hwang







|Nh(b) (g) ∩ h(A2 )| 1

|Nh  (b) (g) ∩ h (A2 )| 1



− ≥

−



ηh(b) (g) 2 ηh  (b) (g) 2

and

where there exists at least one strict inequality. By substituting Eqs. (7) and (8), the above condition can be rewritten as





|Nh(a) (g) ∩ h(A1 )| 1



≥ 1 − |Nh(b) (g) ∩ h(A2 )| − 1

−



ηh(a) (g) 2 ηh(b) (g) 2



 

|Nh(b) (g) ∩ h(A2 )| 1

|Nh(a) (g) ∩ h(A1 )|



− ≥ 1− −

ηh(b) (g) 2 ηh(a) (g)

and

1

2

where there exists at least one strict inequality. When verifying the above conditions, a contradiction yields.   Proof of Lemma 2 Consider agent a. According to the specification of u 1 (·),







|Nh(a) (g) ∩ h(A1 )| 1

|Nh  (a) (g) ∩ h (A1 )| 1



− ≥

− . πa (h) ≤ πa (h ) ⇐⇒

ηh(a) (g) 2 ηh  (a) (g) 2



Without loss of generality, assume that 

|Nh(a) (g) ∩ h(A1 )| 1 > . In this case, πa (h) ≤ ηh(a) (g) 2

πa (h ) implies that ⎧ ⎪ ⎪ ⎪ ⎪ ⎨





|Nh  (a) (g) ∩ h (A1 )| 1 |Nh(a) (g) ∩ h(A1 )| |Nh  (a) (g) ∩ h (A1 )| ≥ if ≥ ; ηh(a) (g) ηh  (a) (g) ηh  (a) (g) 2  ⎪ |Nh(a) (g) ∩ h(A1 )| 1 1 |Nh  (a) (g) ∩ h (A1 )| ⎪ ⎪ ⎪ − ≥ − otherwise. ⎩ ηh(a) (g) 2 2 ηh  (a) (g) 

Simplifying the above expression, πa (h) ≤ πa (h ) only if 

|Nh(a) (g) ∩ h(A1 )| |Nh  (a) (g) ∩ h (A1 )| + ≥ 1. ηh(a) (g) ηh  (a) (g) Hence, Inequality (3) is verified. The above reasoning also applies to agent b; that is, Inequality (4) holds. Following from Definition 1, the conclusion can be verified.  

References Abdulkadiroglu A, Sonmez T (1998) Random serial dictatorship and the core from random endowments in house allocation problems. Econometrica 66:689–701 Abdulkadiroglu A, Sonmez T (1999) House allocation with existing tenants. J Econ Theory 88:233–260

123

House exchange and residential segregation in networks Ben-Shoham A, Serrano R, Volij O (2004) The evolution of exchange. J Econ Theory 114:310–328 Chen Y, Sonmez T (2002) Improving efficiency of on-campus housing: an experimental study. Am Econ Rev 92:1669–1686 Chen Y, Sonmez T (2004) An experimental study of house allocation mechanisms. Econ Lett 83:137–140 Fagiolo G, Valente M, Vriend NJ (2007) Segregation in networks. J Econ Behav Organ 64:316–346 Grauwin S, Bertin E, Lemoy R, Jensen P (2009) Competition between collective and individual dynamics. Proc Natl Acad Sci 106:20622–20626 Grauwin S, Goffette-Nagot F, Jensen P (2012) Dynamic models of residential segregation: an analytical solution. J Publ Econ 96:124–141 Kandori M, Serrano R, Volij O (2008) Decentralized trade, random utility and the evolution of social welfare. J Econ Theory 140:328–338 Massey DS, Rothwell J, Domina T (2009) The changing bases of segregation in the United States. ANN Am Acad Polit Soc Sci 626:74–90 Miyagawa E (2002) Strategy-proofness and the core in house allocation problems. Games Econ Behav 38:347–361 Morris S (2000) Contagion. Rev Econ Stud 67:57–78 Pancs R, Vriend NJ (2007) Schelling’s spatial proximity model of segregation revisited. J Publ Econ 91:1–24 Roth A (1982) Incentive compatibility in a market with indivisible goods. Econ Lett 9:127–132 Roth A, Postlewaite A (1977) Weak versus strong domination in a market with indivisible goods. J Math Econ 4:131–137 Roth A, Sonmez T, Unver U (2004) Kidney exchange. Q J Econ 119:457–488 Serrano R, Volij O (2008) Mistakes in cooperation: the stochastic stability of Edgeworth’s recontracting. Econ J 118:1719–1741 Schelling TC (1969) Models of segregation. Am Econ Rev 59:488–493 Schelling TC (1971) Dynamic models of segregation. J Math Soc 1:143–186 Schelling TC (1978) Micromotives and macrobehavior. W. W. Norton & Company, New York Shapley L, Scarf H (1974) On cores and indivisibility. J Math Econ 1:23–37 Sonmez T, Unver U (2005) House allocation with existing tenants: an equivalence. Games Econ Behav 52:153–185 Vinkovi´c D, Kirman A (2006) A physical analogue of the Schelling model. Proc Natl Acad Sci 103:19261– 19265 Young HP (1998) Individual strategy and social structure: an evolutionary theory of institutions. Princeton University Press, Princeton Zhang J (2004a) A dynamic model of residential segregation. J Math Soc 28:147–170 Zhang J (2004b) Residential segregation in an all-integrationist world. J Econ Behav Organ 54:533–550 Zhang J (2011) Tipping and residential segregation: a unified Schelling model. J Reg Sci 51:167–193

123