Evolutionary game theory in a cell: A membrane computing approach

Evolutionary game theory in a cell: A membrane computing approach Pedro García-Victoria a , Matteo Cavaliere b, ⇑ , Miguel A. Gutiérrez-Naranjo a , Miguel Cárdenas-Montes c a Department of Computer Sciences and Artificial Intelligence University of Seville, Spain b Department of Computing and Mathematics, Manchester Metropolitan University, UK c Department of Basic Research, Centro de Investigaciones Energéticas Medioambientales y Tecnológicas, Madrid, Spain article info Article history: Received 30 June 2021 Received in revised form 15 December 2021 Accepted 27 December 2021 Available online 5 January 2022 Keywords: Probabilistic P systems Membrane computing Evolutionary game theory abstract Evolutionary Game Theory studies the spreading of strategies in populations. An important question of the area concerns the possibility that certain population structures can facilitate the spreading of more cooperative behaviours associated to the sustainability and resilience of many different systems ranging from ecological to socio-economic systems. In this paper, we propose a novel approach to study the spreading of behaviours in structured populations by combining Evolutionary Game Theory and membrane computing. We show that there is a general way to encode Evolutionary Game Theory into membrane computing, leading to a novel computational framework which can be used to study, analyze and simulate the spreading of behaviours in structured populations organized in communicating compartments. The proposed approach allows to extend the works on membrane systems, population and ecological dynamics, and, at the same time, suggests a novel bioinspired framework, based on formal languages theory, to investigate the dynamics of evolving structured populations. 1. Introduction Evolutionary Game Theory (EGT, for short) is a mathematical and computational framework which is used to study the spreading of behaviours (strategies) in evolving populations [1,2]. While classical game theory is used to describe the behaviour of completely rational players, in EGT, the individual strategies are not associated to rational choices, but they are assumed to be encoded into inherited programs that can be passed to the offsprings [2]. The main driving principle of EGT is that individuals that perform better (they get a higher payoff/fitness) will tend to replicate more often, so their encoded strategy will spread in the population [2]. The success (fitness) of an individual depends not only on its own adopted strategy but also on the strategies of the other individuals with whom is interacting in the population [2]. This means that there could not be an universal optimal strategy but the optimal choice may depend on the strategies that are adopted by the other components of the population (this makes EGT different from standard optimization and is technical referred as frequency-dependent selection in the area of evolutionary dynamics [2]). ⇑ Corresponding author. E-mail addresses: [email protected] (P. García-Victoria), [email protected] (M. Cavaliere), [email protected] (M.A. Gutiérrez-Naranjo), [email protected] (M. Cárdenas-Montes). https://doi.org/10.1016/j.ins.2021.12.109 0020-0255/ An important problem studied using EGT is the resilience of cooperation and the conflict between cooperative and noncooperative (cheating/defecting) individuals [3]. This issue is present in many systems, at different scales ranging from technological systems [4] to microbial systems [5] and human societies [6] and it is considered one of the most relevant problems in science [7]. The study of the resilience of cooperation in structured populations has received a strong attention [8,?,?,11– 13], suggesting that the population structure (e.g., the social network) is a crucial part of the problem [10,12]. Therefore the search of appropriate, efficient and general mathematical and computational frameworks to study the interplay of population structure and spreading of certain strategies has become an important research area [8,9,14,15]. The dynamics of an EGT model can be studied analytically [1] but very often is simulated using ad hoc agent-based computational models [15]. In these models, the replication and death of individuals (agents) are explicitly simulated using a system updated by a series of discrete events [15]. In this paper, we propose a novel computational approach to study the spreading of behaviours in structured populations by combining EGT and membrane computing. Using the proposed approach, we show that there is an effective and general way to encode EGT into probabilistic membrane computing and P-Lingua [16,17]. This work therefore enhances the area of membrane computing, extending the line of research focused on the simulation and study of population/ecological dynamics [17,18] allowing the study of the spreading of strategies in populations structured in compartments using probabilistic simulators such as P-Lingua [17]. At the same time, the proposed combination enriches the EGT area with a novel cellularinspired framework to study, analyze and simulate the spreading of behaviours in structured evolving populations organized in communicating nested compartments. Our proposal will make possible to tackle further systems, for instance those related to the cooperation concerns. To sum up, the main contributions of this paper are the following: A novel approach to study the spreading of behaviours in structured populations by combining Evolutionary Game Theory and membrane computing is proposed. We show that there is a general way to encode Evolutionary Game Theory into membrane computing, leading to a computational framework which can be used to study, analyze and simulate the spreading of behaviours in structured populations organized in communicating compartments. The proposed approach allows to extend the works on membrane systems, population and ecological dynamics, and, at the same time, suggests a novel bio-inspired framework, based on formal languages theory, to investigate the dynamics of evolving structured populations. The paper is organized as follows: Section 2recall some basics of the P system model used along the paper. Among the possible models, our choice has been probabilistic P systems, since probability (in replication, deletion or migration) is one of the pillars of EGT. In Section 3, we present the design of a family of probabilistic P systems which simulates the behaviour of EGT and a short overview of the computation. It deserves to be remarked that all the simulation is performed by P system rules, without considering oracles or external functions. In this way, MeCoSim simulator [19] has been used for the experiments. Section 4show some examples of EGT cases and how the compartmental structure of P systems can help in the development of the interaction among populations. Finally, the paper finishes with some conclusions and hints for future work. 2. Probabilistic P systems Since Gh. Pa ˘un introduced in 1998 the first model of membrane computing [20] till now, many different variants of P systems have been presented. Among them, spiking neural P systems (SNPS) [21] is one of the most widely extended. From the starting model of SNPS, many other features have been added and explored. Among the most recent, we can cite Homogeneous spiking neural P systems with structural plasticity [22],Delayed Spiking Neural P Systems with Scheduled Rules [23] or Spiking neural P systems with autapses,[24]. Among the recent contributions we can cite the SN P systems with communication on requests [25,26] or SN P systems variant used in optimization and for building an arithmetic calculator [27–29]. Beyond SNPS, many other P system variants have proved their efficiency in order to model real life problems. In particular, probabilistic/stochastic models [16] have shown its efficiency in problems from biological processes. In this paper, we consider the so-called probabilistic P systems [17] introduced by Cardona et al.in 2011. Next, we briefly summarize some of their main features. Let us consider a working alphabet Cand a membrane structure where different membranes have different labels. Membranes have electrical charges from the set f0;þ;g and Ris a finite set of evolution rules of the form u½ v  a i !u0½ v 0 a 0 j where u;u0; v and v 0are multisets over C;iand jare labels 1 and a;a02f0;þ;g. The representation of information as multisets placed on a membrane structure and the use of biologically inspired rules for performing the evolution of such multiset of objects is common to many P system variants. The main feature of the prob- 1 In the original description of probabilistic P systems i¼j. P. García-Victoria, M. Cavaliere, M.A. Gutiérrez-Naranjo et al. 581 abilistic P systems is that the rules are endowed with a computable function f r ;ðr2RÞsuch that domðf r Þ#f1;...;Tg(with T a natural number) and rangeðf r Þ#½0;1verifying that if r 1 ;...;r z are the rules form Rwith the same left-hand side (i.e., u½ v  a i ) then P z j¼1 f r j ðaÞ¼1 for a¼1;...;T. Intuitively, such f r ðaÞrepresents the probabilistic constant associated with rule r. In general, it is written as r:u½ v  a i ! f r ðaÞ u0½ v 0 a 0 j .Iff r ðaÞ¼1, then it is denoted by r:u½ v  a i !u0½ v 0 a 0 j . The key point is that in this P systems applicable rules are non-deterministic chosen as usual, but, in this case the probability of each rule can be fixed at the beginning of the computation. The semantics of the P system follow the next principles: [I1] When an object cross a membrane, its polarization may change. In such way, the electrical charges can act as traffic lights, i.e., rules can only be applied if the polarization of the rule is the appropriate. [I2] If a rule can be applied inside a membrane and, in the same step a send-in or send-out rule which changes the polarization of the membrane can also be applied, both rules are applied. In a certain sense, we can consider that the change of the polarization is performed after the application of the evolution rules. 3. Evolutionary Game Theory in P systems In this section, the description of a P system which computes the evolution of a population according to Game Theory is provided. The main contribution of this approach is that different sub-populations can be encapsulated in P system membranes. Individuals inside such membranes evolve according Game Theory principles: Each individual gets a fitness value obtained by meetings with other individuals according to a chosen strategy. One of the individuals is replicated. The probability of replication of an individual is proportional to its fitness value. In order to keep constant the number of individuals, after replication one individual is randomly chosen to be deleted. Each sub-population evolves by these principles in a compartment. After each cycle one individual in each compartment migrates to other compartment. These migration between compartments is possible due to the intrinsic nature of P systems and it represents a big chance for exploring the behaviour of these populations. Next, we describe the technical details of the proposed model. Let us consider a population of nQindividuals distributed on Qcompartments. In each compartment, there are nindividuals with identifiers 1;...;n. Due to technical reasons, in our approach, nmust be even. Each individual can follow two different strategies: cooperator or defector. When a cooperator meets another cooperator, they both get R(Reward). If a cooperator meets a defector, the cooperator gets S(the Sucker’s payoff) and the defector T(the Temptation). If two defectors meet, they both get P(the Punishment). This can be encoded in a payoff matrix. Cooperate Defect Cooperate RS Defect TP or in a 4-tuple hR;S;T;Pi. In our design, each compartment (which is represented by an elementary membrane) has a different payoff matrix and individuals can move from one into other compartment. In this way, we can study the evolution of the different populations of individuals according to the different payoff matrices and the influence of the communication among compartments. The number of individuals in each compartment keeps constant along the computation, but the proportion of defectors and cooperators in each compartment can change due to the processes of replication, deletion and migration. For each compartment k2f1;...;Qg, we have a payoff matrix represented by hR k ;S k ;T k ;P k i. In our approach, each individual have exactly Mmeetings per cycle. In such way, a cooperator in the compartment kwill have, after Ameetings, an accumulated payoff which can be calculated as the sum of Avalues taken from R k and S k in all the possible ways, i.e., the possible accumulated payoff of a cooperator after Ameetings in the membrane kis one of the values of V c;k;A ¼fðrS k ÞþððNrÞR k Þjr2f0;...;Agg Analogously, the possible accumulated payoff of a defector after Ameetings in the membrane kis one of the values of V d;k;A ¼fðrT k ÞþððNrÞP k Þjr2f0;...;Agg In EGT, the fitness F of an individual depends on: (1) The accumulated payoff Ac; (2) The number of meetings of the individual Mand; (3) A parameter wwhich we call influence. The fitness is computed by the formula F¼ð1wÞþwAc Mð1Þ P. García-Victoria, M. Cavaliere, M.A. Gutiérrez-Naranjo et al. 582 In this way, each individual will obtain a fitness depending on Ac;Mand wand its probability of replication will be proportional to its fitness. In our model, the number of meetings Mis fixed and also the influence wand therefore, the fitness F i of an individual iwith accumulated payoff Ac i is computed as F i ¼ð1wÞþwAc i Mð2Þ From this equation we have MF i ¼Mð1wÞþwAc i ð3Þ We can consider that New F i ¼MF i is the fitness F i scaled by a constant Mand then New F i ¼MþwðAc i MÞ ð4Þ Since P systems deal with integer numbers, we can approximate Eq. 4by considering New F i ¼MþbwðAc i MÞc ð5Þ where bxcis greatest integer less than or equal to x. We define the following set LF c;k of pairs ðAc;New F i Þ, where Ac is the accumulated payoff obtained by a cooperator after Mmeetings in the membrane kand New F i the fitness value obtained from Ac according to Eq. 5, LF c;k ¼fðAc;New FÞjAc 2V c;k;M g We will denote by MaxF c the maximum value of the fitness that can be reached by a cooperator in any membrane, i.e., MaxF c ¼maxfBjðA;BÞ2[ k¼Q k¼1 LF c;k g Analogously, LF d;k of pairs ðAc;New F i Þ, where Ac is the accumulated payoff obtained by a defector after Mmeetings in the membrane kand New F i the fitness value obtained from Ac according to Eq. 5, LF d;k ¼fðAc;New FÞjAc 2V d;k;M g and MaxF d is the maximum value of the fitness that can be reached by a defector in any membrane, i.e., MaxF d ¼maxfBjðA;BÞ2[ k¼Q k¼1 LF d;k g In order to define formally a P system which simulates the evolution of the Game Theory, we will consider different type of objects: An individual will be represented by a tuple hId;t;Am;Apiwhere –Id 2f1;...;ngis the identifier of the individual; –t2fc;dgis the strategy of the individual: cooperator ðcÞor defector ðdÞ; –Am is the number of meetings in the current configuration; –Ap is the accumulated payoff in the current configuration. At the beginning of the computation, each compartment has nindividuals with identifiers 1;...;nand each individual has a strategy. After each cycle, each compartment has again nindividuals with identifiers 1;...;n, but the proportion of defectors and cooperators can change due to the processes of deletion, replication and migration. Two special kind of objects are p Id;j and q Id;j . Each of these objects represent a payoff unit of the individual with identifier Id :p Id;j if it is a cooperator and q Id;j if it is a defector. Other auxiliary objects will be also used: z i ;f i ;h i ;K;L;L a ;L b ;V;def;coop ... Broadly speaking, the computation is performed according to the following stages: 1. Meetings stage. Each individual have Mmeetings with other individuals randomly chosen in each cycle. It can have more than one meeting with the same individual. Each meeting modifies the accumulated payoffs of the individuals according to their strategies and increases by 1 the number of meetings of the individuals. From a P system point of view, these meetings will be performed along Msteps. In order to be sure that all the individuals can be paired and have a meeting in each step, we will consider that the number of individuals nin each compartment is an even number. The end of this stage will be controlled by changing the polarization of the membrane where the meetings occur. This stage is performed in parallel along the Qelementary membranes. 2. Replication and killing stage. After Msteps, the meetings between individual stop and the reproduction stage begins. In each elementary membranes, only one of the individuals is chosen to replicate and the probability of an individual to be chosen is proportional to its fitness. As pointed out above, the correspondence between the accumulated payoff and the fitness is stored in the sets LF c;k and LF d;k . Each of the pairs ðA;BÞin these sets will produce rules of type ½hId;c;M;Ai!p Id;1 ...p Id;B hId;c;0;0i þ k P. García-Victoria, M. Cavaliere, M.A. Gutiérrez-Naranjo et al. 583 ½hId;d;M;Ai!q Id;1 ...q Id;B hId;d;0;0i þ k Rule ½hId;c;M;Ai!p Id;1 ...p Id;B hId;c;0;0i þ k takes a cooperator with identifier Id such that, after Mmeetings, has obtained an accumulated payoff Aand produces Bdifferent objects p Id;1 ...p Id;B where Bis the fitness associated 2 to the accumulated payoff Aaccording to the corresponding LFc;k. This rule also reset to 0 the accumulated payoff and the number of meetings and produces hId;c;0;0i. The case of a defector is analogous. In parallel with the production of objects pId;jand qId;j, a set of rules is applied in order to compute the mutation process. A unique object L(Lfor life) is produced in each elementary membrane. In the next step of computation, one and only one of the following rules is triggered: ½L!Laþ kwith probability U(the probability of mutation). ½L!Lbþ kwith probability V(the probability of no mutation). Let us notice that both rules have the same left-hand-side and the sum of the probabilities is UþV¼1. If Lais produced the replication process inside the membrane kwill occur with mutation. If Lbis produced, the replication will be without mutation. Let us suppose that Lbis generated, i.e., the replication of the randomly chosen individual will be performed without mutation. In such case one and only one of the following rules is applied. ½p Id;j L b !coopK  þ k ½q Id;j L b !def K  þ k Since the amount of copies of p Id;j and q Id;j represents the fitness of the individual Id (cooperator and defector, respectively), the probability of triggering one of these rules is proportional to B, i.e., proportional to the fitness of the individual. Since there is only one object L b , only one of these rules is applied. Since L b denotes no mutation, the object p Id;j produces a new object coop and q Id;j produces a new object def. Such object coop and def can be considered flags in order to recall that the individual which will be produced at the end of the replication process will be a cooperator or a defector (respectively). If L a is generated, the replication will be performed with mutation. It means that L a together with a copy of p Id 1 ;j (i.e., an object which represents a payoff unit of a cooperator) will produce a defector or, analogously, L a together with a copy of q Id 1 ;j (i.e., an object which represents a payoff unit of a defector) will produce a cooperator. The rules are the following: ½p Id;j L a !def K  þ k ½q Id;j L a !coopK  þ k In any case, the application of one of these replication rules produce an object K(Kfor killer). In the next step, Kchooses randomly one of the individuals and delete it by application of one of the rules ½KhId;c;0;0i!K Id  þ k ½KhId;d;0;0i!K Id  þ k The application of such rule produces an object K Id which can be considered a flag for recalling the identifier of the object which has been deleted. Finally we combine the flag K Id with the flag coop or def and produce a new individual with the strategy obtained by the probabilistic process of mutation and with the identifier of the deleted individual. The rules are ½K Id coop !hId;c;0;0i þ k ½K Id def !hId;d;0;0i þ k In any case, after the replication and killing stage, in each compartment kthere are nindividuals with identifiers 1;...;n. 3. Migration stage. At the end of the replication and killing stage, a new object V(Vstands for voyager) appears in each elementary membrane k. In parallel, each of these objects Vchooses randomly one of the individuals of the compartment and sends it out of the elementary membrane, by the application of one of the rules ½VhId;c;0;0i þ k !V k;Id hId;c;0;0i½  k ½VhId;d;0;0i þ k !V k;Id hId;d;0;0i½  k One of these rules is applied in parallel in each of the Qmembranes and therefore, after the application, there are Qindividuals in the membrane surrounding the Qelementary membranes. Objects V k;Id can be considered as flags for remembering that the individual sent out from membrane khad identifier Id. In the next step of computation, each of these individuals is randomly paired to an object V k;Id 2 and one of the following rules is randomly applied 2 If B¼0, then these rules are simply ½hId;c;M;AihId;c;0;0iþ kand ½hId;d;M;Ai!hId;d;0;0iþ k. P. García-Victoria, M. Cavaliere, M.A. Gutiérrez-Naranjo et al. 584 hId 1 ;c;0;0iV k;Id 2 ½ þ k !½hId 2 ;c;0;0i  k hId 1 ;d;0;0iV k;Id 2 ½ þ k !½hId 2 ;d;0;0i  k Object V k;Id 2 brings the individual hId 1 ;c;0;0iinside the membrane kand modifies the identifier in order to keep the unicity of the identifiers in the membrane. Let us notice that sending hId 1 ;c;0;0iinside the membrane kchanges its identifier to Id 2 , but the individual keeps its strategy. With this step, the migration process finishes. After computing these stages Meeting, Replication/Killing and Migration, the P system is again ready for a new Meeting stage. 4. Stopping stage. The cycle of the previous three stages is performed Ctimes. After these Ccycles, the computation stops. These stages are summarized in Algorithm 1. Algorithm1: Summary The following cycle of three stages is performed Ctimes Stage 1 (Meeting stage): It is performed in parallel in the Qelementary membranes; It takes Msteps of the P system; Each meeting modifies the accumulated payoff of the involved individuals. Stage 2 (Replication and killing stage): In each elementary membrane: IOne individual is chosen with probability proportional to its fitness; IThe individual is replicated (maybe with mutation in its strategy). IAn individual is removed (killed). Stage 3 (Migration stage): In each elementary membrane, one individual is randomly chosen and sent into other membrane; The algorithm finishes with a Stopping stage. Definition of the P system Let us consider a EGT system with the following parameters 3 : For each compartment i: R i :Reward S i :Sucker’s payoff T i :Temptation R i :Punishment Other parameters: n: Number of individuals in each compartment M: Number of meetings per cycle w: Influence U: Prob. of mutation V: Prob. of no mutation C: Number of cycles Q: Number of compartments Let us also consider the finite sets of tuples LF c;k and LF d;k . In these conditions, let us consider the following P system P ¼h C ;H;EC; l ;w 1 ;...;w Q ;w g ;w s ;Ri where The alphabet of objects is 3 Let us remark that the choice of these parameters (number of compartments Q, number of individuals in each compartment n, etc. depends on the concrete instance of the problem to be simulated. Once fixed these parameters, the P system Pis completely defined and its evolution, and hence the simulation of the EGT problem, follows the membrane computing principles. P. García-Victoria, M. Cavaliere, M.A. Gutiérrez-Naranjo et al. 585 C ¼fhId;t;Am;ApijId 2f1;...;ng;t2fc;dg;Am 2f0;...;Mg;Ap 2[ i¼Q i¼1 g [fp Id;j jId 2f1;...;ngj2f1;...;MaxF c gg [fq Id;j jId 2f1;...;ngj2f1;...;MaxF d gg [fz k jk2f0;...;Mþ3gg [fL;L a ;L b ;K;V;coop;defg [ff i;k ji2f1;...;7gk2f1;...;Qgg [fV k;Id jId 2f1;...;ngk2f1;...;Qgg [fh s js2f0;...;CM þ7C3gg H¼f1;...;Qg[fg;sgis the set of labels; EC ¼f0;þ;g is the set of electrical charges; The membrane structure has Qelementary membranes with labels 1;...;Q; the skin with label s; an intermediary membrane with label g; l ¼½½½ 0 1 ... ½ 0 Q  0 g  0 s The initial multisets are w j ¼z 0 hId;t j Id ;0;0ifor j2f1;...;Qg;Id 2f1;...;ngand t j Id 2fc;dgis the strategy followed by the Id-th individual in the j-th elementary membrane in the initial configuration. We also have w g ¼£and w s ¼h 0 . We will also consider the following sets of rules R(krepresents the empty multiset). Meeting rules: Let hR k ;S k ;T k ;P k iis the encoding of the payoff matrix inside the compartment k2f1;...;Qg. RS 1 ½hId 1 ;c;A;BihId 2 ;c;A;Ci!hId 1 ;c;Aþ1;BþR k ihId 2 ;c;Aþ1;CþR k i 0 k for k2f1;...;Qg;Id 1 ;Id 2 2f1;...;ng;A2f0;...;M1g;B;C2V c;k;A RS 2 ½hId 1 ;c;A;BihId 2 ;d;A;Ci!hId 1 ;c;Aþ1;BþS k ihId 2 ;c;Aþ1;CþT k i 0 k , for k2f1;...;Qg;Id 1 ;Id 2 2f1;...;ng;A2f0;...;M1g, B2V c;k;A ;C2V d;k;A RS 3 ½hId 1 ;d;A;BihId 2 ;d;A;Ci!hId 1 ;d;Aþ1;BþP k ihId 2 ;d;Aþ1;CþP k i 0 k for k2f1;...;Qg;Id 1 ;Id 2 2f1;...;ng;A2f0;...;M1g;B;C2V d;k;A Replication rules: RS 4 ½hId;c;M;Ai!p Id;1 ...p Id;B hId;c;0;0i þ k for k2f1;...;Qg;Id 2f1;...;ng, A2V c;k;M and ðA;BÞ2LF c;k RS 5 ½hId;d;M;Ai!q Id;1 ...q Id;B hId;d;0;0i þ k for k2f1;...;Qg;Id 2f1;...;ng, A2V d;k;M and ðA;BÞ2LF d;k RS 6 ½L! U L a  þ k , i.e., ½L!L a  þ k with probability U(for k2f1;...;Qg). RS 7 ½L! V L b  þ k , i.e., ½L!L b  þ k with probability V(for k2f1;...;Qg). RS 8 ½p Id;j L a !def K  þ k for k2f1;...;Qg, Id 2f1;...;ngand j2f1;...;MaxF c g RS 9 ½q Id;j L a !coopK  þ k for k2f1;...;Qg, Id 2f1;...;ngand j2f1;...;MaxF d g RS 10 ½p Id;j L b !coopK  þ k for k2f1;...;Qg, Id 2f1;...;ngand j2f1;...;MaxF c g RS 11 ½q Id 1 ;j L b !def K  þ k for k2f1;...;Qg, Id 2f1;...;ngand j2f1;...;MaxF d g RS 12 ½K Id coop !hId;c;0;0i þ k for k2f1;...;Qgand Id 2f1;...;ng. RS 13 ½K Id def !hId;d;0;0i þ k for k2f1;...;Qgand Id 2f1;...;ng. Killing rules: RS 14 ½KhId;t;0;0i!K Id  þ k for k2f1;...;Qg;t2fc;dgand Id 2f1;...;ng Migration rules: RS 15 ½VhId;t;0;0i þ k !V k;Id hId;t;0;0i½  k for k2f1;...;Qg;Id 2f1;...;ng;t2fc;dg RS 16 hId 1 ;t;0;0iV k;Id 2 ½  k !½hId 2 ;t;0;0i  k for k2f1;...;Qg;Id 1 ;Id 2 2f1;...;ng;t2fc;dg Control rules: For k2f1;...;Qg. RS 17 ½z i !z iþ1  0 k for i2f0;...;M3g[fM;Mþ1;Mþ2g. P. García-Victoria, M. Cavaliere, M.A. Gutiérrez-Naranjo et al. 586 RS 18 ½z M2 !z M1 f 0;k  0 k RS 19 ½z M1 !z M L 0 k RS 20 ½z Mþ3 !V þ k RS 21 ½f 0;k  0 k !f 1;k ½ þ k RS 22 ½f i;k !f iþ1;k  0 g for i2f1;...;6g. RS 23 f 7;k ½  k !½z 0  0 k Stopping rules: RS 24 ½h i !h iþ1  0 s for i2f0;...;CM þ7C4g. RS 25 h CMþ7C3 ½ 0 g !½h CMþ7C3  þ g Cleaning rules: RS 26 ½p Id;j !k 0 k for k2f1;...;Qg, Id 2f1;...;ngand j2f1;...;maxfBjðA;BÞ2LF c;k g RS 27 ½q Id;j !k 0 k for k2f1;...;Qg, i2f1;...;ngand j2f1;...;maxfBjðA;BÞ2LF d;k g RS 28 ½L a !k 0 k for k2f1;...;Qg. RS 29 ½L b !k 0 k for k2f1;...;Qg. Overview of the Computation We start with the initial configuration. In consists on Qelementary membranes, the skin (with label s) and the intermediate one (with label g). All of them have polarization 0. Each elementary membrane contains the object z 0 , plus nindividuals with identifiers 1;...;n. All the individuals have accumulates meetings and accumulated payoff equals to 0. Each of them has also a strategy cor d(t j i denotes the strategy of the individual with identifier iin the elementary membrane j). The skin contains an object h 0 . C 0 ¼ hId 1 ;t 1 1 ;0;0i...hId n ;t 1 n ;0;0iz 0  0 1 ... hId 1 ;t Q 1 ;0;0i...hId n ;t Q n ;0;0iz 0  0 Q 2 6 6 4 3 7 7 5 0 g h 0 2 6 6 4 3 7 7 5 0 s From this starting configuration only meeting rules can be applied (together with rules ½z 0 !z 1  0 k from the set of rules RS 17 and the rule ½h 0 !h 1  0 s from the set of rules RS 24 ). Each individual has a meeting with another individual and their accumulated payoff change according to their strategies. In order to fix ideas let us consider a concrete example in the elementary membrane 1 with the payoff matrix settled to R 1 ¼5;S 1 ¼1;T 1 ¼10;P 1 ¼3. Let us also consider that there are six individuals, four cooperators with identifiers 1;...;4 and two defectors with identifiers 5 and 6. In this case, the initial configuration in the elementary membrane 1 is: h1;c;0;0ih2;c;0;0ih3;c;0;0i h4;c;0;0ih5;d;0;0ih6;d;0;0iz 0  0 1 Let us suppose that the non-deterministically chosen rules has been ½h1;c;0;0ih3;c;0;0i!h1;c;1;5ih3;c;1;5i 0 k ½h2;c;0;0ih5;d;0;0i!h2;c;1;1ih5;d;1;10i 0 k ½h4;c;0;0ih6;d;0;0i!h4;c;1;1ih6;d;1;10i 0 k From a Game Theory point of view, cooperators 1 and 3 meet; cooperator 2 and defector 5 meet; and cooperator 4 with defector 6. In this way, the configuration at time 1 in this elementary membrane is h1;c;1;5ih2;c;1;1ih3;c;1;5i h4;c;1;1ih5;d;1;10ih6;d;1;10iz 1  0 1 These meetings occur in parallel in the Qelementary membranes. Since the polarization of these elementary membranes has not changed, the next step is similar to this one: only rules from the meeting set can be applied together with the corresponding rules from RS 17 and RS 24 . The P system goes on with the evolution till reaching the configuration M2. The configuration at time M2 is (in the general case) is C M2 ¼ hId 1 ;t 1 1 ;M2;Y 1;1 M2 i...hId n ;t 1 n ;M2;Y n;1 M2 iz M2 hi 0 1 ... hId 1 ;t Q 1 ;M2;Y 1;Q M2 i...hId n ;t Q n ;M2;Y n;Q M2 iz M2 hi 0 Q 2 6 6 6 4 3 7 7 7 5 0 g h M2 2 6 6 6 6 4 3 7 7 7 7 5 0 s P. García-Victoria, M. Cavaliere, M.A. Gutiérrez-Naranjo et al. 587 In the next step of computation, the meeting rules are still applied. We also applied the rules RS 18 and a rule of the set RS 24 . C M1 ¼ ... hId j ;t 1 j ;M1;Y j;1 M1 i... z M1 f 0;1 hi 0 1 ... ... hId j ;t Q j ;M1;Y j;Q M1 i... z M1 f 0;Q hi 0 Q 2 6 6 6 4 3 7 7 7 5 0 g h M1 2 6 6 6 6 4 3 7 7 7 7 5 0 s In each elementary membrane kin the configuration C M1 a new object f 0;k appears. From this configuration, meeting rules can be applied together with RS 19 , rules from RS 21 and the corresponding rule from the set RS 24 . The application of rules from R 21 changes the polarization of the elementary membranes, but according to the principle I2, we consider that the evolution inside this membrane can be performed in the same computation step. In this way, the configuration a time Mis C M ¼ ... hId j ;t 1 j ;M;Y j;1 M i... z M L hi þ 1 f 1;1 ... ... hId j ;t Q j ;M;Y j;Q M i... z M L hi þ Q f 1;Q 2 6 6 6 4 3 7 7 7 5 0 g h M 2 6 6 6 4 3 7 7 7 5 0 s Since the polarization of the elementary membranes has changed to +, now the meeting rules cannot be applied and the replication and killing stage starts. Each individual hId;c;M;Aiin the membrane kevolves to an individual hId;c;0;0itogether with Bobjects p Id;1 ;...p Id;B where ðA;BÞis a pair in LF c;k . This evolution is performed by the application of the corresponding rule from RS 4 . As pointed out above, the fitness Bcorresponding to the accumulated payoff Ais expressed by the object p Id;1 ...p Id;B . The application of the rule also resets the accumulated meetings and payoff of the individual to 0. The case of the defectors and the application of the rules from the set RS 5 is analogous. In each elementary membrane, a new objects Lhas appeared. Lstarts the replication process. In each elementary membrane, one and only one of the rules RS 6 or RS 7 is triggered according to the probability of mutations. If L a is produced, then there is mutation in the replication process; otherwise, if L b is produced, there is no mutation. Rules RS 17 and the corresponding from the sets RS 22 and RS 24 are also applied. C Mþ1 ¼ ... hId j ;c;0;0iq Id j ;1 ...p 1;B 1 j ... z Mþ1 L a=b hi þ 1 f 2;1 ... ... hId j ;d;0;0iq Id j ;1 ...q 1;B 1 j ... z Mþ1 L a=b hi þ 1 f 2;Q 2 6 6 6 4 3 7 7 7 5 0 g h Mþ1 2 6 6 6 4 3 7 7 7 5 0 s In the next step the replication is starts. Let us consider that L b was produced in the previous step. The object L b is interpreted as the no-mutation object. This object is involved in the application of rules from RS 10 and RS 11 . Since p Id;j is a fitness unit of a cooperator and L b denotes that there is no mutation, the application of the rule RS 10 ½p Id;j L b !coopK  þ k will produce a flag coop which will be used to recall the strategy of the offspring. Rules for 8 to RS 11 consider all the possibilities of producing a flag coop or def depending on the strategy of the individual chosen to be replicated (denoted by p Id;j or q Id;j and the probability of mutation. Let us notice that, in any case, a new object Kis produced. Rules from RS 17 ;RS 22 and RS 24 are also triggered. C Mþ2 ¼ ... hId j ;c;0;0iq Id j ;1 ...p 1;B 1 j ... z Mþ2 coop=def K hi þ 1 f 3;1 ... ... hId j ;d;0;0iq Id j ;1 ...q 1;B 1 j ... z Mþ2 coop=def K hi þ 1 f 3;Q 2 6 6 6 4 3 7 7 7 5 0 g h Mþ2 2 6 6 6 4 3 7 7 7 5 0 s In any case, regardless which of the rules from RS 8 to RS 11 is triggered, an object Kwill appear in the elementary membrane. As we will see below, such object Kwill be used to delete one of the individuals of the membrane randomly chosen. Let us notice the special case where all the individuals in the membrane are defectors all of them and the punishment P k of the payoff matrix associated to the membrane is P k ¼0. In such case, all the possible meetings couple two defectors and their accumulated payoffs are constant (increased by P k ¼0). In such case, objects q i;j are never produced by RS 5 and therefore, RS 9 nor RS 11 are applied. This means that in such membrane there is no replication. As a secondary effect, since RS 9 and RS 11 are not applied, then the object Kis not produced, an none of the individuals of the membrane is deleted. There is no replication an no deletion in this elementary membrane, but it is still possible the migration and then, the possibility of introducing cooperators in the membrane. In the next step, one of the killing rules from RS 14 is applied in each elementary membrane. The object Krandomly chooses an individual and removes it. The result of the application of the rule is a new object K Id which recalls the identifier of the deleted individual. Rules from RS 17 ;RS 22 and RS 24 are also triggered. P. García-Victoria, M. Cavaliere, M.A. Gutiérrez-Naranjo et al. 588