ALTERED PAYOFF VALUES AND THE EFFECT ON A POPULATION OFITERATED PRISONER'S DILEMMA PLAYERSByMichael Clark WeeksB.E.S., University of Louisville, 1993A ThesisSubmitted to the Faculty of theUniversity of LouisvilleSpeed Scientific Schoolas Partial Fulfillment of the Requirementsfor the Professional DegreeMASTER OF ENGINEERINGDepartment of Engineering Mathematics and Computer ScienceMay 1994ALTERED PAYOFF VALUES AND THE EFFECT ON A POPULATION OFITERATED PRISONER'S DILEMMA PLAYERSSubmitted by:Michael Clark WeeksA Thesis Approved on(Date)by the Following Reading and Examination Committee:Dr. R. K. Ragade, Thesis Director,Engineering Mathematics and Computer ScienceDr. M. J. Maron,Engineering Mathematics and Computer ScienceDr. T. G. Cleaver,Electrical EngineeringACKNOWLEDGMENTSThe author would like to thank Dr. R. K. Ragade for hissupport, encouragement, and ideas for this thesis. The authorappreciates Dr. M. J. Maron and Dr. T. G. Cleaver for servingon the thesis committee.The following people were also helpful in making thisproject possible. Georg Fuellen at MIT, who provided a list ofinitial references. David B. Fogel of the ORINCON Corporation,who was kind enough to send a copy of one of his papers, whichthe author referenced extensively. Leigh Testfatsion alsoprovided a copy of an important paper. Mark Atkinson, GregorySeront from the Free University of Brussels, Belgium, and I.M. Ikram from Rhodes University, South Africa, who helped byclarifying some of the biological terminology. Finally, theauthor appreciates the Internet correspondence of everyoneposting to the comp.ai.genetic bulletin board. The people ofthis newsgroup were helpful in providing references andinsight through personal correspondence.TABLE OF CONTENTSPageAPPROVAL PAGE ...................................... iiACKNOWLEDGMENTS .................................... iiiABSTRACT ........................................... viNOMENCLATURE ....................................... viiiLIST OF FIGURES .................................... ixLIST OF TABLES ..................................... xiI. INTRODUCTION ............................. 1A. Definitions of Terms .................. 6B. Objective of this Thesis .............. 9C. Assumptions ........................... 9II. LITERATURE REVIEW ....................... 12A. Evolving IPD Players .................. 12B. Prisoner's Dilemma Used to Study Moralityand Rationality ....................... 21C. Evolutionary Programming and GeneticAlgorithms ............................ 26D. Genetic Algorithms and IPD Players .... 28E. The Parallel Genetic Algorithm andDarwin's Continental Cycle ............ 30F. Cellular Automata and the Prisoner'sDilemma ............................... 34G. The Validity of Cellular AutomataExperiments ........................... 36H. Payoff Values and Their Effect on EvolvingPlayers ............................... 38III. DESIGN AND APPROACH ...................... 42IV. SIMULATION MODULES ....................... 56A. Program 1: Cellular Automata .......... 56B. Program 2: The Prisoner's Dilemma World 59C. Program 3: Payoffs and Rankings ....... 60D. Program 4: Wandering Players .......... 61V. PROCEDURE ................................ 65A. The Finite State Machine .............. 65B. The Players ........................... 66C. The Population ........................ 67D. The Genetic Operators ................. 68E. The Data Structures ................... 69VI. RESULTS AND ANALYSIS ..................... 70VII. DISCUSSION ............................... 87VIII. CONCLUSIONS AND RECOMMENDATIONS ........... 104IX. FUTURE STUDY .............................. 108REFERENCES ......................................... 111BIBLIOGRAPHY ....................................... 113APPENDIX SAMPLE PROGRAM OUTPUT .................... 119VITA ............................................... 123ABSTRACTGame theory and evolutionary programming are used tomodel social interactions, and simulate aspects of nature.Scientists often use the prisoner's dilemma game with GeneticAlgorithms for this purpose. The prisoner's dilemma gives eachplayer a choice between the move best for both players, ifthey can trust each other (cooperation), or the selfish butsafer choice (defection). The combined choices result in apayoff of utilities to each player. This thesis examines theeffect of varying payoff values on populations of prisoner'sdilemma players. For example, will a selfish player thriveunder certain payoffs? As the saying goes, "every man has hisprice." This thesis asks, "if we alter the risks forselfishness, would the population become more or lessselfish?"The prisoner's dilemma game is significant because itreadily models conflict in cooperative situations. Scientistsalso use it to simulate evolutionary biology.Altering payoff values for the supergame influences thesuccess of the individual players. The author found that thepayoff values do affect how the population evolves, ifcooperation evolves at all. How the players interact alsochanges the evolution of cooperation. Random interactionprovides a more realistic simulation of several kinds ofnatural behavior. Finally, counting the number of cooperativeoutputs of the finite state machine proves to be another wayto measure cooperation.NOMENCLATUREFSM = Finite State MachineGA = Genetic AlgorithmPGA = Parallel Genetic AlgorithmPD = Prisoner's DilemmaIPD = Iterated Prisoner's DilemmaXPD = Extended Prisoner's DilemmaC = CooperateD = DefectDC = payoff value for a player that defects against acooperatorDD = payoff value for a mutual defectionCC = payoff value for a mutual cooperationCD = payoff value for a player who cooperates with adefectorLIST OF FIGURESPageFigure 1 - Payoffs for the 2 Player PD Game ......... 3Figure 2 - Three Player PD Payoffs .................. 5Figure 3 - Chicken (Hawk/Dove) Payoff Matrix ........ 6Figure 4 - Evolutionary Programming Algorithm ....... 26Figure 5 - Parallel Genetic Algorithm ............... 32Figure 6 - The Algorithm of "Wandering Players" ..... 45Figure 7 - How the FSM is encoded ................... 47Figure 8 - Drawing of a FSM ......................... 48Figure 9 - The Matrices Classfor "Payoffs and Rankings" ............. 50Figure 10 - The People Class ....................... 51Figure 11 - Barriers class and Matrices classfor "Wandering Players" ................ 52Figure 12 - Delta Values and Ranking Changes ....... 75Figure 13 - How Payoff Values Affected Player #1 ... 77Figure 14 -