# distance_preservation_games__1f08548d.pdf

Distance Preservation Games

Haris Aziz1 , Hau Chan2 , Patrick Lederer1 , Shivika Narang1 and Toby Walsh1

1University of New South Wales 2University of Nebraska-Lincoln {haris.aziz,p.lederer,s.narang,t.walsh}@unsw.edu.au, hchan3@unl.edu

We introduce and analyze distance preservation games (DPGs). In DPGs, agents express ideal distances to other agents and need to choose locations in the unit interval while preserving their ideal distances as closely as possible. We analyze the existence and computation of location profiles that are jump stable (i.e., no agent can benefit by moving to another location) or welfare optimal for DPGs, respectively. Specifically, we prove that there are DPGs without jump stable location profiles and identify important cases where such outcomes always exist and can be computed efficiently. Similarly, we show that finding welfare optimal location profiles is NP-complete and present approximation algorithms for finding solutions with social welfare close to optimal. Finally, we prove that DPGs have a price of anarchy of at most 2.

1 Introduction Assume a university management wants to optimize the assignment of researchers to offices by taking the relationships between the researchers into account to promote collaborations. For example, scholars who like each other should be seated close to each other, scholars who dislike each other should be seated far away from each other, and some scholars may want to be neither too close nor too far from each other. However, given this information, how should we decide on the new office assignment? And can we, e.g., ensure that no researcher would prefer to move to another office? In recent years, questions similar to these have been actively researched for numerous models [Brânzei and Larson, 2011; Bullinger et al., 2021; Agarwal et al., 2021; Berriaud et al., 2023; Bullinger and Suksompong, 2024]. For instance, Bullinger and Suksompong [2024] study topological distance games for which agents need to be assigned to the nodes of a graph and each agent s utility depends on its distance to the other agents in the graph. All of these models have in common that for each agent, the other agents can be partitioned into friends, enemies, and neutrals: agents want to be as close as possible to their friends, as far away as possible from their enemies, and they do not care about the positions of neutrals. However, in practice, the agents preferences may be more

complicated. For instance, in our office assignment example, it seems plausible that senior researchers want to be at some distance from their Ph D students to ensure that they are not interrupted too much, but the Ph D students should not be as far away as possible since this makes meetings between the Ph D student and the senior researcher cumbersome. To capture such distance preferences and explore their effects, we introduce and analyze distance preservation games (DPGs). In these games, each agent specifies an ideal distance for each other agent or indicates that the other agent s position does not matter to them. Based on this information, the agents need to choose locations in the unit interval with the aim of preserving their ideal distances as closely as possible. Specifically, we assume that an agent s utility linearly decreases when the difference between the actual distance and their ideal distance to an agent increases. Given a DPG, we aim to find location profiles that are jump stable (i.e., no agent can benefit by jumping to another location) or welfare optimal (i.e., the location profile maximizes utilitarian the social welfare), respectively. Put differently, this means we seek location profiles that preserve the agents ideal distances well.

Example 1. To further illustrate DPGs, consider the following example where three researchers need to be assigned to one of many identical offices in a corridor. The agents are a Ph D student a, a postdoc b, and a professor c. The Ph D student wants to be neither too far nor too close to the professor and does not care about the location of the postdoc. The postdoc wants to be as far away as possible from the Ph D student and as close as possible to the professor. Lastly, the professor wants to be at a moderate distance from both other agents. We capture this as a DPG as follows: the Ph D student a has an ideal distance of 1

2 to c and does not care about the position of b. The postdoc b has an ideal distance of 1 to a and of 0 to c. Finally, the professor c has an ideal distance of 1 2 to both a and b. We note that DPGs can also be presented via preference graphs, where an edge from x to y with weight z means that agent x wants to be at distance z to agent y. The preference graph of our toy example is shown in Figure 1. Now, if we locate the Ph D student at 0, the postdoc at 1

2, and the professor at 1, the postdoc b wants to change their location to be closer to the professor. By contrast, if the Ph D student is at 0, the professor at 1

2, and the postdoc at 1, we preserve the agents ideal distances optimally and no agent has an incentive to change their position.

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-25)

Figure 1: The preference graph of the DPG in Example 1

Our Contribution. In this paper, we initiate the study of distance preservation games. Specifically, we will analyze these games with respect to jump stability and welfare optimality. Roughly speaking, a location profile is jump stable if no agent can benefit by moving to another position. In our setting, this corresponds to the notion of Nash equilibria. On the other hand, a location profile is welfare optimal if it maximizes the (utilitarian) social welfare, i.e., the sum of the agents utilities. An overview of our results is given in Table 1. We first examine jump stable location profiles and show the following results. We prove that there are DPGs without jump stable location profiles and that deciding whether a DPG admits such a location profile is NP-complete.

With the aim of deriving more positive results, we study two natural classes of DPGs, namely symmetric and acyclic ones. First, we say a DPG is symmetric if the ideal distance for i to j is the same as the ideal distance for j to i for all agents i and j. For such symmetric DPGs, we show that jump stable location profiles are guaranteed to exist and can be computed by a best response dynamics. However, we also prove that this best response dynamics may need exponential time and, more generally, that finding jump stable location profiles in symmetric DPGs is PLS-complete.

As a second restriction, we investigate acyclic DPGs, which are defined to have an acyclic preference graph. For this class of DPGs, we show that jump stable location profiles always exist and can be computed efficiently. Secondly, we analyze welfare optimal location profiles and show the following results. We prove that it is NP-complete to find welfare optimal location profiles, even for some of the simplest classes of DPGs. In more detail, we show this claim for DPGs where the preference graph forms a path or where the agents ideal distances, if any, are required to be 1.

