Individual Rationality in Topological Distance Games Is Surprisingly Hard

1 Introduction

You are the coordinator of the annual banquet of your organization and your task is to convince all employees to attend the event. Clearly, a person agrees to show up at such an event, only if they get at least some positive experience from their participation. However, the enmity between grumpyJohn, prickly-Jack, and grouchy-Joe is known to everyone. It should be fairly easy to convince all three of them to attend the banquet if their seats are far away from each other and some friendly people sit between them. Right? As we will see, it is not easy at all.

Situations like the above occur in several other scenarios; think of assigning desks to students, offices to academics, or seats on an assembly line. In such cases, the happiness of a participant depends not only on who are their immediate neighbors and how close their friends are, but also on how far their "enemies" are located. Recently, Bullinger and Suksompong [2024] proposed the elegant framework of topological distance games in order to model such preferences for the agents. In such a game, there is an underlying topology, represented by an undirected graph, where a set of agents needs to be assigned on (a subset of) its vertices. Crucially though, the utility of an agent depends not only on its inherent utility for other agents, but also on the distance from them on the topology.

In this model, Bullinger and Suksompong [2024] studied the existence and the complexity of stable outcomes. More specifically, they have focused on jump stability, i.e., an assignment where no agent has incentives to "jump" to an empty vertex in order to increase their utility. However, they have assumed that the agents actually want to participate in the game, even if there is no way to receive positive utility. For example, imagine a topology with the same number of vertices as the number of agents and two agents that hate each other. Then, although every assignment is jump-stable, arguably these agents would not participate if they had to sit next to each other; it is simply not individually rational.

1.1 Our Contribution

We perform a comprehensive and in-depth study of the complexity of individual rationality (IR) in topological distance games with the aim of identifying the precise cut-off between tractable and intractable classes of instances. IR is "a minimal requirement for a solution to be considered stable" [Aziz and Savani, 2016] and formally states that there exists an assignment that guarantees non-negative utility to every agent. We identify several dimensions of the model - the number of agents, the enmity graph, the distance factor function, and the topology structure - and we sketch the complexity of the problemwith respect to them. Here, the enmity graph is a directed graph that shows which agents are "enemies", i.e., get negative utility from their interaction, and the distance factor function is a monotonically decreasing function that weighs the utility of the agents depending on their distance.

We begin in Section 3 by considering the number of agents as part of the input and we show that ensuring IR in this case is extremely hard, even for very restricted cases; see Figure 1 for a simplified overview of the results of this section. We start our investigation by not imposing any restrictions on the enmity graph and we show that the problem is NPcomplete for every distance factor function, even when the utilities of the agents are symmetric and they have at most 2 different values per agent (Thm. 1). Hence, in order to hope for tractability, we need to restrict the enmity graph. We then show that, if at most one agent has enemies, the problem can be solved in polynomial time (Thm. 2). Unfortunately, this is the best possible, since the problem is NP-complete when there are two arcs in the enmity graph, i.e., there are two agents with enemies (this establishes a dichotomy with respect to the number of arcs of the enmity graph). More specifically, we provide two different reasons for hardness when there are two arcs in the enmity graph: Theorem 3 shows that the problem is hard even when the utilities are symmetric, while Theorem 4 shows hardness for any distance factor function when the two arcs are towards the same vertex and there are two types of utilities. Finally, we show that restricting only the topology does not help us either, as the problem remains intractable even when the topology is a path and there are four types of utilities (Thm. 5).

With the above considerations in mind, in Section 4 we take the number of agents as a parameter; see Figure 2 for a summary of results of this section. Our first result shows that there is an easy XP algorithm for the problem (Thm. 6). However, without any further restrictions, this result is "tight", as the problem is W[1]-complete even with two types of symmetric utility functions (Thm. 7) and, moreover, the running time of the algorithm cannot be substantially improved under the well-known Exponential-Time Hypothesis (ETH).

