Stability Under Valuation Updates in Coalition Formation

Fabian Frank; Matija Novaković; René Romen

cs.GTFeb 24, 2026

Stability Under Valuation Updates in Coalition Formation

Authors: Fabian Frank, Matija Novaković, René Romen

Organizations: Technical University of Munich

Abstract

Coalition formation studies how to partition a set of agents into disjoint coalitions under consideration of their preferences. We study the classical objective of stability in a variant of additively separable hedonic games where agents can change their valuations. Our objective is to find a stable partition after each change. To minimize the reconfiguration cost, we search for nearby stable coalition structures. Our focus is on stability concepts based on single-agent deviations. We present a detailed picture of the complexity of finding nearby stable coalition structures in additively separable hedonic games, for both symmetric and non-symmetric valuations. Our results show that the problem is NP-complete for Nash stability, individual stability, contractual Nash stability, and contractual individual stability. We complement these results by presenting polynomial-time algorithms for contractual Nash stability and contractual individual stability under restricted symmetric valuations. Finally, we show that these algorithms guarantee a bounded average distance over long sequences of updates.

Figures & tables

	strict	FENGs	FEGs	AFGs	AEGs
X	$\mathbb{Q}\setminus\{0\}$	$\{-1,0,1\}$	$\{-1,1\}$	$\{-1,n\}$	$\{-n,1\}$
NS	NP-c (Th. 9 )	NP-c (Th. 1 )	NP-c (Th. 10 )	NP-c (Th. 10 )	NP-c (Th. 9 )
IS	NP-c (Th. 8 )	NP-c (Th. 1 )	NP-c (Th. 8 )	NP-c (Th. 8 )	NP-c (Th. 9 )
CNS	NP-c (Th. 3 )	NP-c (Th. 1 )	P (Co. 3 )	P (Co. 3 )	P (Co. 3 )
CIS	P (Co. 2 )	NP-c (Th. 1 )	P (Co. 2 )	P (Co. 2 )	P (Co. 2 )

Table 1: Computational complexity of X-1-1-Sym-Altered . The rows indicate the stability notions, and the columns correspond to the allowed valuation values. For X-1-1-Altered , we show throughout the paper that every entry is NP-complete.

Panel of Figure 1 — Figure 1: Illustration of the symmetric ASHG $G$ from the reduction in Theorem 1 . Dotted rectangles are independent sets. All edges that are not shown correspond to a valuation of $0$ . Coalitions in $\pi$ are highlighted in blue.

Panel of Figure 2 — Figure 2: A symmetric FEG where the closest CNS coalition has distance 4. There is an edge between agents $i$ and $j$ if and only if $v(i,j)=1$ . Otherwise, it holds that $v(i,j)=-1$ .

Panel of Figure 3 — Figure 3: An FEG where the closest CNS/CIS partition has distance $n-3$ after altering one valuation of agent $n$ depicted for $n=6$ . There is an arc $(i,j)$ between agents $i$ and $j$ if and only if $v_{i}(j)=1$ . Otherwise, it holds that $v_{i}(j)=-1$ . The original game is on the left and the altered game on the right. Coalitions in $\pi$ and $\pi^{\prime}$ are highlighted in blue.

Panel of Figure 4 — Figure 4: Illustration of $G$ in Theorem 15 . Rectangles are cliques with valuations of $1$ , and edges without an edge weight correspond to valuations of $1$ . Coalitions in $\pi$ are highlighted in blue.

Appendix figures & tables9 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 5 — Figure 5: Illustration of $G$ from the reduction in Theorem 1 . Dotted rectangles are independent sets. All edges that are not shown correspond to a valuation of $0$ . Coalitions in $\pi$ are highlighted in blue.

Panel of Figure 6 — Figure 6: Illustration of $G$ from the reduction in Theorem 2 . Undotted rectangles are cliques, and dotted rectangles are independent sets. There is an edge $\{i,j\}$ if and only if $v(i,j)=\alpha$ . Coalitions in $\pi$ are highlighted in blue.