We then focus on finding approximately welfare optimal location profiles and show that a greedy algorithm guarantees half of the optimal social welfare.

We prove that the price of anarchy of every DPG, i.e., the ratio between the optimal social welfare and the social welfare of the worst jump stable location profile, is at most 2.

Related Work. The problem of assigning agents to positions on some topology based on their preferences among each other has recently attracted significant attention. We refer to the papers by Bullinger and Suksompong [2024] and Berriaud et al. [2023] for a more extensive discussion of this literature. The most relevant related models include the following:

In Schelling games [e.g., Agarwal et al., 2021; Bilò et al., 2022; Bullinger et al., 2021; Kreisel et al., 2024], the agents are partitioned into classes and located on the nodes of a graph. An agent s utility depends on the fraction of agents of the same class in their neighborhood of the graph.

In the dinner party arrangement problem [e.g., Berriaud et al., 2023; Bodlaender et al., 2020; Ceylan et al., 2023; Aziz et al., 2024], n agents have to be located on a graph with n nodes. Each agent has a utility function over the other agents and an agent s utility in an assignment is the sum of the utilities for their neighbors in the graph.

In topological distance games [e.g., Bullinger and Suksompong, 2024; Deligkas et al., 2024], agents are located on the nodes of a graph and have utilities for the other agents. An agent s utility for a position depends on their utilities and the distances to the other agents in the graph.

The central question for all of these models is to find desirable assignments of the agents to the nodes of the graph. Thus, these papers consider similar problems to ours but they focus on different settings. In particular, DPGs differ from the aforementioned models in two crucial aspects: the agents report ideal distances over the other agents instead of utilities, and our underlying topology is the continuous unit interval instead of a discrete graph. Further, our work is related to facility location on the real line [e.g., Procaccia and Tennenholtz, 2013; Feldman et al., 2016; Chan et al., 2021]. In this setting, the goal is to place one or multiple facilities on the real line depending on the agents preferences on the location of the facilities. In particular, an agent s disutility for a location is typically the distance to their own location. One can see facility location as a variant of our model, where the agents report positions and their ideal distance to the facility is 0. We note that Filos Ratsikas et al. [2017] considered an extension of facility location where agents report both ideal distances to the facility and their location, which is, to our knowledge, the only other game-theoretic paper that studies the idea of ideal distances. More broadly, DPGs are also connected to many other topics in computational social choice, such as hedonic games [e.g., Aziz and Savani, 2016] and social distance games [e.g., Brânzei and Larson, 2011; Balliu et al., 2022], where the agents need to be partitioned into coalitions based on their preferences over each other. Finally, DPGs are related to problems considered in machine learning because they can be seen as a game-theoretic variant of unidimensional scaling, a special case of the multidimensional scaling problem [e.g., Dunn-Rankin et al., 2014; Borg et al., 2018]. Specifically, in unidimensional scaling, we are given ideal distances between all pairs of objects and the goal is to locate the objects based on this information on the real line while preserving the distances between the agents [e.g., Mc Iver, 1981; Pliner, 1996; Groenen et al., 1998]. This can be seen as a variant of DPGs without agents. However, the prior work in unidimensional scaling is limited to heuristics and experimental evaluations of algorithms. Moreover, our work has similarities with clustering problems as a location profile can be seen as an aggregate similarity measure for agents [e.g., Bansal et al., 2004; Xu and Wunsch, 2008].

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-25)

In a distance preservation game (DPG), there is a set N = {1, . . . , n} of agents who express ideal distances over each other. In more detail, each agent i N has a relationship set Mi N \{i} which contains the agents about whom i cares, and an ideal distance function di : Mi [0, 1] which specifies the ideal distance of agent i to all agents in Mi. Given this information, the agents must choose locations in the unit interval. Hence, the outcome of a DPG is a location profile A [0, 1]n, which specifies for every agent i N a location Ai in the unit interval. In DPGs, the agents aim to preserve their ideal distances as closely as possible. Specifically, we assume that the utility of each agent i from an agent j Mi linearly decreases when the absolute difference between their actual distance and agent i s ideal distance to j increases, i.e.,

ui(A, j) = 1 |Ai Aj| di(j) .

By this definition, it holds that ui(A, j) [0, 1] for all location profiles A and agents i N, j Mi. Furthermore, agent i s utility for agent j is 1 precisely if the actual distance between these two agents is equal to agent i s ideal distance to j. The utility of each agent i N for a location profile A is the sum of the utilities that i receives from the agents in Mi, i.e., ui(A) = P j Mi ui(A, j). The utility function ui(A, j) is an affine transformation of the cost ci(A, j) = ||Ai Aj| di(j)|. As a consequence, all our results except for approximation ratios remain valid when using the cost ci instead of the utility ui. We decided to focus on utilities instead of the cost because the minimum social cost turns out to be inapproximable. We emphasize that the action space of every DPG is the unit interval and the agents ideal distances induce their utility functions. Hence, a distance preservation game (DPG) is fully described by a tuple I = N, (Mi)i N, (di)i N specifying the set of agents N, their relationship sets Mi, and their ideal distance functions di. We will frequently represent DPGs via graphs. Specifically, the preference graph GI of a DPG I = N, (Mi)i N, (di)i N is a weighted directed graph GI = (N, E, d) on the agents such that (i, j) E if and only if j Mi and d(i, j) = di(j) for all i N, j Mi. That is, an edge from i to j with weight x in the preference graph indicates that i wants to be at distance x from j.

