Multi-agent Reinforcement Learning for Decentralized Coalition Formation Games

Kshitija TaywadeAAAI 2021 · DOI

Abstract

This paper investigates the challenge of decentralized coalition formation in environments where agents lack a central coordinator and face spatial constraints. By integrating multi-agent reinforcement learning (MARL) with novel heuristic techniques, the research demonstrates that autonomous agents can learn to form high-utility, stable coalitions. The study evaluates these methods across various simulated environments, including spatial grid worlds and social networks, showing that decentralized agents can achieve near-optimal performance compared to centralized solvers.

Introduction

Coalition formation is a fundamental problem in game theory and multi-agent systems, where agents must group together to maximize collective or individual utility. Traditional approaches typically assume a centralized controller with global knowledge of agent preferences and locations. However, real-world applications—such as autonomous rescue robots, drone swarms, or decentralized labor markets—require agents to operate independently with limited information.

This research addresses the "spatial" dimension of coalition formation, where agents must navigate an environment to discover potential partners. This introduces a cost to information gathering, making the formation process dynamic and uncertain. The paper explores how agents can overcome these challenges using decentralized learning frameworks.

Methodology

The research proposes three primary learning frameworks to facilitate decentralized coalition formation:

1. Decentralized Heuristic Learning and "Budding"

For Additively Separable Hedonic Games (ASHGs), the author introduces a rule-based approach where agents explore a grid-world to identify potential partners. A key innovation is the Budding Technique, which allows agents to "break away" from existing coalitions to form new ones in a locally centralized manner. This mechanism is crucial for helping the system escape local optima and improve overall social welfare.

2. Multi-agent Reinforcement Learning (MARL)

In non-stationary environments where preferences may be complex or incomplete, the paper employs MARL. Agents learn behavioral strategies through trial and error, receiving noisy rewards based on their interactions. This approach is particularly effective for Stable Matching problems, where agents must find partners despite having incomplete information about the broader market.

3. Bayesian MARL for Task Allocation

To handle task allocation—where agents must match specific skills to task requirements—the paper suggests a Bayesian MARL framework. This allows agents to maintain and update a "belief" about the hidden capabilities (efficiency vectors) of their peers, reducing uncertainty over time through repeated interaction.

Experimental Setup

The frameworks were evaluated using several simulated environments:

  • Spatial Grid Worlds: Agents move on a 2D grid, making the cost of finding partners explicit.
  • Small-World and Affiliation Networks: These model social connections and professional agencies where matches are suggested based on network proximity.
  • Baselines: Performance was benchmarked against the Hungarian Algorithm (a centralized optimal solver for matching) and random partitions.

Key Insights and Results

Performance and Efficiency

The decentralized heuristic approach proved surprisingly robust, achieving 84% to 95% of the utility generated by the optimal centralized Hungarian algorithm. This suggests that for many matching problems, decentralized heuristics can provide a high-performing, scalable alternative to computationally expensive centralized solvers.

The Value of Fluidity

The "budding" heuristics (specifically Greedy and Clique Detection) significantly outperformed standard random partitions in ASHGs. The ability for coalitions to be "fluid"—splitting and reforming as agents discover better opportunities—was a primary driver of increased utility.

Stability in MARL

In stable matching scenarios involving incomplete preference lists and ties, the MARL approach consistently yielded stable and fair outcomes. By minimizing "regret cost," the agents learned to reach equilibria where no individual had a strong incentive to deviate from their current group, even without global oversight.

Discussion and Future Work

While the results for matching and hedonic games are promising, the author notes that task allocation remains a significant challenge due to the complexity of matching diverse skill sets to specific requirements. Future research will focus on refining the Bayesian MARL framework to better handle uncertainty regarding agent capabilities. Additionally, scaling these decentralized models to larger, more densely populated environments remains a priority to ensure the methods are applicable to massive multi-agent systems.

Conclusion

This work demonstrates that decentralized agents can effectively learn to form coalitions in spatially-extended environments. By accounting for the costs of information and movement, and by utilizing techniques like budding and MARL, the research bridges the gap between theoretical game theory and the practical requirements of autonomous decentralized systems.

Summary updated

BibTeX
@inproceedings{taywade2021multi,
  author = {Kshitija Taywade},
  title = {{Multi-agent Reinforcement Learning for Decentralized Coalition Formation Games}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i18.17866},
}
Figure