# strategic_resource_selection_with_homophilic_agents__5d7f0d3c.pdf

Strategic Resource Selection with Homophilic Agents

Jonathan Gadea Harder1 , Simon Krogmann1 , Pascal Lenzner1 and Alexander Skopalik2

1Hasso Plattner Institute, University of Potsdam 2Mathematics of Operations Research, University of Twente {jonathan.gadeaharder, simon.krogmann, pascal.lenzner}@hpi.de, a.skopalik@utwente.nl

The strategic selection of resources by selfish agents is a classic research direction, with Resource Selection Games and Congestion Games as prominent examples. In these games, agents select available resources and their utility then depends on the number of agents using the same resources. This implies that there is no distinction between the agents, i.e., they are anonymous. We depart from this very general setting by proposing Resource Selection Games with heterogeneous agents that strive for joint resource usage with similar agents. So, instead of the number of other users of a given resource, our model considers agents with different types and the decisive feature is the fraction of same-type agents among the users. More precisely, similarly to Schelling Games, there is a tolerance threshold τ [0, 1] which specifies the agents desired minimum fraction of sametype agents on a resource. Agents strive to select resources where at least a τ-fraction of those resources users have the same type as themselves. For τ = 1, our model generalizes Hedonic Diversity Games with a peak at 1. For our general model, we consider the existence and quality of equilibria and the complexity of maximizing social welfare. Additionally, we consider a bounded rationality model, where agents can only estimate the utility of a resource, since they only know the fraction of same-type agents on a given resource, but not the exact numbers. Thus, they cannot know the impact a strategy change would have on a target resource. Interestingly, we show that this type of bounded rationality yields favorable game-theoretic properties and specific equilibria closely approximate equilibria of the full knowledge setting.

1 Introduction

Selecting resources in a multi-agent setting is a longestablished field of study in Artificial Intelligence, Operations Research, and Theoretical Computer Science. Resources can

be as diverse as compute servers or printers, facilities like hospitals, universities, high schools or kindergartens, office rooms, restaurants or pubs, or driving routes to the workplace. The main common feature of all such resources typically is that the utility of the agents selecting them depends on the resource selections of all other agents. For almost all resources, the utility of an agent depends on the number of other agents that chose to select the same resource as the agent. However, if the utility only depends on the number of agents that use a resource, this implies that the agents are indifferent to whom they are sharing their selected resource with. While this is a natural assumption in some settings, e.g., for jobs on a compute server or for customers of a gas station, there are many scenarios where real-world agents have more complex preferences. One prime example of this is the phenomenon of residential segregation [Massey and Denton, 1988]. There, the agents are residents of a city that select a place to live. Typically, real-world residents are not indifferent to who else lives in their neighborhood, but instead prefer at least a certain fraction of neighbors of the same ethnic group or socioeconomic status. This behavior is commonly called homophily and it is seen as the driving force behind the strongly segregated neighborhoods, i.e., regions where similar people live, that can be observed in most major cities. A classic way to model homophilic agents is to assume that agents have different types and that they strive for having at least a τ-fraction of same-type agents sharing their selected resource. In terms of residential segregation, this is captured by Schelling s seminal agent-based model [Schelling, 1971]. In this paper, we present and investigate a general model for strategic resource selection by a set of heterogeneous agents with homophilic preferences. For this, we incorporate Schelling s idea of threshold-based agent preferences into the classic setting of Resource Selection Games, where a set of resources is given and agents each can access a subset of them. Now, instead of selecting a resource with few users, an agent aims for selecting a resource that is shared at least with a τ-fraction of users that have the same type as the agent. We believe that this adds an important new dimension to classic agent-based resource selection problems. For example, our model allows us to investigate strategic school choice, where families of different ethnic groups that are located within a city select nearby schools for their children. Each family can select a subset of the available schools, typ-

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (IJCAI-23)

ically schools that are in their neighborhood, but they want to ensure that their children have a certain fraction of fellow pupils of their own ethnic group.1 Another example, is the choice of pubs that supporters of different sports teams select for watching the next match. For enjoying the match with friends, each supporter aims for patronizing a pub with a least a certain fraction of like-minded fans.

1.1 Model and Notation

We consider a strategic game, called the Schelling Resource Selection Game (SRSG), defined by a given bipartite accessibility graph G = (Q A, E), with Q A = , where Q is the set of resources and A is the set of agents that want to use the resources at the same time. Let |Q| = k, |A| = n, and |E| = m. An edge {q, a} E, with q Q and a A encodes that agent a has access to resource q, i.e., resource q is accessible for agent a. We use qa as shorthand for {q, a}. See Figure 1 for an illustration. Most importantly for our paper, we assume that the society of agents is heterogeneous, in particular, that we have two2 types of agents that we distinguish by the colors red and blue. We have A = R B, where R is the set of 0 < r < n many red agents and B is the set of b = n r many blue agents. We assume that all resources are identical in quality. Agents strategically select a single accessible resource to use, i.e., they each choose a single incident edge of G. We consider homophilic agents, i.e., agents that favor a joint resource usage with other agents of the same type, if there are other agents using the same resource at all. In particular, analogously to Schelling s model for residential segregation [Schelling, 1971], we assume a global tolerance threshold τ [0, 1] for all the agents, that defines the minimum fraction of same-type agents that an agent seeks when using a resource. More formally, let a A be any agent and let X(a) Q denote the set of accessible resources for agent a, i.e., we have X(a) = {q Q | qa E}. Similarly, we define Y (q) = {a A | qa E} for all q Q. Each agent a selects a resource s(a) X(a) and we say that s(a) is agent a s strategy. The strategy profile s = (s(a1), . . . , s(an)), with ai A and s(ai) X(ai), for 1 i n, then denotes the vector of strategies of all agents. For a strategy profile s and a resource q, we denote #(q, s) = |{a A | s(a) = q}| as the number of agents that jointly use q under s. Moreover, let #R(q, s) = |{a R | s(a) = q}| denote the number of red agents that use resource q under s. Analogously, #B(q, s) = #(q, s) #R(q, s) is the number of blue agents using resource q under s. Also, let