2.1 Objectives

Given a DPG, our aim is to find a location profile that guarantees high utilities to the agents. We will formalize this idea by two standard concepts, namely jump stability and welfare optimality. These concepts have been repeatedly considered in related settings [e.g., Agarwal et al., 2021; Bullinger et al., 2021; Kreisel et al., 2024; Bullinger and Suksompong, 2024].

Jump stability. Given a location profile, jump stability requires that no agent can increase their utility by unilaterally jumping to another location in the unit interval. Formally, we denote by Ai7 x the location profile derived from another location profile A by placing agent i at Ai7 x i = x and all other

agents j N \ {i} at Ai7 x j = Aj. We say a location profile A is jump stable for a DPG I = N, (Mi)i N, (di)i N if ui(A) ui(Ai7 x) for all agents i N and locations x [0, 1]. We note that jump stable location profiles are equivalent to Nash equilibria, but we prefer to use the term jump stability since it is commonly used in related works.

Welfare optimality. Welfare optimality requires of a location profile that its (utilitarian) social welfare, i.e., the sum of the agents utilities, is maximal. To this end, we define the social welfare of an assignment A for a DPG I = N, (Mi)i N, (di)i N by SWI(A) = P i N ui(A). Then, a location profile A is welfare optimal for a DPG I if SWI(A) SWI(A ) for all other location profiles A .

2.2 Classes of Distance Preservation Games

In our analysis of DPGs, we will often focus on more constrained subclasses of these games. In particular, we will discuss the following restrictions of distance preservation games. The first three restrictions capture large natural classes of DPGs, whereas the remaining two classes are rather restricted and will mainly be used for hardness results.

Symmetric DPG. Intuitively, a DPG is symmetric if for each pair of agents i, j N, agents i and j have the same ideal distance to each other. More formally, a DPG I = N, (Mi)i N, (di)i N is symmetric if for all agents i, j N, i Mj implies that j Mi and di(j) = dj(i).

k-discrete DPGs. The high-level idea of k-discrete DPGs is that there is a precision parameter k N and that the agents are only allowed to report ideal distances that are multiples of 1

k. More formally, a DPG I = N, (Mi)i N, (di)i N is k-discrete if di(j) { 0

k, . . . , k

k} for all i N, j Mi. We believe that this assumption is rather natural as, e.g., 100discrete DPGs ask the agents to specify their ideal distances with up to 2 decimal digits.

Acyclic DPGs. In acyclic DPGs, the preference graph of the game is acyclic. That is, we restrict the relationship structure between the agents instead of their ideal distances. Formally, we call a DPG I = N, (Mi)i N, (di)i N acyclic if there is no sequence of agents i1, . . . , ik such that ij+1 Mij for all j {1, . . . , k 1} and i1 Mik. Acyclic DPGs arise naturally in hierarchical settings, where agents only care about the distances to their superiors.

Enemies and Neutrals DPGs. In an enemies and neutrals DPG, all agents are either enemies and want to be as far away from each other as possible, or they do not care about each other s location. Moreover, we require enemies and neutrals DPGs to be symmetric. Formally, we say that a DPG I = N, (Mi)i N, (di)i N is an enemies and neutrals DPG if it is symmetric and di(j) = 1 for all i N, j Mi.

Path DPGs. A path DPG is a special case of an acyclic DPG where the preference graph forms a path. That is, a DPG I = N, (Mi)i N, (di)i N is called a path DPG if the agents can be ordered such that ij+1 Mij for all j {1, . . . , n 1} and Min = .

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-25)

3 Jump Stability We will now analyze the existence and computation of jump stable location profiles. To this end, we first show that such location profiles do not exist for all DPGs. Proposition 1. There are DPGs without jump stable location profiles.

Proof. Let I be a DPG with two agents N = {1, 2} such that M1 = {2}, M2 = {1}, d1(2) = 1, and d2(1) = 0. Intuitively, this means that agent 1 wants to be as far away as possible from agent 2 and agent 2 wants to be as close as possible to agent 1. Hence, in a location profile A with A1 = A2, agent 2 can improve their utility by changing their location to A1. By contrast, if A1 = A2, agent 1 can improve their utility by moving to any other location. Consequently, one of the two agents always has an incentive to deviate. Therefore, no jump stable location profile exists.

Motivated by this example, we examine computational questions regarding jump stability in Section 3.1. Furthermore, we turn to restricted classes of DPGs in Sections 3.2 and 3.3 with the aim of deriving more positive results. Due to space constraints, we defer most proofs of this section and Section 4 to the extended version [Aziz et al., 2025] and give proof sketches instead.

3.1 Checking for Jump Stability We first consider the problem of deciding whether a location profile is jump stable for a DPG. As we show next, this problem can be solved efficiently because we only need to check a linear number of locations for every agent to decide whether they can improve their utility by changing their position. Theorem 1. It can be verified in polynomial time whether a location profile is jump stable for a DPG.

Proof Sketch. For deciding whether a location profile A is jump stable for a DPG I = N, (Mi)i N, (di)i N , we need to check for every agent i whether there is a beneficial jump. To this end, we consider an agent i N and let hj(x) = ui(Ai7 x, j) denote the utility agent i receives from an agent j Mi when jumping to x. Moreover, let Lj = max(0, Aj di(j)) and Rj = min(1, Aj + di(j)). Our key insight is that hj(x) is linear on the intervals [0, Lj], [Lj, Aj], [Aj, Rj], and [Rj, 1]. Applying this for all agents in Mi implies that h(x) = ui(Ai7 x) = P j Mi hj(x) is a piecewise linear function with at most 3n + 1 linear regions. Because linear functions on a closed interval are maximized at one of the endpoints of the interval, it suffices to check whether i can benefit by jumping to one of the 3n + 2 endpoints. This can be done in polynomial time.

