Exploration enhances cooperation in the multi-agent communication system
Authors: Zhao Song, Chen Shen, Zhen Wang, The Anh Han
Organizations: School of Computing, Engineering and Digital Technologies, Teesside University, Middlesbrough, UK · Faculty of Engineering Sciences, Kyushu University, Fukuoka 816-8580, Japan · School of Cybersecurity, and School of Artificial Intelligence, OPtics and ElectroNics (iOPEN), Northwestern Polytechnical University, China
Designing protocols enhancing cooperation for multi-agent systems remains a grand challenge. Cheap talk, defined as costless, non-binding communication before formal action, serves as a pivotal solution. However, existing theoretical frameworks often exclude random exploration, or noise, for analytical tractability, leaving its functional impact on system performance largely unexplored. To bridge this gap, we propose a two-stage evolutionary game-theoretical model, integrating signalling with a donation game, with exploration explicitly incorporated into the decision-making. Our agent-based simulations across topologies reveal a universal optimal exploration rate that maximises system-wide cooperation. Mechanistically, moderate exploration undermines the stability of defection and catalyses the self-organised cooperative alliances, facilitating their cyclic success. Moreover, the cooperation peak is enabled by the delicate balance between oscillation period and amplification. Our findings suggest that rather than pursuing deterministic rigidity, embracing strategic exploration, as a form of engineered randomness, is essential to sustain cooperation and realise optimal performance in communication-based intelligent systems.
Figures & tables
Strategy
Signal ( u )
Resp. to Signal ( p )
Resp. to Silence ( q )
Strategy Description
Strategy Type
ACC
1 (A)
1 (C)
1 (C)
Unconditional Cooperation
Intuitive strategy
ACD
1 (A)
1 (C)
0 (D)
Conditional Cooperation
Deliberative strategy
ADC
1 (A)
0 (D)
1 (C)
Paradoxical Cooperation
Deliberative strategy
ADD
1 (A)
0 (D)
0 (D)
Strategic Defection
Deliberative strategy
NCC
0 (N)
1 (C)
1 (C)
Silent Cooperation
Deliberative strategy
NCD
0 (N)
1 (C)
0 (D)
Conditional Defection
Deliberative strategy
TABLE I : The strategy space defined by the triplet (u,p,q) . u=1 denotes active signalling, u=0 denotes silence. p and q denote the action in a game, responding to a signal or silence, respectively.
Fig. 1 : Two-stage cheap talk game and population structures. (a) The game includes two stage: pre-game communication and in-game decision-making. In each evolutionary update step, a focal player, either explores a new random strategy or learn the strategy from a random role model. (b) Examples of the investigated population structures: square lattice, small-world, random, well-mixed, and scale-free networks.
Fig. 2 : Cheap talk sustains cooperation in the exploration scenarios, with optimal exploration maximising the overall cooperation. Panels (a)-(c) show the frequency of cooperation across parameter sets without and with exploration; panels (d)-(f) show the average frequency and the standard deviation of cooperation as a function of exploration. Shown are the results of independent simulations on lattice, small world, and random networks, respectively and uniformly sampled r∈[0,0.3] , γ∈[0,0.3] , and μ∈[10−5,10−43] .
Fig. 3 : Cheap talk can not sustain cooperation in the absence of network reciprocity, while exploration disturbs cooperation on heterogeneous networks. Panels (a) and (c) show the frequency of cooperation across parameter sets without and with exploration; panels (b) and (d) show the average frequency and the standard deviation of cooperation as a function of exploration. Shown are the results of independent simulations on well-mixed and scale-free networks, respectively and uniformly sampled r∈[0,0.3] , γ∈[0,0.3] , and μ∈[10−5,10−43] .
Fig. 4 : exploration enables the optimal success of cooperative strategies across both intuitive and deliberative types. Panels show the average frequency and the standard deviation of each strategy as a function of exploration on lattice, small world, and random networks, from top to bottom. Shown are the results of 100,000 simulations and randomly sampling from uniform distributions of μ∈[10−5,1043] , r∈[0,0.3] , γ∈[0,0.3] .
Fig. 5 : Moderate exploration maximises cooperation by balancing the amplitude and period of cyclic success. Shown is the time evolution of strategy frequencies starting from a population of full unconditional defection (NDD). exploration lets the phase lag between NDD (purple) → ACD (red) → ACC (blue) → NDC (yellow). Parameters are set as r=0.02 , γ=0.1 , μ=10−5,10−4,10−3,10−2 , and 10−1 from the left column to the right column, respectively.
Fig. 6 : Moderate exploration enables the cooperation alliance of intuitive and deliberative strategies. Panels show the strategy distribution during the evolution process on lattice network. Parameters are set as: r=0.02 , γ=0.1 , and μ=10−3 in the top row, μ=10−1 in the bottom row.
Fig. 7 : Exploration can boost cooperative survival, but it is not a panacea. Panels show the frequency of cooperation as a function of exploration on lattice network. Parameters are set as: r=0.02 in (a), r=0.2 in (b), γ=0.1 in (c), and γ=0.3 in (d).
Multi-agent communication studies how autonomous agents exchange information to coordinate decisions, share knowledge, and act together under constraints.
Multi-agent autonomous exploration is essential for applications such as environmental monitoring, search and rescue, and industrial-scale surveillance. However, effective coordination under communication constraints remains a significant challenge. Frontier exploration algorithms analyze the boundary between the known and unknown regions to determine the next-best view that maximizes exploratory gain. This article proposes an enhancement to existing frontier-based exploration algorithms by introducing a probabilistic approach to frontier prioritization. By leveraging Dirichlet process Gaussian mixture model (DP-GMM) and a probabilistic formulation of information gain, the method improves the quality of frontier prioritization. The proposed enhancement, integrated into two state-of-the-art multi-agent exploration algorithms, consistently improves performance across environments of varying clutter, communication constraints, and team sizes. Simulations showcase an average gain of 10% and 14% for the two algorithms across all combinations. Successful deployment in real-world experiments with a dual-drone system further corroborates these findings.
John Lewis Devassy, Meysam Basiri, Mário A. T. Figueiredo +1
Institute for Systems and Robotics / LARSyS and Instituto Superior Técnico, Universidade de Lisboa, Lisbon 1049-001, Portugal · Instituto de Telecomunicações and Instituto Superior Técnico, Universidade de Lisboa, Lisbon 1049-001, Portugal
Exploration is essential for reliable autonomy in multi-agent systems, yet it remains unclear whether large language model (LLM) agents can explore effectively when interacting with one another. We show that modern LLM agents often fail to do so, exhibiting myopic and polarized interaction patterns that lead to suboptimal coordination and increased regret. We formalize this challenge as the Multi-Agent Exploration problem, modeling it as a partially observable stochastic game (POSG), in which agents must probe peers to infer their capabilities and identify effective interaction strategies. To address this, we introduce Multi-Agent Contextual Exploration (MACE), a lightweight framework that explicitly promotes exploration through structured peer selection. Across both contextual and parametric diversity settings, exploration behavior and downstream task performance substantially improve when MACE is applied. We further provide theoretical insight that MACE achieves a sublinear expected-regret bound. Overall, our results highlight a fundamental limitation of current LLM agents and underscore the importance of explicitly guided exploration for reliable multi-agent autonomy.
Hyeong Kyu Choi, Jiatong Li, Wendi Li +2
University of Wisconsin–Madison · University of California, Santa Barbara
In long-horizon open-world multi-agent systems, existing methods often treat local anomalies as automatic triggers for communication. This default design introduces coordination noise, interrupts local execution, and overuses public interaction in cases that could be resolved locally. To address this issue, we propose a partitioned information architecture for MLLM agents that explicitly separates private execution states from public coordination states. Building on this design, we introduce two key mechanisms. First, we develop an event-triggered working memory based on system-verified outcomes to maintain compact and low-noise local state representations. Second, we propose a cost-sensitive gated escalation mechanism that determines whether cross-region communication should be initiated by jointly considering node criticality, local recovery cost, and downstream task impact. In this way, communication is transformed from a default reaction into a selective decision. Experiments conducted on long-term construction tasks in open environments demonstrate that, compared to baseline models based on strong communication and planned structures, the introduction of gated communication and a partitioned information architecture results in superior performance in terms of blueprint completion quality and execution chain length. It also improves local self-recovery, reduces ineffective escalations, and increases the utility of public communication.
HuaDong Jian, Chenghao Li, Haoyu Wang +4
University of Electronic Science and Technology of China Chengdu, China