Abstract
Multiagent coordination in cooperative multiagent systems (MASs) has been widely studied in both fixed-agent repeated interaction settings and static social learning frameworks. However, two aspects of dynamics in real-world MASs are currently missing. First, network topologies can dynamically change during the course of interaction. Second, the interaction utilities between each pair of agents may not be identical and are often unknown a priori. Both issues increase the difficulty of coordination. In this paper, we consider multiagent social learning in a dynamic environment where agents can alter their connections and interact with randomly chosen neighbors with unknown utilities. We propose an optimal rewiring strategy to select the most beneficial peers to maximize accumulated payoffs in long-run interactions. We empirically demonstrate the effects of our approach in large-scale MASs.
Introduction
In traditional Multiagent Social Learning (MASL), researchers typically assume a static social structure where agents interact with a fixed set of neighbors. However, real-world networks are inherently dynamic; agents often have the autonomy to choose their partners. Furthermore, the utility of these interactions is rarely uniform or known beforehand. Agents must navigate the "exploration-exploitation" tradeoff not just in their actions, but in their social connections themselves. This paper addresses the challenge of how an agent should decide when to sever a current connection and form a new one, particularly when switching partners incurs a cost.
Methodology: The K-Sight Rewiring Strategy
The core of our approach is the K-Sight Rewiring Strategy, which models network evolution as a Markov Decision Process (MDP). This strategy is inspired by Weitzman’s "Pandora’s Rule" from optimal search theory, treating potential new partners as "boxes" with unknown rewards and a cost to open.
The Benefit Index ($\Lambda$)
To evaluate potential peers, agents calculate a Benefit Index. This index represents the expected improvement in payoff compared to the agent's current worst-performing neighbor. It accounts for the probability distribution of the new peer's potential utility, ensuring that agents prioritize partners with the highest potential to improve their long-term standing, rather than just those with high historical averages.
Cost-Benefit and Horizon
The decision to rewire is governed by two parameters: the rewiring cost ($c$) and the "sight" horizon ($K$). The variable $K$ represents the number of future rounds the agent considers. An agent will only rewire if the expected gain over $K$ rounds ($K\Lambda$) outweighs the cost of the transition ($c$). This mechanism prevents "jittering"—constant switching for marginal gains—and encourages stable, high-value relationships.
Experimental Evaluation
We evaluated the strategy in simulated environments with population sizes ($N$) ranging from 100 to 1,000 agents. Coordination payoffs were sampled from unique probability distributions for each pair of agents to simulate diverse utilities.
As shown in Table 1, the Optimal strategy significantly outperforms both "Random" rewiring and the "Highest Expected Payoff" (K-HE) heuristic across all scales. For instance, in a 100-agent setup, the Optimal strategy achieved an average payoff of 1372, nearly double that of the Random strategy (763).
Results and Analysis
Robustness to Cost
A critical finding is the strategy's robustness to the cost-to-sight ratio ($c/sight$). While simpler heuristics like K-HE show significant performance dips at moderate cost levels, the Optimal strategy maintains a high and stable average reward.
Synergy with Learning Algorithms
Beyond network formation, we observed that the optimal rewiring strategy synergizes effectively with advanced interaction learning rules. When paired with algorithms like Joint-Action WoLF-PHC, the system converges more reliably to optimal Nash equilibria than when using simpler strategies like Fictitious Play (FP).
Conclusion
By treating social network formation as an optimal search problem, we provide a robust framework for agents to autonomously optimize their social structures in dynamic environments. Our K-Sight strategy effectively balances the costs of network change against the long-term benefits of high-utility partnerships. Future work will explore these dynamics in competitive environments and investigate methods for agents to discover potential peers beyond their immediate reach.
Summary updated