ρR(q, s) = #R(q, s)

#(q, s) and ρB(q, s) = #B(q, s)

denote the fraction of red and blue agents, respectively, that use resource q under strategy profile s. Note that these fractions are undefined if no agent uses q under s.

1Schools are more segregated than their neighborhoods [Burgess et al., 2005], i.e., families actively select schools where the own ethnic group has a high presence [Hailey, 2022]. 2For more types of agents, Theorems 1, 4 and 8 to 11 still hold.

The utility of agent a under strategy profile s is defined as

u(a, s) = min{ρR(s(a), s), τ}, if a is red, and min{ρB(s(a), s), τ}, if a is blue. Thus, agents are striving for using a resource in a group of same-type agents that represents at least a τ-fraction of all users of that resource.3 Note that u(a, s) is monotonically increasing in the fraction of same-type agents using the same resource. Also, if at least a τ-fraction of same-type agents use resource q, then all of these agents have maximum utility.4 Given a strategy profile s with s(ai) = q, we use the shorthand s = (q, s i), where vector s i = (s(a1), . . . , s(ai 1), s(ai+1), . . . , s(an)) is identical to the vector s without the i-th entry. Regarding strategy changes, we will consider two variants: impact-blind improving moves and impact-aware improving moves. Let s = (q , s i) denote a strategy profile that is identical to s except for the i-th entry, i.e., s(aj) = s (aj) for i = j and s(ai) = s (ai), with s (ai) = q . We say that the strategy change of agent ai from strategy q to strategy q that leads from s to s is an impactaware improving move if u(ai, (q , s i)) > u(ai, (q, s i)). The same strategy change is an impact-blind improving move, if min{ρR(q , s), τ} > u(ai, s) and ai is red, or if min{ρB(q , s), τ} > u(ai, s) and ai is blue. Since ρR(q , s) and ρB(q , s) are undefined for #(q , s) = 0, we say that switching to an empty resource is also an impact-blind improving move for an agent ai, if u(ai, s) < τ. We call such an improving move impact-blind, since agent ai only compares her utility with the fraction of same-type agents on resource q , prior to moving to resource q . This models that agent ai has limited information about resource q , that is, she does not know #(q , s i) exactly, but only knows the fraction of agents of her type on q before the move. Hence, agent ai cannot estimate the exact fraction of same-type agents using resource q after she joins resource q , i.e., under strategy profile s . She only knows that her joining resource q does not decrease this fraction of same-type agents. Based on impact-aware and impact-blind improving moves, we define two solution concepts for our strategic game. We say that s is in impact-aware equilibrium (IAE) if no agent has an impact-aware improving move. Analogously, strategy profile s is in impact-blind equilibrium (IBE) if no agent has an impact-blind improving move. Slightly abusing notation, we will use IAE and IBE also for denoting the sets of strategy profiles that are in IAE or IBE, respectively. Since u(ai, (q , s i)) min{ρR(q , s), τ} if ai is red or u(ai, (q , s i)) min{ρB(q , s), τ} if ai is blue, every impact-blind improving move also is an impact-aware improving move, i.e., every strategy profile in IAE also is in IBE. However, the converse does not hold.5 Moreover, we will also consider approximate equilibria. A β-approximate IAE is a strategy profile where no agent has an impact-aware improving move that yields β times her current utility.

3Using a resource alone gives a fraction of same-type agents of 1. 4Capping the utility at τ is a technical assumption that allows for more elegant proofs. All our results also hold if the utility is normalized to be 1 if the fraction of same-type agents is at least τ. 5Counterexample: Let two resources be used by exactly one red and one blue agent each.

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (IJCAI-23)

(a) Social optimum. Neither impact-aware nor impact-blind equilibrium.

(b) Impact-aware equilibrium. Not socially optimal.

(c) Impact-blind equilibrium but no impact-aware equilibrium.

Figure 1: Example instance of our model with three strategy profiles. The instance has two resources q1 and q2 (shown as circles, with their color fractions shown as pie charts), four red agents, and four blue agents, each shown as squares of the respective color. Moreover, we assume τ = 3

5. Accessibility is shown via edges, thick black edges show the chosen resource of the respective agent. The fractions below the squares show the utilities of the agents. (a) shows the social optimum strategy profile with a social welfare of 62

15 > 4.1. It is neither an IAE nor an IBE, since the blue agent highlighted in green can increase her utility from 2

5 by selecting resource q1 instead of q2. (b) shows an IAE. Since it has social welfare of 4.1 it is not socially optimal. (c) depicts an IBE with social welfare of 4. It is not an IAE, since changing to the respective other resource is an impact-aware improving move for all the green highlighted agents.

