Schelling Games with Continuous Types

1 Introduction

"Birds of a feather flock together" is an often used proverb to describe homophily [McPherson et al., 2001], 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 [Massey and Denton, 1988].

Segregated neighborhoods have a strong impact on the socioeconomic prospects [Massey and Denton, 2019] and on the health of its inhabitants [Acevedo-Garcia and Lochner, 2003; Williams and Collins, 2016]. This explains why residential segregation is widely studied. Typical models are agent-based and they assume that the agents are partitioned into a given fixed set of types, which can be understood as an ethnic group, a trait, or an affiliation. The landmark model of this kind was proposed by Schelling [1969] 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 noncategorical 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. In contrast, the utility of an agent should depend on the respective non-categorical type-values of her neighbors. 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 [Clark and Oswald, 1996; Clark et al., 2008] states that people compare their income with a reference value, e.g., the mean or median income of their neighborhood [Luttmer, 2005; Clark et al., 2009].

With this paper, we initiate the study of agent-based models for residential segregation that use non-categorical typevalues 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 different or the average type-value in their neighborhood, or they have a tolerance range for the accepted type-value difference. All three variants of the cost function are motivated by plausible realworld behavior. Comparing with the maximum-difference 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.

(c) SE for the ADG

(d) SE for the CG with λ = 15

Figure 1: Sample swap equilibria (SE) in different Schelling Games with Continuous Types obtained from the same initial random state (a), in an 8-regular toroidal grid graph of size 50 × 50. (b), (c), and (d) show SE for our models reached from (a) via improving swaps. Each pixel represents a node with an agent. Colors represent type-values ranging from white (type-value 0) to black (type-value 1).

As Figure 1 shows, our models yield very different residential patterns in equilibrium.

1.1 Model

Given an undirected graph G = (V, E) and a node v ∈ V , we denote the degree of v in G as deg(v) = |{u ∈ V : {v, u} ∈ E}|. If every node in G has the same degree ∆, we say that G is ∆-regular. For x ∈ N+, let [x] = {1, . . . , x}.

A Schelling Game with Continuous Types is defined by an undirected connected graph G, n strategic agents and a type function t : [n] → [0, 1] mapping agent i ∈ [n] to her type t(i) ∈ [0, 1]. Unless stated otherwise, we assume wlog that t(i) ≤ t(j) for i, j ∈ [n] and i ≤ j. The type-distance d : [n]2 → [0, 1] between two agents i and j is defined as d(i, j) = |t(i) - t(j)|.

An agent's strategy is her location on the graph, i.e., a node of G. A strategy profile σ is an n-dimensional vector whose i-th entry corresponds to the strategy of the i-th agent and where all strategies are pairwise disjoint. Let σ-1 be its inverse function, mapping a node v ∈ V to the agent i choosing v as her strategy, with the assumption that σ-1 is equal to ø if v is empty, i.e., no agent chooses v as her strategy. We denote the set of empty nodes in σ as E(σ) = {v ∈ V : σ-1 (v) = ø}. Let |E(σ)| = e. For an agent i ∈ [n], let the neighborhood of i be the set Ni(σ) = {j ∈ [n] : {σ(i), σ(j)} ∈ E} of agents living in the neighborhood of σ(i) in G. If Ni(σ) = ∅, we say that i is isolated.

