# Dynamic Coalition Structure Detection in Natural Language-based Interactions

arXiv: https://arxiv.org/abs/2502.16339 · HTML: https://mlsanity.com/paper/2502.16339/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 41 references that are in the map.
- First posted on arXiv 22 Feb 2025.

## Builds on (most cited first, 9 of 9)

- [Deal or No Deal? End-to-End Learning for Negotiation Dialogues](https://mlsanity.com/paper/1706.05125/) (2017)
- [Improving Language Model Negotiation with Self-Play and In-Context Learning from AI Feedback](https://mlsanity.com/paper/2305.10142/) (2023)
- [Strategic Reasoning with Language Models](https://mlsanity.com/paper/2305.19165/) (2023)
- [Welfare Diplomacy: Benchmarking Language Model Cooperation](https://mlsanity.com/paper/2310.08901/) (2023)
- [No-Press Diplomacy from Scratch](https://mlsanity.com/paper/2110.02924/) (2021)
- [Social Influence Dialogue Systems: A Survey of Datasets and Models For Social Influence Tasks](https://mlsanity.com/paper/2210.05664/) (2022)
- [Modelling Political Coalition Negotiations Using LLM-based Agents](https://mlsanity.com/paper/2402.11712/) (2024)
- [Deceptive Labeling: Hypergames on Graphs for Stealthy Deception](https://mlsanity.com/paper/2004.05213/) (2020)
- [Synthesis of Deceptive Strategies in Reachability Games with Action Misperception (Technical Report)](https://mlsanity.com/paper/2104.11676/) (2021)

## Built on by (most cited first, 3 of 3)

- [A Survey on Hypergame Theory: Modelling Misaligned Perceptions and Nested Beliefs for Multi-Agent Systems](https://mlsanity.com/paper/2507.19593/) (2025)
- [Coalition Formation in LLM Agent Networks: Stability Analysis and Convergence Guarantees](https://mlsanity.com/paper/2604.14386/) (2026)
- [Translating Natural Language to Strategic Temporal Specifications via LLMs](https://mlsanity.com/paper/2606.30441/) (2026)

## Abstract (arXiv)

In strategic multi-agent sequential interactions, detecting dynamic coalition structures is crucial for understanding how self-interested agents coordinate to influence outcomes. However, natural-language-based interactions introduce unique challenges to coalition detection due to ambiguity over intents and difficulty in modeling players' subjective perspectives. We propose a new method that leverages recent advancements in large language models and game theory to predict dynamic multilateral coalition formation in Diplomacy, a strategic multi-agent game where agents negotiate coalitions using natural language. The method consists of two stages. The first stage extracts the set of agreements discussed by two agents in their private dialogue, by combining a parsing-based filtering function with a fine-tuned language model trained to predict player intents. In the second stage, we define a new metric using the concept of subjective rationalizability from hypergame theory to evaluate the expected value of an agreement for each player. We then compute this metric for each agreement identified in the first stage by assessing the strategic value of the agreement for both players and taking into account the subjective belief of one player that the second player would honor the agreement. We demonstrate that our method effectively detects potential coalition structures in online Diplomacy gameplay by assigning high values to agreements likely to be honored and low values to those likely to be violated. The proposed method provides foundational insights into coalition formation in multi-agent environments with language-based negotiation and offers key directions for future research on the analysis of complex natural language-based interactions between agents.