Theorem 1 implies that the problem of deciding whether a DPG admits a jump stable location profile is in NP as we can guess and verify such location profiles if they exist. Unfortunately, we will next show that this problem is NP-complete for general DPGs. Theorem 2. It is NP-complete to decide whether a DPG I = N, (Mi)i N, (di)i N admits a jump stable location profile, even if |Mi| 1 for all i N.

Proof. It follows from Theorem 1 that the problem is in NP. To show NP-hardness, we will give a reduction from BALANCEDPARTITION [Garey and Johnson, 1979]. In this problem, we are given a set of items S = {s1, . . . , sk} with weights w : S N such that w(s) 1 2 P x S w(x) for all s S, and we need to decide whether there is a partition (X, S \ X) such that P s X w(s) = P s S\X w(s). Given an instance (S, w) of BALANCEDPARTITION, we define B = P s S w(s) and we construct the following cyclic DPG: we set N = {1, . . . , k}, Mi = {i + 1} and di(i + 1) = w(si)

B for all i N \ {k}, and Mk = {1} and dk(1) = w(sk)

B . To ease notation, we let Ak+1 = A1 and dk(k + 1) = dk(1).

Since w(s) B

2 for all s S, it holds that di(i + 1) 1

2 for all i N. This implies that x di(i + 1) [0, 1] or x + di(i + 1) [0, 1] for all i N, x [0, 1]. Hence, if ui(A) < 1 for an agent i and a location profile A, this agent can benefit by jumping to Ai+1 di(i+1) or Ai+1+di(i+1). Thus, a location profile A is jump stable for the constructed DPG if and only if ui(A) = 1 for all i N. We will now show that a jump stable location profile exists if and only if there is a solution to the instance (S, w) of BALANCEDPARTITION. First, suppose that there is a jump stable location profile A. Consequently, ui(A) = 1 for all i N, so |Ai Ai+1| di(i+1) = 0. Because di(i+1) = w(st)

B > 0, it holds that Ai = Ai+1 for all i N. Next, let R = {i N : Ai > Ai+1} and L = {i N : Ai < Ai+1}. By definition, the set L and R are disjoint. Moreover, it holds for the agent i minimizing Ai that Ai < Ai+1 and Ai 1 > Ai, so i L and i 1 R. Now, since |Ai Ai+1| = di(i + 1) for all i N, it holds that Ai Ai+1 = di(i + 1) if i R and Ai+1 Ai = di(i + 1) if i L. This means that P i L di(i + 1) P i R di(i + 1) = P i L(Ai+1 Ai) P i R(Ai Ai+1) = P i N(Ai+1 Ai) = 0. Here, the last step follows as P i N(Ai+1 Ai) = Ak+1 A1 and Ak+1 = A1 by definition. Since di(i + 1) = w(si)

B for all i N, this implies that P i L w(si) = P i R w(si), which shows that there is a solution to the partition instance. For the converse, let there be a partition (X, S \ X) such that P s X w(s) = P s S\X w(s). Without loss of generality, we assume that sk X. Now, consider the location profile A given by A1 = 1 2, Ai = Ai 1 + di 1(i) for all si X \ {s1}, and Ai = Ai 1 di 1(i) for all si S \ (X {x1}). We observe that A is a valid location profile since Ai [0, 1] for all i N. This holds because P si X di(i + 1) = 1 B P si X w(si) = 1 2 and P si S\X di(i + 1) = 1 B P si S\X w(si) = 1 2. Further, it holds for all agents i N \ {k} that ui(A) = 1 since |Ai Ai+1| = di(i+1) by construction. Finally, for agent k, we note that P

si X\{sk} w(si) P

si S\X w(si) = w(sk) since sk X and P si X w(si) = P si S\X w(si). This implies that P si X\{sk} di(i + 1) P si S\X di(i + 1) = dk(1). Thus, Ak = A1 + P si X\{sk} di(i + 1) P si S\X di(i + 1) = A1 dk(1). This shows that uk(A) = 1, so we conclude that A is jump stable as all agents get their maximal utility.

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-25)

ALGORITHM 1: Best Response Dynamics

Input: A symmetric DPG I = N, (Mi)i N, (di)i N Output: A location profile A

1 Let A be a location profile s.t. Ai = 0 for all i N;

2 while exists x [0, 1] and i N s.t. ui(Ai7 x) > ui(A) do

3 x min{x [0, 1]: x arg maxy A ui(Ai7 y)};

4 A Ai7 x ;

5 Return A;

3.2 Symmetric Distance Preservation Games

Observe that both Proposition 1 and Theorem 2 rely on asymmetric ideal distances and cyclic preference graphs. We hence examine next how our results change when disallowing these features and start by analyzing symmetric DPGs. In particular, we show next that jump stable location profiles are guaranteed to exist for symmetric DPGs and that they can be computed by a simple best response dynamics. In more detail, in the best response dynamics, which is outlined in Algorithm 1, agents repeatedly change their location to the left-most position that maximizes their utility given the position of the other agents. Further, we will prove that this best response dynamics terminates after at most O(kn2) iterations of the while loop if the DPG is additionally k-discrete.