In Swap Schelling Games with Continuous Types, every node is occupied by exactly one agent, so n = |V |. Agents can change their strategies only by swapping their location with another agent. A swap by agents i and j in σ yields a new strategy profile σij, which is identical to σ with exchanged i-th and j-th entries. 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., n < |V |, and for every strategy profile σ we have e = |V | - n. An agent can change her strategy by jumping to any empty node. Consider agent i on node σ(i). A jump of agent i to an empty node v ∈ E(σ) yields a new strategy profile σi, which is identical to σ with the i-th entry changed to v. 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 i in σ is defined as the average distance towards her neighbors, i.e., costi(σ) = ∑j∈Ni(σ) d(i,j) |Ni(σ)| . In Maximum Type-Distance Games (MDGs), the cost of agent i in σ is defined as the maximum distance towards her neighbors, i.e., costi(σ) = maxj∈Ni(σ) d(i, j). In Cutoff Games (CGs), given a cutoff parameter λ ∈ [0, 1], let N + i (σ) = {j ∈ Ni(σ) : d(i, j) ≤ λ} be the set of friends of agent i in σ and N - i (σ) = Ni(σ) \ N + i (σ) be the set of enemies. The cost i in σ is the fraction of enemies in the neighborhood of i, i.e., costi(σ) = |N - i (σ)| |Ni(σ)| . The model of CGs is closer to the original Schelling model, i.e., neighbors whose type difference is within the cutoff 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 different model only for jump games. In summary, we obtain nine different 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, when 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(σ) = ∑i∈[n] costi(σ) and denote by σ∗ a social optimum, i.e., a strategy profile minimizing the social cost 1 . The quality of equilibria is measured by the price of anarchy (PoA) and the price of stability (PoS). The PoA of a game G 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.

1 The 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.

PoS) of a class of games C is obtained by taking the worstcase PoA (resp. PoS) over all games in the class. Formally, PoA(C) = supG∈C PoA(G) and PoS(C) = supG∈C PoS(G).

A game has the finite improvement property (FIP) if any sequence of improving moves must be finite. For showing this, we employ ordinal potential functions, since the FIP is equivalent to the existence of an ordinal potential function [Monderer and Shapley, 1996].

1.2 RelatedWork

Given the breadth of the research on residential segregation, we focus on recent work from the Artificial Intelligence and Algorithmic Game Theory communities.

Schelling's seminal residential segregation model was formulated as a strategic game by Chauhan et al. [2018]. 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. [2019] extended this model to more than two types and showed that the convergence behavior of improving response dynamics strongly depends on τ. Agarwal et al. [2021] 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 [Bil`o et al., 2022b] and welfare guarantees have been investigated [Bullinger et al., 2021].

A variant where the agent itself is counted in the fraction of same-type neighbors has been introduced in [Kanellopoulos et al., 2021]. Moreover, recently also agents with nonmonotone utility functions, in particular, with single-peaked utilities, have been considered in [Bil`o et al., 2022a].

Closest to our work is another very recent variant, called Tolerance Schelling Games, introduced by Kanellopoulos et al. [2022]. In this model agents have a discrete type and all k types are ordered according to a given total ordering ≻, i.e., T1 ≻ T2 ≻ · · · ≻ Tk. 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 = (t0, . . . , tk-1) and the tolerance between agents of type Ti and type Tj is equal to t|i-j|. 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 t1 < 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 k 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 k-type model by Agarwal et al. [2021] with k = 2 can be captured by both the ADG and the CG, by setting one type to value 0 and the other to value 1 (and λ < 1). Also, the k-type model by Echzell et al. [2019] for τ = 1 can be modeled via the CG with suitable type-values and low enough λ. Moreover, also the α-binary Tolerance Schelling Game by Kanellopoulos et al. [2022] is captured by the CG, with equally spaced type-values and a suitably chosen cutoff λ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 different games that behave very differently, 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 efficiently. The same holds for the J-HIS-MDG, the ADG, and the CG on specific graph classes. Also, the HISassumption has not been studied before. See Table 1 for an overview over our equilibrium existence results.

Besides equilibrium existence, we also studied the computational complexity of computing the social optimum and of finding states that minimize the maximum type-difference of neighbors. Both problems are NP-hard, see [Bil`o et al., 2023]. Moreover, we provide extensive results on the Price of Anarchy and the Price of Stability. In essence, the PoA is extremely high for all variants but the PoS is very low on paths or regular graphs. See Section 3 for a high-level overview and [Bil`o et al., 2023] for all the details. Finally, to shed light on the equilibrium structure and properties of our game variants, we present simulation experiments in Section 4. We find that the MDG and the ADG yield strongly segregated equilibria, while the CG produces more integrated equilibria.

All omitted details can be found in [Bil`o et al., 2023].

2 Existence and Construction of Equilibria

