Mechanisms For The Emergence Of Social Norms In Networked Multi-Agent Systems

Social norms, such as coordination norms and cooperation norms, play an important role in maintaining the order and efficiency of networked multi-agent systems. The challenge is how to establish social norms quickly and effectively in a particular scene. In a networked multi-agent system, selfish agents have the ability to reason and learn, thereby adjusting their behaviors to optimize their own income based on rewards obtained in the system and other local information (e.g., neighbors'behaviors and rewards). So bottom-up emergence becomes an effective way to establish social norms in a multi-agent system. However, under different network structures and game models, various mechanisms provide alternative information to agents, which will significantly affect the emergence of social norms. Therefore, the goal of this paper is to design suitable mechanisms for social norm emergence under specific scenarios.In this thesis, we first review the existing research on the emergence of coordination and cooperation norms. Then, we focus on four specific scenarios:coordination game on ring networks, prisoner's dilemma game on static networks, prisoner's dilemma game on mobile networks and repeated prisoner's dilemma game. We propose strategy updating rules, payoff matrix adjustment mechanism and network construction mechanism for norm emergence in each scenario from different landscapes and analyzed emergence process of each mechanism. The main contributions of this dissertation are listed as follows:1). Ring network is most likely to induce local coordination norms due to it having largest network diameter. The existing Myopic Best Response rule (MBR), the highest cumulative reward rule, Q learning rule and other mechanisms cannot effectively promote the emergence of global norms in ring networks. This paper presents a Frozen Best Response rule (FBR). In this mechanism, agent is frozen after adopting a new behavior, and the frozen agents have a small transition rate for switching behaviors. The simulation results and microscopic analysis show that the rule can transform the interface between the local norms from random walk into a biased random walk, which leads to a higher interface diffusion rate, and promotes global coordination norm emergence in a ring network with a moderate freezing period length.2). Previous research proposed several strategy updating rules and payoff matrix adjustment mechanisms to promote the emergence of cooperation norms on static networks. Although these mechanisms can help the survival of cooperation in a large parameter space, they usually cannot guarantee the emergence of a global cooperation norm. To solve this problem, we proposed a Neighborhood-extended Fermi Updating Rule (N-FUR) and a Multi-Game matrix adjustment mechanism (MG). Under N-FUR rule, the weighted sum of the opponent's reward and the average reward of the opponent's neighbors was used to evaluate the fitness of an opponent agent, which led to survival and expansion of small clusters of cooperators within the sea of defectors, thereby optimizing the critical value of global cooperation norm emergence. Under the MG mechanism, each individual is assigned a payoff matrix with either a positive or a negative value of the sucker's payoff (S). This mechanism can first enhance the level of cooperation for the sub-population with positive S, and then give rise to an asymmetric strategy imitation flow from positive S group to negative S group, thus improving the cooperation level and social benefit.3). In mobile networks, improper motion mechanisms may break the clusters of cooperators, and are not conducive for the emergence of cooperation norms. In this paper, we proposed a Degree-aware Vector Average Moving rule (DVAM). In this rule, the direction of each agent is updated by the weighted average directions of its neighbors, and the agent with more neighbors is given a greater weight. Simulation and analysis results show that the mechanism can promote the formation of large cooperator clusters, so as to resist the invasion of defectors, thereby promoting the emergence of cooperation norms on mobile networks more effectively than the traditional random and vector average moving rules.4). The strategy space exponentially increase in repeated games, thus the widely-used imitating-based updating rules cannot be applied due to the unrealistic ability assumption for players. Further, the Aspiration payoff-based Updating Rule (AUR) and Global Extremal Updating Rule (GEUR) cannot promote the emergence of cooperation norms in this scenario. To solve this problem, we proposed a Localized Extremal Updating Rule (LEUR), in which each player only needs to recognize the payoff of his neighbors and changes his strategy randomly when he receives the lowest payoff in his neighborhood. The simulation results and microscopic analysis show that when the neighborhood radius is 2, the number of small clusters and the number of active players simultaneously reach an optimal value, which helps the system evolve into a TFT-like state and reaches the highest average income.