Reproduce “Coalition Formation in LLM Agent Networks: Stability Analysis and Convergence Guarantees” on OpenResearch

About this paper

Dongxin Guo, Jikun Wu, Siu-Ming Yiu

A hedonic-game framework for LLM Coalition Formation Games formalizes how language-model agents choose coalition partitions under heterogeneous capabilities, per-capita utility, and coordination costs. The CoalT prompting protocol raises Nash-stable outcomes to 73.2% across 2,400 episodes, compared with 58.4% for vanilla chain-of-thought, while reducing convergence rounds and increasing measured welfare.

Key insights

• Preference consistency is a stronger practical determinant of stability than perfect utility optimization: agents making consistently imperfect choices can still converge, whereas inconsistent choices can produce cycling.
• Heterogeneous coalitions deliver higher welfare through complementary skills, but homogeneous GPT-4 and Claude-3 groups are more stable, exposing a welfare–stability tradeoff.
• The deterministic convergence guarantee applies when preference error is below half the minimum coalition-value gap; for noisier empirical settings, the paper uses a probabilistic analysis based on critical comparisons and logit-style behavior.

Summary by alphaXiv.