Control in Hedonic Games
New study reveals how to control AI agent teams by adding or deleting members to achieve specific goals.
A team of computer scientists has published a foundational paper, 'Control in Hedonic Games,' that formally analyzes how to manipulate groups of AI agents by strategically adding or removing members. The research, led by Jiehua Chen, Jakob Guttmann, Merisa Mustajbašić, and Sofia Simola, will be presented at AAMAS 2026. It introduces a formal framework for an external actor to influence how self-interested agents form coalitions, a core problem in multi-agent systems (MAS).
The study examines three specific control goals: preventing an agent from being alone (NA), forcing a specific pair of agents to work together (PA), and herding all agents into a single, grand coalition (GR). To achieve these, the controller can take one of two actions: adding new agents (AddAg) or deleting existing ones (DelAg). The researchers analyzed these scenarios for common preference structures—friend-oriented and additive preferences—under four classic stability concepts from game theory: individual rationality, individual stability, Nash stability, and core stability.
The key technical contribution is a complete computational complexity classification for all combinations of goals, actions, and stability concepts. This map tells system designers which control problems are computationally tractable (solvable in polynomial time) and which are intractable (NP-hard), guiding the design of practical algorithms. The work provides a rigorous mathematical foundation for predictable orchestration in systems where AI agents must collaborate, such as robotic fleets, decentralized task allocation, or automated supply chains, moving beyond simple optimization to managing strategic, self-interested behavior.
- Formalizes control of AI coalitions via adding/deleting agents for three goals: preventing isolation, forcing pairs, or creating a single team.
- Provides complete complexity classification for friend-oriented and additive preferences under four stability concepts (individual, Nash, core).
- Establishes a foundational framework for predictable orchestration in multi-agent systems like autonomous fleets and resource networks.
Why It Matters
Provides a formal framework for reliably orchestrating teams of strategic AI agents in real-world systems like logistics and robotics.