後大学 Under graduate course Work N Paper title: Cooperat ive behaviors in evolutionary games on complex networks Col lege: school of informat ion science and techno logy Ma jor electronic engineer ing Name Li Jingya Number 14307130355 Date 2016/06/12
Undergraduate Course Work Paper title： Cooperative behaviors in evolutionary games on complex networks College： school of information science and technology Major： electronic engineering Name： Li Jingya Number： 14307130355 Date： 2016/06/12
NFO13018901 Intro Network science14307130355李婧雅 2. 1 model¶meter 2.1.lp 2 2.2 network structu 2.2. 1 square lattice network 2.2.2 BA scale-free network 2.2.2.2 proced setting up 2. 3 evolutionary rules 2.3. 1 Optimum substitution 2.3.2 Fermi rule 3. Theoretical analysis 3. 1 prisoners'dilemma in the rule network 6 3.2 prisoners'dilemma in BA scale-free network 7 3. 2. 1 the spread of cooperative behaviors in BA scale-free network 3.2.2 the spread of defective behaviors in BA scale-free network 4. Simulation experiment&analysis 4. 1 prisoners'dilemma in the square lattice network 41.1 simulation result 4. 1.2 analysis .12 4.2 prisoners'dilemma in BA scale-free network 4.2.1 simulation result 13 4.2.2 analysis 13 4.3 5.2 networks 5.3 incentive mechanism 6. Summary Reference 17
INFO130189.01 Intro Network Science 14307130355 李婧雅 Contents 1. Background...............................................................................................................1 2. Related elements.......................................................................................................2 2.1 model¶meter.............................................................................................2 2.1.1 prisoners’ dilemma................................................................................2 2.1.2 parameters.............................................................................................3 2.2 network structures.............................................................................................3 2.2.1 square lattice network.............................................................................3 2.2.2 BA scale-free network............................................................................4 2.2.2.1 two basic characteristics..............................................................4 2.2.2.2 procedure of setting up................................................................4 2.3 evolutionary rules..............................................................................................5 2.3.1 Optimum substitution.............................................................................5 2.3.2 Fermi rule...............................................................................................5 3. Theoretical analysis...................................................................................................6 3.1 prisoners’ dilemma in the rule network.............................................................6 3.2 prisoners’ dilemma in BA scale-free network...................................................7 3.2.1 the spread of cooperative behaviors in BA scale-free network..............7 3.2.2 the spread of defective behaviors in BA scale-free network..................8 4. Simulation experiment&analysis..............................................................................9 4.1 prisoners’ dilemma in the square lattice network..............................................9 4.1.1 simulation result.....................................................................................9 4.1.2 analysis.................................................................................................12 4.2 prisoners’ dilemma in BA scale-free network.................................................13 4.2.1 simulation result...................................................................................13 4.2.2 analysis.................................................................................................13 4.3 comparison......................................................................................................14 5. Improvements..........................................................................................................14 5.1 Strategy............................................................................................................14 5.2 networks..........................................................................................................14 5.3 incentive mechanism.......................................................................................15 5.4 robustness........................................................................................................15 6. Summary..................................................................................................................15 Reference......................................................................................................................17
NFO13018901 Intro Network science14307130355李婧雅 Cooperative behaviors in evolutionary games on complex networks 14307130355 LI Jing-ya ( Abstract) From the class study, we know defection is the rational choice in the prisoners dilemma. However in fact, it appears cooperative behaviors among selfish individuals which seems unreasonable with the classic game theory. This article bases on the latest evolutionar game theory, using the most classic models-prisoners' dilemma to find differences of cooperative behaviors in the square lattice network and Ba scale-free network. In the study, it uses theoretical analysis and Matlab simulation experiment and finds the resistance theory of cooperative nodes and the impact of network characteristic. Finally, according to the result, it gets some summaries and comes up with some improvement advice about stud (Key Words] cooperative behavior; evolutionary game theory; prisoners'dilemma; complex network 1. Background Since the mathematician von Neumann and the economist Morgenstern published their book Theory of Games and Economic Behavior" in 1944, game theory was used widely in various fields such as economic competition, military conflict evolution of species and so on. Game theory provides theoretical frame to describe interacted behaviors between selfish individuals Although this theory which is based on rational hypothesis and individual selfish character is simple and practical, but it's not appropriate in real life. In fact, individual cognizance is limited and it cannot reach absolutely rational[1] Evolutionary game theory is the latest research result which make improvements according to the above-mentioned problem. It roots in the Darwins theory" Natural Selection and Survival of the Fittest". The core problem of evolutionary game theory is why it will appear widely cooperative behaviors among selfish individuals in the society. We have known a bit about it from the video shown in the class We know
INFO130189.01 Intro Network Science 14307130355 李婧雅 1 Cooperative behaviors in evolutionary games on complex networks 14307130355 LI Jing-ya 【Abstract】 From the class study, we know defection is the rational choice in the prisoners’ dilemma. However in fact, it appears cooperative behaviors among selfish individuals which seems unreasonable with the classic game theory. This article bases on the latest evolutionary game theory, using the most classic models—prisoners’ dilemma to find differences of cooperative behaviors in the square lattice network and BA scale-free network. In the study, it uses theoretical analysis and Matlab simulation experiment and finds the resistance theory of cooperative nodes and the impact of network characteristic. Finally, according to the result, it gets some summaries and comes up with some improvement advice about study. 【Key Words】 cooperative behavior; evolutionary game theory; prisoners’ dilemma; complex network 1. Background Since the mathematician von Neumann and the economist Morgenstern published their book ”Theory of Games and Economic Behavior” in 1944, game theory was used widely in various fields such as economic competition, military conflict, evolution of species and so on. Game theory provides theoretical frame to describe interacted behaviors between selfish individuals. Although this theory which is based on rational hypothesis and individual selfish character is simple and practical, but it’s not appropriate in real life. In fact, individual cognizance is limited and it cannot reach absolutely rational[1]. Evolutionary game theory is the latest research result which make improvements according to the above-mentioned problem. It roots in the Darwin’s theory”Natural Selection and Survival of the Fittest”. The core problem of evolutionary game theory is why it will appear widely cooperative behaviors among selfish individuals in the society. We have known a bit about it from the video shown in the class. We know
NFO13018901 Intro Network science14307130355李婧雅 defection always has higher payoff and follows the evolutionary strategy but with the evolution there will be some cooperative behaviors. So far, five mechanisms have been put forward to explain it: Kin selection, Direct reciprocity, Indirect reciprocity, Group selection and Network reciprocity This article will focus on cooperative behaviors in evolutionary games on complex notworks and explore the impact network makes on it 2. Related elements Model, network structure and evolutionary rule are three factors of networked evolutionary game 2.1 model parameter 2.1.1 prisoners'dilemma Two men who cooperatively made a crime were put into prison. For better interrogation, the police have arranged them in different rooms so they cannot communicate with each other. If both of them choose to keep silent and dont admit the crime( Cooperation, C), the police will only impose a light sentence on them. In this situation, the payoff of the two is r(Reward). If one chooses to confess(Defection, D) but another chooses to resist, then the former will be discharged and get the payoff T (Temptation), the later will be given a sever judgment and have payoff S( Suckers). If the two both confess the crime, they will be both sentenced and get the payoff P(Punishment). Besides, the parameters have the relation: T>R>P>S and 2R>T+S. So we can get the payoff matrix C ((R, R)(S,T) (P,P) To the two people, if we regard them as a whole, they will have maximal payoff 2R when they both choose to resist. But for each individual, he will always make the choice which is best for himself from the rational thinking. We can see. if the other
INFO130189.01 Intro Network Science 14307130355 李婧雅 2 defection always has higher payoff and follows the evolutionary strategy but with the evolution there will be some cooperative behaviors. So far, five mechanisms have been put forward to explain it: Kin selection, Direct reciprocity, Indirect reciprocity, Group selection and Network reciprocity. This article will focus on cooperative behaviors in evolutionary games on complex notworks and explore the impact network makes on it. 2. Related elements Model, network structure and evolutionary rule are three factors of networked evolutionary game. 2.1 model & parameter 2.1.1 prisoners’ dilemma Two men who cooperatively made a crime were put into prison. For better interrogation, the police have arranged them in different rooms so they cannot communicate with each other. If both of them choose to keep silent and don’t admit the crime(Cooperation, C), the police will only impose a light sentence on them. In this situation, the payoff of the two is R (Reward). If one chooses to confess(Defection, D) but another chooses to resist, then the former will be discharged and get the payoff T (Temptation), the later will be given a severe judgment and have payoff S (Suckers). If the two both confess the crime, they will be both sentenced and get the payoff P (Punishment). Besides, the parameters have the relation: T>R>P>S and 2R>T+S. So we can get the payoff matrix: C D D C ( , ) ( , ) T S R R ( , ) ( , ) P P S T To the two people, if we regard them as a whole, they will have maximal payoff 2R when they both choose to resist. But for each individual, he will always make the choice which is best for himself from the rational thinking. We can see, if the other
NFO13018901 Intro Network science14307130355李婧雅 choose to resist(C) but i choose to confess(D), so i will get T (T>R)and if the other choose to confess(D), choosing to confess(d)will still have higher payoff(P>S). So whichever choice the other makes, people should al ways choose to confess(d)to get the higher payor From the analysis we can know the only Nash equilibrium in the prisoners'dilemma is the two both choose confession(D, D) 2.1.2 parameters Cooperator density p: the percentage of cooperators in the whole network Temptation of defectors T: when one player chooses to defect and another chooses to cooperate, the payoff defector gets. Usually in the rule network, for easier calculation we set R=l, P=S=0, so T is the only variate 2.2 network structures We use complex networks to describe game relationship among social individuals Nodes in the network are the individuals in the game and links means the two individuals have game relationship Considering the variety of interaction among individuals in the real life, here we use two different network structures to describe game relationshi 2.2.1 square lattice network
INFO130189.01 Intro Network Science 14307130355 李婧雅 3 choose to resist(C) but i choose to confess(D), so i will get T (T>R) and if the other choose to confess(D), choosing to confess(D) will still have higher payoff (P>S). So whichever choice the other makes, people should always choose to confess(D) to get the higher payoff. From the analysis, we can know the only Nash equilibrium in the prisoners’ dilemma is the two both choose confession(D,D). 2.1.2 parameters Cooperator density : the percentage of cooperators in the whole network Temptation of defectors T : when one player chooses to defect and another chooses to cooperate, the payoff defector gets. Usually in the rule network, for easier calculation, we set R=1, P=S=0, so T is the only variate. 2.2 network structures We use complex networks to describe game relationship among social individuals. Nodes in the network are the individuals in the game and links means the two individuals have game relationship. Considering the variety of interaction among individuals in the real life, here we use two different network structures to describe game relationship. 2.2.1 square lattice network
NFO13018901 Intro Network science14307130355李婧雅 FIG. 1 square lattice network Picture one is the square lattice network with the structure N=LL. Square lattice network is the most common rule network. The degrees of all nodes in the network are even distribution. The characteristics of it are the small average length and big clustering coefficient In the picture, nodes are distributed orderly in the points of intersection and we give he corresponding coordinate(i,j(ij are both integers in the range of (1, L)to each of them 2.2.2 BA scale-free network Barabasi and albert finds that er random network and ws small-world network overlook two important characteristics of network in real life: growth and preferential attachment. In 1999, they set up the Ba scale-free network model, solving the problems we referred 2.2.2.1 two basic characteristics A. Growth: the scale of network is constantly growing, B. Preferential attachment: new nodes are more likely to connect with hub nodes which have higher degree. It's called"rich get richer 2.2.2.2 procedure of setting up A. In the beginning, there are mo nodes in the network. Every time adding a new node, connect the new one with the origin node in the network and generate m s(m≤m0) B. When connect the new node with the origin ones, the probability follows the rule p ∑ C It cant appear repeated connections in the network Follow the above rules to generate Ba scale-free network. When the number of nodes N>0, degree distribution follow the relation P(k)=2mk and the power
INFO130189.01 Intro Network Science 14307130355 李婧雅 4 FIG. 1 square lattice network Picture one is the square lattice network with the structure N=L*L. Square lattice network is the most common rule network. The degrees of all nodes in the network are even distribution. The characteristics of it are the small average length and big clustering coefficient. In the picture, nodes are distributed orderly in the points of intersection and we give the corresponding coordinate (i , j) (i,j are both integers in the range of (1,L)) to each of them. 2.2.2 BA scale-free network Barabási and Albert finds that ER random network and WS small-world network overlook two important characteristics of network in real life: growth and preferential attachment. In 1999, they set up the BA scale-free network model, solving the problems we referred. 2.2.2.1 two basic characteristics A. Growth: the scale of network is constantly growing; B. Preferential attachment: new nodes are more likely to connect with hub nodes which have higher degree. It’s called “rich get richer”. 2.2.2.2 procedure of setting up A. In the beginning, there are m0 nodes in the network. Every time adding a new node, connect the new one with the origin node in the network and generate m links( m≤ m0 ) B. When connect the new node with the origin ones, the probability follows the rule: j i i k k p C. It can’t appear repeated connections in the network. Follow the above rules to generate BA scale-free network. When the number of nodes N , degree distribution follow the relation P k m k 2 ( ) 2 and the power
NFO13018901 Intro Network science14307130355李婧雅 exponent y>3, average shortest length L In(N), cluster coefficient C-N-075 For example, when m,=3, m=2, the procedure of setting up BA scale-free network can be shown FIG 2. The evolutionary of BA scale-free network( mo=3, m=2)[2] 2.3 evolutionary rules 2.3.1 Optimum substitution After every evolutionary, the node compares the payoff of all neighbor nodes and itself and chooses the strategy that the node with highest payoff used as its new game strategy 2.3.2 Fermi rule After every evolutionary, the node i randomly chooses a neighbor node j and according to the difference value between the two decides the possibility of the node i using the node j's strategy in the next game. The possibility can be calculated according to Fermi Function in the statistical physics 1+exp[-(E, -E)/K E, and E represents the payoff the node i and j get in the game When the payoff of i is lower than that of j, i will tend to use j's strategy and the bigger difference value between the two nodes is, the more likely i is to use js strategy. However, when the payoff of i is higher than that of j, it's still possible that i use j's strategy with small possibility. Parameter K represents noise figure which means the behavior can be irrational. It shows the uncertainty in the process of updating strategy. When K>00
INFO130189.01 Intro Network Science 14307130355 李婧雅 5 exponent 3, average shortest length L~ ln(N), cluster coefficient C ~ 0.75 N . For example, when m0 =3, m=2, the procedure of setting up BA scale-free network can be shown: FIG 2. The evolutionary of BA scale-free network( m0 =3, m=2)[2] 2.3 evolutionary rules 2.3.1 Optimum substitution After every evolutionary, the node compares the payoff of all neighbor nodes and itself and chooses the strategy that the node with highest payoff used as its new game strategy. 2.3.2 Fermi rule After every evolutionary, the node i randomly chooses a neighbor node j and according to the difference value between the two decides the possibility of the node i using the node j’s strategy in the next game. The possibility can be calculated according to Fermi Function in the statistical physics: 1 exp[ ( ) ] 1 E E K w i j Ei and Ej represents the payoff the node i and j get in the game. When the payoff of i is lower than that of j, i will tend to use j’s strategy and the bigger difference value between the two nodes is, the more likely i is to use j’s strategy. However, when the payoff of i is higher than that of j, it’s still possible that i use j’s strategy with small possibility. Parameter K represents noise figure which means the behavior can be irrational. It shows the uncertainty in the process of updating strategy. When K
NFO13018901 ntro Network science14307130355李婧雅 strategy update is totally random. When K >0, there is no uncertainty in the process, which means if the payoff of j is higher than that of i, i will be sure to use j's strategy 3. Theoretical analysis 3.1 prisoners'dilemma in the rule network Nowak and May made researches about the prisoner's dilemma in the two-dimensions quare lattice network. As the picture one shows, in the square lattice network, every node has four neighbor nodes and connected nodes play games with each other. For easier calculation, we set up the temptation of defection T>l, the reward of cooperation R=l, both punishment of defection P and suckers S are 0, so in this situation,it' s called poor prisoners' dilemma(弱囚徒困境) Nowak has proved the evolutionary results of poor prisoners' dilemma and prisoners' dilemma is the same After each time's game, nodes will calculate the payoff of others and itself and choose the strategy that the nodes with the highest payoff used as its new strategy. So it nakes a strategy update. [2 According to Nowak's research, using this strategy update mechanism in the square lattice network, when IsT<2, p doesnt equal to 0 which means it exists the cooperative nodes and these nodes can gather together to form clusters in the network and show the pattern like picture two. In the picture, the dark ones are the cooperative nodes. The clusters consisting of these nodes will have changes in the process of game but will exist in the network all the time. Thats because cooperative ones unite with each other and get the payoff higher than detective ones. Clusters can prevent the invade from defection strategy. [3]
INFO130189.01 Intro Network Science 14307130355 李婧雅 6 strategy update is totally random. When K 0 , there is no uncertainty in the process, which means if the payoff of j is higher than that of i, i will be sure to use j’s strategy. 3. Theoretical analysis 3.1 prisoners’ dilemma in the rule network Nowak and May made researches about the prisoner’s dilemma in the two-dimensions square lattice network. As the picture one shows, in the square lattice network, every node has four neighbor nodes and connected nodes play games with each other. For easier calculation, we set up the temptation of defection T>1, the reward of cooperation R=1, both punishment of defection P and suckers S are 0, so in this situation, it’s called poor prisoners’ dilemma(弱囚徒困境). Nowak has proved the evolutionary results of poor prisoners’ dilemma and prisoners’ dilemma is the same. After each time’s game, nodes will calculate the payoff of others and itself and choose the strategy that the nodes with the highest payoff used as its new strategy. So it makes a strategy update.[2] According to Nowak’s research, using this strategy update mechanism in the square lattice network, when 1≤T<2, c doesn’t equal to 0 which means it exists the cooperative nodes and these nodes can gather together to form clusters in the network and show the pattern like picture two. In the picture, the dark ones are the cooperative nodes. The clusters consisting of these nodes will have changes in the process of game but will exist in the network all the time. That’s because cooperative ones unite with each other and get the payoff higher than detective ones’. Clusters can prevent the invade from defection strategy.[3]
NFO13018901 Intro Network science14307130355李婧雅 FIG3 clusters formed by nodes in the prisoners'dilemma evolutionary in square lattice network[ 4] 3.2 prisoners'dilemma in BA scale-free network As we have learned in the class, many networks in real life are scale-free network degree distribution of which follows the power-law distribution, such as transport network, Internet and so on. Because of the differences in topological structure between rule network and Ba scale-free network, cooperative behaviors in the prisoners dilemma evolutionary are also different. Santos has compared cooperative ehaviors in different network models such as square lattice network, Er random network and scale-free network and find that scaleless property makes network easier to appear cooperative behaviors In the Ba scale-free network, connected nodes play prisoners'dilemma game with each other and nodes will update game strategy with certain rule. Here we use the Fermi rule referred in 2.3.2 and focus on the impact hub nodes make in the network 3.2.1 the spread of cooperative behaviors in ba scale-free network We choose two hub nodes x,y to watch. The node x, y is directly connected and other nodes with small degree are randomly connected with one of them. In the beginning we set x as cooperator and y as defector. Half neighbor nodes of each hub nodes are cooperators and the others are defectors. In each round of game, all nodes play prisoners dilemma games with each of its neighbor nodes and payoff will be added up Nodes will use Fermi rules to make evolution: each node chooses one neighbor
INFO130189.01 Intro Network Science 14307130355 李婧雅 7 FIG. 3 clusters formed by nodes in the prisoners’ dilemma evolutionary in square lattice network[4] 3.2 prisoners’ dilemma in BA scale-free network As we have learned in the class, many networks in real life are scale-free network , degree distribution of which follows the power-law distribution, such as transport network , Internet and so on. Because of the differences in topological structure between rule network and BA scale-free network, cooperative behaviors in the prisoners’ dilemma evolutionary are also different. Santos has compared cooperative behaviors in different network models such as square lattice network, ER random network and scale-free network and find that scaleless property makes network easier to appear cooperative behaviors. In the BA scale-free network, connected nodes play prisoners’ dilemma game with each other and nodes will update game strategy with certain rule. Here we use the Fermi rule referred in 2.3.2 and focus on the impact hub nodes make in the network. 3.2.1 the spread of cooperative behaviors in BA scale-free network We choose two hub nodes x,y to watch. The node x,y is directly connected and other nodes with small degree are randomly connected with one of them. In the beginning, we set x as cooperator and y as defector. Half neighbor nodes of each hub nodes are cooperators and the others are defectors. In each round of game, all nodes play prisoners’ dilemma games with each of its neighbor nodes and payoff will be added up. Nodes will use Fermi rules to make evolution: each node chooses one neighbor
NFO13018901 Intro Network science14307130355李婧雅 node to compare with. If the neighbor's payoff in this round is higher than itself, the node will copy the neighbors strategy in this round with possibility w, that means in the round, the strategy of nodes with higher payoff are more likely to be copied by the ir neighbors FIG4 A typical subgraph of a scale-free network, where two connected hub nodes are linked to many others having significantly less neighbors[5] At first, because each hub node is surrounded by many cooperative neighbor nodes so its accumulated payoff willl be higher than the small-degree nodes and small-degree nodes will copy the strategy of hub node it connects with. Although now cooperative x has lower payoff than defective y does, because of random choice of strategy comparing, x still has higher payoff than most of small-degree neighbor nodes, x can insist cooperative strategy for a time. As time goes by, the neighbor nodes of x tend to copy x's strategy, so there will be more and more cooperators around x, which contributes to the rise of x's payoff. On the contrary, it means there appears more and more defectors around y and y's payoff will decline and gradually be lower than its neighbor node x. At one moment, y will copy x's strategy and change into cooperator and then y's neighbor nodes will also change into cooperators In the end, cooperation will spread in the whole network and all the hub nodes will choose to cooperate. This means if individual chooses to add up its payoff, the hub nodes in the Ba scale-free network tend to choose cooperation and will affect their neighbor nodes[1] 3.2.2 the spread of defective behaviors in Ba scale-free network Besides, to find how hub nodes effectively resist the invade from defectors, we can analyze the spread of defective behaviors. In the beginning, we set only the node X
INFO130189.01 Intro Network Science 14307130355 李婧雅 8 node to compare with. If the neighbor’s payoff in this round is higher than itself, the node will copy the neighbor’s strategy in this round with possibility w, that means in the round, the strategy of nodes with higher payoff are more likely to be copied by their neighbors. FIG. 4 A typical subgraph of a scale-free network, where two connected hub nodes are linked to many others having significantly less neighbors[5] At first, because each hub node is surrounded by many cooperative neighbor nodes, so its accumulated payoff willl be higher than the small-degree nodes and small-degree nodes will copy the strategy of hub node it connects with. Although now cooperative x has lower payoff than defective y does, because of random choice of strategy comparing, x still has higher payoff than most of small-degree neighbor nodes, x can insist cooperative strategy for a time. As time goes by, the neighbor nodes of x tend to copy x’s strategy, so there will be more and more cooperators around x, which contributes to the rise of x’s payoff. On the contrary, it means there appears more and more defectors around y and y’s payoff will decline and gradually be lower than its neighbor node x. At one moment, y will copy x’s strategy and change into cooperator and then y’s neighbor nodes will also change into cooperators. In the end, cooperation will spread in the whole network and all the hub nodes will choose to cooperate. This means if individual chooses to add up its payoff, the hub nodes in the BA scale-free network tend to choose cooperation and will affect their neighbor nodes[1]. 3.2.2 the spread of defective behaviors in BA scale-free network Besides, to find how hub nodes effectively resist the invade from defectors, we can analyze the spread of defective behaviors. In the beginning, we set only the node x