後大学 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