The social welfare of a strategy profile s, denoted by W(s), is defined as W(s) = Pn i=1 u(ai, s), i.e., as the sum of all the agents utilities. For a given graph G, let OPTG, called social optimum, denote a strategy profile that maximizes the social welfare for G. Using the social welfare, we now define our measure for the quality of equilibria. For a graph G, let max IAE(G) and min IAE(G) be the strategy profiles in IAE for G with maximum and minimum social welfare, respectively. Analogously, we define max IBE(G) and min IBE(G) for IBE. Then the Price of Anarchy with respect to the IAE, IAE-Po A for short, is defined as max G{ W (OPTG)

min IAE(G)}. The Price of Stability with respect to the IAE, IAE-Po S for short, is defined as max G{ W (OPTG)

max IAE(G)}. For the IBE, we define the IBE-Po A and the IBE-Po S analogously. Regarding the game dynamics, if the agents only perform impact-aware improving moves, then we call this impactaware dynamics. Analogously, in impact-blind dynamics only impact-blind improving moves occur. If starting from every strategy profile every sequence of impact-aware (impact-blind) improving moves is finite, then we say that the impact-aware (impact-blind) finite improvement property, short IA-FIP or IB-FIP, holds.

1.2 Related Work

Resource selection as an optimization problem is a classic topic in combinatorial optimization [Papadimitriou and Steiglitz, 1998], with many variants of scheduling, packing, or covering problems as examples. Strategic resource selection started with Congestion Games [Rosenthal, 1973], where a set of resources is given, and agents select a subset of them. The agents cost then depends solely on the number of users on their chosen set of resources. In extensions, weighted versions and even agent-specific cost functions are allowed [Milchtaich, 1996]. Prominent examples are the strategic selection of paths in a network [Roughgarden and Tardos, 2002; Anshelevich et al., 2004] or server selection by selfish jobs [V ocking, 2007]. Also, competitive facility location, where the facilities compete for the clients [Vetta, 2002] or the clients compete for facilities [Kohlberg, 1983; Peters et al., 2018; Krogmann et al., 2021; Krogmann et al., 2023] can be seen

as strategic resource selection. Another example is the selection of group activities [Darmann et al., 2012; Igarashi et al., 2017]. In all the above models, the utility of an agent depends on the number of other agents that select the same resources. In contrast to this, and much closer to our work, are models with heterogeneous agents. Recently, game-theoretic models for the creation of networks by homophilic agents have been studied [Bullinger et al., 2022]. More related to our model is Schelling s model for residential segregation [Schelling, 1971], where agents with a type strategically select a location in a residential area. These agents behave according to a threshold-based utility function that yields maximum utility if at least a certain fraction of same-type agents populate the neighborhood of the selected location. Game-theoretic variants of Schelling s model, called Schelling Games, have recently been studied [Chauhan et al., 2018; Echzell et al., 2019] and also variants became popular, where agents strive to maximize the fraction of same-type neighbors [Agarwal et al., 2021; Bullinger et al., 2021; Kanellopoulos et al., 2021; Bil o et al., 2022b; Kanellopoulos et al., 2022] or with singlepeaked preferences [Bil o et al., 2022a; Friedrich et al., 2023]. Schelling Games are different from our model since every resource, i.e., location, can only be chosen by at most one agent and thus the agent neighborhoods only partially overlap. Also, the size of these neighborhoods is bounded, whereas in our model there is no limit on the number of users of a specific resource. Closest related to our model are Hedonic Diversity Games [Bredereck et al., 2019; Boehmer and Elkind, 2020; Darmann, 2021; Ganian et al., 2022], where agents of different types strategically form coalitions, and their utility depends on the fraction of same-type agents in their chosen coalition. While preferences over fractions may be arbitrary in these games, our model generalizes the special case with preferences resembling a τ-threshold function as in Schelling s model or with agents having single-peaked utilities with a peak at 1, since in our model the access to the resources can be restricted. Thus, these special cases of Hedonic Diversity Games match our model with a suitable τ on a complete bipartite accessibility graph. Also related are Hedonic Expertise Games [C askurlu et al., 2021], where the utility of agents increases with more different types in the coalition.

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (IJCAI-23)

1.3 Our Contribution We consider strategic resource selection problems with homophilic agents. In contrast to previous work, the utility of our agents does not depend on the number of other agents that use the same resource, but on the fraction of same-type agents. This opens up a new direction for resource selection problems, like Congestion Games. Another main conceptual contribution is the study of impact-blind equilibria, which can be understood as a natural bounded-rationality variant of classic Nash equilibria and hence might be of independent interest. Impact-blindness models that the exact number of users of a resource might not be known to the agents, but only the fraction of user types. For example, for a large-scale multi-agent technical system, it might be reported that it is currently used by 25% red and 75% blue users. From an agent s perspective, this is a game with incomplete information. For risk-averse agents, the best response is indeed equivalent to being impact-blind. Even for risk-neutral agents, if the (expected) number of agents is large, the optimal behavior is impact blind. Mathematically speaking, as the number of agents grows, the set of Bayesian equilibria of the game with incomplete information converges to the set of impact-blind equilibria. As our main technical contribution, we consider strategic resource selection with homophilic agents both with impactaware and with impact-blind agents. For the latter, we prove that equilibria always exist and that they can be constructed efficiently. Moreover, equilibria are guaranteed to exist for τ 1 2 for impact-aware agents. Also, we show that specific impact-blind equilibria resemble 2-approximate impactaware equilibria, which ensures the existence of almost stable states for any τ in the impact-aware setting. Regarding the quality of equilibria, we prove tight constant bounds on the Po A for both versions and we show that the Po S is 1 for τ = 1. On the complexity side, we show that maximizing social welfare is NP-hard in general, but efficient computation is possible for restricted instances. See [Gadea Harder et al., 2023] for all omitted details.

