-
1. Introduction
"Birds of a feather flock together" is an often used proverb to describe homophily [
1
], i.e., the
phenomenon that homogeneous groups are prevalent in society. The group members might be
similar in terms of, for example, their ethnic group, their socioeconomic status, or their political
orientation. Within a city, such groups typically cluster together, which then leads to segregated
neighborhoods, called residential segregation [
2
].
Segregated neighborhoods have a strong impact on the socioeconomic prospects [
3
] and on
the health of its inhabitants [
4, 5
]. This explains why residential segregation is widely studied.
Typical models are agent-based and they assume that the agents are partitioned into a given
ifxed set of types, which can be understood as an ethnic group, a trait, or an afiliation. The
landmark model of this kind was proposed by Schelling [
6, 7
] roughly fifty years ago. There,
agents of two types are placed on the line or a grid and it is assumed that an agent is content
with her current location, if at least a -fraction of all neighbors are of her type, for some
∈ [
0, 1
]. Discontent agents try to relocate. As a result, large homogeneous neighborhoods
eventually form, even if all the agents are tolerant, i.e., if ≤ 1/2.
However, real-world agents show more complex behavior than predicted by Schelling’s
two-type model. For example, people might not care about the ethnic group, but they might
compare themselves with their neighbors along non-categorical aspects like age, household
income, or position in a political left-right spectrum. Given these more complex preferences,
the agents cannot be assumed to simply classify their neighbors into friends and enemies.
This is in line with recent economics research which reveals that individuals’ happiness is
relative to a particular peer group. E.g., the reference income hypothesis [
8, 9
] states that
people compare their income with a reference value, e.g., the mean or median income of their
neighborhood [
10, 11
].
With this paper, we initiate the study of agent-based models for residential segregation that
use non-categorical type-values for the agents. This allows for modeling more realistic agent
preferences. Using arbitrary type-values in [
0, 1
] unlocks an entirely new class of game-theoretic
models, that we call Schelling Games with Continuous Types. As the first steps, we consider
three natural behavioral models: agents compare their type-value with the most diferent or the
average type-value in their neighborhood, or they have a tolerance range for the accepted
typevalue diference. All three variants of the cost function are motivated by plausible real-world
behavior. Comparing with the maximum-diference type-value is motivated by considering
types as positions in a political left-to-right spectrum, comparing with the average type-value
is suggested by the setting where types are household incomes, and the model with a tolerance
range is inspired by types being the age of the agents, where agents consider other agents as
similar if they are roughly their age.
1.1. Model
A Schelling Game with Continuous Types is defined by an undirected connected graph = (, ),
a set of strategic agents and a type function : → [
0, 1
] mapping agent ∈ to her
type () ∈ [
0, 1
]. Unless stated otherwise, we assume without loss of generality that () ≤ ()
for , ∈ and ≤ . The type-distance : 2 → [
0, 1
] between two agents and is defined
as (, ) = |() − ()|.
An agent’s strategy is her location on the graph, i.e., a node of . A strategy profile is an
-dimensional vector whose -th entry corresponds to the strategy of the -th agent and where
all strategies are pairwise disjoint. For an agent ∈ , let the neighborhood of be the set
( ) = { ∈ : { (), ()} ∈ } of agents living in the neighborhood of () in . If
( ) = ∅, we say that is isolated.
In Swap Schelling Games with Continuous Types, every node is occupied by exactly one agent,
so = | |. Agents can change their strategies only by swapping their location with another
agent. As agents are rational, we only consider profitable swaps that strictly decrease the
individual cost of both involved agents. A strategy profile is a swap equilibrium (SE) if it does
not admit any profitable swaps.
In Jump Schelling Games with Continuous Types, empty nodes exist, i.e., < | | with
:= | | − . An agent can change her strategy by jumping to any empty node. Agents only
perform profitable jumps that strictly decrease their cost. A strategy profile is a jump equilibrium
(JE) if it does not admit any profitable jumps.
We consider the following three cost models. In Average Type-Distance Games (ADGs), the
cost of agent in is defined as the average distance towards her neighbors, i.e., cost( ) =
∑︀∈|(( ))|(,) . In Maximum Type-Distance Games (MDGs), the cost of agent in is defined
as the maximum distance towards her neighbors, i.e., cost( ) = max∈( ) (, ). In Cutof
Games (CGs), given a cutof parameter ∈ [
0, 1
], let +( ) = { ∈ ( ) : (, ) ≤ } be
the set of friends of agent in and − ( ) = ( ) ∖ +( ) be the set of enemies. The cost
in is the fraction of enemies in the neighborhood of , i.e., cost( ) = |− ( )| . The model of
|( )|
CGs is closer to the original Schelling model, i.e., neighbors whose type diference is within
the cutof are considered as friends; however, in contrast to previous models, friendship is not
transitive.
For all cost models, we consider two possible variants depending on how we define the cost
of an isolated agent. Under the unhappy-in-isolation (UIS) variant, this cost is set to 1; under the
happy-in-isolation (HIS) variant, it is set to 0. Since we are considering connected graphs, an
agent can never be isolated in swap games, so the two variants create a diferent model only for
jump games. In summary, we obtain nine diferent games that we denote as X-Y-Z, where X ∈
{J,S} stands for the deviation model, either jump (J) or swap (S), Z ∈ {ADG,MDG,CG} stands for
cost model and, whenever X = J, Y ∈ {UIS,HIS} states which cost is paid in isolation.
We measure the quality of a strategy profile by its social cost cost( ) = ∑︀ cost( ) and
denote by * a social optimum, i.e., a strategy profile minimizing the social co s∈t1. The quality
of equilibria is measured by the price of anarchy (PoA) and the price of stability (PoS). The
PoA of a game is obtained by comparing the equilibrium with the largest social cost with the
social optimum, while the PoS refers to the equilibrium with the lowest social cost. The PoA
(resp. PoS) of a class of games is obtained by taking the worst-case PoA (resp. PoS) over all
games in the class. Formally, PoA() = sup∈ PoA() and PoS() = sup∈ PoS().
1.2. Related Work
Schelling’s seminal residential segregation model was formulated as a strategic game by Chauhan
et al. [
12
]. In their model, agents of two types have a threshold-based utility function and an
agent gets maximum utility if for this agent the fraction of same-type neighbors is at least
. Later, Echzell et al. [
13
] extended this model to more than two types and showed that the
convergence behavior of improving response dynamics strongly depends on . Agarwal et al.
[
14
] focused on the case with = 1 and proved that equilibrium existence on trees is not
guaranteed and that computing socially optimal strategy profiles or equilibria with high social
welfare is NP-hard. Also, the authors introduced a new welfare measure that counts the number
of agents that have an other-type neighbor, called the degree of integration. For = 1 also the
influence of the underlying graph and of locality was studied [
15
] and welfare guarantees have
been investigated [
16
].
1The social cost can be considered as a segregation measure, since a low social cost in our models means that many
agent neighborhoods are very homogeneous, i.e., are strongly segregated.
A variant where the agent itself is counted in the fraction of same-type neighbors has been
introduced in [
17
]. Moreover, recently also agents with non-monotone utility functions, in
particular, with single-peaked utilities, have been considered in [
18
].
Closest to our work is another very recent variant, called Tolerance Schelling Games,
introduced by Kanellopoulos et al. [
19
]. In this model agents have a discrete type and all types
are ordered according to a given total ordering ≻ , i.e., 1 ≻ 2 ≻ · · · ≻ . Agents have
tolerance values to agents of other types depending on the number of types in between the two
in the given ordering. Specifically, the model uses a tolerance vector t = (0, . . . , − 1) and the
tolerance between agents of type and type is equal to |− |. In their work, they specifically
analyze balanced tolerance Schelling games in which every type has the same number of agents
and only consider the jump variant of the game. The authors show that for every tolerance
vector with 1 < 1 there are graphs that do not admit equilibria. Furthermore, they look at
-binary Tolerance Schelling Games where agents tolerate all other agents of types with at
most − 1 other types in between in the ordering. For specific values of and this game
admits at least one equilibrium on trees and grid graphs and they provide algorithms to find
such states. Also, they prove high tight asymptotic bounds on the PoA and the PoS.
1.3. Our Contribution
We introduce very general strategic residential segregation models with the decisive new feature
that non-categorical types are possible. This allows for modeling more complex and arguably
also more realistic agent behavior. Moreover, the power of our models can be seen by noting
that they generalize several existing variants. For example, the -type model by Agarwal et al.
[
14
] with = 2 can be captured by both ADGs and CGs, by setting one type to value 0 and the
other to value 1 (and < 1). Also, the -type model by [
13
] for = 1 can be modeled via a CG
with suitable type-values and low enough . Moreover, also the -binary Tolerance Schelling
Game by Kanellopoulos et al. [
19
] is captured by a CG, with equally spaced type-values and a
suitably chosen cutof 2.
Besides generalizing several known models, our results go beyond what was known for the
special cases. In particular, we demonstrate with the MDG that our model allows for drastically
diferent games that behave very diferently, compared to previously considered variants. For
the S-MDG, not only do equilibria always exist, independently of the underlying graph, but
we are also able to construct these states very eficiently. The same holds for the J-HIS-MDG,
the ADG, and the CG on specific graph classes. Also, the HIS-assumption has not been studied
before.
More precisely, we obtain the following results.
Existence of Equilibria. First of all, we observe that whenever the type function is such
that (0) = 1, (1) = 1 and () ∈ {0, 1} for each ∈ , ADGs and CGs boil down to classical
Swap or Jump Schelling games with two types considered in [
14
] for which non-existence of
equilibria is known in general graphs. Hence, we immediately derive that S-ADGs, S-CGs,
J-UIS-ADGs, and J-UIS-CGs may not have equilibria when played on general graphs. However,
2In the other direction, the J-UIS-ADG can be represented as a Tolerance Schelling Game by using enough types,
with the tolerance of two types , ∈ [
0, 1
] being 1 − | − |. However, irrational type-values cannot be translated.
we show that a SE always exists in S-MDGs and it can be computed in (||) time by exploiting
the properties of a breadth-first search tree of a graph. For S-ADGs, we prove existence of SEa on
regular graphs, while, for S-CGs, existence is extended to even almost ∆ -regular graphs3. Both
results are obtained by resorting to a potential function technique. For the latter, in particular,
an (∆ ) algorithm can be derived. For jump games, stability is much harder to achieve and we
can prove positive results mostly only under the HIS variant. For J-UIS-MDGs, in fact, existence,
provable again via a potential function argument, is guaranteed as long as is smaller than the
minimum degree of . To complement this result, we exhibit a game on a ∆ -regular graph,
with = ∆ , without any JE. For J-HIS-MDGs, instead, JEa are always guaranteed to exist, still
via a potential function argument. Interestingly, we can compute a JE in (| |1+min{2,}), as
long as admits 2, as a subgraph. In fact, a JE can be constructed by assigning agents 1
and to the two nodes of the left bipartition and the remaining agents arbitrarily to nodes
not belonging to the right bipartition. Two direct consequences of this result is an (| |2)
algorithm for the case of = 1 and an (| |3) algorithm for graphs with (| |3/2) edges. We
also design an (| |3) algorithm for the case of = 2. Finally, for J-HIS-MDGs, J-HIS-ADGs
and J-HIS-CGs played on a path, we give an ( log ) algorithm for computing a JE.
Eficiency of Equilibria. We also provide extensive results on the PoA and the PoS. In
particular, under a worst-case perspective, we can prove that there can be equilibria of positive
social cost, while a social optimum with social cost zero exists, yielding an unbounded PoA,
which often holds also for games played on paths. The only exceptions are S-MDGs and S-ADGs,
having a PoA in Θ( ) and in Θ( ∆) , respectively, where ∆ is the maximum degree of the
underlying graph. For characterizing the PoS, usually, the existence of either potential functions
or algorithms computing equilibria with provable approximation guarantees are required. As
we have seen, this may be either impossible or require quite an efort; nevertheless, these
dificulties are common also in previous models of Schelling games. For games played on paths,
we derive a bound of 1 in S-ADGs and an upper bound of 2 in S-MDGs, S-CGs and J-HIS-MDGs.
On regular graphs, a bound of 1 holds for both S-ADGs and S-CGs. Finally, for games played on
unrestricted topologies, we show that the PoS is in Θ( ) for both S-MDGs and J-HIS-MDGs
and even unbounded for J-UIS-MDGs.
For all missing details, we refer the reader to the extended version of this paper [
20
].