Next, we show that restricting "just" the topology is not sufficient for tractability, as the problem remains W[1]- complete even on path topology; this is our technically most involved result (Thm. 9). On the positive side though, the problem is in FPT on path topology when the enmity graph has arcs only towards at most one agent (Thm. 10); this combination of structural restrictions seems necessary since the problem becomes W[1]-complete under the enmity graph above for general topologies, even when there are only two types of utilities (Thm. 11).

Due to space constraints, some details are omitted and are available in the full version of the paper [Deligkas et al., 2024b].

1.2 RelatedWork

Topological Distance Games are closely related to many wellknown classes of coalition formation and network games.

The first important source of inspiration includes hedonic games [Dr`eze and Greenberg, 1980], a prominent model in coalition formation. Here, we are given a set of agents together with their preferences, and our goal is to partition them into coalitions. The crucial property of hedonic games is that the agent's utility is based solely on other members of his or her coalition. In general hedonic games, every agent a has preferences over possible coalitions (subsets of agents) containing a. It follows that such preferences cannot be represented succinctly, and therefore many variants with restricted preferences are studied, such as graphical [Peters, 2016; Hanaka and Lampis, 2022], fractional [Aziz et al., 2019; Fanelli et al., 2021], anonymous [Bogomolnaia and Jackson, 2002], or diversity [Bredereck et al., 2019; Ganian et al., 2023b; Darmann, 2023]. The variant that is closest to our setting is hedonic games with additively-separable preferences [Bogomolnaia and Jackson, 2002; Aziz et al., 2013] (ADHGs), where each agent a assigns some value to each other agent b and the utility for agent a is simply the sum of values agent a has for all other agents in its coalition.

The modeling of ADHGs in our model is very straightforward; the topology consists of n cliques, each of size n (or k in the case of fixed-size coalitions [Bil`o et al., 2022c; Li et al., 2023]), where n is the number of agents. It should be noted that achieving individual rationality in ADHGs is trivial: we put each agent into its own coalition.

Closely related are also social distance games [Brˆanzei and Larson, 2011; Kaklamanis et al., 2018; Balliu et al., 2019; Balliu et al., 2022], where our goal is again to partition agents into coalitions. This time, the agents are given together with a topology representing relations between them. Agent's utility with respect to a coalition is then the average of the reciprocal distances to all other agents in this coalition; however, we assume the distances with respect to the subgraph induced by the members of this coalition. Consequently, the role of the topology in social distance games is very different compared to TDGs. Later, [Flammini et al., 2020] generalized social distance games by adding a global scoring vector that allows us to extend the model beyond the reciprocal distance function. This direction was further developed in [Ganian et al., 2023a], who studied the computational complexity of this generalization with respect to multiple stability notions, including individual rationality.

None of the above-mentioned models included the assignment of agents to a topology. In this line of research, very prominent is Schelling's segregation model [Schelling, 1969; Schelling, 1971] and its game-theoretical refinement called Schelling games [Chauhan et al., 2018; Echzell et al., 2019; Agarwal et al., 2021; Kreisel et al., 2022; Bil`o et al., 2022a; Bil`o et al., 2022b; Friedrich et al., 2023; Deligkas et al., 2024a; Bil`o et al., 2023]. Here, we are given a set of agents and a topology, and our goal is to assign agents to the topology in a desirable way. However, in contrast to TDGs, in Schelling games, the agents are additionally partitioned into types, and the utility of each agent is implicitly derived from the fraction of agents of the same type assigned to its neighborhood.

A similar situation, that is, agents' utilities are based solely on their neighbors, also appears in hedonic seat arrangement [Bodlaender et al., 2020; Ceylan et al., 2023; Wilczynski, 2023], where preferences can be more general, or recently introduced refugee housing [Knop and Schierreich, 2023; Schierreich, 2023; Lisowski and Schierreich, 2023], where we additionally have a subset of agents that are initially assigned to some vertices of the topology, and our task is to assign the remaining agents in a sort of IR manner.

2 Preliminaries

For each positive integer i, we define [i] to be the set {1, . . . , i}. For a set S and a positive integer k, we denote by (Sk ) the set of all k-sized subsets of S, and by 2S we denote the set of all subsets of S.

