cs.GTFeb 18, 2026

Control in Hedonic Games

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

Organizations: TU Wien Vienna, Austria

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

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.

Figures & tables

HGNA\mathsf{NA} - AddAg\mathsf{AddAg}NA\mathsf{NA} - DelAg\mathsf{DelAg}PA\mathsf{PA} - AddAg\mathsf{AddAg}PA\mathsf{PA} - DelAg\mathsf{DelAg}GR\mathsf{GR} - AddAg\mathsf{AddAg}GR\mathsf{GR} - DelAg\mathsf{DelAg}
FriHG -{ IR\mathsf{IR} , IS\mathsf{IS} , CS\mathsf{CS} } SYMP\boldsymbol{\mathsf{P}}[T 1 ,T 3 ]imm\boldsymbol{\mathsf{imm}}[ Proposition 2 ]P\boldsymbol{\mathsf{P}}[T 1 ,T 3 ]imm\boldsymbol{\mathsf{imm}}[ Proposition 2 ]W[2]h\boldsymbol{\mathsf{W[2]h}} , XP\boldsymbol{\mathsf{XP}}[ Theorem 4 ]P\boldsymbol{\mathsf{P}}[ Proposition 5 ]
FriHG - NS\mathsf{NS}NPc\mathsf{NPc}( Brandt et al., 2024 ) ,[ Observation 5 ]NPc\mathsf{NPc}( Brandt et al., 2024 ) ,[ Observation 5 ]NPc\mathsf{NPc}( Brandt et al., 2024 ) ,[ Observation 5 ]NPc\mathsf{NPc}( Brandt et al., 2024 ) ,[ Observation 5 ]W[2]h\boldsymbol{\mathsf{W[2]h}} , XP\boldsymbol{\mathsf{XP}}[ Theorem 4 ]P\boldsymbol{\mathsf{P}}[ Proposition 5 ]
SYM\mathsf{SYM}P\boldsymbol{\mathsf{P}}[ Proposition 2 ]imm\boldsymbol{\mathsf{imm}}[ Proposition 2 ]P\boldsymbol{\mathsf{P}}[ Proposition 2 ]imm\boldsymbol{\mathsf{imm}}[ Proposition 2 ]W[2]h\boldsymbol{\mathsf{W[2]h}} , XP\boldsymbol{\mathsf{XP}}[ Theorem 4 ]P\boldsymbol{\mathsf{P}}[ Proposition 5 ]
FriHG -{ IR\mathsf{IR} , IS\mathsf{IS} , NS\mathsf{NS} , CS\mathsf{CS} } DAG\mathsf{DAG}never\boldsymbol{\mathsf{never}}[ Observation 8 ]never\boldsymbol{\mathsf{never}}[ Observation 8 ]never\boldsymbol{\mathsf{never}}[ Observation 8 ]never\boldsymbol{\mathsf{never}}[ Observation 8 ]never\boldsymbol{\mathsf{never}}[ Observation 8 ]never\boldsymbol{\mathsf{never}}[ Observation 8 ]
AddHG - IR\mathsf{IR}NPc\boldsymbol{\mathsf{NPc}}[ Theorem 1 ]imm⋆\boldsymbol{\mathsf{imm}^{\star}}[ Proposition 3 ]NPc\boldsymbol{\mathsf{NPc}}[T 5 ,T 6 ]imm⋆\boldsymbol{\mathsf{imm}^{\star}}[ Proposition 3 ]W[2]h\boldsymbol{\mathsf{W[2]h}} , XP\boldsymbol{\mathsf{XP}}[T 7 ,T 8 ]W[2]h\boldsymbol{\mathsf{W[2]h}} , XP\boldsymbol{\mathsf{XP}}[T 7 ,T 8 ]
DAG\mathsf{DAG} / SYM\mathsf{SYM}P\boldsymbol{\mathsf{P}}[ Proposition 2 ]imm\boldsymbol{\mathsf{imm}}[ Proposition 3 ]NPc\boldsymbol{\mathsf{NPc}}[T 5 ,T 6 ]imm⋆\boldsymbol{\mathsf{imm}^{\star}}[ Proposition 3 ]W[2]h\boldsymbol{\mathsf{W[2]h}} , XP\boldsymbol{\mathsf{XP}}[T 7 ,T 8 ]W[2]h\boldsymbol{\mathsf{W[2]h}} , XP\boldsymbol{\mathsf{XP}}[T 7 ,T 8 ]
Table 1. Complexity results of control in hedonic games, by either adding ( AddAg\mathsf{AddAg} ) or deleting agents ( DelAg\mathsf{DelAg} ), with the goals of ensuring that either a given agent is n ot a lone ( NA\mathsf{NA} ), or a pa ir of agents is in the same coalition ( PA\mathsf{PA} ), or all agents are in the grand coalition ( GR\mathsf{GR} ). We study two compact preference representations–additive preferences ( AddHG ) or friend-oriented preferences in the friends-and-enemies model ( FriHG )–and four stability concepts–individual rationality ( IR\mathsf{IR} ), individual stability ( IS\mathsf{IS} ), Nash stability ( NS\mathsf{NS} ), and core stability ( CS\mathsf{CS} ). All hardness results hold even if no control action is allowed (i.e., k=0k=0 ). Problems with tag “ DAG ” (resp. “ SYM ”) means that the corresponding hardness results hold even if the preference graph is a DAG (resp. symmetric). Entries labeled “ P\mathsf{P} ” denote polynomial-time solvability, “ NPc\mathsf{NPc} ” NP-completeness, and “ Σ2Pc\Sigma^{P}_{2}{c} ” Σ2P\Sigma^{P}_{2} -completeness. “ imm\mathsf{imm} ” means immune and “ imm⋆\mathsf{imm}^{\star} ” means that it is immune while deciding yes-instances with k=0k=0 remains NP\mathsf{NP} -hard. W[2]h\mathsf{W[2]h} and XP\mathsf{XP} are with respect to the budget kk . “ never\boldsymbol{\mathsf{never}} ” means that the given instance is always a no instance. Results in bold are our contributions.
Figure 1. The three possible substructures for an IR\mathsf{IR} coalition containing x{x} and y{y} . The arcs indicate paths of varied lengths. Structure on left corresponds to line 1 , middle to line 1 , and right to line 1 .
Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 2. Illustration of the relevant part of the reduction for Theorem 1 , assuming that S1={1,2,3n^−1}S_{1}=\{1,2,3\hat{n}-1\} and Sj={2,3n^−1,3n^}S_{j}=\{2,3\hat{n}-1,3\hat{n}\} . The remaining negative utilities to x{x} and the negative utilities of the set-agents are omitted in the figure.
Figure 3. Illustration of the relevant part of the reduction for Theorem 3 , assuming that S1={1,2,i}S_{1}=\{1,2,i\} and Sj={2,i,3n^}S_{j}=\{2,i,3\hat{n}\} .
Figure 4. Illustration of the relevant part of the reduction for Theorem 4 , assuming that S1={1,2,i}S_{1}=\{1,2,i\} and Sj={2,i,3n^}S_{j}=\{2,i,3\hat{n}\} . Note that xx has negative edges between all other agents (except yy ) and {s1,…,s3n^},{d1,…,d2n^}\{s_{1},\dots,s_{3\hat{n}}\},\{d_{1},\dots,d_{2\hat{n}}\} form a complete bipartite graph.
Figure 5. Illustration of the relevant part of the reduction for Theorem 5 , assuming that element 11 appears in sets S1,S3S_{1},S_{3} , and S3n^S_{3\hat{n}} .
Figure 6. Illustration of the relevant part of the reduction for Theorem 6 , assuming that element 11 appears in sets S1,S3S_{1},S_{3} , and S3n^S_{3\hat{n}} . Note that not all utilities from the auxiliary-agents dℓd_{\ell} are drawn.
More in this topic

