Stability Under Valuation Updates in Coalition Formation

1 Introduction

Many real-life applications, such as the formation of study groups, the interaction of robots, or international organizations, are multi-agent systems in which agents have different preferences for the agents they interact with. Coalition formation research is concerned with modeling cooperation in such systems. The objective is to improve the outcome of the agents through coordinated actions. In this paper, we assume selfish agents that aim to maximize their own outcomes, in contrast to cooperative agents that jointly aim to maximize a global objective. Hedonic games [Dr`eze and Greenberg, 1980] provide a general framework for modeling this setting. In these games, agents' preferences are given by complete rankings over their potential coalitions, i.e., all subsets of agents that contain them. The output is a coalition structure where each agent is assigned to a unique coalition. Since each agent can be in an exponential number of different coalitions, this requires ranking an exponential number of coalitions for each agent. A well-studied subclass of hedonic games is additively separable hedonic games (ASHGs) [Bogomolnaia and Jackson, 2002], in which agents' preferences are efficiently encoded in cardinal valuations for other agents and the valuation of a coalition is given by a sum-based aggregation. They have, for example, been used to model the formation of research teams [Alcalde and Revilla, 2004]. Most research in this area focuses on a single game for which a solution is searched.

In many real-life scenarios, however, the game changes in various ways over time, and the solution has to be adapted accordingly. For example, consider a malfunction of an agent that causes other agents to update their valuations towards her once they notice it. Or consider an agent that significantly overperforms, for example, because of updated software, which again leads to other agents updating their valuations towards her. As a third example, consider a group of agents collaborating on a project. Each interaction affects how the teammates value one another.

The starting point of our setting is a stable partition that serves as the status quo in a given game. We then investigate how to respond to valuation updates, with the goal of finding a new stable partition. One approach is to compute a new solution from scratch each time an update occurs. This is reasonable if there are no costs or other negative effects arising from potentially completely rearranging the coalition structure. Nevertheless, in many settings, changing the coalition structure has a negative impact. Consider, for example, a group of agents that works together on a task. Removing too many agents from that project will affect the group's current workflow, and it might take a long time to reach the same level of routine as before. In such settings, finding a close stable partition would be beneficial. We assume a cost proportional to a natural distance measure between the previous and new solution, such that minimizing the distance is equivalent to minimizing the cost. Specifically, we study the distance metric defined as the minimum number of agents that need to change their coalition to arrive from one coalition structure to another [Day, 1981].

We focus on stability, one of the most studied solution concepts for ASHGs [Bogomolnaia and Jackson, 2002; Olsen, 2009; Aziz et al., 2013; Woeginger, 2013; Gairing and Savani, 2019; Brandt et al., 2023; Brandt et al., 2024], and explore four well-known stability notions based on deviations by single agents, namely Nash stability (NS), individual stability (IS), contractual Nash stability (CNS), and contractual individual stability (CIS). In particular, given an initial instance, a stable coalition structure for that instance, and small valuation changes, we study the complexity of finding a nearby stable coalition structure according to our distance function for all four stability notions.

2 Our Contribution

We introduce a model that allows us to study ASHGs under valuation updates. Our focus is on the algorithmic question of how to find a nearby stable partition, given an ASHG, a stable starting position, and valuation changes. For this, we study a general setting in which any agent in group A can update her valuations towards anyone in group B. As a second case, we consider the symmetric setting in which the valuations between agents are symmetric, and where any valuation update of an agent a towards an agent b also applies to b's valuation for a. As important special cases, we consider valuation updates in which all agents change their valuation towards one agent, updates in which one agent changes her valuations towards many agents, and the case that only one agent updates one valuation, or in the symmetric case that only two agents update their valuations for each other.

All of our hardness results hold both for symmetric and non-symmetric valuations. Our positive results, on the other hand, only hold for the symmetric setting.

We prove that checking whether a close stable partition exists is NP-complete for NS, IS, CNS, and CIS, even if we heavily restrict the set of allowed valuation values, such as {-1, 0, 1}. In particular, in Theorem 1 we show that finding a stable partition with distance at most k after a single agent updates her preferences towards one single other agent is NPhard. The same holds in the symmetric setting when only one pair of agents changes their valuation towards each other. Our reductions are from variants of the set cover problem and also show that finding an approximation is computationally hard even for the case when only the valuations {-1, 0, 1} are allowed.

Next, we study the four considered stability notions for strict ASHGs. We show that both the non-symmetric and symmetric problems remain NP-complete for both NS and IS, even under severely restricted valuations. For CIS, we show that there always exists a stable partition with distance at most 3 to the starting partition. For CNS, we give an algorithm that always computes a partition with distance at most 4 under the assumption that valuations can take on only one negative value. In both cases, we give a polynomial-time algorithm that computes such a partition.

The valuation restrictions that we study subsume restrictions proposed by Dimitrov et al. [2006], which are frequently considered in the literature. Table 1 shows an overview of our computational complexity results for the symmetric setting.

Finally, we also consider a sequence of valuation updates and show that in symmetric friend-and-enemy games (FEGs), one can compute a sequence of stable partitions such that the average number of changes is bounded by a constant for all stability notions we consider. Moreover, we extend this result to strict symmetric ASHGs for CNS and CIS. Similar bounds for NS and IS do not hold, which we prove by providing an instance where the average number of changes is linear in the number of agents. In order to evaluate the different settings, we define the average distance dX(n) as the limit of average changes over the worst possible sequence of updates. Notably, dX only depends on the considered stability notion and subclass of games.

3 RelatedWork

Hedonic games have been introduced by Dr`eze and Greenberg [1980] and have since then been extensively studied, especially additively separable hedonic games [Bogomolnaia and Jackson, 2002]. Often, the valuations are also restricted to a limited number of values. Commonly considered restrictions only allow valuations {-1, n}, {-n, 1} [Dimitrov et al., 2006], and {-1, 1}, which distinguish only whether an agent is desired or undesired.

A key challenge in ASHGs is to find stable partitions, meaning that no agent has an incentive to deviate. In the literature, many different notions of stability have been studied, most commonly different versions of core stability [Karakaya, 2011; Woeginger, 2013; Peters, 2017; Peters and Elkind, 2015; Dimitrov et al., 2006] and Nash stability (NS), individual stability (IS), contractual Nash stability (CNS), and contractual individual stability (CIS) [Gairing and Savani, 2019; Peters and Elkind, 2015; Brandt et al., 2024]. In this paper, we focus on the latter ones. For most stability notions, there may not exist a stable partition. The existence decision problem is NP-complete for Nash stability [Olsen, 2009], individual stability [Sung and Dimitrov, 2010], and contractual Nash stability [Brandt et al., 2024]. Ballester [2004] shows that a CIS partition always exists. Aziz et al. [2013] provide a polynomial-time algorithm to find CIS partitions. Peters and Elkind [2015] give an overview and provide a framework for hardness of different stability notions and classes of games. For symmetric ASHGs, there always exists a stable partition for all four stability notions [Bogomolnaia and Jackson, 2002].

Next, we discuss literature on dynamic coalition formation models. First, there are models that study the convergence of deviation sequences to stable states [Bil`o et al., 2022;

Boehmer et al., 2025; Brandt et al., 2024]. Boehmer et al. [2025] show convergence under the assumption that agents increase their valuations for agents that join and decrease their valuations for agents that leave their coalitions. They also consider the question whether a stable partition can be reached from a given partition after k deviations. They show NP-hardness for NS, IS, and CNS for non-symmetric, nonstrict ASHGs. This differs from our setting in that we consider starting partitions that were stable in the original game, and we do not insist on the stable partition to be reachable via deviations.

Brandt et al. [2024] prove that the individual stability dynamics converge with at most one non-negative valuation, and that contractual Nash stability dynamics converge with at most one non-positive valuation. The main difference between our model and these is that the underlying ASHG changes. Second, there are online coalition formation models that allow agents to arrive online and require an algorithm to immediately and irrevocably assign them to a coalition upon arrival [Flammini et al., 2021; Bullinger and Romen, 2023; Bullinger and Romen, 2025]. Bullinger and Romen [2025] show that finding a stable partition online is not possible in most cases, even if they are guaranteed to exist. Finally, Cohen and Agmon [2024] study a model in which agents have incomplete information, i.e., agents are unsure of their preferences and must learn them. In comparison to those papers, our model allows for valuation changes across all agents and for any agent to be reassigned to any coalition.

Another related line of research is based on robustness. Given a stability notion X, Igarashi et al. [2019] study the complexity of deciding whether a game admits an X partition such that it remains stable in any subgame obtained by removing k agents. They study this problem in symmetric games with valuations in {-1, n}, which we also consider. Interestingly, many of their positive results hold for stability notions in which the problems we consider are NP-complete, and their hardness results hold when we can give polynomialtime algorithms for the problems we consider. The key difference between their work and ours is that they aim to find stable partitions that remain stable after k agents disappear, whereas we seek to find new stable partitions that are sufficiently close to the original partition after agents change their preferences.

Barrot et al. [2019] study how unknown agents might affect different stability concepts, and Okimoto et al. [2018] study robustness with respect to the social welfare of each agent.

4 Model

4.1 Hedonic Games

Let N be a finite set of agents. A nonempty subset C ⊆ N is called a coalition. The set of coalitions containing agent i ∈ N is denoted by Ni := {C ⊆ N | i ∈ C}. A set π of disjoint coalitions containing all members of N is a partition of N. For agent i ∈ N and partition π, let π(i) denote the unique coalition in π that i belongs to.

A (cardinal) hedonic game is a pair G = (N, u) where N is the set of agents and u = (ui)i∈N is a tuple of utility functions ui : Ni → Q. Agents seek to maximize utility and prefer partitions in which their coalition achieves a higher utility. Hence, we define the utility of a partition π for agent i as ui(π) := ui(π(i)). The social welfare of G = (N, u) given a partition π is defined as SW(G, π) = ∑i∈N ui(π). We denote by n(G) := |N| the number of agents and write n if G is clear from the context. Following Bogomolnaia and Jackson [2002], an ASHG is a hedonic game (N, u), where for each agent i ∈ N there exists a valuation function vi : N \ {i} → Q such that for all C ∈ Ni it holds that ui(C) = ∑j∈C\{i} vi(j). Note that this implies that the utility for a singleton coalition is 0. Since the valuation functions contain all information for computing utilities, we can also represent an ASHG as the pair (N, v), where v = (vi)i∈N is the tuple of valuation functions. Additionally, an ASHG can be succinctly represented as a complete, directed, weighted graph, where the weights of the directed edges induce the valuation functions.

An ASHG (N, v) is said to be symmetric if for every pair of distinct agents i, j ∈ N, it holds that vi(j) = vj(i). We write v(i, j) for the symmetric valuation between i and j. A complete undirected weighted graph can represent a symmetric ASHG. For simplicity, we also denote this graph by (N, v). An ASHG (N, v) is said to be strict if for every pair of distinct agents i, j ∈ N, it holds that vi(j) ̸= 0. Furthermore, a subclass of ASHGs is (valuation) restricted if it contains only valuations from a set of allowed values. We consider the following classes of restricted ASHGs, friend-and-enemy games (FEGs), friend-enemyand-neutral games (FENGs), appreciation-of-friends games (AFGs), and aversion-to-enemies games (AEGs). They restrict the allowed valuations to {-1, 1}, {-1, 0, 1}, {-1, n}, and {-n, 1}, respectively.

4.2 Stability

Next, we define different types of single-agent deviations and their corresponding stability notions. Assume we are given a hedonic game (N, u), an agent i ∈ N, and a partition π of N. A deviation by agent i is a beneficial move of agent i from one coalition to another. Formally, from partition π a different partition π′ can be reached via a deviation of agent i if for all j ∈ N \ {i} it holds that π(j) \ {i} = π′ (j) \ {i}. A deviation by i is called

• a Nash deviation (NS) if ui(π′ ) > ui(π),
• an individual deviation (IS) if it is a Nash deviation, and for all j ∈ π′ (i) it holds that uj(π′ ) ≥ uj(π),
• a contractual Nash deviation (CNS) if it is a Nash deviation, and for all j ∈ π(i) it holds that uj(π′ ) ≥ uj(π),
• a contractual individual deviation (CIS) if it is an individual deviation and a contractual Nash deviation.

For each type of deviation, we define the respective stability concept as the absence of corresponding deviations. For example, a partition π is said to be Nash stable (NS) if no agent can perform a Nash deviation.

Note that Nash stability implies the other three notions, while both contractual Nash stability and individual stability imply contractual individual stability [Aziz and Savani, 2016]. For every ASHG, there exists a CIS partition

[Ballester, 2004]. This is not the case for the other stability notions, meaning that for each of them, there exists an ASHG without any such stable partition [Bogomolnaia and Jackson, 2002; Sung and Dimitrov, 2007]. However, using a potential function argument, Bogomolnaia and Jackson [2002] show that every symmetric ASHG admits a Nash stable partition.

4.3 Problem Statement

We say that two partitions π, π′ have distance 1 if we can reach π′ from π via a change of coalition for some agent i. Further, we define d(π, π′ ) as the length of a minimal sequence π0, π1, . . . , πs, such that for all t ∈ [s] it holds that d(πt-1, πt) = 1 and π = π0 and π′ = πs. This distance can be computed in polynomial time [Day, 1981, Theorem 9].

In this paper, we are interested in the following problem, where X ∈ {NS, IS, CNS, CIS}.

X-A-B-ALTERED

Input: An ASHG G = (N, v), an X partition π of G, two sets of agents D,E ⊆ N with |D| = A and |E| = B, an updated valuation function v′ such that v′i (j) ̸= vi(j) implies that i ∈ D and j ∈ E, and a distance parameter k ∈ N.

Solution: An X partition π′ of G′ = (N, v′ ), where d(π, π′ ) ≤ k if it exists.

In this paper, we often consider the restricted setting in which A or B equals 1, meaning that either one agent changes her valuation for all other agents or all agents change their valuations for one agent. Additionally, we consider the case of symmetric preferences and define the problem as follows:

X-A-B-SYM-ALTERED

Input: A symmetric ASHG G = (N, v), an X partition π of G, two sets of agents D, E ⊆ N with |D| = A and |E| = B, an updated symmetric valuation function v′ such that v′ (i, j) ̸= v(i, j) implies that i ∈ D, j ∈ E or i ∈ E, j ∈ D, and a distance parameter k ∈ N.

Solution: An X partition π′ of G′ = (N, v′ ), where d(π, π′ ) ≤ k if it exists.

As a consequence of the definition, X-A-B-SYMALTERED and X-B-A-SYM-ALTERED are equivalent. Observe that X-A-B-SYM-ALTERED is not a special case of X-A-B-ALTERED. For the simplest case, note that in X1-1-ALTERED exactly one agent changes her valuation towards one other agent, whereas in X-1-1-SYM-ALTERED two agents change their valuations towards each other. Also, note that if A ≤ A′ and B ≤ B′ , an instance of X-AB-(SYM)-ALTERED is also a valid instance of X-A'-B'- (SYM)-ALTERED. Thus, showing NP-hardness for the former implies NP-hardness for the latter. Finally, we always assume that updates do not affect the subclass of ASHGs. If, for example, we consider FEGs, the updated valuations must also be in {-1, 1}.

5 Results

In this section, we present our results. They are divided into three parts. In the first part, we show hardness results for all four considered stability notions for general ASHGs. In the second part, we restrict our attention to strict ASHGs. Finally, in the last part, we conduct an average-case analysis on the distance for a sequence of valuation updates.

To show NP-completeness, we give reductions from the set cover problem and restricted variants of it, which are known to be NP-complete [Karp, 1972; Garey and Johnson, 1979]. Before we give the reductions, we state two lemmas that guarantee that all problems we consider are in NP and that, if k is fixed, there are only a polynomial number of partitions with distance at most k from the original partition. The proof of Lemma 1 is based on a result of Day [1981]. Both proofs can be found in the full version of the paper, along with all other omitted proofs.

Lemma 1. The distance d(π, π′ ) between two partitions π and π′ can be computed in polynomial time. Moreover, checking whether π is X for X ∈ {NS, IS, CNS, CIS} can be done in polynomial time.

Lemma 2. For any partition π, there exist at most n2k partitions with distance k from π.

The latter lemma directly implies that if k is a fixed constant, we can enumerate all possible coalition structures with distance at most k in polynomial time and can therefore efficiently find a closest stable partition if it exists.

Next, we show that for all stability notions we consider, finding a stable partition after updating only one valuation is already NP-hard if we allow 0-valuations and at least one positive and one negative valuation value.

Theorem 1. Let α, β : N → Q>0 be two polynomial-time computable functions. Then,

• X-1-1-ALTERED and X-1-1-SYM-ALTERED are NPcomplete for X ∈ {IS, CIS} in ASHGs with valuations in {-β(n), 0, α(n)}.
• X-1-1-ALTERED and X-1-1-SYM-ALTERED are NPcomplete for X ∈ {NS, CNS} in ASHGs with valuations in {-β(n), 0, α(n)} if it holds that α(n) ≤ β(n) for all n ∈ N.

Proof sketch. We give a proof sketch for the case α(n) ≤ β(n) and X ∈ {NS, IS, CNS, CIS} for X-1-1-SYMALTERED. The other settings are covered by slight modifications of this argument, which are detailed in the full version of the paper. The proof is based on a reduction from the set cover problem.

Let (E, S, k) be a set cover instance. Without loss of generality, we may assume that k < |E|, |S| and that S is a set cover of E, as otherwise the problem is trivial. Let G be a symmetric ASHG with agent set N = E ∪ S ∪ Y ∪ {z1, z2}, where |Y | = |E| + |S| + 3 (see Figure 1 for an illustration). The valuations of G are given by

• v(e, S) = -β for all S ∈ S and e ∈ S,
• v(z1, e) = α for all e ∈ E,
• v(z2, e) = v(z2, S) = -β for all S ∈ S and e ∈ E,

• v(z1, y) = v(z1, z2) = α for all y ∈ Y ,
• 0 for all other valuations,

where we set α := α(|N|) and β := β(|N|).

It holds that π = {{e}e∈E, {S}S∈S, Y ∪ {z1, z2}} is an X partition in G since no agent can make a Nash deviation.

Alter the valuation between agents z1 and z2 such that v′ (z1, z2) = -β and denote the altered game by G′ . We claim that a set cover C ⊆ S of E with |C| ≤ k exists if and only if G′ has an X partition π′ with d(π, π′ ) ≤ k + 1.

To this end, suppose that C ⊆ S is a set cover of E of size at most k. We claim that π′ = {{e}e∈E, {S}S∈S\C, C ∪ Y ∪ {z1}, {z2}} is an X partition in G′ . To see this, note that ua(π′ (a)) ≥ 0 for all a ∈ N and the only deviations by an agent to another coalition in which she has a positive valuation for at least one other agent are deviations by e ∈ E to π′ (z1). However, no e ∈ E can Nash deviate to π′ (z1) since there is some S ∈ C ⊆ π′ (z1) with e ∈ S and v(e, S) = -β, so ue(π′ (z1)) ≤ α - β ≤ 0. Clearly, it holds that d(π, π′ ) ≤ k + 1.

To prove the reverse direction, suppose that π′ is an X partition in G′ with d(π, π′ ) ≤ k + 1. Note that since v(y, z1) = α and v(y, a) = 0 for all a ∈ N \ {z1}, we have that y ∈ π′ (z1) for all y ∈ Y . Moreover, z2 is in a singleton coalition in π′ since v′ (z2, a) < 0 for all a ∈ N \ (Y ∪{z2}). Let RE and RS denote the agents in E and S that were moved to another coalition from π. Let f : E → S map each e ∈ E to some S ∈ S with e ∈ S. We claim that C := f(RE) ∪ RS is a set cover of E with |C| ≤ k. By assumption, it holds that |RE| + |RS| ≤ k since z2 has moved to another coalition as well. To see that C is a set cover of E, assume for contradiction that there is some e ∈ E that is not covered by C. Hence, by construction of C, there is no S ∈ π′ (z1) with v(e, S) < 0. Therefore, e can X deviate to π′ (z1) since there is no a ∈ π′ (e) with v(e, a) > 0 and no b ∈ π′ (z1) with v(e, b) < 0. This is a contradiction to π′ being X in G′ , so C is in fact a set cover of E.

Due to the one-to-one correspondence of the problem with the set cover problem, we can even show the following statement [Raz and Safra, 1997].

Corollary 1. Approximating X-A-B-SYM-ALTERED better than by a logarithmic factor is NP-hard.

These results paint a rather negative picture. Whenever agents can be indifferent to other agents, allowing one positive and one, in absolute size, larger negative value is sufficient for hardness. In the reduction, the 0-valuations are crucial. Allowing agents to be completely indifferent to whether an agent is in her coalition or not circumvents the restrictions that different stability notions impose. Therefore, in the following, we consider strict ASHGs.

6 Strict ASHGs

The results for IS and NS differ from the results for CNS and CIS. This is because contractual deviations align better with stability and allow for efficient algorithms in some settings. The intuition is that for the contractual notion, for an agent not to have any valid deviation, it is sufficient to have one agent in the same coalition that approves her, whereas for individual stability, we might require an agent in every other coalition that blocks her from deviating.

6.1 CNS and CIS

In this section, we consider CNS and CIS for strict ASHGs. Our negative results hold in both the symmetric and nonsymmetric settings, whereas our positive results require symmetry.

We first prove that even in these restricted settings, X-1-NSYM-ALTERED and X-1-N-ALTERED remain NP-hard for both CNS and CIS.

Theorem 2. X-1-N-ALTERED and X-1-N-SYM-ALTERED are NP-complete for X ∈ {CNS, CIS} in strict ASHGs with valuations in {-β(n), α(n)}, where α, β : N → Q>0 are polynomial-time computable functions.

The theorem shows that finding close stable partitions in the symmetric setting is computationally hard when altering all preferences of an agent, even when only a single positive and negative valuation value exists. In particular, this implies hardness for FEGs, AFGs, and AEGs.

In the following, we again consider the setting in which an agent can only change her valuation for one other agent (or, in the symmetric setting, only one pair of valuations changes). Even in this setting, the problem remains hard for CNS. The reduction is again from set cover.

Theorem 3. CNS-1-1-ALTERED and CNS-1-1-SYMALTERED are NP-complete for strict ASHGs.

The hardness of CNS-1-1-SYM-ALTERED is closely related to the number of singleton coalitions in π since we can compute a CNS partition π′ whose distance to π only depends on the number of singleton coalitions in π.

Theorem 4. For the CNS-1-1-SYM-ALTERED problem in strict ASHGs, Algorithm 1 computes a CNS partition π′ with d(π, π′ ) ≤ 4+ϕ(π)-ϕ(π′ ), where ϕ(π) denotes the number of singleton coalitions in π.

Algorithm 1: CloseCNS

input : A symmetric strict ASHG (N, v), a CNS partition π, and a pair of agents (a, b) together with an altered valuation v′ (a, b).

output: A CNS partition π′ for the altered ASHG.

1 if π(a) = π(b) then 2 for x ∈ {a, b} do 3 if ∃ sx with π(sx) = {sx} and v(x, sx) > 0 then 4 C ← π(x) ∪ π(sx) 5 π ← (π \ {π(x), π(sx)}) ∪ {C} 6 else if x can make a CNS deviation then 7 Let x make a CNS deviation to the largest possible coalition

• 8 Let agents make CNS deviations until no more are possible and denote the resulting partition by π′ 9 return π′

Proof sketch. The proof uses the following two observations about CNS partitions in strict symmetric ASHGs.

• For any two agents s and s′ in singleton coalitions, it holds that v(s, s′ ) < 0 and us(C) ≤ 0 for any C ∈ π with |C| > 1.
• For any agent x with |π(x)| > 1, there must be some y ∈ π(x) with v(x, y) > 0.

Now let the altered valuation be between two agents a and b. We perform a case analysis depending on whether a and b are in the same coalition or not.

Case 1: π(a) = π(b). Without loss of generality, we can assume that v′ (a, b) < 0 as otherwise π is again CNS in G′ . If there is an agent sa (or sb) in a singleton coalition in π with v(a, sa) > 0 (or v(b, sb) > 0), then a (or b) cannot make a CNS deviation after merging their respective coalitions. If either a or b leaves their coalition, then only agents in singleton coalitions can join this coalition by CNS deviations. Due to the first observation, no agent in a singleton coalition can make a CNS deviation to a coalition other than π(a) since π is CNS in G. Since there can be at most two singleton coalitions in π′ that are not in π and at most two agents in non-singleton coalitions can make a CNS deviation in the algorithm, it holds that d(π, π′ ) ≤ 4 + ϕ(π) - ϕ(π′ ).

Case 2: π(a) ̸= π(b). If π is not CNS in G′ , then either a or b is in a singleton coalition. In this case, merging π(a) and π(b) yields a CNS partition π′ with d(π, π′ ) = 1.

Algorithm 1 also works for CIS if, instead of CNS deviations, we consider CIS deviations. However, we can prove a stronger bound on d(π, π′ ) that is independent of ϕ(π) and is based on any sequence of CIS deviations.

Theorem 5. Let G and G′ be strict symmetric ASHGs such that G′ arises from G by altering the valuation between two agents, and let π be CIS in G. Then, any sequence of CIS deviations in G′ starting from π converges to a CIS partition π′ with d(π, π′ ) ≤ 3.

Due to Theorem 5 we can guarantee the existence of a CIS partition with distance at most 3. If we are interested in whether there exists an even closer CIS partition, we can compute all possible partitions with distance 1 and 2 in polynomial time due to Lemma 2 and check whether any is CIS.

Corollary 2. CIS-1-1-SYM-ALTERED can be decided in polynomial time in strict ASHGs.

To prove a constant distance bound for CNS, we need to further restrict the valuations, such that only a constant number of agents in singleton coalitions in π can deviate.

Theorem 6. For CNS-1-1-SYM-ALTERED in strict ASHGs with at most one negative valuation value, Algorithm 1 computes a CNS partition π′ with d(π, π′ ) ≤ 4.

Proof sketch. Let -β denote the negative valuation value. By the proof of Theorem 4, we only need to bound the number of agents in singleton coalitions that make a CNS deviation to π(a) in the case π(a) = π(b). Again, we may assume that v′ (a, b) < 0. At most two agents, namely a and b, can leave π(a) = π(b) by a CNS deviation. Moreover, for any two agents s, s′ in singleton coalitions in π, it holds that v(s, s′ ) = -β < 0 and us(π(a) \ {a, b}) ≤ us(π(a)) + 2β ≤ 2β, where us(π(a)) ≤ 0 since π is CNS in G. Hence, at most two agents in singleton coalitions can join this coalition by a CNS deviation.

As for CIS, we can infer from Theorem 6 that we can find a closest CNS partition efficiently under such valuation restrictions.

Corollary 3. CNS-1-1-SYM-ALTERED can be decided in polynomial time in strict ASHGs with at most one negative valuation value (which includes FEGs, AEGs, and AFGs).

While one can show a similar bound as in Theorem 6 for multiple negative valuation values if they are sufficiently close to one another, this is not possible in general, as Theorem 3 shows.

In the full version of the paper, we give examples that show that the bounds from Theorem 4 and Theorem 6 are tight and that these bounds do not translate to non-symmetric games. In fact, here the distance to the closest CNS/CIS partition can be as large as Θ(n). Hence, it is not surprising that X-11-ALTERED remains NP-hard for X ∈ {CNS, CIS} even in FEGs, AFGs, and AEGs.

Theorem 7. X-1-1-ALTERED is NP-complete for X ∈ {CNS, CIS} in strict ASHGs with valuations in {-β(n), α(n)} for any polynomial-time computable functions α, β : N → Q>0.

6.2 NS and IS

As mentioned, the picture is quite different for NS and IS. We first show NP-hardness for IS if there exists at least one positive and one negative valuation value such that the positive valuation value is at least as large as the absolute value of the negative one.

Theorem 8. IS-1-1-ALTERED and IS-1-1-SYM-ALTERED are NP-complete in strict ASHGs with valuations in {-β(n), α(n)}, where α, β : N → Q>0 are polynomial-time computable functions with α(n) ≥ β(n) for all n ∈ N.

Note that Theorem 8 covers the case of FEGs and AFGs. Using a reduction from Exact Cover by 3-Sets (X3C), we can prove NP-completeness of IS-1-1-(SYM)-ALTERED for the remaining case of AEGs. Since NS and IS are equivalent in symmetric AEGs, this immediately implies the hardness of NS-1-1-SYM-ALTERED. However, we can also utilize this fact to prove hardness for the non-symmetric case.

Theorem 9. X-1-1-ALTERED and X-1-1-SYM-ALTERED are NP-complete for X ∈ {NS, IS} in AEGs.

These results show that X-1-1-(SYM)-ALTERED remains hard even for very restricted settings. However, for Nash stability, we relied on the fact that IS and NS are equivalent in symmetric AEGs to prove hardness. For FEGs and AFGs, this is not possible. Here, one needs to provide a reduction by arguing only about the valuations of each agent, without relying on any single agent blocking others from making a deviation. To this end, we give a reduction from a restricted version of X3C, which allows us to better control how the utilities of agents change after altering the valuation between two of them.

Theorem 10. NS-1-1-ALTERED and NS-1-1-SYMALTERED are NP-complete in FEGs and AFGs.

7 Average Distance of Multiple Updates

In the previous sections, we showed that, in most of the considered settings, deciding whether a close partition exists is NP-hard. In the following, we move away from considering only single updates (in the symmetric setting, this means two agents update their valuation towards each other) and study the case in which a sequence of updates occurs. In this setting, we can prove more positive results. Let G be a subclass of ASHGs in which an X partition always exists, and define G(n) ⊆ G to be all games in the subclass with n agents. Denote by Gm = (G0, . . . , Gm) a sequence of m + 1 ASHGs such that Gi+1 arises from Gi by altering at most one valuation between two agents. Further, let π0 be an X partition in G0. We define the average distance of X as

where πm = (π1, . . . , πm) is a vector of m partitions such that πi is X in Gi. If G is clear from the context, we omit the superscript. First, we note that dGX (n) is in fact well-defined.

Lemma 3. Let X be some stability notion, n ∈ N, and let G be a subclass of ASHGs for which an X partition always exists. Then, dGX (n) exists and is well-defined.

In the previous section, we saw that changing a single valuation in a strict symmetric game might require moving many agents to uphold CNS stability if there are at least two negative valuation values. However, when considering a sequence of updates, Algorithm 1 allows us to find CNS partitions for which we can bound the average distance.

Theorem 11. Let G0, . . . ,Gm be a sequence of strict symmetric ASHGs, where Gi+1 arises from Gi by altering a valuation between two agents, and let π0 be a CNS partition in G0. Then, Algorithm 1 computes partitions π1, . . . , πm, where πi is CNS in Gi, and

Together with Theorem 5, we can show a constant bound on dX(n) for X ∈ {CNS, CIS} in strict symmetric games.

Theorem 12. Let G be the family of strict symmetric ASHGs. Then, it holds that dGCNS (n) ≤ 4 and dGCIS (n) ≤ 3.

Since any CIS deviation is a Pareto improvement, we can prove that dCIS(n) is constant in FENGs in the non-symmetric case.

Theorem 13. In non-symmetric FENGs, it holds that dCIS(n) ≤ 2.

Proof sketch. A deviating agent a increases her utility by at least 1. Furthermore, since it is a CIS deviation, it does not decrease the utility of any other agent. On the other hand, a valuation update can decrease the social welfare by at most 2. Since the social welfare of any partition always lies in {-n(n - 1), . . . , n(n - 1)}, the claim follows.

In the symmetric case, this holds for all stability notions we consider since any Nash deviation in a symmetric FENG increases the social welfare [Bogomolnaia and Jackson, 2002].

Theorem 14. In symmetric FENGs, it holds that dX(n) ≤ 2 for X ∈ {NS, IS, CNS, CIS}.

Finally, we show that for unbounded valuations, the statement no longer holds.

Theorem 15. In strict symmetric ASHGs, it holds that dX(n) ≥ ⌊ n2 ⌋ for X ∈ {NS, IS}.

8 Conclusion

In this paper, we proved the NP-completeness of deciding whether a close stable partition exists in a symmetric ASHG after an agent has changed her preferences for another agent for the stability notions NS, IS, CNS, and CIS. This holds even if the valuations are restricted to {-1, 0, 1}. However, for such restricted valuations and sufficiently long sequences of valuation updates, one can compute a sequence of stable partitions such that the average distance is constant, which shows a clear contrast to the previous hardness result.

In strict symmetric ASHGs, finding a closest stable partition can be done in polynomial time for CIS, and for CNS under the additional restriction that there is only one negative valuation value. Without this restriction, the problem is NPcomplete, but for sequences of valuation updates of length Ω(n), our algorithm computes a sequence of CNS partitions for which the average distance is constant. For NS and IS, the problem remains NP-complete in symmetric FEGs, AFGs, and AEGs.

We analyzed the average distance dX(n) over the worst possible sequence of valuation updates, where dX(n) only depends on the considered stability notion and subclass of games. We showed that dX(n) ∈ Θ(n) for X ∈ {NS, IS} in strict symmetric ASHGs. It is an interesting direction for future research to study how dX(n) behaves for other subclasses of ASHGs and stability notions.

Acknowledgments

• This work was supported by the Deutsche Forschungsgemeinschaft under grant BR 2312/14-1. We thank the anonymous reviewers for their valuable feedback.