Variety-Seeking Jump Games on Graphs

1 Introduction

While analyzing residential segregation, Schelling; Schelling [1969; 1971] imagined a simple scenario in which agents of two different types are randomly assigned to the nodes of a graph representing a city. The agents are allowed to randomly jump to other available locations or swap locations with other agents whenever this increases the fraction of same-type neighbors they have, up to a threshold. Schelling experimentally showed that, in most cases, this random behavior of the agents leads to segregated neighborhoods consisting only of agents of one type. His work inspired researchers in different disciplines to further study this model and generalize it to capture complicated dynamics between agents of different types. Recent work within the multi-agent literature has considered game-theoretic variants in which agents act selfishly rather than randomly by aiming to maximize a utility function. This strategic behavior of the agents defines a game and the objective is to analyze whether equilibria (stable assignments where agents simultaneously achieve the maximum possible utility they can) exist and what properties (related to segregation) they have.

With few exceptions, most of the utility functions that have been proposed and studied over the years can be described as similarity-seeking or homophilic in the sense that agents prefer to be close to other agents of the same type [Bullinger et al., 2022; Bullinger et al., 2021; Chauhan et al., 2018; Echzell et al., 2019; Agarwal et al., 2021; Kanellopoulos et al., 2021]. Such a behavior is well-justified in scenarios where agents aim to form groups that share similar interests or require similar skill sets to complete tasks. On the other hand, however, there many other important applications where the desideratum is diversity. For example, data from the General Social Survey [Smith et al., 2019] (conducted in the US since 1950) show that a steadily increasing percentage of people prefer to live in diverse neighborhoods. In addition, many governments, businesses, and other institutions are actively promoting increased diversity as being beneficial to both societal harmony and efficiency.

