Information Sharing Under Costly Communication in Joint Exploration

Igor Rochlin, David SarneAAAI 2013 · DOI

Introduction

In multi-agent systems, the group's overall performance is often limited by its "weakest link"—the minimum value achieved by any single agent. This paper investigates how agents should balance the benefits of sharing information against the literal costs of communication in such "bottleneck" scenarios. The authors derive optimal, threshold-based strategies that dictate when agents should coordinate and when they should explore in isolation.

The Bottleneck Problem

The "minimum accumulation function" characterizes many real-world tasks. For instance, in Dynamic Spectrum Access, a joint communication link is only as reliable as the worst channel selected by any participating device. Similarly, in complex project management, a task's completion is often delayed by its least successful sub-task. While agents can explore to find better values, this exploration consumes time and energy. Coordinating to share findings avoids redundant work but introduces communication costs. The central question is: how many agents should pay to coordinate, and when should they stop exploring?

Modeling Exploration Strategies

The authors analyze three distinct scenarios for a group of $k$ agents:

  1. Non-Coordinated Exploration: Agents work in parallel without communication, each using a fixed "reservation value" (a threshold) to decide when to stop.
  2. Fully Coordinated Exploration: With free communication, exploration becomes sequential. Only the agent with the lowest current value continues exploring, as they are the only one capable of improving the group's minimum score.
  3. Costly Coordination (The Hybrid Case): This primary contribution assumes linear communication costs. A subset of agents ($k'$) coordinates while others work independently.

The authors prove these strategies are threshold-based. These thresholds can be calculated offline, allowing agents to make optimal real-time decisions with minimal computational overhead.

Key Insights and Results

Coordination is most valuable when exploration costs are high, as the savings from avoiding redundant, expensive searches outweigh communication fees.

Figure 1: Expected benefit as a function of exploration cost (c). (a) shows benefits for fixed coordination sizes, while (b) identifies the 'dominating coordination strategy' where the optimal number of coordinating agents increases with cost.

As shown in Figure 1, the optimal strategy is not binary. Depending on the ratio of exploration to communication costs, the best setup often involves a specific "elite" group of coordinating agents. As communication costs decrease, the optimal number of coordinating agents naturally increases.

Figure 2: Performance gap between coordinated and non-coordinated systems. (a) shows benefit vs. exploration cost, and (b) shows benefit vs. the number of agents (k).

Figure 2 demonstrates that a coordinated system significantly outperforms non-coordinated ones, especially as the number of agents ($k$) grows. Without coordination, the "minimum" of many independent variables tends to be very low, making the "weakest link" problem increasingly severe in larger groups.

Limitations and Future Work

The current model assumes linear communication costs and homogeneous agents. Future research could explore non-linear cost patterns (e.g., broadcast overhead), heterogeneous groups with varying exploration capabilities, and alternative aggregation functions like the average or sum of values.

Summary updated

BibTeX
@inproceedings{rochlin2013information,
  author = {Igor Rochlin and David Sarne},
  title = {{Information Sharing Under Costly Communication in Joint Exploration}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2013},
  doi = {10.1609/aaai.v27i1.8574},
}
Figure