First of all, we observe that whenever the type function t is such that t(0) = 1, t(1) = 1 and t(i) ∈ {0, 1} for each i ∈ [n], ADGs and CGs boil down to classical Swap or Jump Schelling games with two types considered in [Agarwal et al., 2021] for which non-existence of equilibria is known in general graphs. Hence, we immediately get the following result.

Proposition 1. S-ADGs, S-CGs, J-UIS-ADGs, and J-UISCGs may not have equilibria when played on general graphs.

2.1 Swap Games

Despite the negative result from Proposition 1, we show that a SE always exists when considering S-MDGs and it can even be efficiently computed.

2 In 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 x, y ∈ [0, 1] being 1-|r-s|. However, irrational typevalues cannot be translated.

Maximum Type-Distance Game

The following lemma states that an improving swap never hurts those agents who end up paying a sufficiently large cost after the swap.

Lemma 1. Let agents i, j ∈ [n] perform a profitable swap in a S-MDG and let k be an agent with costk(σij) ≥ max{costi(σ), costj(σ)}. Then, costk(σ) ≥ costk(σij).

Proof. Assume the cost of agent k increases. Since the cost of k changes, agent i or j must belong to Nk(σij) and must be crucial for the new cost of k. Assume wlog that agent i is responsible for the increased cost, so costk(σij) = d(k, i). Since i ∈ Nk(σij), we get costi(σij) ≥ d(k, i). Thus, we obtain costi(σij) ≥ costk(σij) ≥ costi(σ) which contradicts the assumption that agent i performs a profitable swap.

We show that SE exist for S-MDGs since the FIP holds.

Proposition 2. The S-MDG has the FIP.

Proof. By Lemma 1, the lexicographical order of the ndimensional vector which sorts the agents' costs in a nonincreasing way decreases after each improving swap.

Proposition 2 implies that any sequence of improving swaps converges to a SE. However, as there is no guarantee of polynomial-time convergence, this result does not yield a polynomial-time algorithm for computing a SE. The following result shows how to efficiently construct a SE. To this end, we need some additional notation. Given a strategy profile σ and an agent i, we define the leftmost neighbor of i the agent lσ(i) = minj∈Ni(σ) j of smallest index among the neighbors of i in σ and the rightmost neighbor of i the agent rσ(i) = maxj∈Ni(σ) j of largest index among the neighbors of i in σ. As G is connected, σ is injective, and there are |V | agents, the leftmost and rightmost neighbors always exist. Moreover, by definition, we have costi(σ) = max{d(i, lσ(i)), d(rσ(i), i)}.

Theorem 1. A SE for the S-MDG can be computed in O(|E|).

Proof. For a given graph G defining an S-MDG, let τ be an arbitrary node of G and let T be a breadth-first search (BFS) tree of G rooted at τ. This tree exists as G is connected. Number the nodes of T from 1 to n in a natural way, that is, in increasing order of levels and proceedings from left to right within the same level. Let σ be the strategy profile such that, for every i ∈ [n], the i-th agent is assigned to the i-th node.

A BFS tree of a connected graph can be computed in O(|E|). So, σ can be computed in O(|E|+n) = O(|E|). For a node u, let p(u) denote u's parent in T . It is well known that a BFS tree satisfies the following properties: (1) every nontree edge of G only connects nodes of the same level or nodes of two consecutive levels; (2) there cannot be a non-tree edge connecting a node u to a node at the left of p(u). Exploiting these claims, we immediately obtain that σ satisfies the following property (p1): for every agent i not assigned to τ, lσ(i) = σ-1 (p(σ(i))), i.e., the leftmost agent of i is the agent assigned to the parent of the node to which i is assigned; so, for every 1 < i < j, we have lσ(i) ≤ lσ(j).

We now show that σ is a SE. To this end, we prove that for any i ∈ [n], agent i has no incentive in swapping her position with agent j, for every j > i.