Motivated by applications like those mentioned above, some recent papers have considered utility functions which aim to model diversity as being beneficial for the agents. In particular, Bil`o et al. [2022] and Friedrich et al. [2023] studied games with two types of agents and a single-peaked utility function which increases monotonically with the fraction of same-type neighbors in the interval [0,Λ] for some Λ ∈ (0, 1), and then decreases monotonically. A different model was proposed by Kanellopoulos et al. [2023] who focused on a utility function that assigns different weights to different types according to their position on a line, indicating different preferences over the types. More recently, Narayanan et al. [2023] focused on jump games where the utility of an agent is the fraction of its different-type neighbors; essentially, this function is the complement of the one implied by Schelling's original model and used in a plethora of subsequent works.

1.1 Our Contribution

An important aspect of the models studied in the aforementioned papers is that the agents are mainly concerned with the type difference between themselves and their neighbors, and not the difference or diversity among their neighbors. For example, according to the utility function considered by Narayanan et al. [2023], an agent is fully satisfied even if all its neighbors are of one type, as long as this type is different than its own. Whether this is a truly diverse neighborhood is up to debate. In this paper, we study jump games where agents are seeking variety: An agent's utility is defined as the number of types different from its own among its neighbors. Such a utility function was very recently studied for swap games by Li et al. [2025]. With this utility function, the maximum possible utility is the maximum between the number of types and the degree of the underlying graph.

To be more specific, we consider jump games with n agents that are partitioned into k ≥ 2 different types and occupy the nodes of a graph G = (V,E) where |V | < n. Each agent aims to maximize the number of different types in its neighborhood. We first show that such games may have an improving response cycle, even when G is 3-regular and |V | = n+3. This means that there is an initial assignment of the agents to the nodes of the graph so that if the agents jump one by one to empty nodes of the graph, they will eventually cycle back to that initial assignment; in other words, starting from such an assignment, an equilibrium cannot be reached. In spite of this impossibility, we show that the game is potential (that is, the Nash dynamics converges to an equilibrium) under any of the following conditions: k = 2; |V | = n+1; the graph is of degree at most 2; the graph is 3-regular and |V | = n+2. Additionally, we show that there is always an equilibrium when the graph is a tree, or a cylinder, or a torus by carefully constructing one for these cases.

We next switch to analyzing the quality of equilibria under two different objectives: The social welfare (defined as the total utility of the agents) and the number of colorful edges (defined as the number of edges between agents of different types). Both objectives are different measures of diversity and have been considered before by [Li et al., 2025] for the case of swap games. We show tight bounds on the price of anarchy, which quantifies the loss in the social welfare or the number of colorful edges in the worst equilibrium. In particular, we show that the price of anarchy with respect to social welfare is Θ(n) for general games, and Θ(k) for symmetric types (that is, when all types are of the same cardinality). For colorful edges, we show that the price of anarchy is Θ(n) even for symmetric types, and Θ(δ) when the graph is δ-regular and the types are symmetric. In addition, for both objectives, we provide lower bounds on the price of stability, showing that there are instances in which the optimal assignment is not necessarily an equilibrium.

1.2 RelatedWork

As already mentioned, many generalizations and variations of Schelling's random model have been studied via agentbased simulations in many different disciplines, including sociology [Clark and Fossett, 2008], economics [Pancs and Vriend, 2007; Zhang, 2004], and physics [Vinkovi´c and Kirman, 2006]. In computer science, most of the work has focused on probabilistic analyses of Schelling's model [Barmpalias et al., 2014; Bhakta et al., 2014; Brandt et al., 2012; Immorlica et al., 2017; Bl¨asius et al., 2023] and also on the computational complexity of assignments with certain efficiency properties [Bullinger et al., 2021; Deligkas et al., 2024].

Our work is related to a recent stream of papers that consider Schelling games induced when the agents do not act randomly but strategically by maximizing a utility function. The majority of papers in this literature study jump and swap games with similarity-seeking utility functions that one way or another depend on the ratio of same-type agents in the neighborhood, and consider questions related to the existence of equilibria, their computational complexity, and their quality as measured by the price of anarchy and the price of stability. Some of the first papers in this area include the works of Chauhan et al. [2018] and Echzell et al. [2019] who studied the convergence of the best response dynamics to equilibrium assignments, and the work of Agarwal et al. [2021] who showed that equilibria may not always exist and, even when they do, they might be hard to compute. Much of the follow-up work provided stronger hardness results [Kreisel et al., 2024], studied different utility functions aiming to model other natural agent behaviors [Kanellopoulos et al., 2021; Bil`o et al., 2022], and made different assumptions about how agents are related to each other [Bil`o et al., 2023; Chan et al., 2020]

Some recent work on Schelling games has deviated from the standard assumption that agents aim to be close to their own type and have proposed different models in which the agents derive utility from other types of agents as well [Bil`o et al., 2022; Friedrich et al., 2023; Kanellopoulos et al., 2023; Narayanan et al., 2023; Li et al., 2025]. The paper most related to ours is that of [Li et al., 2025] who studied swap games with several different diversity-seeking utility functions, including the one we consider here, that is the number of different types in an agent's neighborhood. Among other results, in contrast to our work here where we show that there might exist improving response cycles, they showed that swap games are always potential no matter the structure of the underlying graph. They also showed tight bounds on the price of anarchy for objectives such as the number of colorful edges that we also consider, as well as some other ones. Most of their bounds indicate that the price of anarchy depends on the degree of the graph and in many case tends to 1 as the number of agents n or the number of types k grows; in contrast, our price of anarchy bounds suggest a linear dependency on n or k in most cases.

2 Preliminaries

There is a set N of n ≥ 2 agents who are partitioned into k ≥ 2 types T = {T1, . . . , Tk}. We denote by t(i) the type of agent i; that is, t(i) = T if i ∈ T. We denote by nT the number of agents of type T; if nT = n/k for each type T, then the types are called symmetric. Each agent i occupies a node of a connected graph G = (V,E) with |V | > n. An assignment v = (vi)i∈N specifies the node vi that each agent i occupies in G, such that vi ̸= vj for different agents i and j. Given an assignment v, we denote by Ni(v) the neighbors of i, which is the set of all agents that occupy nodes adjacent to vi in G. Also, for any node v ∈ V and assignment v, we denote by Tv(v) the set of agent types located at nodes adjacent to v. Given this, the type-count of node v is τv(v) = |Tv(v)|. Depending on the formation of its neighborhood, each agent i gains a utility ui(v) equal to the number of types different than t(i) in i's neighborhood.

An assignment v is a pure Nash equilibrium (or, simply, equilibrium) if no agent can strictly increase its utility by unilaterally jumping to an empty node in the graph. That is, for every agent i and empty node v (according to v), ui(v) ≥ ui(v′ ), where v′ is the same as v with the only exception that v′i = v. For an instance I = (N, T ,G), let NE(I) be the set of equilibrium assignments; note that this set might be empty.