Graph Theory. We follow the standard graph-theoretical notation [Diestel, 2017]. A simple undirected graph G is a pair (V, E), where V is a non-empty set of vertices and E ⊆ (V2 ) is a set of edges. For two vertices u, v ∈ V , we denote by distG(u, v) the length of the shortest path between u and v in the graph G, and we set distG(u, v) = ∞ if there is no u, v-path in G.

Topological Distance Games. We use N to denote the set of agents. Each agent i ∈ N is accompanied with a utility function ui : N → R such that ui(i) = 0. We say that agent j is a friend of agent i if ui(j) > 0. If ui(j) < 0, the agent j is an enemy of the agent i. The enmity graph is a directed graph on the set N of agents such that there is an edge from an agent i to an agent j if and only if j is an enemy of i.

The topology is a simple undirected graph G = (V,E) with at least |N| vertices. An assignment is an injective mapping λ: N → V assigning agents to vertices of the topology. The distance factor function f : N → R>0 is a strictly decreasing function that scales the influence of one agent to another agent based on their distance in the topology. In addition, we define f(∞) = 0. We further extend the utility function for assignments as follows. Given an assignment λ, we define its utility ui(λ) as

Definition 1. An assignment λ is called individually rational if for every agent i ∈ N we have ui(λ) ≥ 0.

Now, we are ready to formally define the computational problem of our interest.

Definition 2. The input of the IR-TOPOLOGICAL DISTANCE GAME problem (IR-TDG for short) is a topology G, a set of agents N, a utility function ui for every agent i ∈ N, and a distance factor function f . The goal is then to decide whether there exists an assignment λ that is individually rational.

Parameterized Complexity. The framework of parameterized complexity [Niedermeier, 2006; Downey and Fellows, 2013; Cygan et al., 2015] gives us formal tools for a finergrained complexity of computational problems that are assumed to be intractable in their full generality. Informally, under this problem, we study variants of intractable problems that are somehow restricted, and this restriction is captured in the so-called parameter k. The ultimate goal is then to invent algorithms such that the exponential blow-up in the running time can be confined to the parameter and not to the input size. In this direction, the best possible outcome is an algorithm running in g(k) · nO(1) time for any computable function g. Such an algorithm is called fixed-parameter algorithm, and FPT is the class of all parameterized problems that admit a fixed-parameter algorithm. Slightly worse, but still positive, is an algorithm running in g(k) · nh(k) time, where g, h are computable functions. The complexity class containing all parameterized problems admitting such algorithms is called XP. One can rule out the existence of a fixedparameter algorithm by proving that the problem of interest is W[1]-hard. This can be shown by a parameterized reduction from some other W[1]-hard parameterized problem. For a more comprehensive introduction to the parameterized complexity, we refer the interested reader to the monograph of [Cygan et al., 2015].

3 Unrestricted Number of Agents

In our first negative result we show that the problem is intractable even if we severely restrict the utilities of the agents.

Theorem 1. For every distance factor function f, it is NPcomplete to decide the IR-TOPOLOGICAL DISTANCE GAME problem even if the utilities are symmetric and every agent uses at most 2 different utility values.

Proof sketch. We provide a reduction from the UNARY BIN PACKING problem [Garey and Johnson, 1979]. The input of this problem is a list S = (s1, . . . , sn) of positive integers given in unary, the number of bins B, and a capacity c of bins. The question is then whether there exist an allocation α: S → [B] such that ∀j ∈ [B] : ∑i∈[n] : α(si)=j si = c.