2 Complexity We begin by studying the computational complexity of finding optimal profiles of Schelling Resource Selection Games. We show that this is a hard problem in general, but for sparse instances, i.e., with bounded degrees of the resource nodes or the agent nodes, we can compute optimal solutions efficiently. Theorem 1. For any threshold τ > 0, it is NP-hard to decide if every agent can get maximum utility. As a corollary, we obtain hardness for the problem of computing a profile maximizing social welfare since finding an optimal profile also solves the problem of deciding whether every agent can achieve utility τ. Corollary 1. Computing the social optimum is NP-hard. Theorem 1 even holds if we restrict it to instances where every agent can choose from a set of at most three resources. However, this can not be extended to a maximum of two. Theorem 2. For τ = 1, deciding if every agent can get utility 1 is solvable in polynomial time if each a A has degree 2.

A similar result holds if resource nodes have low degree.

Theorem 3. A social optimum can be computed in polynomial time for τ [0, 1] if the degree of each resource is 2.

Proof. The following procedure yields an optimal strategy profile: In the first step, we iteratively check for a resource that is accessible by only a single agent or by agents of the same color only. We assign those agents to that resource and remove the resource and those agents from the instance. We are left with an instance in which every resource is accessible by exactly one red and one blue agent in its associated accessibility graph. In the second step, we compute a maximum matching in the accessibility graph and assign agents to resources according to the matching. Each remaining unmatched agent is assigned to an arbitrary accessible resource. To prove optimality, we first observe that all agents assigned in step one have maximal utility and all resources removed in step one are not accessible by any agent left for step two. It remains to show that the assignment of step two is optimal. To that end, let n be the number of agents of the instance at the beginning of step two and let k denote the cardinality of a maximum matching. Hence, our algorithm computes a profile with n k resources that each have two agents of different colors and 2k n resources with exactly one agent. Assume this was not optimal, then there needs to be a solution with fewer than n k resources that have two differently colored agents. Hence, the total number of used resources needs to be larger, as n agents still have to be assigned. However, this implies the existence of a matching of cardinality strictly larger than k which yields a contradiction. The algorithm can be implemented in polynomial time using a standard algorithm, e.g. [Hopcroft and Karp, 1973].

3 Equilibrium Existence and Computation

In this section, we show that IBE exist in all instances and for all τ > 0, since an ordinal potential function exists. Improving response dynamics converge in a polynomial number of steps, but an even more efficient greedy algorithm exists to construct IBE directly from scratch.

3.1 Impact-Blind Equilibria Lemma 1. For τ = 1, an impact-blind improving move increases social welfare.

Proof. Let, w.l.o.g., a red agent make an impact-blind improving move from resource q to q , changing the strategy profile from s to s . Let r1 = #R(q, s), b1 = #B(q, s), r2 = #R(q , s) and b2 = #B(q , s). The total social welfare of the agents on q in s is Wq(s) = r2 1+b2 1 r1+b1 = r1 b1 + 2 b2 1 r1+b1

and in s it is Wq(s ) =

(r1 1)2+b2 1 r1+b1 1 = r1 b1 1+2 b2 1 r1+b1 1 . If r1 +b1 1 = 0,

then a would not improve by switching to q . Thus, the change of welfare of the agents on q is Wq(s ) Wq(s) =

2 b2 1 r1+b1 1 2 b2 1 r1+b1

1 = 2 b2 1 (r1+b1 1)(r1+b1) 1.

Similarly, the total social welfare of the agents on q in s is Wq (s) = r2 2+b2 2 r2+b2 = r2 b2 + 2 b2 2 r2+b2

and in s it is

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (IJCAI-23)

Algorithm 1: compute Equilibrium(G)

1 while Q not empty do

2 assign all a B with |X(a)| = 1;

3 q arg maxq Q |R Y (q)| |B assigned(q)|;

4 assign all a R Y (q) to q;

5 remove q and its assigned agents from G;

Wq (s ) = (r2+1)2+b2 2 r2+b2+1 = r1 b1+1+2 b2 2 r2+b2+1 . Thus, the

change of welfare of the agents on q is Wq (s ) Wq (s) =

2 b2 2 r2+b2+1 2 b2 2 r2+b2

+1 = 2 b2 2 (r2+b2+1)(r2+b2) +1.

Therefore, the total difference is W(s ) W(s) = 2 b2 1 (r1+b1 1)(r1+b1) b2 2 (r2+b2+1)(r2+b2) >

2 b2 1 (r1+b1)2 b2 2 (r2+b2)2 . Since the move is improving, we

have b1 r1+b1 > b2 r2+b2 and therefore W(s ) W(s) > 0.

Note that Lemma 1 does not hold for impact-aware improving moves. (See Theorem 11.) With the difference considered in the proof of Lemma 1, we can also bound the number of steps needed to reach an IBE.

Lemma 2. For τ = 1, an IBE is reached after O(n5) impactblind improving moves.

Proof. As seen in Lemma 1, an improving move increases social welfare by W(s ) W(s) > 2 b2 1 (r1+b1)2 b2 2 (r2+b2)2 =