We are interested in characterizing the classes of graphs for which equilibrium assignments are guaranteed to exist. To do so, we will in many cases show that the best-response Nash dynamics converges to an equilibrium by identifying an ordinal potential function Φ(v). Such a function has the following property: For any two assignments v and v′ that differ only on the node occupied by an agent i, it holds that

Essentially, this property requires that the function is strictly increasing whenever there is an agent with a deviating strategy that leads to strictly larger utility. Note that a strictly decreasing function can be also used as a potential since its monotonicity can be switched by changing its sign. A potential function can be defined only if there is no improving response cycle (IRC) in the Nash dynamics (that is, a sequence of assignments in which the first and last assignments are the same, and two consecutive assignments differ only on the node occupied by an agent who has larger utility in the latter assignment of the two).

When equilibrium assignments exist, we are also interested in measuring their quality in terms of achieved diversity. To do this, we consider two objective functions:

• The social welfare (SW), defined as the total utility of the agents:

• The number of colorful edges (CE) which is the number of edges whose endpoints are occupied by agents of different types.

For each objective g ∈ {SW, CE}, we define the price of anarchy as the worst-case ratio (over a class of instances I) between the maximum possible g-value over all possible assignments and the minimum g-value over all equilibrium assignments:

3 Existence of Equilibria

In this section we focus the existence of equilibrium assignments. We first start with an impossibility: There exists a game with an improving response cycle in its Nash dynamics. This implies that the jump game we consider is not always a potential game, and thus the existence of an equilibrium assignment cannot be shown by constructing a potential function.

Theorem 1. There exists a game with an improving response cycle in the Nash dynamics, even when the graph is 3-regular and there are three empty nodes.

Proof. Consider the improving response cycle shown in Figure 1. In the first assignment in the left column, the red agent occupying node a has utility 1 (as it only has blue neighbors) and prefers to jump to node d to improve its utility to 2. This leads to the second assignment in the left column where the blue agent at node b has now utility 1 (as it only has green neighbors) and incentive to jump to node e to increase its utility to 2. This leads to the third assignment in the left column where the green agent at node c has utility 1 (as it only has red neighbors) and incentive to jump to node f to increase its utility to 2. This leads to the third assignment in the right column where the red agent at node d has utility 1 again, and would now prefer to jump back to node a where it can get utility 2. This leads to the second assignment in the right column where the blue agent at node e has utility 1 and would also now prefer to go back to node b to get utility 2. This leads to the first assignment in the right column where the green agent at node f has been left with only red neighbors and now has incentive to jump to node c again to get utility 2, thus completing the cycle.

Next, we identify several cases where the game is indeed potential, and thus there is always at least one equilibrium assignment. In particular, we show that this is true when (1) there are only two types of agents, (2) there is a single empty node, (3) the graph is of degree at most 2, and (4) there are two empty nodes and the graph is 3-regular.

Theorem 2. The game is potential when there are only two types of agents.

Proof. We argue that the social welfare (the total utility of the agents) is a potential function. Observe that, if some agent i jumps to an empty node, then it does so because its utility increases from 0 to 1. Since i has only neighbors of its own type (so that its utility is 0) in the initial assignment, the jump/deviation of i does not alter the utility of those agents. In addition, the utility of each of i's new neighbors in the new assignment does not decrease in comparison to how much it was before; in particular, it either remains the same or increases from 0 to 1. Hence, the social welfare overall increases by at least 1 after i jumps, and is thus a potential function, leading to an equilibriumwhen it is maximized.

Theorem 3. The game is potential when the graph contains just one empty node.

Proof. We will prove by induction that, for every ℓ ∈ [k], there is no IRC containing an assignment v in which the empty node, say u, has agents of ℓ different types surrounding it, that is, τu(v) = ℓ. Consequently, no IRC can exist in the Nash dynamics, thus showing that the game is potential.

Base case: ℓ = 1. Suppose for the purpose of contradiction that there exists an IRC containing an assignment v, in which |Tu(v)| = 1 for the empty node u. Without loss of generality, suppose all the agents adjacent to u are of type R. Consider the next assignment v′ in the IRC, and suppose agent i is located at node u in v′ . Let v be the node that i occupies in v; that is, agent i jumps from node v to node u, implying that ui(v′ ) > ui(v). Note that v is the empty node in the assignment v′ .

