In large-scale distributed systems—whether they consist of unmanned aerial vehicles (UAVs), cognitive radios, or edge computing nodes—agents often need to organize themselves into cooperative teams. For instance, sensors might group together to improve detection accuracy, or data centers might form alliances to manage power grid demands.
Finding the globally optimal grouping (or network partition) is notoriously difficult. From a centralized perspective, evaluating every possible combination of agents is an NP-complete combinatorial problem that fails to scale. Furthermore, in decentralized networks, a central controller may not even exist.
The solution is to turn the optimization problem into a game. By allowing individual agents to make local, autonomous decisions based on their own preferences, the network can self-organize into a stable, highly efficient configuration.
The Hedonic Framework and Local Utilities
To make decentralized grouping tractable, researchers rely heavily on hedonic coalition formation games. The defining feature of a hedonic game is that an agent's utility or satisfaction depends solely on the members of its own coalition. The agent does not care how the rest of the network is partitioned.
As outlined by Walid Saad et al. in Hedonic Coalition Formation for Distributed Task Allocation among Wireless Agents, this localization of utility allows agents to make independent decisions using only local information. For example, a UAV deciding which task group to join only needs to balance its expected data throughput against the physical delay of cooperating with the members of that specific group.
Even when extended to handle external factors like network interference—modeled as games in partition form by Walid Saad et al. in Coalitional Games in Partition Form for Joint Spectrum Sensing and Access in Cognitive Radio Networks—the core mechanism remains driven by localized, preference-based rules. This approach bypasses the need for global coordination, allowing independent entities to form stable groups for resource sharing, as seen in the cloud federation models proposed by Monireh Mohebbi Moghaddam et al. in On Data Center Demand Response: A Cloud Federation Approach.
The Mechanics of Self-Organization: Merge, Split, and Switch
How does a chaotic collection of independent agents actually arrive at a structured partition? The literature converges on two primary types of local dynamics:
- Merge-and-Split Rules: As reviewed comprehensively by Walid Saad et al. in Coalitional game theory for communication networks, nodes can iteratively combine into larger coalitions (merge) if it improves their collective utility, or break apart into smaller ones (split) if the overhead of a large group becomes too high. Zhu Han demonstrates in Coalitional Games for Distributed Eavesdroppers Cooperation in Wireless Networks that even adversarial entities like independent eavesdroppers can use simple merge-and-split rules to autonomously maximize their interception capabilities.
- Individual Switch Rules: Instead of whole groups moving, individual agents can unilaterally migrate. In Single-Agent Dynamics in Additively Separable Hedonic Games, Felix Brandt 0001 et al. analyze how single-agent dynamics allow nodes to transition between groups based on individual utility preferences, providing a combinatorial tool called the Deviation Lemma to map out exactly when these local moves are guaranteed to terminate efficiently.
Why Local Decisions Lead to Global Stability
A critical question arises: why don't these local movements result in infinite loops or chaotic oscillations? The answer lies in the mathematical formulation of the stability criteria, typically Nash stability or Pareto-optimality.
Under a Pareto-order criterion, as applied by Walid Saad et al. in Physical layer security: Coalitional games for distributed cooperation, a structural change (like a merge or split) is only permitted if it benefits at least one node without harming any others. This strict requirement ensures that each step moves the network toward a stable state.
Alternatively, individual switch rules often target a Nash-stable partition. A partition is Nash-stable if no single agent can improve its personal utility by unilaterally moving to another existing group or forming a new one. Alkida Balliu et al. explore this in Nash Stability in Social Distance Games, showing how selfish agents naturally settle into stable communities based on their "social distance" or affinity to others. Because the state space is finite and the rules enforce monotonic utility improvements, these iterative local adjustments naturally converge to a fixed point where no further beneficial moves are possible, as shown by Chen Chen 0107 et al. in Coalition Game based User Association for mmWave Mobile Relay Systems in Rail Traffic Scenarios.
From Physical Networks to Machine Learning
While early applications focused heavily on the physical and network layers of wireless communication—such as collaborative spectrum sensing (Walid Saad et al.), device-to-device fog communities (Junjie Yan et al.), and edge resource pooling (Jie Xu 0001 et al.)—the core intuition has recently migrated into machine learning and optimization.
For example, clustering can be entirely reframed as a hedonic game. In Clustering via Hedonic Games: New Concepts and Algorithms, Gergely Csáji et al. treat data points as rational agents that seek out "friends" (similar points) and avoid "enemies" (dissimilar points). Instead of optimizing a global loss function like variance or modularity, individual points move to clusters that maximize local similarity, often outperforming traditional algorithms like $k$-means.
Similarly, in modern distributed machine learning, Xiaotong Cheng et al. in Parallel Online Clustering of Bandits via Hedonic Game use hedonic games to dynamically cluster users with similar preferences in recommendation systems. In federated learning, Songyang Zhang et al. in DualGFL: Federated Learning with a Dual-Level Coalition-Auction Game and Danni Yang et al. in Decentralized Dynamic Cooperation of Personalized Models for Federated Continual Learning demonstrate that allowing clients to autonomously select their cooperative clusters or edge servers via hedonic frameworks aligns conflicting incentives, minimizes training costs, and stabilizes personalized models over time.
Key Foundational Work
Hedonic Coalition Formation for Distributed Task Allocation among Wireless Agents (2010) — contributed 3 concept elements to this direction.
Coalitional game theory for communication networks (2009) — contributed 2 concept elements to this direction.
Physical layer security: Coalitional games for distributed cooperation (2009) — contributed 2 concept elements to this direction.