Given an instance I = (S,B, c) of UNARY BIN PACKING, we construct an equivalent instance J of the IRTOPOLOGICAL DISTANCE GAME problem as follows. We start with the topology G, which is a disjoint union of B cliques C1, . . . ,CB, each of size c. Since all vertices are in distance either one or infinity, the distance factor function f can be arbitrary. For the sake of exposition, we assume that f(1) = 1. Next, we define the agents and the utilities. For every item si ∈ S, we create si agents ai,1, . . . , ai,si . The utility function of these agents is the same and is constructed such that these agents have to be part of the same clique; otherwise, their utility is necessarily negative. Specifically, we set uai,j (aℓ,k) = -1, where i ∈ [n], j ∈ [si], ℓ ∈ [n] \ i, and k ∈ [sℓ], and uai,j (ai,ℓ) = c-si si-1 , where i ∈ [n] and j, ℓ ∈ [si]. The utilities are indeed symmetric, and every agent uses 2 different values in the utility function. One can now verify that the two instances are indeed equivalent and that the reduction runs in polynomial time.

Then, we prove that the problem is tractable when there is at most one agent that has enemies.

Theorem 2. If there is at most one agent p assigning negative utility to other agents, the IR-TOPOLOGICAL DISTANCE GAME problem can be solved in polynomial time for any distance factor function f.

Proof sketch. Let there be at least one arc in the enmity graph. We can split the agents into two sets N + and N - according to the utility the agent p has for them. Then, we try all possible assignments of agent p to the topology, and for every possibility, we do the following. Let v be the vertex the agent p is assigned in the currently examined possibility. We run the Breadth-first search algorithm starting with the vertex v to find a BFS-tree T . Now, we do a level order traversal of the tree T , and for each vertex u of T , we assign to u an agent i ∈ N + that was not assigned before, and the agent p has for it the highest utility between all agents in N +. As the final step, we assign the agents from N -. This is again done by the level-order traversal with the following differences. The traversal is done from the deepest level, and the agents are assigned according to the increasing utility that the agent p has for them. If, for this assignment, the utility of i is nonnegative, we return yes and exit the algorithm. Otherwise, we will continue with another possibility. If no possibility leads to an individually rational assignment, we return no.

In our next result, we show that a single arc in the enmity graph (cf. Theorem 2) is basically the only restriction that makes the problem tractable. Specifically, in our next result, we show that if there are two arcs in the enmity graph, the problem becomes intractable.

The NP-hardness is proven via a reduction from the EQUITABLE PARTITION problem [Garey and Johnson, 1979]. In fact, we start with this problem in Theorems 4 and 5 as well. In this problem, we are given a list S = (s1, . . . , s2n) of 2n positive integers such that ∑i∈[2n] si = 2k, and the goal is to decide whether there exists a set I ⊆ [2n] of size n such that ∑i∈I si = ∑i∈[2n]\I si = k. Without loss of generality, we can assume that minS ≥ n2 and that for any i, j ∈ [2n] we have |si - sj| ≤ minS n2 [Deligkas et al., 2024c]. In particular, this means that for any J ⊆ [2n] with |J| < n, we have ∑i∈J si < k.

Theorem 3. For every distance factor function f, it is NPcomplete to decide the IR-TOPOLOGICAL DISTANCE GAME problem even if the enmity graph contains only two arcs and the utilities are symmetric.

Proof sketch. Given an instance S of the EQUITABLE PARTITION problem, we construct an equivalent instance J of the IR-TOPOLOGICAL DISTANCE GAME problem as follows. First, we construct the topology G. At the beginning, we create a complete bipartite graph Kn,n with two parts L and R. Then, we add a vertex vℓ, which is connected with all vertices of the part L, and a vertex vr, which is connected with all vertices of the part R. The set of agents consists of 2n element-agents, each corresponding to one element of the set S, and two guard-agents g1, g2. The idea behind the construction is that the guards hate each other, and the only way to make their utility non-negative is to assign to vertices vℓ and vr, respectively, and to partition the element-agents between two parts of Kn,n such that utility the agents g1 and g2 gain from neighboring agents is exactly k. To ensure this, we define the utilities as follows. Let f be an arbitrary but fixed distance factor function. For the guard-agents, we set ug1 (g2) = ug2 (g1) = -(k + f(2) f(1) · k)/f(2). Next, let si, i ∈ [2n], be an element-agent. We set ug1 (ai) = ug2 (ai) =

uai (g1) = uai (g2) = si f(1) . The remaining utilities, that is, between element-agents, are zero.