Theorem 3. For symmetric DPGs, jump stable location profiles are guaranteed to exist. If the DPG is additionally kdiscrete for some k N, the best response dynamics finds a jump stable location profile in O(kn2) steps.

Proof Sketch. To prove the existence of jump stable location profiles, we show that, for symmetric DPGs, a beneficial jump always increases the social welfare. This implies that welfare optimal location profiles are jump stable, so jump stable location profile are guaranteed to exist. Moreover, if the considered DPG is additionally k-discrete, we prove that an optimal jump increases the social welfare by at least 2

k. Since the social welfare is at most P i N |Mi| n(n 1), the best response dynamics converges in at most O(kn2) steps.

Theorem 3 suggests a tradeoff between the precision of the agents ideal distances and the runtime of the best response dynamics: the smaller the k such that a DPG is k-discrete, the faster a jump stable location profile is found. We next show that this tradeoff is tight because the best response dynamics may indeed need Ω(k) steps for symmetric k-discrete DPGs.

Example 2. Consider the DPG given by the preference graph in Figure 2 and assume that all agents start at 0. First, agents 1, 2, 3, and 4 do not have an incentive to move because they are at their ideal distance from each other. Next, agents 7, 8, 9, and 10 have no incentive to move as long as they are at the same position as at least two of their friends (5, 6, and one of 11 and 12). Thirdly, the agents in 11 and 12 will not move as long as they are at the same position as 7, 8 and 9, 10. Hence, the only agents who want to move are 5 and 6. At their current positions, these agents receive a utility of 4 + (1 1

k). If they move to 1

k, they obtain the best possible utility of 5. In turn,

1 1 1 1 1 1 1 1

0 0 0 0 0 0 0 0 0 0

Figure 2: The preference graph of the DPG of Example 2. The edges are bidirectional and colorcoded to ease readability. Blue edges indicate an ideal distance of 0, red edges of 1, and green edges of 1/k.

agents 7, , 10 will move to 1

k. Lastly, the agents 11 and 12 will also move to this position. However, now agents 5 and 6 again have an incentive to move to the location 2

k, and the agents 7, , 12 will follow again. This process repeats until the agents 5, , 12 are at 1 and thus requires Ω(k) steps.

Example 2 demonstrates that the best response dynamics may need exponential time if, e.g., k = 2n. This leads to the question of whether jump stable location profiles can be found efficiently for all symmetric DPGs. We next answer this question by showing that finding jump stable location profiles in symmetric DPGs is PLS-complete. Specifically, the complexity class PLS ( Polynomial Local Search ) captures optimization problems for which (locally) optimal solutions are guaranteed to exist due to local search arguments. However, it is believed that it is not possible to efficiently find locally optimal solutions for PLS-hard problems.

Theorem 4. Finding a jump stable location profile in a symmetric DPG is PLS-complete.

Proof Sketch. The membership in PLS follows as we can use the social welfare as a potential function. In particular, by combining Theorem 1 with the fact that each beneficial jump increases the social welfare, we can find in polynomial time another location profile with higher social welfare or prove the local optimality of a location profile. For PLS-hardness, we provide a reduction from the PLScomplete problem MAXCUT under the FLIP neighborhood [Schäffer and Yannakakis, 1991]. In this problem, we are given a weighted undirected graph G = (V, E, w) with edge weights w : E R>0 and the goal is to find a partition of the vertices (X, V \ X) such that the cut weight P (x,y) E : x X,y V \X w(x, y) cannot be increased by moving a vertex from X to V \ X or vice versa. In our reduction, we map each vertex v V to a vertex agent iv, and we define the ideal distance between all vertex agents ix, iy with {x, y} E by dix(iy) = diy(ix) = 1

2 + w({x,y}) 2 maxe E w(e). Next, we add several auxiliary agents to ensure that the vertex agents can only be located at 0 or 1 in a jump stable location profile. We hence get a partition of the vertices by considering the vertex agents at 0 and 1, and we will show that this partition is locally optimal for MAXCUT under the FLIP neighborhood if and only if the corresponding location profile is jump stable.

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-25)

3.3 Acyclic Distance Preservation Games

As a second escape route to Proposition 1 and Theorem 2, we will next investigate acyclic DPGs. For these DPGs, we show that jump stable location profiles always exist and can be efficiently computed.

Theorem 5. For acyclic DPGs, a jump stable location profile always exists and can be computed in polynomial time.

Proof Sketch. For acyclic DPGs I = N, (Mi)i N, (di)i N there is an order i1, . . . , in over the agents such that Mit {i1, . . . , it 1} for all it N. We iterate through the agents in this order and place each agent it at the optimal position given the locations of the agents i1, . . . , it 1, which are already fixed. An optimal position for it can be found in polynomial time by using Theorem 1. Since it only cares about the agents i1, . . . , it 1 and their position maximizes their utility subject to the positions of these agents, this process indeed finds a jump stable location profile.

4 Welfare Optimality

We now turn to welfare optimal location profiles, which, by definition, always exist. However, as we show next, finding such location profiles is computationally intractable even for some of the simplest classes of DPGs.

Theorem 6. Given a DPG I and value q Q, it is NPcomplete to decide whether there is a location profile A such that SWI(A) q even if I is (i) a path DPG or (ii) an enemies and neutrals DPG.

