Skyrms & Pemantle (2000) A dynamic model of social network formation

Skyrms B & Pemantle R (2000) A dynamic model of social network formation. PNAS, 97, 9340-9346.

A population of individuals. Pairs from among this population interact repeatedly.
As time progresses, players adapt their strategies. They also exert control over their environment. They may improve their lot in two different ways:

• Change strategies – strategic dynamics
• Change associates – structure dynamics 

The main idea behind the model:
Individual agents begin to interact at random. The interactions are modeled as games. The game payoffs determine which interactions are reinforced, and the social network structure emerges as a consequence of the dynamics of the agents’ learning behavior.

Model 1: Making Friends
1.1. Friends I: Asymmetric weights

• 10 agents.
• Each day, each agent goes to visit some other agent.
• The choice of whom to visit is made by chance, determined by the relative weights each agent has assigned to the others. Thus, agent i has a vector of weights {w_i1, …, win} that she assigns to other players (assume w_ii = 0). Then she visits agent j with a probability proportionate to j’s relative weight. 
• All weights are initially 1. 
• Each agent updates her weight vector by adding 1 to the weight associated with the agent she just visited. 
• There is therefore a probability matrix p_ij of probabilities for i  to visit j. 
• Simulation to 1,000 time steps
• The probabilities seem to converge after a few hundred rounds.
• There is one agent, A, who visits another agent, B, more than half the time (no reciprocation).
• Most agents will not visit any one agent more than a third of the time. 
• Theorem 1: The probability matrix for Friends I with n players will converge to a random limit p as time goes to infinity. At this limit, the rows of p are independent, each having Dirichlet distribution [a multivariate form of the Beta distribution] (ignoring the zero entry on the diagonal) whose parameters are n – 1 ones. 

1.2. Friends II: Symmetrized reinforcement

• Interactions are mutually pleasant, so that when agent i visits agent j, we add 1 to both w_ij and w_ji. 
• A typical outcome for 10 agents after 1,000 rounds of visits is similar to the table for Friends I, except that the entries are nearly symmetric.
• Interesting behavior. 10 runs were done with 3 agents for 1,000 time steps. 
• Sometimes each players visits are split evenly between the others.
• Sometimes it’s close to this.
• Sometimes two agents nearly always visit the third, which splits its time among the other two.
• The remaining runs give something between these extreme outcomes. 
• The limiting weights for Friends II are always 1/2 with 3 agents. But, it may take a very long time for the weights to reach this, meaning that the limiting values might not be a good guide to the behavior of the system on time scales we are interested in. 
• When the population > 3, the weights will always converge, but the limit is random and restricted to the subspace of symmetric matrices. 
• Theorem 2: The probability matrix p_ij for Friends II with n players converges to random limit p as time goes to infinity. If n = 3, the limit is the matrix all of whose off-diagonal entries are 1/2. In general, the limit may be any symmetric matrix whose rows sum to 1; that is, the closed support of the random limit is the entire subspace of symmetric stochastic matrices.

Model 2: Making Enemies

• This is the same model as “Making Friends,” except that agents are punished, so that interactions add –1 to weights. 
• Here, we cannot use the same update rule as Model 1 will be meaningless, as weights will be negative.  It will have to be normalized. 
• With negative reinforcement, the network becomes uniform (all agents visited equal amounts). 
• Two other possible update rules are considered for inhibiting past interactions. 

2.1. The Transfer Model

• Here, when i visits j, the weight wij is diminished by 1 and the weight wik, k ≠ i, j, is increased by 1. 

2.2. The Resistance Model

• In this model, negative payoffs generate resistance.
• Initially, every choice has resistance 1. 

Summary of remainder:

They explore, in brief but formal detail, a number of other scenarios, including one in which agents play a stag hunt and adjust strategies and weights. It’s a good first step toward coevolutionary networks.