Swarm intelligence inspired shills and the evolution of cooperation

Potential Game Theoretic Learning for the Minimal Weighted Vertex Cover in Distributed Networking Systems

Toward the minimal weighted vertex cover (MWVC) in agent-based networking systems, this paper recasts it as a potential game and proposes a distributed learning algorithm based on relaxed greed and finite memory. With the concept of convention, we prove that our algorithm converges with probability 1 to Nash equilibria, which serve as the bridge connecting the game and the MWVC. More importantly, an additional degree of freedom is also provided for equilibrium refinement, such that increasing memory lengths and mutation probabilities contributes to the improvement of system-level objectives. Comparisons with typical methods, centralized and distributed, demonstrate the advantage of our algorithm for both weighted and unweighted versions. This paper not only provides a useful tool for the MWVC problem in decentralized environments but also paves an effective way for distributed coordination and optimization that could be modeled as potential games.

A New Network Feature Affects the Intervention Performance on Public Opinion Dynamic Networks

The neighborhood network structure plays an important role in the collective opinion of an opinion dynamic system. Does it also affect the intervention performance? To answer this question, we apply three intervention methods on an opinion dynamic model, the weighted DeGroot model, to change the convergent opinion value \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\bar{x}$$\end{document}x¯. And we define a new network feature Ω, called ‘network differential degree’, to measure how node degrees couple with influential values in the network, i.e., large Ω indicates nodes with high degree is more likely to couple with large influential value. We investigate the relationship between the intervention performance and the network differential degree Ω in the following three intervention cases: (1) add one special agent (shill) to connect to one normal agent; (2) add one edge between two normal agents; (3) add a number of edges among agents. Through simulations we find significant correlation between the intervention performance, i.e., \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$|\Delta {\bar{x}}^{\ast }|$$\end{document}|Δx¯⁎| (the maximum value of the change of convergent opinion value \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$|\Delta \bar{x}|$$\end{document}|Δx¯|) and Ω in all three cases: the intervention performance \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$|\Delta {\bar{x}}^{\ast }|$$\end{document}|Δx¯⁎| is higher when Ω is smaller. So Ω could be used to predict how difficult it is to intervene and change the convergent opinion value of the weighted DeGroot model. Meanwhile, a theorem of adding one edge and an algorithm for adding optimal edges are given.

How does the interaction radius affect the performance of intervention on collective behavior?

The interaction radius r plays an important role in the collective behavior of many multi-agent systems because it defines the interaction network among agents. For the topic of intervention on collective behavior of multi-agent systems, does r also affect the intervention performance? In this paper we study whether it is easier to change the convergent heading of the group by adding some special agents (called shills) into the Vicsek model when r is larger (or smaller). Two kinds of shills are considered: fixed-heading shills (like leaders that never change their headings) and evolvable-heading shills (like normal agents but with carefully designed initial headings). We know that with the increase of r, two contradictory effects exist simultaneously: the influential area of a single shill is enlarged, but its influence strength is weakened. Which factor dominates? Through simulations and theoretical analysis we surprisingly find that r affects the intervention performance differently in different cases: when fixed-heading shills are placed together at the center of the group, larger r gives a better intervention performance; when evolvable-heading shills are placed together at the center, smaller r is better; when shills (either fixed-heading or evolvable-heading) are distributed evenly inside the group, the effect of r on the intervention performance is not significant. We believe these results will inspire the design of intervention strategies for many other multi-agent systems.