Some Models of Reproducing Graphs: II Age Capped Vertices

In the prequel to this paper we introduced eight reproducing graph models. The simple idea behind these models is that graphs grow because the vertices within reproduce. In this paper we make our models more realistic by adding the idea that vertices have a finite life span. The resulting models capture aspects of systems like social networks and biological networks where reproducing entities die after some amount of time. In the 1940’s Leslie introduced a population model where the reproduction and survival rates of individuals depends upon their ages. Our models may be viewed as extensions of Leslie’s model-adding the idea of network joining the reproducing individuals. By exploiting connections with Leslie’s model we are to describe how many aspects of graphs evolve under our systems. Many features such as degree distributions, number of edges and distance structure are described by the golden ratio or its higher order generalisations.

Some Models of Reproducing Graphs: I Pure Reproduction

Many real world networks change over time. This may arise due to individuals joining or leaving the network or due to links forming or being broken. These events may arise because of interactions between the vertices which occasion payoffs which subsequently determine the fate of the nodes, due to ageing or crowding, or perhaps due to isolation. Such phenomena result in a dynamical system which may lead to complex behaviours, to self-replication, to chaotic or regular patterns, to emergent phenomena from local interactions. They give insight to the nature of the real-world phenomena which the network, and its dynamics, may approximate. To a large extent the models considered here are motivated by biological and social phenomena, where the vertices may be genes, proteins, genomes or organisms, and the links interactions of various kinds. In this, the first paper of a series, we consider the dynamics of pure reproduction models where networks grow relentlessly in a deterministic way.

Some Models of Reproducing Graphs: III Game Based Reproduction

Many real world networks change over time. This may arise due to individuals joining or leaving the network or due to links forming or being broken. These events may arise because of interactions between the vertices which occasion payoffs which subsequently determine the fate of the vertices, due to ageing or crowding, or perhaps due to isolation. Such phenomena result in a dynamical system which may lead to complex behaviours, to selfreplication, to chaotic or regular patterns, or to emergent phenomena from local interactions. They hopefully give insight to the nature of the real-world phenomena which the network, and its dynamics, may approximate. To a large extent the models considered here are motivated by biological and social phenomena, where the vertices may be genes, proteins, genomes or organisms, and the links interactions of various kinds. In this, the third paper of a series, we consider the vertices to be players of some game. Offspring inherit their parent’s strategies and vertices which behave poorly in games with their neighbours get destroyed. The process is analogous to the way different kinds of animals reproduce whilst unfit animals die. Some game based systems are analytically tractable, others are highly complex-causing small initial structures to grow and break into large collections of self replicating structures.

Best Response Games on Regular Graphs

With the growth of the internet it is becoming increasingly important to understand how the behaviour of players is affected by the topology of the network interconnecting them. Many models which involve networks of interacting players have been proposed and best response games are amongst the simplest. In best response games each vertex simultaneously updates to employ the best response to their current surroundings. We concentrate upon trying to understand the dynamics of best response games on regular graphs with many strategies. When more than two strategies are present highly complex dynamics can ensue. We focus upon trying to understand exactly how best response games on regular graphs sample from the space of possible cellular automata. To understand this issue we investigate convex divisions in high dimensional space and we prove that almost every division of k - 1 dimensional space into k convex regions includes a single point where all regions meet. We then find connections between the convex geometry of best response games and the theory of alternating circuits on graphs. Exploiting these unexpected connections allows us to gain an interesting answer to our question of when cellular automata are best response games.

The Stationary Distributions of a Class of Markov Chains

The objective of this paper is to find the stationary distribution of a certain class of Markov chains arising in a biological population involved in a specific type of evolutionary conflict, known as Parker’s model. In a population of such players, the result of repeated, infrequent, attempted invasions using strategies from{0,1,2,…,m-1}, is a Markov chain. The stationary distributions of this class of chains, for m ε {3,4,…,∞} are derived in terms of previously known integer sequences. The asymptotic distribution (for m →∞) is derived.

A version of Geiringer-like theorem for decision making in the environments with randomness and incomplete information

Purpose-The purpose of this paper is to establish a version of a theorem that originated from population genetics and has been later adopted in evolutionary computation theory that will lead to novel Monte-Carlo sampling algorithms that provably increase the AI potential.Design/methodology/approach-In the current paper the authors set up a mathematical framework,state and prove a version of a Geiringer-like theorem that is very well-suited for the development of Mote-Carlo sampling algorithms to cope with randomness and incomplete information to make decisions.Findings-This work establishes an important theoretical link between classical population genetics,evolutionary computation theory and model free reinforcement learning methodology.Not only may the theory explain the success of the currently existing Monte-Carlo tree sampling methodology,but it also leads to the development of novel Monte-Carlo sampling techniques guided by rigorous mathematical foundation.Practical implications-The theoretical foundations established in the current work provide guidance for the design of powerful Monte-Carlo sampling algorithms in model free reinforcement learning,to tackle numerous problems in computational intelligence.Originality/value-Establishing a Geiringer-like theorem with non-homologous recombination was a long-standing open problem in evolutionary computation theory.Apart from overcoming this challenge,in a mathematically elegant fashion and establishing a rather general and powerful version of the theorem,this work leads directly to the development of novel provably powerful algorithms for decision making in the environment involving randomness,hidden or incomplete information.