Next, we show that the problem remains hard even if the enmity graph consists of two arcs pointed towards the same agent; in other words, if we ignore isolated vertices, the enmity graph is an in-star with two arcs.

Theorem 4. For any distance factor function f, it is NPcomplete to decide the IR-TOPOLOGICAL DISTANCE GAME problem, even if there are only two arcs in the enmity graph and both of them are directed towards the same agent.

Our last result of the section shows that even restricting the topology to a path does not surprisingly suffice for tractability.

Theorem 5. It is NP-complete to decide the IRTOPOLOGICAL DISTANCE GAME problem, even if there are only three arcs in the enmity graph, all of them are directed towards the same agent, and the topology is a path.

Proof sketch. Given an instance S of EQUITABLE PARTITION with 2n integers, we construct an equivalent instance J of the IR-TOPOLOGICAL DISTANCE GAME problem as follows. Recall that we assume that for any I ⊆ [2n] such that |I| ≤ n - 1, we have ∑i∈I si < k.

The topology of J is a path P = (v1, v2, . . . , v2n+4) on 2n + 4 vertices. The set of agents N also contains 2n + 4 vertices, split into:

• one trouble-maker t;
• three grumpy agents g1, g2, g3;
• 2n element-agents a1, a2, . . . , a2n.

The idea is that only negative utilities are set from the three grumpy agents towards the trouble-maker. To balance it, the grumpy agents will have positive utility towards the element agents that depend on which element the given agent represent. The most animosity is from g3 towards t and the function f is carefully crafted, so that g3 and t are at the opposite sides of P and g3 needs n element-agents, at distance at most n each, representing elements with total sum at least k to balance the negative contribution of t. The second most animosity is from g2 towards t, crafted that g2 needs to be at distance at least n+2 from t and when it is at distance exactly n+2, then g2 needs all the element-agents at distance at most n to balance its animosity towards t. Finally, this will fix g1 exactly next to t and to balance its animosity towards t, we need n element-agents, at distance from g1 at most n each, representing elements with total sum at least k to balance the negative contribution of t.

4 Parameter-Many Agents

In the previous section, we have established strong intractability results for the problem when the number of agents is part of the input. For this reason, in this section, we follow the parameterized complexity paradigm and we consider |N| to be a parameter of the problem; Figure 2 provides a mind-map of our results. Note that parameterization by the number of agents has been successfully used to give fixed-parameter algorithms for various hard problems in computational social choice; see, e.g., [Bredereck et al., 2020; Deligkas et al., 2021; Ganian et al., 2023c].

Our first result is a brute-force algorithm that finds an individually rational assignment (if one exists) in XP time. In other words, the IR-TDG problem is solvable in polynomial time if the number of agents is a fixed constant.

Theorem6. There is an algorithm for the IR-TOPOLOGICAL DISTANCE GAME problem running in |V (G)|O(|N|) time.

Proof. The algorithm is a simple brute-force. We exhaustively try all assignments of vertices of the topology to agents. Then, in polynomial time, we verify whether the checked possibility assigns to each agent a different vertex and whether the assignment is individually rational. If this is the case, we return yes as the result. Otherwise, if no possibility leads to an individually rational assignment, we return no. The algorithm is trivially correct as it checks all possible assignments. Additionally, there are V (G)O(|N|) possible agents-vertices assignments, and for each assignment, the verification of the uniqueness of the vertices and of the individual rationality can be performed in polynomial time. Therefore, the overall running time is |V (G)|O(|N|) .

Now, the natural question arises. Is the XP algorithm of Theorem 6 the best we can hope for, or is there an FPT algorithm for the problem? We resolve this question in negative in our next result.

Theorem 7. For every distance factor function f, it is W[1]- complete to decide the IR-TOPOLOGICAL DISTANCE GAME problem parameterized by the number of agents |N|, even if the utilities are symmetric, the utility function uses two different values, and there are only two types of agents.