Proof Sketch. First, for both variants, membership in NP is straightforward as a location profile with sufficient social welfare can be verified in polynomial time. On the other hand, for NP-hardness, we provide two independent reductions. In more detail, for path DPGs, we show NP-hardness by a reduction from BALANCEDPARTITION similar to the one in Theorem 2. Specifically, given an instance of BALANCEDPARTITION with k items, we construct a path DPG with k + 5 agents such that an assignment with a social welfare of k + 4 exists if and only if the partition instance has a solution. For enemies and neutrals DPGs, we provide a reduction from MAXCUT. In this problem, we are given an undirected graph G = (V, E) and a value k, and we need to decide if there is a cut in G with weight at least k. Given such an instance, we construct an enemies and neutrals DPG by using G as the preference graph: for each vertex v V , we introduce an agent iv with Miv = {iu N : {u, v} E} and div(j) = 1 for all j Mi. We then show for enemies and neutrals DPGs that we can assume Ai {0, 1} for each agent i N without decreasing the social welfare. Further, the social welfare of such solutions corresponds to the weight of the partition {v V : Aiv = 0} and {v V : Aiv = 1}.

The reduction for path DPGs shows that it is NP-hard to determine for a DPG whether there is a location profile where every agent i gets the maximum possible utility of |Mi|. Consequently, it is also computationally intractable to find Paretooptimal location profiles or location profiles that maximize

the egalitarian social welfare. Further, our reduction for enemies and neutrals DPGs shows that, for this case, maximizing social welfare is effectively equivalent to solving MAXCUT. Hence, the inapproximability results for MAXCUT carry over to DPGs [Papadimitriou and Yannakakis, 1991; Håstad, 2001], which yields the following corollary. Corollary 1. For enemies and neutrals DPGs, there is no polynomial time algorithm that computes location profiles whose social welfare is guaranteed to be at least 16

17 of the optimal social welfare, unless P = NP.

4.1 Approximation Algorithms Theorem 6 shows that for many interesting DPGs, it is impossible to efficiently compute welfare optimal location profiles. In light of this, we now provide approximation algorithms for computing location profiles with close to optimal social welfare. In particular, we show next that a greedy approach guarantees at least half of the optimal social welfare. Theorem 7. Given a DPG I = N, (Mi)i N, (di)i N , we can compute a location profile A with SWI(A) 1 2 P i N |Mi| in polynomial time.

Proof Sketch. Given a DPG I, we choose an arbitrary order i1, . . . , in over the agents and construct a location profile as follows. First, we place agent i1 at 0. Then, we iterate through our sequence and place each agent it with t > 1 at 0 or 1, depending on which position generates a higher social welfare for the agents i1, , it. We then show that, when the agents i1, . . . , it 1 have already been placed, placing agent it at the better of these two positions generates a welfare of at least 1

