EVOLUTION AND THE COMPLEXITY OF FINITE AUTOMATA

被引：1
作者：
Kilani, Moez [1 ]
机构：
[1] Univ Sousse, Dept Quantitat Econ, ISG, Rue Abdelaziz el Behi, Sousse 4000, Tunisia
来源：
INTERNATIONAL GAME THEORY REVIEW | 2007年 / 9卷 / 04期
关键词：
Finite automata; complexity of the strategy; cooperation; evolution;
D O I：
10.1142/S0219198907001692
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
Prisoner's dilemma played by finite automata is reviewed again using a slightly modified measure of complexity. At a first step, an equilibrium with a large number of possible outcomes is shown to hold. At a second stage, we consider a game of repeated interaction, and show that on (limit) equilibrium only cooperative actions are played. We conclude that cooperation is the result of a (complex) long interaction.
引用
收藏
页码：731 / 743
页数：13
相关论文
共 50 条
  • [1] Complexity of control on finite automata
    Delvenne, Jean-Charles
    Blondel, Vincent D.
    IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 2006, 51 (06) : 977 - 986
  • [2] Transition Function Complexity of Finite Automata
    Valdats, Maris
    BALTIC JOURNAL OF MODERN COMPUTING, 2019, 7 (03): : 342 - 353
  • [3] The Complexity of Compressed Membership Problems for Finite Automata
    Jez, Artur
    THEORY OF COMPUTING SYSTEMS, 2014, 55 (04) : 685 - 718
  • [4] The Complexity of Compressed Membership Problems for Finite Automata
    Artur Jeż
    Theory of Computing Systems, 2014, 55 : 685 - 718
  • [5] THE COMPLEXITY OF CONCATENATION ON DETERMINISTIC AND ALTERNATING FINITE AUTOMATA
    Hospodar, Michal
    Jiraskova, Galina
    RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS, 2018, 52 (2-4): : 153 - 168
  • [6] On the descriptional complexity of finite automata with modified acceptance conditions
    Holzer, M
    Kutrib, M
    THEORETICAL COMPUTER SCIENCE, 2005, 330 (02) : 267 - 285
  • [7] Descriptional and computational complexity of finite automata-A survey
    Holzer, Markus
    Kutrib, Martin
    INFORMATION AND COMPUTATION, 2011, 209 (03) : 456 - 470
  • [8] The complexity of compressing subsegments of images described by finite automata
    Karhumäki, J
    Plandowski, W
    Rytter, W
    DISCRETE APPLIED MATHEMATICS, 2003, 125 (2-3) : 235 - 254
  • [9] Communication complexity method for measuring nondeterminism in finite automata
    Hromkovic, J
    Seibert, S
    Karhumäki, J
    Klauck, H
    Schnitger, G
    INFORMATION AND COMPUTATION, 2002, 172 (02) : 202 - 217
  • [10] The complexity of intersecting finite automata having few final states
    Michael Blondin
    Andreas Krebs
    Pierre McKenzie
    computational complexity, 2016, 25 : 775 - 814
12345