Proof. We provide a parameterized reduction from the INDEPENDENT SET problem, which is very well-known to be W[1]-complete when parameterized by the solution size k [Downey and Fellows, 1995]. Let I = (H, k) be an instance of the INDEPENDENT SET problem. We construct an equivalent instance J of the IR-TOPOLOGICAL DISTANCE GAME problem as follows.

First, the topology G is just a copy of the graph H with one added apex vertex x. The set of agents consists of k standard agents a1, . . . , ak and a single guard agent g. Next, let β ∈ R>0 be a number. We fix an arbitrary distance factor function f. Finally, we define the utilities. For every pair of distinct standard agents ai, aj ∈ N, we set uai (aj) = uaj (ai) = -β and uai (g) = ug(aj) = (k-1)·f(2)·β f (1) . There are two types of agents, and the utilities are symmetric.

Consequently, if we parameterize only with the number of agents, an FPT algorithm cannot exist (unless FPT = W[1]). What is even more disturbing is that the simple brute-force algorithm proposed in Theorem 6 is, under standard theoretical assumptions, asymptotically optimal.

Theorem 8. Unless ETH fails, there is no algorithm solving the IR-TOPOLOGICAL DISTANCE GAME problem in g(|N|)· |V (G)|o(|N|) -time for any computable function g.

The previous results clearly indicate that, in order to reveal at least some tractability, we need to further restrict the input instances. We start with a very strong intractability result, which shows that when the distance factor function remains unrestricted, there cannot be an FPT algorithm with respect to the number of agents, even under the severe restriction of having a path topology. The proof is based on a reduction from the PARTITIONED SUBGRAPH ISOMORPHISM problem (PSI for short). Here, we are given two undirected graphs G and H with |V (H)| ≤ |V (G)| (H is smaller) and a mapping ψ: V (G) → V (H). The question is whether H is isomorphic to a subgraph of G? I.e., is there an injective mapping ϕ: V (H) → V (G) such that {ϕ(u), ϕ(v)} ∈ E(G) for each {u, v} ∈ E(H) and ψ ◦ ϕ is the identity?

Theorem 9. IR-TOPOLOGICAL DISTANCE GAME is W[1]- complete parameterized by the number of agents, even if the topology is a path. Unless ETH fails, there is no algorithm solving the IR-TOPOLOGICAL DISTANCE GAME problem in g(|N|) · |V (G)|o( |N| log |N| ) -time for any computable function g.

Proof sketch. We showW[1]-hardness by a parameterized reduction from the PARTITIONED SUBGRAPH ISOMORPHISM problem, which is known to be W[1]-complete when parameterized by the solution size k even on 3-regular graphs. Furthermore, there is no algorithm A and function g such that A correctly decides every instance of PSI with the smaller graph H being 3-regular in time g(|V (H)|)no(|V (H)|/ log |V (H)|) , unless ETH fails (see [Marx, 2010] and [Eiben et al., 2019]). Let (G,H, ψ) be an instance of PSI with H 3-regular and denote k = |V (H)|. Note that the mapping ψ: V (G) → V (H) partitions the vertices of V (G) into x = |V (H)| many parts V1, . . . , Vx, each corresponding to a specific vertex of H. Moreover, we wish to select in each part Vi, i ∈ [x], exactly one vertex vi, such that if vw ∈ E(H) and Vi corresponds to v and Vj corresponds to w, then vivj is an edge in G. Notice that if vw /∈ E(H), then the edge in vivj is not required to be in E(G), however, it is also not forbidden. Hence we can, without loss of generality, assume that G does not contain edges between Vi and Vj if these two vertex sets correspond to vertices in H that are not adjacent. It follows that we can also partition the edges of E(G) into y = |E(H)|

many parts E1, . . . , Ey, each corresponding to a specific edge of H. This is important, because, as is usual for a reduction from PSI, we will have a "gadget" to select a single vertex in each Vi, a gadget to select an edge in each Ej , and then a way to check that this selection is consistent.