Coalition Formation

See all 13 papers

Explore similar work

CardsList
Feb 24, 2026

Stability Under Valuation Updates in Coalition Formation

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.

Fabian Frank, Matija Novaković, René Romen

Technical University of Munich

Coalition FormationCooperative Game Theory
AskPDF
May 19, 2025

Non-Obvious Manipulability in Additively Separable and Fractional Hedonic Games

Hedonic Games are a well-established model for describing the formation of coalitions. In this work, we considered the design of Non-Obviously Manipulable (NOM) mechanisms, that are mechanisms that bounded rational agents may fail to recognize as manipulable, for two relevant classes of succinctly representable Hedonic Games, namely Additively Separable and Fractional Hedonic Games. In these classes, agents have cardinal scores towards other agents, and their preferences towards different coalitions are determined by aggregating these scores. Moreover, the quality of an outcome can also be easily evaluated through these scores by means of the utilitarian social welfare. We first prove that, when scores can be arbitrary, every welfare-maximizing mechanism is NOM, and, when scores are limited in a continuous interval, then there exist tie-breaking rules making welfare-maximizing mechanisms NOM. Next, we focus on efficient NOM mechanisms, since there is no known polynomial-time algorithm to compute welfare-maximizing outcomes in the considered classes of hedonic games. To this aim, we first prove a characterization of NOM mechanisms that simplifies the class of mechanisms of interest. Then, we design a NOM mechanism returning approximations that essentially match the best-known approximation achievable in polynomial time. Finally, we turn our attention to discrete scores, and specifically, the case that scores are {−x,0,1}\{-x, 0, 1\} for x>0x > 0. We prove that the ability to design welfare-maximizing NOM mechanisms depends on the magnitude of the scores. In particular, for x>1x > 1, we prove that a welfare-maximizing NOM mechanism exists only when xx is very large. For x≤1x \leq 1, instead, we observe that a welfare-maximizing NOM mechanism always exists except when xx lies in the interval [a,b][a, b] where a≈2/n2a \approx 2/n^2 and b≈1/nb \approx 1/n.

Diodato Ferraioli, Maria Fomenko, Giovanna Varricchio

University of Salerno, Italy · University of Calabria, Italy

Cooperative Game TheoryMechanism DesignGame TheorySocial Welfare Maximization
AskPDF
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−1n-1 for AEGs and 2n2n 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.00007591.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 22 admits polynomial-time solvability, whereas bounds of 33 or more yield NP-hardness or unbounded inapproximability.

Marta Pagano, Alexander Schlenga

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

Cooperative Game TheoryGame TheoryApproximation AlgorithmsCoalition Formation
AskPDF