Add Moran process

[marcharper]

At this point it would be fairly easy (I think) to add in support for population dynamics, with the Moran process and/or the common imitative-switching process. If there is interest I can get something started.

These simulations take a much longer time of course but allow the empirical computation of e.g. fixation probabilities.

[meatballs]

Do you have any links to material I could read? (i.e. I have no idea what the Moran or imitative-switching processes are)!

[marcharper]

Sure. These are called population games, and typically use the same strategies that people study for e.g. the prisoner's dilemma. So since we have so many strategies now perhaps it makes sense to consider population dynamics, but it might be out of the scope of what you all intended for this library.

Basically you have a population of N replicators all playing some strategy. The population is updated in rounds where in each round some replicator is chosen to reproduce and one is chosen uniformly at random to be replaced (a birth-death process). The reproduction process usually proceeds either as

• the Moran process -- everyone plays everyone else and the total score is fitness. Then someone is chosen to reproduce proportional to fitness
• A switching process -- total fitness is the same but individuals chose to switch strategies with a Boltzmann type probability, i.e. something like e^{\sigma F_i} where F_i is the total fitness and these values are normalized to probabilities.

The process ends when one type dominates the population (which is inevitable for these dynamics since there is no mutation). There is a wikipedia page for the Moran process but it stops short of using games for fitness (which started around 2003?); the exponential-switching process is somewhat new in the literature but essentially the same thing, just with the extra parameter sigma that plays the role of the "strength of selection". Exponentiating also avoids having zeros in the denominator for fitness-proportionate-selection, which is an issue depending on what your game matrix looks like. You can see an example in the Materials and Methods section of this paper (note that using stationary payout as fitness is not necessarily standard though).

There are some other variants, i.e. where rather than have each player play every other play every round, instead they each play a random sample of other players. In any case, the questions shift from which player gets the greater long term payout to e.g. whether a single WSLS can take over a population of TFT players (fixation probability), if a mutant has better than neutral fitness, etc.

[drvinceknight]

This would certainly need thinking about, as to where it fits etc... but it would be a brilliant addition to the library.

[meatballs]

Thank you. Some more fascinating reading for me.

but it might be out of the scope of what you all intended for this library.

That would involve us defining the purpose of this exercise!

[drvinceknight]

but it might be out of the scope of what you all intended for this library.

I think it's certainly within the scope.

That would involve us defining the purpose of this exercise!

Is this not defined? (A part from the medium term 'and then become billionaires part') I see it as:

1. Allow for people to contribute more/innovative strategies.
2. Allow anyone to reproduce versions of the tournament easily (so that this could be used as another research tool)

I tried to write a third point aiming to repeat something you said very eloquently about Djaxelrod at Djangocon @meatballs but failed, so just erased it. But what you said should definitely be it's own goal and/or indeed comes in a way under the scope of both of those points.

Those two points might well have changed though, what else are we thinking?

As such I certainly think having the replicator dynamic implemented would be a great thing to have. From the very start we have incorporated a variety of implementations of the tournament (cheating strategies, ecological variants etc...).

My only concern is A: to place it carefully within the library and B: to not make things too heavy. I don't think B is a problem and we just need to think about A :)

Right, I really am going to head to sleep now :zzz: :sleeping: :+1: :dash:

[drvinceknight]

Perhaps a simpler 'goal' is to be the 'go to package for anything Axelrod related'... Or perhaps that's too much...

I do not seem capable of removing myself from this computer. Someone might need to send food...

[langner]

I fail to see how the outcome of a Moran process or switching process would be different from the ecological variant we already have. Ultimately strategies with higher overall scores will proliferate, I presume. Can someone point out what we would expect to learn from these more complicated processes?

[marcharper]

I'd say that the Moran process isn't more complicated; there's also a vast literature on the Moran process that can be connected to, and it is still actively studied. It is straightforward to add interesting parameters to the Moran process -- mutation, strength of selection, alternate selection mechanisms, spatial distribution, etc., any one of which could lead to to publications.

The Moran process has important theoretical connections to the Wright-Fisher process and the replicator dynamics.

[langner]

Yes, and in my mind mutation would be the most interesting possibility. Is there a particular way in which you imagine this can be done?

Isn't our current ecological simulation a type of Moran process, at the limit of infinite N? Maybe it's not less complicated, but definitely less computationally intensive.

[marcharper]

Well it may be, but the presence of these lines makes it difficult to handle analytically: avg = self.payoff_matrix[ip][jp] dev = self.payoff_stddevs[ip][jp] p = random.normalvariate(avg, dev)

The Moran process is a fairly straightforward Markov process and doesn't involve e.g. normal distributions. For large N the Moran process essentially converges to the replicator equation (which is deterministic), so the model in the library is not really the same as that either.

To add mutation to the Moran process, one typically just assumes a matrix of mutations where each type has some probability of mutating into another type (and usually these are all take the be equal). If you look at my repositories stationary you can see how the transitions are calculated, and I can point you to some relevant papers if you'd like (for example http://arxiv.org/abs/1311.0941 ).

[marcharper]

One simple example of a behavior that one gets from this: coexistence of multiple types in the long run, whereas without mutation, one type will necessarily eventually dominate the population.

[langner]

Yeah, I didn't think about that dev when writing the ecological code, just wanted to reflect the variability of the stochastic strategies somehow. It will tend to zero for large populations... so should we get rid of it or at least make optional? Would that make it a better comparison to the Moran processes that you will implement?

[marcharper]

I'm not suggesting that the current implementation change since it is providing insight; rather I just want to add the Moran process as another model that the library can handle since most of the work is done (defining and testing all the strategies). We can then compare to other known results and simulations (there are a number of papers that look at the Moran process for the classical strategies like ALLD, TFT, GTFT, WSLS, and the newer ZD strategies). That gives both checks on this library and the literature, and also allows extensions in new directions.

[langner]

Yes, of course. I just think it would be nice to keep things comparable within the library itself, too. And the deviation does not influence the result, so if ignoring by default would make a comparison easier I would be for it.

[drvinceknight]

Sorry for just catching up. I would be in favour of not changing the ecological variant you implemented @langner and think it's nice to 'have both'. Comparisons can be made between them in the documentation highlighting the differences (and indeed the discussion you guys have had here). This would help understand them I think?

[langner]

Sorry for just catching up. I would be in favour of not changing the ecological variant you implemented @langner and think it's nice to 'have both'. Comparisons can be made between them in the documentation highlighting the differences (and indeed the discussion you guys have had here). This would help understand them I think?

I agree, I was thinking to just have the deviation be optional so that it would be deterministic.

[marcharper]

How about this -- I've programmed the Moran process before and it's not hard to do, so I'll go ahead and do that and we can compare the results for a few small dimensional populations (perhaps just the "basic strategies") to start.

[marcharper]

Progress!

Jupyter Notebook