Exploration enhances cooperation in the multi-agent communication system

Zhao Song; Chen Shen; Zhen Wang; The Anh Han

cs.MAMar 2, 2026

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

Abstract

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\in[0,0.3]

\gamma\in[0,0.3]

, and

\mu\in[10^{-5},10^{-\frac{3}{4}}]

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\in[0,0.3]

\gamma\in[0,0.3]

, and

\mu\in[10^{-5},10^{-\frac{3}{4}}]

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

\mu\in[10^{-5},10^{\frac{3}{4}}]

r\in[0,0.3]

\gamma\in[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)

\rightarrow

ACD (red)

\rightarrow

ACC (blue)

\rightarrow

NDC (yellow). Parameters are set as

r=0.02

\gamma=0.1

\mu=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$ , $\gamma=0.1$ , and $\mu=10^{-3}$ in the top row, $\mu=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),

\gamma=0.1

in (c), and

\gamma=0.3

in (d).

Multi-Agent Communication

Multi-agent communication studies how autonomous agents exchange information to coordinate decisions, share knowledge, and act together under constraints.

See all 375 papers

Enhancing Multi-Robot Exploration Using Probabilistic Frontier Prioritization with Dirichlet Process Gaussian Mixtures
Apr 3, 2026John Lewis Devassy, Meysam Basiri, Mário A. T. Figueiredo +1Dirichlet Process Mixture Models Multi-Robot Exploration
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
Do Multi-Agent LLMs Explore Each Other?
Jul 13, 2026Hyeong Kyu Choi, Jiatong Li, Wendi Li +2Multi-Agent LLM Systems Multi-Agent Coordination
University of Wisconsin–Madison · University of California, Santa Barbara
Gated Coordination for Efficient Multi-Agent Collaboration in Minecraft Game
Apr 21, 2026HuaDong Jian, Chenghao Li, Haoyu Wang +4Multi-Agent LLM Systems Multi-Agent Collaboration
University of Electronic Science and Technology of China Chengdu, China

Apr 3, 2026J/K move · Enter open · S save

Enhancing Multi-Robot Exploration Using Probabilistic Frontier Prioritization with Dirichlet Process Gaussian Mixtures

John Lewis Devassy, Meysam Basiri, Mário A. T. Figueiredo, Pedro U. Lima

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

Dirichlet Process Mixture Models Multi-Robot Exploration Frontier-Based Exploration Multi-Robot Coordination

Open paper AskPDF arXiv

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.

Abstract

Multi-Agent Communication

Explore similar work

Enhancing Multi-Robot Exploration Using Probabilistic Frontier Prioritization with Dirichlet Process Gaussian Mixtures

Do Multi-Agent LLMs Explore Each Other?

Gated Coordination for Efficient Multi-Agent Collaboration in Minecraft Game