Agent i cannot be of type R since it gets utility 1 after jumping to u, and it must have had utility 0 by occupying v in assignment v. If i had no neighbors in the assignment v, then the only neighbor of v in the graph is u, the empty node, but then u has neighbors of two types, a contradiction. Therefore, agent i must have had only neighbors of its own type when occupying v in v. So, i was segregated in the assignment v and |Tv(v′ )| = 1. Applying the same argument again, it follows that every assignment in the IRC has an empty node in which all neighboring agents are of the same type, and every jump is made by a segregated agent. Notice however, that each such jump reduces the number of segregated agents, leading to a contradiction.

Induction hypothesis: Assume there is no IRC containing an assignment where the empty node has neighbors of p different types, for all p ∈ [ℓ] for some ℓ < k.

Induction step: We will show that the hypothesis remains true for ℓ+1. Suppose instead that there is an IRC containing an assignment v where the empty node u has neighbors of exactly ℓ +1 types, that is, τu(v) = ℓ +1. Consider the next assignment v′ in the IRC that is the result of agent i jumping from node v to u. Then, the empty node in v′ is v and, by the inductive hypothesis, τv(v′ ) > ℓ. Consider the following three cases:

• t(i) ∈ Tu(v). Then ui(v′ ) = ℓ and ui(v) ≥ ℓ, which contradicts the fact that i is motivated to jump.
• t(i) ̸∈ Tu(v) and t(i) ̸∈ Tv(v). Then ui(v′ ) = ℓ+1 and ui(v) > ℓ, which contradicts the fact that i is motivated to jump.
• t(i) ̸∈ Tu(v) and t(i) ∈ Tv(v). Then ui(v′ ) = ℓ + 1, and ui(v) ≥ ℓ. For i to be motivated to jump, it must be that ui(v) = ℓ. Since t(i) ∈ Tv(v), this implies that

τv(v′ ) = ℓ + 1. In other words, the empty node v in assignment v′ has ℓ + 1 types in its neighborhood.

From the above we see that the number of monochromatic edges in v′ is less than that in v. Applying the same argument repeatedly, it follows that for every assignment in the IRC, (a) the empty node has ℓ + 1 types in its neighborhood, and (b) the agent that deviates has at least one neighbor of its own type in its neighborhood, but no neighbors of its type at the empty node it jumps to, causing the number of monochromatic edges to decrease in successive assignments, which contradictions the existence of the IRC.

Theorem 4. The game is potential when the graph is of degree at most 2.

Proof. For any assignment v, recall that CE(v) is the number of colorful edges that connect agents of different types. In addition, let c(v) be the number of empty nodes that are adjacent to at most one type of agents, that is c(v) = |{v ∈ V : v empty in v and τv(v) ≤ 1|}. We will show that the function Φ(v) = 2 · CE(v) + c(v) is a potential one.

We will focus on two assignments v and v′ that differ on the node occupied by a single red agent i. In particular, agent i occupies a source node s in v and jumps to a destination node d in v′ . Note that d is empty in v and s is empty in v′ . We will show that ∆Φ = Φ(v′ ) - Φ(v) > 0 when ui(v′ ) > ui(v). For simplicity, further define ∆CE = CE(v′ )-CE(v) and ∆c = c(v′ )-c(v). We consider the following two cases depending on the utility that agent i derives in assignment v.

Case 1: ui(v) = 0. Since i has only neighbors of its own type or no neighbors at all, the source node s it occupies does not participate in any colorful edges. Since i jumps from s to d to increase its utility, d must be adjacent to at least one non-red agent. Hence, the number of colorful edges increases by at least 1 when i jumps, and thus ∆CE ≥ 1. In v′ , node s is empty and is surrounded by at most one type of agents. Hence, ∆c may increase by 1 due to s. If d is surrounded by only one type of agents in v, then ∆c may decrease by 1. Since the graph is of degree at most 2 and d is adjacent to a non-red agent, d may be adjacent to at most one empty node, say v, and ∆c might further decrease by 1 due to v (when i becomes adjacent to v by jumping to d). Overall, ∆c ≥ -1, and thus ∆Φ = 2∆CE + ∆c ≥ 1.