2 b2 1(r2+b2)2 b2 2(r1+b1)2

(r1+b1)2(r2+b2)2 . Also by Lemma 1, the numerator is a positive integer, so W(s ) W(s) > 1 n4 . Since the social welfare is in [0, n], its maximum is reached after at most n5 steps.

Since an impact-blind improving move for a threshold τ < 1 is also an impact-blind improving move for τ = 1 and since we can compute an improving response in O(m), we get:

Theorem 4. For any τ [0, 1], the Schelling Resource Selection Game possesses the IB-FIB and an IBE can be computed with runtime O(n5m).

Note that the social welfare at τ = 1 is always an ordinal potential function, independently of the actual value of τ.6

We provide Algorithm 1 to greedily compute an IBE, i.e., we can circumvent finding equilibria via expensive improving response dynamics. However, we still think that the IB-FIP is important as the agents can also find an equilibrium independently. Intuitively, our algorithm checks which resource can achieve the highest red fraction, taking into account the blue agents that have only one resource available. Then it assigns all possible red agents and the necessary blue agents to that resource and removes it from the instance. We show, that the algorithm removes the resources sorted by their fraction of red agents in the resulting equilibrium.

6In the full version [Gadea Harder et al., 2023], we show that for τ < 1 the social welfare is not necessarily a potential function.

Lemma 3. If Algorithm 1 producing the IBE s removes resource q1 before resource q2, then ρR(q1, s) ρR(q2, s).

Proof. While running the algorithm, for each resource q, the number of assigned blue agents to q monotonically increases and the number |R Y (q)| of red agents assignable to q monotonically decreases. Thus, after the removal of q1, no resource q2 with a higher fraction can be removed.

Theorem 5. For τ [0, 1], Algorithm 1 computes an IBE in runtime O(m + k log k).

Proof. For the runtime, we build a data structure in which for each resource q we store the number of assigned blue agents and the number of red agents with an edge to q, with runtime O(m + k). Updating this data structure and finding the blue agents can be done in amortized O(m) steps, as we only have to do an operation for each edge that is removed from the instance. Additionally, we maintain a Fibonacci heap [Fredman and Tarjan, 1987] of resources, to select the next resource to be removed. This needs O(m) decrease-key operations for each of the updates of the aforementioned data structure. For extracting the k agents we need a total runtime of O(k log k). A red agent does not want to change strategies, as she cannot access the resources removed before her assignment and, by Lemma 3, all other resources have a worse fraction. For blue agents, the argument is analogous.

Note that Algorithm 1 is not correct for IAE.7

3.2 Impact-Aware Equilibria For impact awareness, we show the existence of an equilibrium for τ 1

2 by using a potential argument. First, we give an ordinal potential function that always remains constant or increases with an improving move. The function is the sum of majority sizes over all resources.