Let us first consider agent 1 which is assigned to τ. In this case, we have cost1(σ) = d(rσ(1), 1) = d(deg(τ) + 1, 1). Agent 1 will be interested in swapping with j > 1 only if j is surrounded by agents of index smaller than deg(τ) + 1, which holds only if σ(j) is adjacent to nodes belonging to either level 0 or level 1 of T, i.e., only if σ(j) is either a child or a nephew of τ in T , with no edges (either tree and non-tree ones) towards nodes of level ℓ ≥ 2. If σ(j) is a child of τ, the leftmost neighbor of j does not change after the swap (it is 1), while, as σ(j) is not adjacent to nodes of a level larger than 1, the rightmost neighbor of j does not decrease, which prevents j from swapping. So, σ(j) can only be a nephew of τ. In this case, as σ(j) can only be adjacent to nodes of level 1, the leftmost neighbor of j does not increase after the swap, while the rightmost one does not decrease, again preventing j from swapping. So, agent 1 is not interested in swapping with any other agent.

Now, consider a swap between agent i > 1 and agent j > i. As, by property (p1), lσ(j) ≥ lσ(i), in order for j to be willing to swap, rσ(j) must be such that costj(σ) = d(rσ(j), j) and d(rσ(j), j) > d(j, lσ(i)). Now, as d(rσ(j), j) > d(j, lσ(i)) implies that d(rσ(j), i) > d(i, lσ(i)), in order for i to be willing to swap, rσ(i) must be such that costi(σ) = d(rσ(i), i) and rσ(i) > rσ(j). But this implies that, after the swap, j pays at least d(rσ(i), j) > d(rσ(j), j) = costj(σ) preventing j from swapping. So, agent i is not interested in swapping with any other subsequent agent.

Average Type-Distance Games and Cutoff Games

As stated by Proposition 1, equilibria are not guaranteed to exist for these games in general topologies. For games played on ∆-regular graphs, however, convergence to equilibria is recovered as shown in the following theorems.

Proposition 3. The S-ADG on ∆-regular graphs has the FIP.

Proof Sketch. We show this proposition using a more general version of the ordinal potential function introduced by Chauhan et al. [2018]. Let G be a ∆-regular graph. We define our ordinal potential function as the sum of distances over all edges in the graph according to a given strategy profile σ:

This is an ordinal potential function.

A graph G is almost ∆-regular if every of its nodes has degree in {∆,∆+ 1}. We show that polynomial-time convergence for S-CG is also guaranteed on almost ∆-regular graphs. Note that paths are almost 2-regular graphs.

Proposition 4. The S-CG on almost ∆-regular graphs has the FIP.