Case 2: ui(v) = 1. In this case, the node d where i jumps to from s must be adjacent to two agents of different types, say blue and green. This further implies that d is not adjacent to s.

• If i has only one non-red neighbor in v, then there will be one more colorful edge in v′ , and thus ∆CE = 1. Now observe that ∆c is not affected due to d since it is adjacent to a blue and a green agent in v where it is empty. Due to s, ∆c might increase by 1 in case s is adjacent to a non-red agent only, or not at all in case s is adjacent to a red and a non-red agent. So, overall, ∆c ≥ 0, and ∆Φ = 2∆CE + ∆c ≥ 2.
• Otherwise, i has two non-red neighbors of the same type in v. Hence, there is no change in the number of colorful edges when i jumps from s to d, that is, ∆CE = 0.

Similarly to before, there is no change in ∆c due to d, but there is an increase of 1 in ∆c due to s, and thus ∆c = 1. Overall, ∆Φ = 2∆CE + ∆c = 1.

This completes the proof.

Theorem 5. The game is potential when the graph has two empty nodes and is 3-regular.

Proof Sketch. For any assignment v, let TE(v) = τv1 (v) + τv2 (v) be the total type-count of the two empty nodes v1 and v2. Also, let M(v) be the number of monochromatic edges in v, and

We show that the function Φ(v) = 2(TE(v)+M(v))+B(v) is a potential one. In particular, we show that it decreases any time an agent jumps. The proof is based on a case analysis of the location of the source and destination nodes of the jumping agent.

Next we show that that even when there is an arbitrary number of empty nodes, an equilibrium assignment is guaranteed to exist for some families of graphs, in particular, for trees, cylinder graphs, and tori. For these cases, we explicitly construct an equilibrium rather than showing that the game is potential. In fact, recall that the graph in the game used to show that there is an IRC in the proof of Theorem 1 is a cylinder, and thus constructing a potential function for such graphs is not possible.

The assignment we construct for these graph classes will have one of the following two properties:

• (P1) ui(v) ≥ 1 for every agent i, and τu(v) ≤ 1 for any empty node u.
• (P0) All empty nodes are adjacent only to red agents or other empty nodes, and ui(v) ≥ 1 for every non-red agent i.

Clearly, an assignment v satisfying (P1) is an equilibrium assignment as no agent is motivated to jump. Suppose v satisfies (P0). Notice that there may be red agents with utility 0, but they cannot increase their utility by jumping to an empty node. Any non-red agent can only get utility 1 by jumping to an empty node, since it already has utility 1, does not have incentive to to jump. Due to space limitations, the full proofs of the following three theorems are omitted.

Theorem6. There exists an equilibriumassignment when the graph is a tree.

Theorem7. There exists an equilibriumassignment when the graph is a cylinder.

Theorem8. There exists an equilibriumassignment when the graph is a torus.

4 Quality of Equilibria

In this section we focus on the diversity quality of equilibria as measured by the social welfare (the total utility of all agents) and the number of colorful edges between agents of different types. In particular, we show tight bounds on the price of anarchy with respect to both of these objective functions.

4.1 Price of Anarchy: Social Welfare

We start by showing an upper bound on the price of anarchy which holds for any class of graphs and is a function of the number of agents n and the maximum cardinality over all types.

Theorem 9. The price of anarchy with respect to the social welfare is exactly n(k - 1)/(n - maxT nT + 1).

Proof. For the upper bound, consider an arbitrary equilibrium assignment v and let v be an empty node that is adjacent to an agent of some type R. All agents of type different than R must have utility at least 1 to not have incentive to jump to v. In addition, at least one agent of type R must be adjacent to an agent of a different type; otherwise, since the graph is connected, there would be an empty node (possibly v) that is adjacent to an agent of type different than R where agents of type R would have incentive to jump. Therefore, the social welfare at equilibrium is

Since the optimal social welfare is at most n(k-1), the price of anarchy is at most n(k-1) n-maxT nT +1 .

For the lower bound, consider a game with k ≥ 2 types {T1, . . . , Tk}. Let R := T1 be the type with the most agents. The graph consists of the following components:

• A clique Kn of size n;
• A line ℓT of size nT for each type T.