2|{i {i1, . . . , it}: it Mi| + 1

2|{i {i1, . . . , it}: i Mit|. From this insight, we infer the theorem since SWI(A) 1 2 Pn ℓ=1 |{i {i1, . . . , iℓ}: iℓ Mi| + |{i {i1, . . . , iℓ}: i Miℓ| = 1

2 P i N |Mi|.

Given the location profile A constructed in the proof of Theorem 7, we can further increase the social welfare by a linear programming approach. For this, let i1, . . . , in be an arbitrary order over the agents such that Ai1 Ain. It is possible to formulate a linear program (LP) that uses the agents positions Bi1, . . . , Bin as variables and maximizes the social welfare subject to the condition that 0 Bi1 Bin 1 (see the extended version [Aziz et al., 2025]). Since the location profile A is a feasible solution for this linear program, the optimal solution A of this LP satisfies that SWI(A ) SWI(A) 1

2 P i N |Mi|. Note that, while this linear program can be used for all orders of the agents, we cannot give a lower bound on its social welfare in general. Additionally to our general approximation, we can obtain better approximation algorithms in many special cases. In particular, in the next theorem, we analyze approximation ratios for the simple DPGs considered in Theorem 6. Theorem 8. The following claims holds: (1) For path DPGs, there is an FPTAS for computing the optimal social welfare. (2) For enemies and neutrals DPGs, there is a polynomial time algorithm that computes location profiles whose social welfare is at least 0.879 of the optimal social welfare.

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-25)

Paths Enemies & Neutrals Acyclic Symmetric General

Jump Stability in P in P in P PLS-complete NP-complete

Welfare Optimality NP-complete FPTAS APX-hard 0.879-Approx. NP-complete 1 2-Approx. APX-hard 1 2-Approx. APX-hard 1 2-Approx.

Table 1: Summary of our results. Each column indicates a subclass of DPGs and the corresponding entries show the computational complexity of finding a jump stable and welfare optimal location profiles as well as our approximation ratios for the optimal social welfare.

Proof Sketch. For enemies and neutrals DPGs, we use the close connection between MAXCUT and finding a welfare optimal location profile. In particular, this connection allows us to apply the approximation algorithm of Goemans and Williamson [1994] for MAXCUT to our setting. For path DPGs, we design an FPTAS by introducing a set of possible locations L = { 0

k, . . . , k

k}. We then show that we can find the location profile A that maximizes the social welfare subject to the condition that A i L for all i N in polynomial time with respect to |N| and k. Specifically, we reduce this problem to finding a longest path in a directed acyclic graph with nk vertices. Moreover, we prove that the social welfare of A is at least 1 2

k times the optimal social welfare, so our algorithm is indeed an FPTAS.

4.2 Price of Anarchy Finally, we relate our results for welfare optimality and jump stability by investigating the price of anarchy of DPGs. The price of anarchy, as suggested by Koutsoupias and Papadimitriou [2009], is the ratio between the optimal social welfare and that of the worst jump stable location profile. To formally define this concept, let JS(I) denote the set of jump stable location profiles for a DPG I. Then, the price of anarchy of a DPG I with JS(I) = is

Po A(I) = max A [0,1]n SWI(A)

min A JS(I) SWI(A) .

We next show that every DPG (that permits jump stable location profiles) has a price of anarchy of at most 2. Consequently, every algorithm for computing jump stable location profiles guarantees at least half of the optimal social welfare.

Theorem 9. It holds that Po A(I) 2 for all DPGs I with JS(I) = . Further, there is a DPG I with JS(I) = and Po A(I) = 2.

Proof. Consider a DPG I = N, (Mi)i N, (di)i N and let A JS(I). We focus on an agent i N and will show that ui(A) |Mi|

2 . For this, we observe that ui(A) ui(Ai7 0) and ui(A) ui(Ai7 1) since A is jump stable. Next, let j denote an agent in Mi. When agent i jumps to 0, we have that ui(Ai7 0, j) = 1 |A(j) di(j))|. Similarly, it holds that ui(Ai7 1, j) = 1 |1 A(j) di(j)|. Next, it can be shown by a case distinction with respect to the absolute values that |A(j) di(j)|+|1 A(j) di(j)| 1, so 1 |A(j) di(j))|+ 1 |1 A(j) di(j)| 1. Applying the same argument for all agents in Mi shows that ui(Ai7 0)+ui(Ai7 1) |Mi|. Since ui(A) ui(Ai7 0) and ui(A) ui(Ai7 1), this means that

2 . Finally, by summing over all agents, it follows that the social welfare of A is at least half of the optimum. Next, to show that our bound on the price of anarchy is tight, let I be a DPG with four agents N = {1, 2, 3, 4} such that M1 = M3 = {2, 4}, M2 = M4 = {1, 3}, and di(j) = 1 for all i N, j Mi. Moreover, let A denote the location profile where A1 = A2 = 0 and A3 = A4 = 1. For each agent i, both agents in Mi are at the opposite ends of the unit interval in A. Thus, all points in [0, 1] yield utility 1 for each agent. Consequently, A is jump stable and SWI(A) = 4. However, in the location profile A with A 1 = A 3 = 0 and A 2 = A 4 = 1, every agent s utility is 2 and SWI(A ) = 8. Hence, Po A(I) = 2.

The proof of Theorem 3 shows that welfare optimality implies jump stability for symmetric DPGs. Thus, for symmetric DPGs, the price of stability, i.e., the ratio between the optimal social welfare and that of the best jump stable location profile [Anshelevich et al., 2008], is 1. In contrast, the price of stability can be arbitrarily close to 2 for general DPGs.

5 Conclusion

We initiate the study of distance preservation games (DPGs) where multiple agents need to choose locations in the unit interval based on their ideal distances to each other. For these games, we examine the existence and computation of both jump stable and welfare optimal location profiles. In more detail, we first show that jump stable location profiles are not guaranteed to exist and that it is NP-complete to decide whether a DPG admits such a location profile. On the other hand, we derive more positive results by focusing on large and realistic subclasses of DPGs, namely symmetric and acyclic DPGs. Specifically, we show for these DPGs that jump stable location profiles always exist and that they can often be computed efficiently. Furthermore, we prove that it is computationally intractable to find welfare optimal location profiles even for severely restricted DPGs. We thus design a 1 2-approximation for the social welfare of general DPGs. Finally, we show that DPGs have a price of anarchy of at most 2. Our work points to several directions for future work. First, we believe it to be worthwhile to study the effect of ideal distances between agents for further settings. For instance, one could also analyze DPGs when assuming a discrete graph or higher dimensional continuous spaces as the topology instead of the unit interval. Another interesting direction is to add additional constraints to DGPs. For example, one could study these games under the condition that there must be a small distance between each pair of agents.

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-25)

Acknowledgments

All authors are supported by an NSF-CSIRO project on Fair Sequential Collective Decision Making". Toby Walsh is supported by an ARC Laureate on Trustworthy AI FL200100204. Hau Chan is supported by the National Institute of General Medical Sciences of the National Institutes of Health [P20GM130461], the Rural Drug Addiction Research Center at the University of Nebraska-Lincoln, and the National Science Foundation under grants IIS:RI #2302999 and IIS:RI #2414554. The content is solely the responsibility of the authors and does not necessarily represent the official views of the funding agencies.

