Implementing Spatial Tournaments

[Nikoleta-v3]

Spatial Tournaments are usually implemented on a lattice, where usually players only play their neighbours(on a lattice). I will be working on implementing a spatial tournament that is more generally defined by a graph(players play who ever they are connected to).

@drvinceknight and I are talking about using networkx for the graph part. The graph would only be an input to a new match generator class. As a dependency networkx is not too heavy but it would be good to hear everyone’s thoughts(we could use a dictionary, but that would be a bit messy).

After this to match the literature I will explore various evolutionary processes one of which could be a spatial Moran process. But that's for later.

If anyone is interested here is some of the literature :

-Nowak and May, 1992
-Lindgren and Nordahl, 1994
-Maciver, 2014

[meatballs]

That's very nicely timed!! I'm looking into the best way to represent graphs on another project and networkx might just be the answer.

[marcharper]

Look into "games on graphs" and birth-death processes on graphs. I've implemented some of the details in my mpsim and stationary libraries, and we can certainly pull from those. But I haven't specifically targeted spatial games.

I actually ended up using a custom graph class, essentially a sparse matrix representation of the adjacency matrix that allows multiplication. I'm sure there are good third party libraries now.

[drvinceknight]

Awesome. Be sure to look through those @Nikoleta-v3, we'll talk about it more next week :) 👍

[langner]

This is something of interest to me as well.

[drvinceknight]

We've been discussing the requirements of the Graph class, just putting all that in an issue here :) Please add below. I think no matter what: the plan can be to try various options.

For the purpose of the tournament I believe we just need it to be static and have the ability to (efficiently) return if a given edge (between two players) exists or not. Something like:

>>> (p1, p2) in G.edges
False

When it comes to evolutionary contexts, from the literature it seems (please correct me here) that the graph is still static in terms of edges (no new/removed edges over time) but we will need to be able to replace nodes (with reproduced players).

# Say that `v` is some node of G
>>> v = axl.player()  # so replacing v by a given player

Also, I am particularly interested in various network topologies so I like the idea of being able to create a particular topology on a given set of players. Thus, as well as being able to create specific networks (by specifying exactly who is connected to who) it would be nice to have something like:

# players is some list of players that a user can create in any given way
>>> G = SmallWorldNetwork(players, parameters...)

However, in a way, from the point of view of the library that's not super important. So for example, a user could use networkx to build such a network and then transform it to whatever class we end up using the library for.

My personal preference is currently leaning towards using a networkx class for for our graphs so that we don't add unneeded class to the library and don't reinvent the wheel. The immediate negative of that is adding a dependency which has a bunch of other things that we won't need.

[drvinceknight]

The immediate negative of that is adding a dependency which has a bunch of other things that we won't need.

Although... If you wanted to look at some topological statistics and compare them to results (perhaps look at the centre of the network and see how that/those players ranks or something like that) then it's nice that a user has that for free from networkx without needing to go back and forth.