The components are connected as follows: A node of Kn is connected to a node of ℓR. For each t ∈ {2, . . . , k - 1}, all but the last node of ℓTt are connected to the last node of ℓTt-1 . All the nodes of ℓTk are connected to the last node of ℓTk-1 ; See Figure 2 for an example for k = 3.

The optimal assignment is for the agents to occupy all the nodes of the Kn component, which leads to a utility of k - 1 for each of them, and a social welfare of n(k-1). A different equilibrium assignment is the following: For each type T , the agents of type T occupy the nodes of line ℓT . Since all agents of type T ̸= R have utility 1, none of them wants to jump to any of the empty nodes; in particular, there is only one node that is adjacent to an agent occupied by a single agent of type R. The social welfare of this equilibrium is n-nR +1 (note that the agent of type R that occupies the last node of ℓR also has utility 1), and thus the price of anarchy is at least n(k-1) n-nR+1 .

Using Theorem 9, we can derive many asymptotically tight bounds on the price of anarchy with respect to the social welfare, for example by considering games in which the types might be asymmetric or symmetric.

Corollary 10. The price of anarchy with respect to the social welfare is Θ(n) in general, and Θ(k) for symmetric types.

Proof. For asymmetric types, since each of the k types has cardinality at least 1, maxT nT ≤ n - k + 1, and thus the price of anarchy is at most

By setting nR = n-k+1 and nT = 1 for T ̸= R in the lower bound construction of Theorem 9, we get an asymptotically tight lower bound that is linear in the number of agents.

For symmetric types, nT = n/k for each type T, and thus the price of anarchy is at most

By setting nT = n/k for each type T in the lower bound construction of Theorem 9, we get an asymptotically tight lower bound that is linear in the number of types.

The previous statements show that the price of anarchy can be high in general graphs, even when the types are symmetric. However, in simple graphs, such as lines and cycles, the price of anarchy is much smaller.

Theorem 11. When the types are symmetric and the graph is of degree at most 2, the price of anarchy with respect to the social welfare is 4/3 for k = 2 and 2k k-1 for k ≥ 3.

4.2 Price of Anarchy: Colorful Edges

We now turn our attention to the second objective, the number of colorful edges. We first show a lower bound on the number of colorful edges achieved in any equilibrium; this lemma will be used in several proofs in the following for showing upper bounds on the price of anarchy.

Lemma 12. The number of colorful edges in any equilibrium is at least (n-maxT nT )/2.

Proof. Consider an arbitrary equilibrium assignment v and let v be an empty node that is adjacent to an agent of some type R. All agents of type different than R must have at least one neighbor of different type than their own to not have incentive to jump to v. Since a colorful edge connects two agents of different type, the number of colorful edges in v is at least (n-nR)/2 ≥ (n-maxT nT )/2.

Now we are ready to show that the price of anarchy with respect to the number of colorful edges is linear in the number of agents, even when the types have the same exact cardinality.

Theorem 13. The price of anarchy with respect to the number of colorful edges is Θ(n), even when the types are symmetric.

Proof. For the upper bound, observe that the maximum number of colorful edges would be achieved if all agents were to be connected to all agents of different type than their own. Hence, the optimal number of colorful edges is at most the number of edges between all agents minus the number of edges between all agents of the same type. Since n = ∑T nT > maxT nT , we have the following upper bound:

So, by Lemma 12, the price of anarchy is at most n + maxT nT ≤ 2n.

For the lower bound, consider a game with k ≥ 2 types {T1, . . . , Tk} consisting of n/k agents each, and assume that n/k is an even number. The graph consists of the following components: A clique Kn of size n, and w cycle cn of size n. The components are connected as follows: A node of Kn is connected to a node of cn. See Figure 3 for an example for k = 3.

The optimal assignment is for the agents to occupy all the nodes of the Kn component, which leads to the maximum possible number of colorful edges equal to

Now consider the following equilibrium assignment according to which the agents occupy the nodes of the cn component such that each agent has a neighbor of the same type and a neighbors of different type. As all agents have utility 1, no agent has incentive to jump to the empty node of Kn that is adjacent to a node of cn. The number of colorful edges of this equilibrium is exactly equal to n/2, leading to a price of anarchy lower bound of n/2.