References [Agarwal et al., 2021] Aishwarya Agarwal, Edith Elkind, Jiarui Gan, Ayumi Igarashi, Warut Suksompong, and Alexandros A Voudouris. Schelling games on graphs. Artificial Intelligence, 301:103576, 2021. [Anshelevich et al., 2008] Elliot Anshelevich, Anirban Dasgupta, Jon Kleinberg, Éva Tardos, Tom Wexler, and Tim Roughgarden. The price of stability for network design with fair cost allocation. SIAM Journal on Computing, 38(4):1602 1623, 2008. [Aziz and Savani, 2016] Haris Aziz and Rahul Savani. Hedonic games. In Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D. Procaccia, editors, Handbook of Computational Social Choice, chapter 15. Cambridge University Press, 2016. [Aziz et al., 2024] Haris Aziz, Grzegorz Lisowski, Mashbat Suzuki, and Jeremy Vollen. Neighborhood stability in assignments on graphs. ar Xiv preprint https://arxiv.org/abs/2407.05240, 2024. [Aziz et al., 2025] Haris Aziz, Hau Chan, Patrick Lederer, Shivika Narang, and Toby Walsh. Distance preservation games. ar Xiv preprint, https://arxiv.org/abs/2505.05765, 2025. [Balliu et al., 2022] Alkida Balliu, Michele Flammini, Giovanna Melideo, and Dennis Olivetti. On Pareto optimality in social distance games. Artificial Intelligence, 312:103768, 2022. [Bansal et al., 2004] Nikhil Bansal, Avrim Blum, and Shuchi Chawla. Correlation clustering. Machine learning, 56:89 113, 2004. [Berriaud et al., 2023] Damien Berriaud, Andrei Constantinescu, and Roger Wattenhofer. Stable dinner party seating arrangements. In International Conference on Web and Internet Economics, pages 3 20. Springer, 2023. [Bilò et al., 2022] Davide Bilò, Vittorio Bilò, Pascal Lenzner, and Louise Molitor. Topological influence and locality in swap schelling games. Autonomous Agents and Multi-Agent Systems, 36(2):47, 2022. [Bodlaender et al., 2020] Hans L. Bodlaender, Tesshu Hanaka, Lars Jaffke, Hirotaka Ono, Yota Otachi, and Tom C van der Zanden. Hedonic seat arrangement problems. In Proceedings of the 19th International Conference

on Autonomous Agents and Multi Agent Systems, pages 1777 1779, 2020. [Borg et al., 2018] Ingwer Borg, Patrick J.F. Groenen, and Patrick Mair. Applied multidimensional scaling and unfolding. 2018. [Brânzei and Larson, 2011] S. Brânzei and K. Larson. Social distance games. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI), pages 273 279, 2011. [Bullinger and Suksompong, 2024] Martin Bullinger and Warut Suksompong. Topological distance games. Theoretical Computer Science, 981:114238, 2024. [Bullinger et al., 2021] Martin Bullinger, Warut Suksompong, and Alexandros A. Voudouris. Welfare guarantees in Schelling segregation. Journal of Artificial Intelligence Research, 71:143 174, 2021. [Ceylan et al., 2023] Esra Ceylan, Jiehua Chen, and Sanjukta Roy. Optimal seat arrangement: what are the hard and easy cases? In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, pages 2563 2571, 2023. [Chan et al., 2021] Hau Chan, Aris Filos-Ratsikas, Bo Li, Minming Li, and Chenhao Wang. Mechanism design for facility location problems: a survey. In Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI), pages 4356 4365, 2021. [Deligkas et al., 2024] Argyrios Deligkas, Eduard Eiben, Dušan Knop, and Šimon Schierreich. Individual rationality in topological distance games is surprisingly hard. IJCAI 2024, 2024. [Dunn-Rankin et al., 2014] Peter Dunn-Rankin, Gerald A. Knezek, Susan R. Wallace, and Shuqiang Zhang. Scaling methods. Psychology Press, 2014. [Feldman et al., 2016] Michael Feldman, Amos Fiat, and Iddan Golomb. On voting and facility location. In Proceedings of the 17th ACM Conference on Economics and Computation (ACM-EC), pages 269 286, 2016. [Filos-Ratsikas et al., 2017] Aris Filos-Ratsikas, Minming Li, Jie Zhang, and Qiang Zhang. Facility location with double-peaked preferences. Autonomous Agents and Multi-Agent Systems, 31:1209 1235, 2017. [Garey and Johnson, 1979] Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. [Goemans and Williamson, 1994] Michel X. Goemans and David P. Williamson. .879-approximation algorithms for max cut and max 2sat. In Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, page 422 431, 1994. [Groenen et al., 1998] Patrick J.F. Groenen, Willem Jan Heiser, and Jacqueline Jacinthe Meulman. City-block scaling: smoothing strategies for avoiding local minima. In Classification, Data Analysis, and Data Highways: Proceedings of the 21st Annual Conference of the Gesellschaft für Klassifikation e V, pages 46 53. Springer, 1998.

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-25)

[Håstad, 2001] Johan Håstad. Some optimal inapproximability results. Journal of the ACM (JACM), 48(4):798 859, 2001. [Koutsoupias and Papadimitriou, 2009] Elias Koutsoupias and Christos H. Papadimitriou. Worst-case equilibria. Computer science review, 3(2):65 69, 2009. [Kreisel et al., 2024] Luca Kreisel, Niclas Boehmer, Vincent Froese, and Rolf Niedermeier. Equilibria in schelling games: computational hardness and robustness. Autonomous Agents and Multi-Agent Systems, 38:9, 2024. [Mc Iver, 1981] JP Mc Iver. Unidimensional scaling. Sage, 1981. [Papadimitriou and Yannakakis, 1991] Christos Papadimitriou and Mihalis Yannakakis. Optimization, approximation, and complexity classes. Journal of Computer and System Sciences, 43(3):425 440, 1991. [Pliner, 1996] Vadim Pliner. Metric unidimensional scaling and global optimization. Journal of classification, 13(1):3 18, 1996. [Procaccia and Tennenholtz, 2013] Ariel D. Procaccia and Moshe Tennenholtz. Approximate mechanism design without money. ACM Transactions on Economics and Computation, 1(4), 2013. [Schäffer and Yannakakis, 1991] Alejandro A. Schäffer and Mihalis Yannakakis. Simple local search problems that are hard to solve. SIAM Journal on Computing, 20(1):56 87, 1991. [Xu and Wunsch, 2008] Rui Xu and Don Wunsch. Clustering. John Wiley & Sons, 2008.

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-25)