The Study Of Evolutionary Game And Mechanism Design On Complex Networks

Complex networks theory is one of the most active branches in the field of complex system science. It is widely recognized that many real-world networks, such as Internet, the World Wide Web, power grids, biological networks, social collaboration networks, and etc, share many similar structural features including the small-world and (or) scale-free phenomena. Besides, various scale-free networks exhibit degree correlations: social collaboration networks usually display the assortative degree-mixing pattern, where hubs tend to interconnect with each other. While in the technological and biological networks, hubs are willing to select those neighbors having smaller degrees, by which the networks are disassortatively mixed. These structural features play crucial roles on the dynamical behaviors.Investigating the emerging mechanisms of cooperation emerging among competitive individuals holds a very long history with strong interest as the hot topic in the fields of economics, biology and information science, and the game theory provides a theoretical framework for it. The networked evolutionary game theory focuses on the interaction between the network structures and the evolution of strategies, where the individuals are located on vertices and the interaction among individuals are described by edges of the network. On the other hand, the mechanism design, the so-called inverse game theory, aims at designing protocols to induce these selfish individuals'behaviors to achieve the optimization of the whole systematic object. Recently, the mechanism design was applied to design the routing protocol and the overpaymen as a structural property was studied.In this paper, we investigate the roles of the small-world, scale-free and degree correlation features on the networked evolutionary games, and study the structural property of overpayment in networks with small-world and scale-free properties. The main content and contributions of this dissertation are summarized as follows:From the viewpoint of the individuals' dynamical organization, we first investigate the cooperative behaviors on small-world networks. We observe that, for a random regular graph where all vertices have the same number of neighbors, the increase of the swapping edge probabilities promotes the emergence of cooperative behaviors in the Prisoner's delimma game, mainly due to the fact that the individuals protect themselves from the invasion of defectors by composing larger clusters at the steady state. While for the snowdrift game, since the cooperators are difficult to form large clusters, the cooperators'frequencies of random regular graphs are less than the equilibrium frequency in well mixed populations when the cost-to-benefit ratio is larger than the threshold value. Moreover, since the mechanism of rewring edges makes the Watts-Strogatz(WS) small-world networks become heterogeneous, the cooperative behaviors are enhanced.We further study the cooperative behaviors on the networks with different degree heterogeneities on an extended snowdrift game model. Our findings show that the cooperative behaviors are promoted rapidly when the network becomes more heterogeneous, because the hubs which have high degrees are found to hold on their cooperation strategy at the steady state, and influence more neighbors to become cooperators. Therefore, the heterogeneity promotes the emergence of individuals with steady strategies.Furthermore, we investigate how the degree-mixing pattern affects the emergence of cooperation in the networked game. Our study shows that not only for the Prisoner's dilemma game, but also for the snowdrift game, when a network becomes assortative mixing by degree, the hubs tend to interconnect each other closely, destroying the sustainability among cooperators and promoting the invasion of defectors. However, in disassortative networks, the absence of close connections among hubs protects the cooperative hubs to hold on their initial strategies from extinction. With extensive investigations of the overpayment on small-world networks, we find that the average overpayment of WS small-world networks is larger than those of nearest neighbor networks and completely random graphs. This is because those shortcuts in WS small-world networks obtain very high overpayments. Therefore, we propose a new method by rewiring some new edges beside those original shortcuts, through which the overpayments of shortcuts are restrained efficiently.Finally, we study the distribution of vertex overpayments in scale-free networks with different degree exponents. We find the relation between degree and overpayment is a power-law form, and the overpayment-degree exponent decrease as the network becomes more heterogeneous. The overpayment distribution is also in a power-law form for the scale-free networks whose degree exponents are less than 3. The bonus per packet of a vertex is obtained through dividing the overpayment of this vertex by its carried traffic. Our investigation shows that a vertex with larger degree will charge more than that with smaller degree for transmitting per packet in heterogeneous networks, and the difference between those vertices with different degrees becomes minor when the network becomes homogeneous.