We next focus again on the case of symmetric types and specific classes of graphs including lines, cycles, and also regular graphs.

Theorem 14. When the types are symmetric and the graph is of degree at most 2, the price of anarchy with respect to the number of colorful edges is 2 when k = 2 and 2k k-1 when k ≥ 3.

Theorem 15. When the types are symmetric and the graph is δ-regular, the price of anarchy with respect to the number of colorful edges is Θ(δ).

Proof. For the upper bound, observe that the maximum number of colorful edges is nδ/2 since each agent can have at most δ neighbors and can thus participate in at most δ colorful edges. Also, by Lemma 12, since maxT nT = n/k, there are at least n2 k-1 k ≥ n/4 colorful edges in an equilibrium, thus leading to an upper bound of 2δ on the price of anarchy.

For the lower bound, consider a game with k ≥ 2 symmetric types {T1, . . . , Tk}, and δ = n/k + 1. The graph consists of the following components:

• A cycle c of size k consisting of nodes {v1, . . . , vk};
• k cliques (Kℓ)ℓ∈[k] of size n/k + 1 each.

The components are connected to each other as follows: For each ℓ ∈ [k], node vℓ is connected to all but two nodes of clique K(ℓ+1) mod k. Observe that this is indeed a δ-regular graph: Each node vℓ of the cycle c has degree 2+n/k-1 = δ, and each node of a clique Kℓ has degree 1 + n/k = δ.

An equilibrium is the following: For each ℓ ∈ [k], node vℓ is occupied by an agent of type Tℓ and the n/k - 1 nodes of clique K(ℓ+1) mod k that are adjacent to vℓ are occupied by agents of type T(ℓ+1) mod k; the remaining two nodes of each clique are left empty. See also Figure 4 for an example with k = 3. This is an equilibrium assignment as all agents have utility at least 1 and each empty node is adjacent to only agents of one type. The only colorful edges in this assignment are those connecting the nodes of c to each other and to nodes in the cliques. So, there are k +k(δ -2) = k(δ -1) colorful edges in this equilibrium. On the other hand, in the optimal assignment, we can assign to each clique, one agent of every type, so that each agent has exactly k - 1 neighbors, all of different types, leading to k δ(δ-1) 2 colorful edges. So, the price of anarchy is Ω(δ).

4.3 Price of Stability

We conclude with a lower bound of approximately 3/2 on the price of stability for both objectives. This implies that there are games in which the optimal assignment is not an equilibrium (in contrast to the games considered in the lower bounds on the price of anarchy). The proof follows by a game with four asymmetric types such that there are x red, one blue, one green, and one yellow agents. The graph is such that the optimal assignment (for any of the two objectives) is to connect each red agent to all non-red agents. However, this is only possible when one of the non-red agents has only red neighbors, and there is an empty node where it can jump and connect to the other two non-red agents, implying that the optimal assignment is not an equilibrium. By case analysis of the possible equilibria, we show the desired bound on the price of stability.

Theorem 16. The price of stability with respect to the social welfare and the number of colorful edges is at least 3/2 - ε, for any ε > 0.

5 Conclusion and Open Problems

In this paper we considered a variety-seeking jump game in which agents occupy the nodes of a graph and aim to maximize the number of different types in their neighborhood. We showed the existence of equilibrium assignments for many classes of games depending on the number of agents and their types, as well as the structure of the graph. We also showed tight bounds on the price of anarchy with respect to the social welfare and the number of colorful edges, both of which measure in different ways the achieved diversity of equilibrium assignments.

Our work leaves open several interesting, yet quite challenging questions. While we have shown that equilibrium assignments exist for several classes of games, it remains unknown whether such assignments always exist or if there are games that do not admit any equilibrium. We conjecture that there is always at least one equilibrium and the game is potential when there are only two empty nodes (without any further restrictions on the structure of the underlying graph). Preliminary experiments using random graphs strongly support the latter claim; improving response cycles were found only when there were at least three empty nodes. A formal proof of this, however, remains elusive.

In terms of measuring the diversity of equilibria, while we showed tight bounds on the price of anarchy in terms of the social welfare and the number of colorful edges, we were not able to show tight bounds on the price of stability. One could also consider many other objective functions to measure diversity, such as the degree of integration or variations of it [Agarwal et al., 2021].