跳到主要內容

臺灣博碩士論文加值系統

(54.224.133.198) 您好!臺灣時間:2022/01/29 20:34
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:黃瑞良
研究生(外文):Ruei-Liang Huang
論文名稱:遊戲理論之電腦模擬─對手選擇對於反覆囚犯困局之影響
論文名稱(外文):The Effects of Biased Opponent Selection on the Iterated Prisoner’s Dilemma.
指導教授:孫春在孫春在引用關係
指導教授(外文):Chuen-Tsai Sun
學位類別:碩士
校院名稱:國立交通大學
系所名稱:資訊科學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:中文
論文頁數:51
中文關鍵詞:囚犯困局以標籤為基礎的偏見對手選擇以空間為基礎的偏見對手選擇以親屬關係為基礎的偏見對手選擇偏見對手選擇
外文關鍵詞:The Prisoner''s DilemmaTag-based ModelSpace-based ModelKinship-based ModelBiased Opponent Selection
相關次數:
  • 被引用被引用:5
  • 點閱點閱:1704
  • 評分評分:
  • 下載下載:421
  • 收藏至我的研究室書目清單書目收藏:5
許多合作行為演化的研究領域上,諸如經濟學、社會學、國際關係等等,都可以見到非常多囚犯困局相關的研究。在Muti-Agent Systems的研究領域中,合作是一個主要的追求目標。近年來有越來越多的研究利用囚犯困局探討在Muti-Agent Systems環境中合作行為的浮現。
而在囚犯困局的研究當中,促進合作是一個相當重要的研究領域。在一般的囚犯困局當中,往往整體一開始會急速陷入背叛狀態,使得整體利益降低,在經過冗長的演化之後,合作行為才會逐漸緩慢的浮現,而在背叛到合作這段期間隱含著資源的浪費。越快地促進合作行為浮現一方面可以使得整體利益獲得最佳狀態,另一方面則可以避免無形中資源的消耗、浪費。
在促進合作的研究領域當中,有著許多不同的方法,而偏見的選擇對手機制為其中一種方法。在偏見的對手選擇模型當中又粗略分為「以標籤為基礎的偏見對手選擇」、「以空間為基礎的偏見對手選擇」以及「以親屬關係為基礎的偏見對手選擇」。在各種偏見的對手選擇模型當中有著不同的優缺點,所以本研究試圖提出一個更簡單、易實行並且具備成效的偏見對手選擇方法,來快速的促進反覆囚犯困局的合作行為浮現。
There are many fields, such like economic science, sociology and international relations, in which researchers are using the Prisoner’s Dilemma to study the evolution of cooperation. Cooperation is also one of the major objectives pursued by researchers in the area of multi-agent systems. There are more and more studies aimed at the Prisoner’s Dilemma to investigate the emergence of cooperation in multi-agent systems.
Promoting cooperation is an important study in the Prisoner’s Dilemma. In a general Prisoner’s Dilemma game, the population usually falls down to the status of defection rapidly, and thus decreases the benefit of the whole population. Cooperation needs long time to be evolved and the process is slow. The gap between defection and cooperation implies the waste of resources. The more quickly cooperation emerges, the more benefit the population can enjoy.
There are many methods to promote cooperation in the Prisoner’s Dilemma, and the biased opponent selection mechanism is one of them. There are three kinds of the biased opponent selection models: tag-based model, space-based model and kinship-based model. There are many advantages and disadvantages in these three models, and this research tries to provide another biased opponent selection method that is simple and effective to trigger the emergence of the cooperation quickly in the Iterated Prisoner’s Dilemma.
摘要...........................................................i
ABSTRACT......................................................ii
誌謝..........................................................iv
目錄...........................................................v
圖表目錄......................................................vii
1 緒論 1
1.1 研究動機 1
1.2 問題描述 2
1.3 研究目標 4
1.4 研究重要性 5
1.5 論文結構 6
2 相關研究 7
2.1 囚犯困局 7
2.1.1 囚犯困局(Prisoner’s Dilemma)簡介…………………………….7
2.1.1 反覆囚犯困局(Iterated Prisoner’s Dilemma)……………….8
2.2 在囚犯困局中偏見的對手選擇 9
2.2.1 偏見的對手選擇簡介……………………………………………..9
2.2.2 以標籤為基礎的偏見的對手選擇………………………………..10
2.2.3 以空間為基礎的偏見的對手選擇………………………………..11
2.2.4 以親屬關係為基礎的偏見的對手選擇…………………………..13
2.3 合作行為中關於形象的研究 15
2.4 基因演算法 17
2.4.1 基本定義…………………………………………………………..17
2.4.2 適存度函式………………………………………………………..18
2.4.3 選擇與複製………………………………………………………..18
2.4.4 演化流程架構……………………………………………………..19
2.4.5 收斂………………………………………………………………..20
2.4.6 基因演算法在囚犯困局中的應用………………………………..20
3 模型設計 22
3.1 Agent設計 23
3.1.1 Agent屬性………………………………………………………….23
3.1.2 Agent編碼設計…………………………………………………….24
3.2 不使用形象來選擇對手 26
3.2 使用形象來選擇對手 27
3.2.1 形象值評估………………………………………………………..27
3.2.2 對手選擇…………………………………………………………..27
3.2.3 搜尋成本…………………………………………………………..28
3.2.4 適存度計算………………………………………………………..28
3.2.4 產生新的世代……………………………………………………..29
3.2.5 測量模型行為……………………………………………………..29
4 實驗結果 31
4.1 反覆比賽次數 32
4.2 形象評估臨界值 35
4.3 搜尋成本與選擇對手臨界值 39
5 結論 45
參考文獻 47
[1]Robert M. Axelrod. The Evolution of Cooperation. Basic Books, New York, 1984.
[2]Robert M. Axelrod. The evolution of strategies in the iterated Prisoner’s Dilemma. pp. 32-41 in L. Davis (Ed.) Genetic Algorithms and Simulated Annealing (Morgan Kaufmannm Los Altos, CA). 1987.
[3]Kurt Brauchli, Timothy Killingback, Michael Doebeli. Evolution of Cooperation in Spatially Structured Population. J. theor. Biol. (1999) 200, 405-417.
[4]Franco Busetti. Genetic algorithms overview.
[5]David Carmel and Shaul Markovitch. How to Explore Your Opponent’s Strategy (almost) Optimally. Computer Science Department, Technion, Haifa 32000, Israel.
[6]K. Chiba and K. Hiraishi. Iterated Continuous Prisoner’s Dilemma Game and Its Usefulness in Analyzing Multi-agent Systems. Systems, Man, and Cybernetics, 1998. 1998 IEEE International Conference on , Volume: 1 , 1998.
[7]P.H. Crowely, L. Provencher, S. Sloane, L.A. Dugatkin, B. Spohn, L. Rogers,
M. Alfieri. Evolving cooperation: the role of individual recognition. BioSystems, 37 (1996) 49-66.
[8]Joshua M. Epstein. Zones of Cooperation in Demographic Prisoner’s Dilemma. Working papers, 1997, Santa Fe Institute.
[9]Jacques Ferber. Multi-Agent Systems. An Introduction to distributed artificial intelligence. English Edition © Addison Wesley Longman 1999.
[10]Marcus Frean. The evolution of degrees of cooperation. Artificial Interllogence Laboratory, Departments of Computer Science and Zoology University of Otago, Dunedin, New Zealand. November 29, 1995.
[11]David Hales. Cooperation Without Memory or Space: Tags, Groups and the Prisoner’s Dilemma. 2000.
[12]David Hales. Cooperation and Specialisation without Kin Selection using Tag. CPM Working Paper 02-88 (version 2), February 2002.
[13]David Hales. Smart Agents Don’t Need Kin ─ Evolving Specialisation and Cooperation with Tags. CPM Working Paper 02-89 (version 2), February 2002.
[14]David Hales. Wise-Up! ─ Smart Tag Pairing Evolves and Persists. CPM Working Paper 02-90 (version 1), March 2002.
[15]Paul Harrald and David Fogel. Evolving continuous behaviours in the iterated prisoner’s dilemma. Biosys-tems, 37:135—145, 1996.
[16]John H. Holland. Adaptation in natural and artificial systems. University of Michigan Press, Michigan, 1975.
[17]Hisao Ishibuchi, Tatsuo Nakari, Tomoharu Nakashima. Evolution of Neighborly Relation in a Spatial IPD Game with Cooperative Players and Hostile Players. Evolutionary Computation, 1999. CEC 99. Proceedings of the 1999 Congress on , 1999 -936 Vol. 2.
[18]Oliver Kirchkamp. Spatial Evolution of Automata in the Prisoners’ Dilemma. 1995.
[19]D. Kraines and V. Kraines. Learning to cooperate with pavlov an adaptive strategy for the iterated prisoner’s dilemma with noise. Theory and Decision, 35:107—150, 1993.
[20]Kristian Lindgren and Mats G. Nordahl. Evolutionary dynamics of spatial games. Physica D 75 (1994) 292-309.
[21]Kristian Lindgren. Evolutionary Dynamics in Game-Theoretic Models. Talk presented at the workshop “The economy as an evolving complex system II”, Santa Fe Institute, Aug. 26 — Sept. 1, 1995. Institute of Physical Resource Theory Chalmers University of Technology and Goteborg University.
[22]John H. Miller. The coevolution of automata in the repeated prisoner’s dilemma. Journal of Economic Behavior and Organization. Vol. 29 (1996) 87-112.
[23]Melanie Mitchell. An Introduction to Genetic Algorithms. 1996, ISBN 0-262-13316-4.
[24]M. Nakamaru, H. Matsuda, Y. Iwasa. The Evolution of Cooperation in a Lattice-Structured Population. J. theor. Biol. (1997) 184, 65-81.
[25]Martin A. Nowak, Sebastian Bonhoeffer, and Robert M. May. Spatial games and the maintenance of cooperation. Proc. Natl. Acad. Sci. USA. Vol. 91, pp. 4877-4881, May 1994.
[26]Martin A. Nowak and Karl Sigmund. Evolution of indirect reciprocity by image scoring. Nature, VOL 393: 573-577, 11 June 1998.
[27]Nowak, Martin and Sigmund, Karl. Oscillations in the Evolution of Reciprocity. J. Theor. Biology, 137, 21-26.
[28]Nowak, Martin and May, R.M. Tit for tat in heterogeneous population. Nature, 355, pp250-253
[29]Marek Obitko and student of Czech Technical University. Introduction to Genetic Algorithms. http://cs.felk.cvut.cz/~xobitko/ga/index.html , August and September 1998.
[30]Jae C. Oh. Emergence of Kin Habitats and Cooperation in Multi-Agent Environments. In: Second International Workshop on Frontiers in Evolutionary Algorithms (FEA ’98), in: JCIS ’98 Proceedings, vol. II, Association for Intelligent Machinary, Research Triangle Park, NC, 1998, pp. 387-390.
[31]Jae C. Oh. Effects of kinship bias on cooperation in multi-agent environment. Ph.D. Dissertation Proposal, Dept of Computer Science, University of Pittsburgh, 1998.
[32]Jae C. Oh. Ostracism for Improving Cooperation in the Iterated Prisoner’s Dilemma Game. Evolutionary Computation, 1999. CEC 99. Proceedings of the 1999 Congress on , 1999 -896 Vol. 2.
[33]Jae C. Oh. Benefits of Clustering among the Internet Search Agents caught in the n-Person Prisoner’s Dilemma Game. Evolutionary Computation, 2000. Proceedings of the 2000 Congress on , Volume: 2 , 2000. Page(s): 864 -871 vol.2
[34]Jae C. Oh. Promoting cooperation using ‘kin’ biased conditional strategy in the prisoner’s dilemma game. Information Sciences 133 (2001) 149-164.
[35]Michael Oliphant. Evolving cooperation in the non-iterated prisoner’s dilemma: The importance of spatial organization. In Christopher G. Langton, editor, Artificial Life IV, page 349-352, Reading MA, 1994. Addison-Wesley.
[36]C. O’Riordan. Iterated Prisoner’s Dilemma: A review. Department of Information Technology, National University of Ireland, Galway. Technical report NUIG-IT-260601.
[37]Rick L. Riolo. The Effects of Tag-Mediated Selection of Partners in Evolving Populations Playing the Iterated Prisoner’s Dilemma. Program for Study of Complex Systems. November, 1996.
[38]Mark D. Smucker, E. Ann Stanley, Dan Ashlock. Anaylyzing Social Network Structures in the Iterated Prisoner’s Dilemma with Choice and Refusal. 1994, University of Wisconsin-Madison, Department of Computer Sciences, Technical Report CS-TR-94-1259.
[39]Masaki Tomochi and Mitsuo Kono. Spatial prisoner’s dilemma games with dynamic payoff matrices. PHYSICAL REVIEW E, VOLUME 65, 026112, 2002 The American Physical Society.
[40]John Chia-chin Wang. A Framework for Resolving Multiagent Collaboration Dilemma. System Sciences, 1998., Proceedings of the Thirty-First Hawaii International Conference on , Volume: 4 , 1998 . Page(s): 444 -451 vol.4
[41]Yao, X.; Darwen, P.J. How important is your reputation in a multi-agent environment. Systems, Man, and Cybernetics, 1999. IEEE SMC ''99 Conference Proceedings. 1999 IEEE International Conference on , Volume: 2 , 1999. Page(s): 575 -580 vol.2.
[42]Yao, X.; Darwen, P.J. Why More Choices Cause Less Cooperation in Iterated Prisoner’s Dilemma. IEEE Catalog Number: 01TH8546. Evolutionary Computation, 2001. Proceedings of the 2001 Congress on , Volume: 2 , 2001. Page(s): 987 -994 vol. 2.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top