Panel of Figure 7 — Figure 7: Illustration of $G$ from the reduction in Theorem 3 . Undotted rectangles are cliques with valuations of 1. Dotted rectangles are independent sets. All edges that are not shown correspond to a valuation of $-1$ . Coalitions in $\pi$ are highlighted in blue.

Panel of Figure 8 — Figure 8: Illustration of $G$ from the reduction in Theorem 7 for $X=\text{CNS}$ . Undotted rectangles are cliques, and dotted rectangles are independent sets. There is an arc $(i,j)$ if and only if $v_{i}(j)=\alpha$ . The coalitions in $\pi$ are highlighted in blue.

Panel of Figure 9 — Figure 9: Illustration of $G$ from the reduction in Theorem 7 for $X=\text{CIS}$ . Rectangles are cliques. There is an arc $(i,j)$ if and only if $v_{i}(j)=\alpha$ . The coalitions in $\pi$ are highlighted in blue.

Panel of Figure 10 — Figure 10: Illustration of $G$ from the reduction in Theorem 8 . Undotted Rectangles are cliques, and dotted rectangles are independent sets. There is an edge $\{i,j\}$ if and only if $v(i,j)=\alpha$ . Coalitions in $\pi$ are highlighted in blue.

Panel of Figure 11 — Figure 11: Illustration of the symmetric AEG $G$ from the reduction in Theorem 9 . Rectangles are cliques. There is an edge $\{i,j\}$ if and only if $v(i,j)=1$ . Coalitions in $\pi$ are highlighted in blue.

Panel of Figure 12 — Figure 12: Illustration of the symmetric FEG $G$ from the reduction in Theorem 10 . Undotted rectangles are cliques, and in the dotted rectangle it holds that $v(F,F^{\prime})=1$ if and only if the corresponding sets are disjoint. There is an edge $\{i,j\}$ if and only if $v(i,j)=1$ . Coalitions in $\pi$ are highlighted in blue.

Panel of Figure 13 — Figure 13: Illustration of the symmetric AEG $G$ from the reduction in Theorem 10 . Undotted rectangles are cliques, and in the dotted rectangle it holds that $v(F,F^{\prime})=n$ if and only if the corresponding sets are disjoint. There is an edge $\{i,j\}$ if and only if $v(i,j)=n$ , otherwise the valuation is $-1$ . Coalitions in $\pi$ are highlighted in blue.

Coalition Formation

See all 13 papers

Control in Hedonic Games
Feb 18, 2026Jiehua Chen, Jakob Guttmann, Merisa Mustajbašić +1Coalition Formation Game Theory
TU Wien Vienna, Austria
Nash Welfare in Additively Separable Hedonic Games
May 18, 2026Marta Pagano, Alexander SchlengaCooperative Game Theory Game Theory
Sapienza University of Rome, Italy · Technical University of Munich, Germany
Exit-and-Join Dynamics for Decentralized Coalition Formation
Jun 18, 2026Quanyan ZhuCooperative Game Theory Coalition Formation
Department of Electrical and Computer Engineering New York University Tandon School of Engineering Brooklyn, NY, USA

Feb 18, 2026J/K move · Enter open · S save

Control in Hedonic Games

Jiehua Chen, Jakob Guttmann, Merisa Mustajbašić, Sofia Simola

TU Wien Vienna, Austria

Coalition Formation Game Theory Cooperative Game Theory

Open paper AskPDF arXiv

We initiate the study of control in hedonic games, where an external actor influences coalition formation by adding or deleting agents. We consider three basic control goals (1) enforcing that an agent is not alone (NA); (2) enforcing that a pair of agents is in the same coalition (PA); (3) enforcing that all agents are in the same grand coalition (GR), combined with two control actions: adding agents (AddAg) or deleting agents (DelAg). We analyze these problems for friend-oriented and additive preferences under individual rationality, individual stability, Nash stability, and core stability. We provide a complete computational complexity classification for control in hedonic games.

Abstract

Coalition Formation

Explore similar work

Control in Hedonic Games

Nash Welfare in Additively Separable Hedonic Games

Exit-and-Join Dynamics for Decentralized Coalition Formation