We will now construct an equivalent instance J of the IR-TOPOLOGICAL DISTANCE GAME problem such that the topology of J is a path on |V (G)|O(1) many vertices. A very crude idea of this reduction is to assign each of the vertexparts Vi, i ∈ [x], and each of the edge-parts Ej, j ∈ [y] an interval on the path such that these intervals are disjoint. Then using two additional "guard" vertices placed at the endpoints of the path, O (|V (H)| + |E(H)|) many so-called "anchor" vertices, and a clever choice of the function f, we force each of the intervals to contain exactly two consecutive vertices at some "allowed" positions inside the interval, that represent a selection of specific edge or vertex in this interval. Finally, using basically the same trick we used to force the "allowed" consecutive vertices in a selection gadget to be only at specific positions - specific distances from an "anchor" vertices - we are able to force that the selected vertices vi ∈ Vi and the selected edges ej ∈ Ej are consisted, i.e., if Ej is associated with an edge of H whose one endpoint is the vertex associated with Vi, then vi is an endpoint of ej. It is important that the intervals for these selection gadgets are placed carefully and all the distances for which we need to set up the value of f are different.

Now let us go a bit more into detail. For ease of notation let n = |V (G)|, m = |E(G)|. We let the topology of J be the path P on 40mn vertices.

The set of agents N consists of the following.

• Two guard agents g1, g2, these will be placed at the endpoints of P and the intervals for "selector" gadgets will be defined by their distance from g1.
• A "dummy" agent d2 to make g2 "happy" if g1 is at the other endpoint and d2 exactly next to it.
• x = |V (H)| many "vertex-selector" pairs of agents vi,wi, i ∈ [|V (H)|]. The idea is that vi represents the selection of the vertex in Vi and wi is a helper agent that fixes vi in the interval for Vi.
• y = |E(H)| many "edge-selector" pairs of agents ej, e′j , j ∈ [|E(H)|]. Again ej represents the selection of an edge in Ej and e′j is the helper agent to fix ej in the interval of P selected for Ej .
• x + y many "anchor" pairs of agents ai, bi i ∈ [x + y]. These are designed such that ai is at the start of each "selector" gadget, and we use them together with the distance factor function f to force the selector-pair to occupy only a specified subset of vertices inside the selector gadget. The agent bi is again a "helper" agent that will be placed next to ai.

We will now describe how we set the distance factor function f and how the utilities of the agents are defined. We remark that if we do not define a utility ui(j) of an agent i toward agents j, then we assume that ui(j) = 0. The function f is such that for any d ∈ {1, . . . , |V (P)| - 1} we have f(d) = 2pd(n) - qd, where 0 ≤ qd < d and n3 ≥ pd(n) ≥ n3 - 7n2 . In addition, steps from d to d + 1 in the function f are always one of the following four types: (i) f(d + 1) = f(d) - 1, (ii) f(d + 1) = 2pd(n)-1 , (iii) f(d+1) = 2pd(n)-1 -qd, and (iv) f(d+1) = 2pd(n)-n . We start with f(1) = 2n3 and f(2) = 2n3-n . Unless we specify otherwise, we have f (d + 1) = f (d) - 1.

To fix g1 and g2 to be at the endpoints of P, we set ug2 (d2) = 1, ug2 (g1) = - f(1) f(|V (P)|-1) and letting utility of g2 towards any other agent to be 0. After this is done, we can fix each of the remaining agent-pairs to specific intervals of distances from g1 by setting only the utility of the helperagent in the pair towards g1, g2, and its partner and using a type-(iv) step to force some minimum distance from g1 and from g2 and use a sequence of type-(i) steps to make sure that the partner has to be next to the helper independently where inside the interval the helper is.

In order to fix a vertex-selector pair (vi, wi) in only the subset of allowed positions, we set the utility of its anchor ai as uai (vi) = 1 and uai (vi) = -2 and use the type-(iii) steps in the distance function to indicate allowed positions and type(i) steps to indicated forbidden positions. This allows us to have distinct distance for each pair of an allowed position for a vertex and an allowed position for an edge.

