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

  1. Stability Under Valuation Updates in Coalition Formation

    Feb 24, 2026Fabian Frank, Matija Novaković, René RomenCoalition FormationCooperative Game Theory

    Technical University of Munich

  2. Non-Obvious Manipulability in Additively Separable and Fractional Hedonic Games

    May 19, 2025Diodato Ferraioli, Maria Fomenko, Giovanna VarricchioCooperative Game TheoryMechanism Design

    University of Salerno, Italy · University of Calabria, Italy

  3. Nash Welfare in Additively Separable Hedonic Games

    May 18, 2026Marta Pagano, Alexander SchlengaCooperative Game TheoryGame Theory

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