Introduction
In Multiagent Systems (MAS), coordination is often achieved through social learning, where agents interact with local neighbors to discover mutually beneficial strategies. Traditional models typically assume static network topologies and uniform payoff structures. However, real-world scenarios involve fluid social connections and heterogeneous coordination benefits. This paper addresses these limitations by introducing an optimal rewiring strategy that allows agents to dynamically manage their interaction partners in environments with uncertain payoffs.
The Social Learning Framework with Optimal Rewiring
The proposed framework integrates a dynamic rewiring mechanism with reinforcement learning. The interaction protocol for each agent follows a structured sequence of decision-making and learning phases.
Rewiring Phase
Agents periodically evaluate their current social circle. The decision to break a connection with a poorly performing neighbor and establish a new one is modeled as a Markov Decision Process (MDP). To solve this efficiently, the authors adapt Pandora’s Rule from search theory. Agents calculate a "K-sight" index ($\Lambda$) for potential partners, representing the expected net benefit of a new connection over the next $K$ rounds, factoring in the cost ($c$) of rewiring. An agent only rewires if the potential gain from a new peer exceeds the utility of its current worst-performing neighbor.
Interaction Phase
Following the rewiring decision, agents engage in a 2-action cooperative game with a randomly selected neighbor. The payoffs for successful coordination (actions $a,a$ or $b,b$) are stochastic variables ($u_a, u_b$), while miscoordination results in a lower reward ($\alpha$). Agents update their internal policies and action models using reinforcement learning algorithms such as Fictitious Play (FP), Joint-Action Learner (JAL), or Joint-Action WoLF-PHC.
Experimental Evaluation
The strategy was tested in simulated environments with varying network topologies, including Regular, Small-world, and Scale-free networks, with populations up to 1,000 agents. Payoffs were sampled from Uniform or Beta distributions to simulate environmental uncertainty. The "Optimal" strategy was benchmarked against Random rewiring and K-HE (K-sight Highest Expectation), a strategy that ignores the baseline utility of current neighbors.
Key Results and Discussion
The Optimal strategy consistently outperformed benchmarks across diverse environment types and rewiring costs. A critical finding is the "K-sight" trade-off: the parameter $K$ must be carefully balanced against the rewiring cost $c$. If $K$ is too small, agents are overly cautious; if $K$ is too large, they become over-optimistic, chasing marginal gains that do not justify the costs.
As shown in the experimental results, the Optimal strategy maintains superior average rewards regardless of the proportion of K-HE agents in the population. Furthermore, the system's performance proved robust to initial network structures, as dynamic rewiring eventually reshaped the networks into configurations optimized for the specific payoff distributions.
Conclusion and Future Work
This research demonstrates that an MDP-based rewiring strategy using the K-sight index significantly enhances coordination and reward maximization in cooperative MAS. Future work will explore extending this framework to non-cooperative or competitive systems, incorporating network-aware strategies (e.g., identifying hubs), and modeling variable costs for breaking long-standing versus new connections.
Summary updated