We investigate a simple stochastic model of social network formation by the process of reinforcement learning with discounting of the past. In the limit, for any value of the discounting parameter, small, stable cliques are formed. However, the time it takes to reach the limiting state in which cliques have formed is very sensitive to the discounting parameter. Depending on this value, the limiting result may or may not be a good predictor for realistic observation times. © 2004 Elsevier B.V. All rights reserved.

Reinforcement schemes are a class of non-Markovian stochastic processes. Their non-Markovian nature allows them to model some kind of memory of the past. One subclass of such models are those in which the past is exponentially discounted or forgotten. Often, models in this subclass have the property of becoming trapped with probability 1 in some degenerate state. While previous work has concentrated on such limit results, we concentrate here on a contrary effect, namely that the time to become trapped may increase exponentially in 1/x as the discount rate, 1-x, approaches 1. As a result, the time to become trapped may easily exceed the lifetime of the simulation or of the physical data being modeled. In such a case, the quasi-stationary behavior is more germane. We apply our results to a model of social network formation based on ternary (three-person) interactions with uniform positive reinforcement. © 2003 Elsevier B.V. All rights reserved.

We consider a dynamic social network model in which agents play repeated games in pairings determined by a stochastically evolving social network. Individual agents begin to interact at random, with the interactions modeled as games. The game payoffs determine which interactions are reinforced, and the network structure emerges as a consequence of the dynamics of the agents' learning behavior. We study this in a variety of game-theoretic conditions and show that the behavior is complex and sometimes dissimilar to behavior in the absence of structural dynamics. We argue that modeling network structure as dynamic increases realism without rendering the problem of analysis intractable.

We consider a spatial (line) model for invasion of a population by a single mutant with a stochastically selectively neutral fitness landscape, independent from the fitness landscape for nonmutants. This model is similar to those considered earlier. We show that the probability of mutant fixation in a population of size (Formula presented.), starting from a single mutant, is greater than (Formula presented.), which would be the case if there were no variation in fitness whatsoever. In the small variation regime, we recover precise asymptotics for the success probability of the mutant. This demonstrates that the introduction of randomness provides an advantage to minority mutations in this model, and shows that the advantage increases with the system size. We further demonstrate that the mutants have an advantage in this setting only because they are better at exploiting unusually favorable environments when they arise, and not because they are any better at exploiting pockets of favorability in an environment that is selectively neutral overall.