Lemma 4. With an impact-aware improving move in the Schelling Resource Selection Game, the potential function Φ(s) = P q Q max{#R(q, s), #B(q, s)} never decreases, for all possible values of τ. (However, it is possible that it does not change.) The number of steps increasing Φ(s) in a sequence of improving moves is limited.

Proof. The potential Φ can only have integer values in [0, n], limiting the number of increasing moves. Let, w.l.o.g, a be a red agent making an improving move from resource q to q changing the state from s to s . We study the possible cases for the relation between #R and #B at q and q and consider the terms of Φ for q and q as all other terms do not change. Case 1: (#R(q, s) > #B(q, s)): We have Φq(s) = max{#R(q, s), #B(q, s)} = max{#R(q, s ), #B(q, s )} + 1 = Φq(s ) + 1. Since the move is improving, #R(q , s ) > #B(q , s ) holds and therefore Φq (s) = max{#R(q , s), #B(q , s)} = max{#R(q , s ), #B(q , s )} 1 = Φq (s ) 1. Thus, the value of Φ remains unchanged. Case 2: (#R(q, s) = #B(q, s)): We have Φq(s) = max{#R(q, s), #B(q, s)} = max{#R(q, s ), #B(q, s )} = Φq(s ). Since the move is improving, #R(q , s ) >

7See [Gadea Harder et al., 2023] for a counterexample.

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (IJCAI-23)

#B(q , s ) and thus Φq (s) = max{#R(q , s), #B(q , s)} = max{#R(q , s ), #B(q , s )} 1 = Φ q(s ) 1. Thus, the value of Φ increases by 1. Case 3: (#R(q, s) < #B(q, s) and #R(q , s) < #B(q , s)): Blue agents stay in the majority for this move in q and q , so Φ remains unchanged. Case 4: (#R(q, s) < #B(q, s) and #R(q , s) #B(q , s)): We have Φq(s) = max{#R(q, s), #B(q, s)} = max{#R(q, s ), #B(q, s )} = Φq(s ) and Φq (s) = max{#R(q , s), #B(q , s)} = max{#R(q , s ), #B(q , s )} 1 = Φ q(s ) 1. Thus, the value of Φ increases by 1.

With Lemma 4, we know that in a sequence of improving moves, Cases 2 and 4 of the proof occur only finitely often.

Theorem 6. For τ 1 2, the Schelling Resource Selection Game has the IA-FIP.8

Proof. Let Z(s) be the descendingly sorted vector of utilities in s. We show that Z in combination with Φ is a lexicographic potential function for the SRSG. To prove this, let, w.l.o.g., a red agent a make an improving move from resource q to q changing the state from s to s . We consider three cases for ρR(q , s) before the move: Case 1 (ρR(q , s) < 1 2): The only agents that lose utility are the red agents that keep using q. (The utility of the blue agents using q does not fall below 1

2 and therefore does not change.) Since agent a ends up with a utility greater than what the losing agents had before, the earliest change in the vector is an increase. Case 2 (ρR(q , s) = 1

2): In this case, the potential given in Lemma 4 increases (Case 2), hence this case may only occur a finite number of times in a sequence of improving moves. Case 3 (ρR(q , s) > 1

2): Only blue agents at q and red agents at q lose utility. All of them have a utility strictly smaller than 1

2 in s before the move. Since a improves from a utility smaller than 1

2 to equal to 1

2, the first change in the vector is an improvement in the new spot of a. The number of possible values of an entry in Z is limited, and thus also the number of possible values for the vector.

4 Equilibrium Approximation

Next, we show that we can compute an approximate IAE by using an IBE with specific properties as a proxy.

Theorem 7. A 2 approximate impact-aware equilibrium can be computed in runtime O(n5m) for any τ [0, 1].

Proof. For the proof, we use τ = 1, but a 2 approximate IAE for τ = 1 is also a 2 approximate IAE for all other values of τ as the utility gain of a move monotonically decreases with decreasing τ. Let, w.l.o.g., a red agent a make an impact-aware improving move from resource q to q , changing the strategy profile from an IBE s to s . First, we show that if a improves by a factor of more than 2, then social welfare increases. Let r1 = #R(q, s), b1 = #B(q, s), r2 = #R(q , s) and b2 = #B(q , s). As s is an IBE and therefore a s current utility is in the interval of r2 r2+b2 and

8We conjecture that this also holds for arbitrary τ.

r2+1 r2+b2+1, we have r2 = 0 to allow for an improvement factor of more than 2. The move changes the sum of utilities of agents using q by the value

1 b2 + 1 b2

= 2 b2 + 1 1

For q this change is

(b1 r1 + 1) r1 r1 + b1 r1 1 r1 + b1 1

=(b1 r1 + 1) b1 (r1 + b1)(r1 + b1 1) r1 r1 + b1

=(b1 + r1 + 1)b1 2b1r1

(r1 + b1)(r1 + b1 1) r1 r1 + b1

=1 r1 r1 + b1 2b1r1 (r1 + b1)(r1 + b1 1) r1 r1 + b1

1 4 r1 r1 + b1 .

In the last step, we use b1 r1+b1 1 1. Therefore the total change in social welfare is at least 2 b2+1 4 r1 r1+b1 , which is

greater than 0, by the assumption that 2 r1 r1+b1

< 1 b2+1. For finding an IBE with no possible strategy change that increases social welfare, we use the algorithm in Lemma 2. However, we execute all strategy changes that improve social welfare and not just impact-blind improving moves.

5 Equilibrium Quality

In this section, we compute the exact Price of Anarchy for all values of τ which holds for both impact-aware and impactblind agents. Additionally, we give an upper bound on the impact-blind Price of Stability and show that for τ 1

2 the social optimum is not necessarily an IBE.

5.1 Price of Anarchy

For giving an upper bound on the Price of Anarchy, we first prove lower bounds for the sum of utilities of the agents using a resource. After that, we use the fact that a social welfare optimum assigns at most utility τ to every agent for deriving our upper bound. Finally, we give a class of instances in which we match this upper bound on the Po A asymptotically. This gives us an exact Po A for both impact-blind and impact-aware agents.

Lemma 5. Consider a resource q in a arbitrary state s, with, w.l.o.g., #R(q, s) #B(q, s). If ρR(q, s) τ, then the sum of utilities of the agents using q is at least #(q, s) τ τ 2

Proof. Let ρB(q, s) = τ ϵ, with ϵ 0. The sum of utilities of agents using q is S(ϵ) = #(q, s)((1 (τ ϵ))τ + (τ ϵ)2) = #(q, s)(τ τϵ + ϵ2). To find the minimum of this expression, we set d dϵS(ϵ) = 0 and get 0 = #(q, s)( τ + 2ϵ) ϵ = τ 2. Thus, the minimum for the sum of utilities

S(ϵ) is S( τ

2) = #(q, s) τ τ 2

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (IJCAI-23)

Lemma 6. Consider a resource q in a arbitrary state s with, w.l.o.g., #R(q, s) #B(q, s). If ρR(q, s) τ, then the sum of utilities of the agents using q is at least #(q,s)

Proof. Form pairs between blue and red agents using q. Each pair has a combined utility of 1. All unpaired red agents have a utility of at least 1

2. Thus, the average utility of an agent using q is at least 1

Theorem 8. The IAE-Po A and IBE-Po A for τ 2

2 are at most 4 4 τ and for τ 2

2 they are at most 2τ.

Proof. Consider a resource q in a arbitrary state s with, w.l.o.g., #R(q, s) #B(q, s) and consider the sum of utilities S of the agents using q in two different cases. Case 1 (ρR(q, s) τ): By Lemma 5, we have S #(q, s) τ τ 2

Case 2 (ρR(q, s) τ): By Lemma 6, we have S #(q,s)

2 . Now, we check which case dominates for which τ:

Thus, for τ 2

2, the state s with the lowest social welfare has at least W(s) n

2 . Similarly, for τ 2

the lowest social welfare is at least W(s) n τ τ 2

4 . The highest social welfare any state can have is τn, so we get bounds of 4 4 τ and 2τ for the Po A, respectively.

We match these upper bounds asymptotically, by creating instances in which only a constant number of agents do not use resources with the worst-case distributions given in Lemmas 5 and 6. Theorem 9. The IAE-Po A and IBE-Po A for τ 2

2 are 4 4 τ and for τ 2

2 they are 2τ.

Proof. For τ 2

2, we create the instance Gα with Q = {q1, q2, q3} with a parameter α such that α N. We have a set Rx of α(2 τ)

2 red agents with edges to q1 and q3 and a set Bx of ατ

2 blue agents with edges to q1 and q2. (Since we let α later, we can use the nearest integer values for Rx and Bx with an error that goes to 0.) Furthermore, we have a set of red agents Rz and blue agents Bz, both with 2

τ agents and edges to q2 and q3. Assigning all red agents to q3 and assigning all blue agents to q2 gives all agents the maximum utility of τ, achieving the same best-case optimum we used in Theorem 8. See Figure 2a. Assigning Rx and Bx to q1, while assigning Rz and Bz to q2 and q3 respectively yields an IAE (see Figure 2b), as the agents using q1 can only switch to a resource used by only the respective other color. In particular, a blue agent a Bx with utility τ

2 cannot improve by moving to q3 with utility 1 2

2 (and similar for agents in Rx). Since the agents on q1 have the worst-case distribution of Lemma 5, we asymptotically achieve the Po A bound with α . For τ 2

2, we use the same construction, but with |Rx| = |Bx| = α

2 , which achieves the worst-case distribution of Lemma 6.

(a) Social optimum.

|{z} |{z} |{z} |{z} Bx Rx 2

(b) Socially bad IAE.

Figure 2: Example instance from the proof of Theorem 9 showing that the Po A bound in Theorem 8 is tight.

5.2 Price of Stability As seen in Lemma 1, the IBE-Po S is 1 for τ = 1. We now generalize this for arbitrary τ. Theorem 10. The IBE-Po S for arbitrary τ > 0 is at most 1

Proof. For a threshold τ, let sτ be the social welfare optimum and denote by Wτ(s) the social welfare of a state s. Observe that by Lemma 1 s1 is an IBE for arbitrary τ. Since the utility of an agent decreases at most by factor t, when changing the threshold from τ = 1 to τ = t, we have Wt(s1) t W1(s1). Also W1(s1) W1(st) Wt(st). Thus, Wt(st)

Note that for τ < 1

2, this result is dominated by the bound on the IBE-Po A. Combining these two bounds, we get a bound of

2 on the IBE-Po S for any τ > 0. Theorem 11. The IBE-Po S for 0 < τ 1

2 is larger than 1.

6 Conclusion and Outlook In this paper, we introduce Schelling Resource Selection Games in which agents strategically select resources to optimize the fraction of same-type agents on their respective selected resources. We investigate agents that fully know the impact of their own actions and also agents that are blind to their exact impact. For the second case, which is arguably more realistic for settings with limited information, we present an efficient algorithm for computing equilibria. Moreover, we show that specific impact-blind equilibria approximate impact-aware equilibria well. Also, we show that the Po A is at most 2, showing that the game is well-behaved. We believe that impact-blind equilibria are a natural object to study also in other settings, like Schelling Games, Hedonic Games, and other types of Resource Selection Games. Given our algorithmic advances on the problem, it may now be interesting to investigate real-world examples of the problem. Especially in the case of school choice, there may be data available on which our model could be used to draw additional conclusions. With further research, it may be possible to identify measures that help to desegregate schools, which is a pressing current problem. Note that careful consideration must be applied to our measure of social welfare. Even though it accurately depicts the agents preferences, the social optimum yields maximally segregated usage of the resources, which might be undesirable for some applications, e.g., in schools. For these cases, diversity is a more suitable measure of social welfare.

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (IJCAI-23)

References [Agarwal et al., 2021] Aishwarya Agarwal, Edith Elkind, Jiarui Gan, Ayumi Igarashi, Warut Suksompong, and Alexandros A. Voudouris. Schelling games on graphs. Artif. Intell., 301:103576, 2021. [Anshelevich et al., 2004] Elliot Anshelevich, Anirban Dasgupta, Jon Kleinberg, Eva. Tardos, Tom Wexler, and Tim Roughgarden. The Price of Stability for Network Design with Fair Cost Allocation. In FOCS, pages 295 304, 2004. [Bil o et al., 2022a] Davide Bil o, Vittorio Bil o, Pascal Lenzner, and Louise Molitor. Tolerance is necessary for stability: Single-peaked swap schelling games. In IJCAI, pages 81 87, 2022. [Bil o et al., 2022b] Davide Bil o, Vittorio Bil o, Pascal Lenzner, and Louise Molitor. Topological influence and locality in swap schelling games. AAMAS, 36(2):47, 2022. [Boehmer and Elkind, 2020] Niclas Boehmer and Edith Elkind. Individual-based stability in hedonic diversity games. In AAAI, pages 1822 1829, 2020. [Bredereck et al., 2019] Robert Bredereck, Edith Elkind, and Ayumi Igarashi. Hedonic diversity games. In AAMAS, pages 565 573, 2019. [Bullinger et al., 2021] Martin Bullinger, Warut Suksompong, and Alexandros A. Voudouris. Welfare guarantees in schelling segregation. J. Artif. Intell. Res., 71:143 174, 2021. [Bullinger et al., 2022] Martin Bullinger, Pascal Lenzner, and Anna Melnichenko. Network creation with homophilic agents. In IJCAI, pages 151 157, 2022. [Burgess et al., 2005] Simon Burgess, Deborah Wilson, and Ruth Lupton. Parallel lives? Ethnic segregation in schools and neighbourhoods. Urban studies, 42(7):1027 1056, 2005. [C askurlu et al., 2021] Bugra C askurlu, Fatih Erdem Kizilkaya, and Berkehan Ozen. Hedonic expertise games. In SAGT, pages 314 328, 2021. [Chauhan et al., 2018] Ankit Chauhan, Pascal Lenzner, and Louise Molitor. Schelling segregation with strategic agents. In SAGT, pages 137 149, 2018. [Darmann et al., 2012] Andreas Darmann, Edith Elkind, Sascha Kurz, J erˆome Lang, Joachim Schauer, and Gerhard Woeginger. Group activity selection problem. In WINE, pages 156 169, 2012. [Darmann, 2021] Andreas Darmann. Hedonic diversity games revisited. In ADT, pages 357 372, 2021. [Echzell et al., 2019] Hagen Echzell, Tobias Friedrich, Pascal Lenzner, Louise Molitor, Marcus Pappik, Friedrich Sch one, Fabian Sommer, and David Stangl. Convergence and hardness of strategic schelling segregation. In WINE, pages 156 170, 2019. [Fredman and Tarjan, 1987] Michael L. Fredman and Robert Endre Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM, 34(3):596 615, 1987.

[Friedrich et al., 2023] Tobias Friedrich, Pascal Lenzner, Louise Molitor, and Lars Seifert. Single-peaked jump schelling games. Co RR, abs/2302.12107, 2023. [Gadea Harder et al., 2023] Jonathan Gadea Harder, Simon Krogmann, Pascal Lenzner, and Alexander Skopalik. Strategic resource selection with homophilic agents. Co RR, abs/2305.00843, 2023. [Ganian et al., 2022] Robert Ganian, Thekla Hamm, Dusan Knop, Simon Schierreich, and Ondrej Such y. Hedonic diversity games: A complexity picture with more than two colors. In AAAI, pages 5034 5042, 2022. [Hailey, 2022] Chantal A. Hailey. Racial preferences for schools: Evidence from an experiment with white, black, latinx, and asian parents and students. Sociology of Education, 95(2):110 132, 2022. [Hopcroft and Karp, 1973] John E. Hopcroft and Richard M. Karp. An n5/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing, 2(4):225 231, 1973. [Igarashi et al., 2017] Ayumi Igarashi, Dominik Peters, and Edith Elkind. Group activity selection on social networks. In AAAI, 2017. [Kanellopoulos et al., 2021] Panagiotis Kanellopoulos, Maria Kyropoulou, and Alexandros A. Voudouris. Modified schelling games. Theor. Comput. Sci., 880:1 19, 2021. [Kanellopoulos et al., 2022] Panagiotis Kanellopoulos, Maria Kyropoulou, and Alexandros A. Voudouris. Not all strangers are the same: The impact of tolerance in schelling games. In MFCS, pages 60:1 60:14, 2022. [Kohlberg, 1983] Elon Kohlberg. Equilibrium Store Locations When Consumers Minimize Travel Time Plus Waiting Time. Economics Letters, 11(3):211 216, 1983. [Krogmann et al., 2021] Simon Krogmann, Pascal Lenzner, Louise Molitor, and Alexander Skopalik. Two-stage facility location games with strategic clients and facilities. In IJCAI, pages 292 298, 2021. [Krogmann et al., 2023] Simon Krogmann, Pascal Lenzner, and Alexander Skopalik. Strategic facility location with clients that minimize total waiting time. In AAAI, 2023. [Massey and Denton, 1988] Douglas S Massey and Nancy A Denton. The dimensions of residential segregation. Social forces, 67(2):281 315, 1988. [Milchtaich, 1996] Igal Milchtaich. Congestion games with player-specific payoff functions. Games and economic behavior, 13(1):111 124, 1996. [Papadimitriou and Steiglitz, 1998] Christos H. Papadimitriou and Kenneth Steiglitz. Combinatorial optimization: algorithms and complexity. Courier Corporation, 1998. [Peters et al., 2018] Hans Peters, Marc Schr oder, and Dries Vermeulen. Hotelling s location model with negative network externalities. Int. J. Game Theory, 47:811 837, 2018.

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (IJCAI-23)

[Rosenthal, 1973] Robert W. Rosenthal. A class of games possessing pure-strategy nash equilibria. Int. J. Game Theory, 2(1):65 67, 12 1973.

[Roughgarden and Tardos, 2002] Tim Roughgarden and Eva Tardos. How bad is selfish routing? J. ACM, 49(2):236 259, 2002. [Schelling, 1971] Thomas C. Schelling. Dynamic models of segregation. The Journal of Mathematical Sociology, 1(2):143 186, 1971. [Vetta, 2002] Adrian Vetta. Nash Equilibria in Competitive Societies, with Applications to Facility Location, Traffic Routing and Auctions. FOCS, pages 416 425, 2002. [V ocking, 2007] Berthold V ocking. Selfish load balancing. Algorithmic game theory, 20:517 542, 2007.

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (IJCAI-23)