Finally, since distances between allowed vertex-agent positions and allowed edge-agent positions are distinct, we can use the exactly same trick to force that the selection of edges and the selection of vertices is consistent by setting the utilities of the vertex-agent vi. The important thing to notice here is that since we are keeping f(d) = 2n3-O(n2 ) + qd, where qd ≤ d, the negative contribution of inconsistent selection cannot be balanced by having all the remaining connections for particular vertex consistent.

On the other hand, if we additionally restrict the enmity graph, we finally obtain fixed-parameter tractability. Namely, if we parameterize by the number of agents, the topology is a path, and all edges in the enmity graph are oriented towards a single agent, the problem becomes tractable.

Theorem 10. For any distance factor function f, if all the edges in the enmity graph are oriented towards one agent p and the topology is a path, then the IR-TOPOLOGICAL DISTANCE GAME problem is in FPT parameterized by the number of agents N.

Proof sketch. Let the graph be a path P = {v1, . . . , vn}, where n is the number of vertices. As the first step of our algorithm, we set λ(p) = vn. Next, we guess the ordering π: N \ {p} → [|N| - 1] of the vertices on the path. Now, for every i ∈ [|N| - 1], we set λ(π-1 (i)) = vi. For the correctness, we show that if there exists an individually rational solution λ′ , then there also exists an individually rational solution λ where agents in N \ {p} are assigned only to vertices v1, . . . , v|N|-1 and p is assigned to vn.

The algorithm in the previous theorem heavily relies on the special path topology. In our next result, we show that this restriction is necessary for tractability; if we allow for an unrestricted topology, the IR-TDG problem again becomes hopelessly intractable.

Theorem 11. For every distance factor function f, if all edges of the enmity graph are oriented toward one agent, then the IR-TOPOLOGICAL DISTANCE GAME problem is W[1]- complete parameterized by the number of agents N, even if there are only 2 types of agents and the utility function uses three different values.

Proof sketch. We show W[1]-hardness by a parameterized reduction from the CLIQUE problem, which is known to be W[1]-complete when parameterized by the solution size k [Downey and Fellows, 1995]. Let I = (H, k) be an instance of CLIQUE. We construct an equivalent instance J of the IR-TOPOLOGICAL DISTANCE GAME problem as follows.

The topology G is the graph H with added apex vertex c with a pendant p. By this tweak, every pair of vertices is now in distance 1 or 2. The set of agents N consists of k selection agents a1, . . . , ak and a single guard agent g. Next, we define the utilities. For the guard agent, we set ug(ai) = 0 for every i ∈ [k]. Next, each selection agent ai receives negative utility from the guard agent and positive utility from other selection agents. The utilities are set so that the guard agent has to be in distance 2 and the selection agents have to form a clique. Otherwise, a selection agent with fewer than k - 1 direct neighbors would have negative utility. Specifically, we set uai (g) = -β and uai (aj) = f(2)·β f(1)·(k-1) , where β ∈ R≥0 is a fixed constant. As utility functions for selection agents are the same, there are clearly only two types of agents. It is also easy to see that utilities use only 3 different values, namely 0, β, and f(2)·β f (1)·(k-1) .

5 Conclusions

This paper studied the complexity of finding individually rational solutions in topological distance games, which is arguably one of the most fundamental stability notions. Albeit this class of games can capture a plethora of models, its versatility comes with the drawback of strong intractability results even for very restricted cases, at least from the theoretical point of view. As our results reveal, individual rationality is hard to be assured even if someone resorts to the parameterized complexity regime. However, our results do not imply parameterized-complexity hardness for jump stability. We strongly believe that this avenue deserves further study.

At a different dimension, our results indicate that following a worst-case point of view is not sufficient for tractability. This makes someone wonder, whether there exist some natural values for the parameters of the model that ensure IR in practice. If not, does individual rationality even exist?

Acknowledgments

This work was co-funded by the European Union under the project Robotics and advanced industrial production (reg. no. CZ.02.01.01/00/22 008/0004590). AD acknowledges the support of the EPSRC grant EP/X039862/1. ˇSS acknowledges the additional support of the Grant Agency of the CTU in Prague, grant No. SGS23/205/OHK3/3T/18.