Proof Sketch. Let G be an almost ∆-regular graph. Consider the function Φ(σ) = |{u, v} ∈ E : σ-1 (u) ∈ N + σ-1 (v) (σ)}| which counts the number of monochromatic edges, i.e., all edges whose endpoints are occupied by agents who are friends. We prove the claim by showing that Φ is an ordinal potential function. See [Bil`o et al., 2023] for details.

Theorem 2. The convergence time for the S-CG on almost ∆-regular graphs is O(∆n).

Proof. In the proof of Proposition 4 we showed that the function Φ(σ) = |{u, v} ∈ E: σ-1 (u) ∈ N + σ-1 (v) (σ)}| is an ordinal potential function that maps strategy profiles to integer values from 0 to at most (∆ + 1)n. As the potential function increases with every improving swap, there can be at most O(∆n) improving swaps to any equilibrium.

2.2 Jump Games

For jump games, stability is harder to achieve and we can prove positive results mostly only under the HIS variant.

Maximum Type-Distance Games

For these games, the happy-in-isolation assumption makes a huge difference. Using it enables the existence of JE.

Proposition 5. The J-HIS-MDG and the J-UIS-MDG when e is smaller than the minimum degree of G have the FIP.

Proof. The same ordinal potential function as in Proposition 2 works. Note that if an agent i ∈ [n] performs an improving jump from σ, every former neighbor of i does not increase her cost unless we are in the UIS variant and the agent becomes isolated. But this can never happen under the claimed premises. By the arguments presented in the proof of Lemma 1, no new neighbor of i can increase her cost to be at least costi(σ). Because agent i's cost strictly decreases, the potential function lexicographically decreases.

We improve the negative result from Proposition 1 and also complement the above theorem by showing that JE for JUIS-MDGs may not exist even when considering ∆-regular graphs and the number of empty nodes is equal to ∆.

Proposition 6. J-UIS-MDGs and J-UIS-ADGs on ∆-regular graphs may not have JE when e ≥ ∆.

Proof. The following instance works for both J-UIS-MDGs and J-UIS-ADGs. Consider a 5-node ring and three agents of types t1 = 0, t2 = 1/3 and t3 = 1, respectively; so, we have ∆ = e = 2. Consider a strategy profile σ. If agent 3 is isolated in σ, then she can jump on the empty spot adjacent to agent 2 and improve her cost. So, agent 3 cannot be isolated in σ. Let i be an agent adjacent to agent 3 in σ. This agent can jump to an empty spot where she is the only neighbor of agent j /∈ {i, 3}, thus decreasing her cost. So, no JE exists.

For the rest of the section, we shall focus on J-HIS-MDGs. We first observe that a JE can be efficiently computed when the input graph satisfies a topological property.

Theorem 3. A JE for the J-HIS-MDG can be computed in O(|V |k+1 ) time in any graph having K2,e as a subgraph, where k = min{2, e}.

Proof. Let G be a graph having K2,e as a subgraph. So, there are two nodes u and v that are both adjacent to all nodes of a set of nodes S such that |S| = e and S ∩{u, v} = ∅. Let σ be any strategy profile assigning agent 1 to u, agent n to v and leaving empty all nodes in S. Observe that σ is a JE. This is because by jumping to any node in S, an agent would be adjacent to both agents 1 and n paying her largest possible cost. Nodes u and v can be discovered in O(|V |k+1 ) time by guessing all k-tuples of nodes in V and checking in O(|V |) whether their neighborhoods satisfy the required property.

This yields an efficient algorithm for the following cases.

Corollary 1. A JE for the J-HIS-MDG can be computed in O(|V |2 ) time when there is only one empty node.

Proof. Since every connected graph with at least 3 nodes admits a node of degree at least 2, i.e., it contains K2,1, the claim follows by Theorem 3.

Corollary 2. A JE for the J-HIS-MDG on graphs with |V | nodes and ω(|V |3/2 ) edges can be computed in O(|V |3 ) time.

Proof. K˝ov´ari et al. [1954] proved that the densest graph on |V | nodes that does not contain Ks,t as a subgraph has size O(|V |2-1/s ). So, every graph with ω(|V |3/2 ) edges contains K2,e as a subgraph. The claim follows by Theorem 3.

With additional work, we can obtain efficient computation of a JE also for the case of e = 2.

Theorem 4. A JE for the J-HIS-MDG can be computed in O(|V |3 ) when there are only two empty nodes.

Proof. Let G be the graph defining the game. By Theorem 3, the claim follows when G contains the cycle C4. We additionally show that a JE can be computed in O(|V |3 ) time if G admits a path of five nodes. One can easily find a path of 5

nodes in G or say that such a path does not exist in O(|V |3 ) time. Indeed, for every two distinct nodes u and v of G each having at least two neighbors not in {u, v}, there is a path of 5 nodes using u and v as its second and fourth node, respectively, if and only if (i) u and v have a neighbor in common (the third node of the path), (ii) either one of the two nodes has at least 3 neighbors not in {u, v} or the two nodes share only one common neighbor that is not in {u, v}.

Let π = ⟨u1, . . . , u5⟩ be a five-node path in G. We assume wlog that nodes are numbered in such a way that the number of neighbors of u1 not in π is not larger than the number of neighbors of u5 not in π. Define tM = (t(1)+t(n))/2 as the middle point between the two extreme types. Let A- = {i ∈ [n] : ti ≤ tM} and A+ = {i ∈ [n] : ti ≥ tM}. We construct a JE, depending on which of these sets is larger.

Assume that |A+| ≥ |A-|. Let σ be the strategy profile defined as follows: agent n is assigned to u1, agent 1 to u3 and agent n-1 to u5; u2 and u4 are left empty; all remaining neighbors of u1 are filled with agents from |A+| (this is always possible as |A+| ≥ |A-| and u1 has less neighbors than u5 outside π); the remaining agents are randomly placed. We claim that σ is a JE. Clearly, no agent is interested in jumping to u2 as this would yield the largest possible cost. So, an agent i may only be interested in jumping to u4. In this case, i would be adjacent to agents 1 and n - 1. So, to have an improving jump, it must be tn-1 < tn, i must be adjacent to u1 in σ, and i ∈ A-, but this never happens in σ.

If |A+| < |A-|, it suffices swapping agents 1 and n, assigning agent 2 to u3 and filling all remaining neighbors of u1 with agents from |A-|.

If G does not contain C4, then either (i) it is a tree or (ii) it contains only cycles of length three.

If G is a tree, as it cannot have a five-node path, either G is a star or G is a star with one of its leaves being, in turn, the center of a star. In both cases, the assignment in which all agents are isolated is a JE.

If G contains two disjoint cycles of length three, as G is connected, these cycles need to be connected, thus creating a five-node path. If the two cycles are not disjoint, then they may have one or two nodes in common. In the first case, a five-node path arises, in the second one, C4 arises. So, G has exactly one cycle of length three. If two nodes of this cycle have neighbors outside the cycle, then a five-node path arises. So, G can only be a star in which two leaves are adjacent. Leaving empty the center of the star and one of these leaves results in a JE as all agents are isolated.

We show how to efficiently compute equilibria for paths.

Theorem 5. A JE for the J-HIS-MDG on paths can be computed in O(n log n) time.

Proof. Clearly, if the number e of empty nodes satisfies e ≥ n - 1, a strategy profile of social cost equal to zero can be obtained by making every agent isolated. Such a profile is trivially a JE and a social optimum. So, assume that e < n-1.

Let S be a set of e pairs of consecutive agents yielding the largest intervals occurring between the types of two consecutive agents, and let σ be the strategy profile obtained by placing the agents in increasing order along the path and leaving an empty spot between any two agents in S. Clearly, σ can be computed in O(n log n) time. We claim that σ is a JE.

To see this, let us consider an agent i who is willing to jump to an empty node u. By construction, both nodes adjacent to u are occupied by two consecutive agents. Let k and k + 1 be these agents. As i improves by jumping, i is not isolated in σ, and so we have costi(σ) = |t(i) - t(j)|, for some j ∈ {i - 1, i + 1}. Assume that j = i - 1. Since i improves by jumping to u, the types of agents k and k + 1 are closer than t(j) = t(i - 1) to t(i). So, it must be max{k, k + 1} ≥ i + 1 (observe that it may be k = i). We derive costi(σ) = t(i) - t(i-1) > t(k+1)-t(i) ≥ t(k+1)-t(k), (k, k+1) ∈ S and (i-1, i) /∈ S, which implies t(i)-t(i-1) ≤ t(k+1)-t(k), a contradiction. The case j = i + 1 is analogous.

Average Type-Distance Games and Cutoff Games

We show that the JE for J-HIS-MDGs on paths returned by the algorithm defined in the proof of Theorem 5 remains stable also when considering J-HIS-ADGs and J-HIS-CGs.

Theorem 6. A JE for both J-HIS-ADGs and J-HIS-CGs on paths can be computed in O(n log n) time.

3 Quality of Equilibria

In this section, we provide an overview of our results for the PoA and PoS of the considered games. For the former, in particular, we were able to provide a full characterization, while, for the latter, we give results for games played on specific topologies. More details can be found in [Bil`o et al., 2023].

