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

Feb 18, 2026

Control in Hedonic Games

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.

Jiehua Chen, Jakob Guttmann, Merisa Mustajbašić +1

TU Wien Vienna, Austria

Coalition Formation Game Theory Cooperative Game Theory

Ask PDF

May 18, 2026

Nash Welfare in Additively Separable Hedonic Games

Additively separable hedonic games (ASHGs) are a prominent model of coalition formation where agents' preferences are derived from their individual valuations of peers. While social welfare maximization in ASHGs has traditionally focused mostly on utilitarian welfare, Nash welfare -- a well-established metric in economics which balances fairness with efficiency and offers scale invariance -- has been entirely overlooked. In this paper, we initiate the study of Nash welfare in ASHGs. We point out desirable properties fulfilled by partitions with high Nash welfare. This includes guaranteed contractual Nash stability in symmetric games, even for any approximation of Nash welfare. This is particularly appealing since, as for other welfare notions, Nash welfare turns out to be NP-hard to maximize, even for the ASHG subclass of symmetric aversion to enemies games (AEGs). A main focus of our study is on approximation algorithms for the Nash welfare objective. We present packing-based algorithms with approximation ratios for well-established subclasses of ASHGs:

n-1

for AEGs and

2n

for appreciation of friends games. This is complemented by a strict inapproximability result showing it is NP-hard to approximate Nash welfare within a factor of

1.0000759

in general ASHGs. Further, we investigate the restricted settings with an upper bound on the coalition size or number of coalitions, and draw the boundary between the cases admitting efficient algorithms and those yielding NP-hardness: bounding the allowed size or number of coalitions by

2

admits polynomial-time solvability, whereas bounds of

3

or more yield NP-hardness or unbounded inapproximability.

Marta Pagano, Alexander Schlenga

Sapienza University of Rome, Italy · Technical University of Munich, Germany

Cooperative Game Theory Game Theory Approximation Algorithms Coalition Formation

Ask PDF

Jun 18, 2026

Exit-and-Join Dynamics for Decentralized Coalition Formation

This paper studies coalition formation as a decentralized dynamical process driven by unilateral exit-and-join decisions. Agents evaluate local moves using the Aumann-Dreze value, so payoffs are computed within the agent's current coalition rather than through a globally negotiated coalition structure. The resulting model links cooperative payoff allocation with noncooperative best-response behavior: a terminal partition is precisely a coalition structure with no admissible, individually profitable exit-and-join deviation. We establish equilibrium characterizations, identify conditions under which the dynamics admit scalar Lyapunov or exact-potential representations, and analyze how switching and acceptance costs shape local stability. Numerical experiments test finite-time stabilization, cost sensitivity, and a special convex-game benchmark.

Quanyan Zhu

Department of Electrical and Computer Engineering New York University Tandon School of Engineering Brooklyn, NY, USA

Cooperative Game Theory Coalition Formation Potential Games

Ask PDF

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