Price of Anarchy. Under a worst-case view, 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. The only exceptions are S-MDGs and SADGs having a PoA in Θ(n) and Θ(n∆), respectively, where ∆ is the maximum degree of the underlying graph.

Price of Stability. For characterizing the PoS, usually, either the FIP or the existence of algorithms computing equilibria with provable approximation guarantees are required. As we have seen in Section 2, this may be either impossible or require quite an effort; nevertheless, these difficulties 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 SCGs. Finally, for games played on unrestricted topologies, we show that the PoS is in Θ(n) for both S-MDGs and JHIS-MDGs and even unbounded for J-UIS-MDGs.

4 Simulation Experiments

We present simulation results to highlight some properties of the obtained equilibria for our model variants.

For our simulations, we consider 8-regular toroidal grid graphs of size 50 × 50 with a total of 2500 nodes and 10000 edges as a residential area. Agent types and starting locations are chosen uniformly at random and are the same if we compare different variants. For simulations of the jump versions, we use 2% uniformly random chosen empty nodes. From the starting location, random improving moves are chosen until an equilibrium is reached. The shown equilibria are representative for all runs. For the jump game, we used the UIS variant, thus, we had no convergence guarantee. However, the simulations always found a JE.

Visualizations of Equilibria. Figure 1 depicts representative sample equilibria for our variants of the swap game. The differences in the equilibria are remarkable. While the SE for the MDG looks very smooth, the SE of the other variants show hard color borders, i.e., they have neighboring agents with large type-difference. This indicates that the segregation strength in the MDG seems to be higher than in the other versions, with the CG having the lowest segregation. We further investigated the equilibria of the CG, in particular the influence of ∆ and λ on the obtained equilibria. See [Bil`o et al., 2023]. Representative sample equilibria for all our variants of the Jump Game are depicted in Figure 2. Here, a marked difference to the Swap Game becomes apparent: the equilibria seem to be less strongly segregated, than their respective counterpart in the Swap Game. This may be due to agents having fewer options to improve since at any time only a few empty cells are available. Moreover, note that in the equilibria the empty cells typically have neighboring agents with large type-difference, rendering these cells less attractive.

QualityMeasures. We now focus on different qualitymeasures to compare the obtained equilibria. For this, we use:

• ADGSC: the social cost of the ADG
• MDGSC: the social cost of the MDG
• # ≤ 1 2 : the number of pairs of neighboring agents with type-difference at most 12 ;
• max d: the maximum neighbor type-difference;
• Steps: the number of steps until convergence.

The results, averaged over 100 runs from randomly chosen initial states, are shown in Table 2. They confirm that the SMDG produces the most segregated equilibria, followed by the S-ADG. Especially the S-MDG yields the lowest cost values in every cost function and on average has 99.79% of edges between agents with type-distance at most 12 . The MDG is also the only model where the maximum type difference between neighbors is significantly below 1. Also, our data indicate that equilibria in swap games are more segregated than the equilibria in jump games.

(b) 8-regular Average Distance Game

(c) 8-regular Cutoff Game

Table 2: Comparison of equilibria of our models. All values are averaged and rounded over 100 runs each.

Discussion. Our experiments shed light on the structural properties of the obtained equilibria. On the one hand, they reveal that the specific choice of cost function can have a strong impact on the obtained states, e.g., that the CG yields very different outcomes compared to the MDG or the ADG, which is not obvious a priori. On the other hand, they also indicate that our model is rather robust with regard to certain kinds of cost functions, i.e., the similar structural results for the MDG and the ADG hint at the fact that varying the involved distance measures might not change the qualitative behavior much. Also, the experiments reveal that more structural properties might be analyzed in future work. E.g., the appearance of "hard borders", i.e., the existence of many pairs of neighboring agents with large type-value difference. Last but not least, such experiments also shed light on the preferences of real-world agents: while all our cost functions model homophily, our plots for the MDG and the ADG resemble segregation patterns that have been observed by sociologists, while the patterns of the CG are different. This reveals what kind of homophilic behavior might be more realistic.

5 Conclusion

In this work, we study game-theoretic models for residential segregation with non-categorical agent types. This allows us to generalize existing models but also to derive novel results.

As a proof of concept, we have considered three very natural variants for the agents' behavior and focused on the most fundamental question: the existence of equilibria. For this, we present many positive results, in particular, we prove that SE in the S-MDG always exist and can be efficiently constructed on all graphs. We complete the picture by providing additional computational hardness results and many tight or almost tight bounds on the PoA and the PoS. Some interesting problems are left open, for example, settling the following:

Conjecture 1. For any Swap Game played on a path, a SE which is also a social optimum can be efficiently computed.

We emphasize that we have just explored a few of the many possible models using continuous type values. Future work could focus on different agent behavior, e.g., employing different norms to compare with. Also, as indicated by our simulations, exploring the relationship between the agents' behavior and the obtained segregation strength seems promising.