Lazer & Friedman (2007) The network structure of exploration and exploitation

Lazer D, Friedman A (2007) The network structure of exploration and exploitation. Administrative Science Quarterly 52:667-694.

From the abstract:

This paper examines how the structure of communication networks among actors can affect system-level performance. We present an agent-based computer simulation model of information sharing in which the less successful emulate the more successful. Results suggest that when agents are dealing with a complex problem, the more efficient the network at disseminating information, the better the short-run but the lower the long-run performance of the system. The dynamic underlying this result is that an inefficient network maintains diversity in the system and is thus better for exploration than an efficient network, supporting a more thorough search for solutions in the long run. For intermediate time frames, there is an inverted-U relationship between connectedness and performance, in which both poorly and well-connected systems perform badly, and moderately connected systems perform best. This curvilinear relationship between connectivity and group performance can be seen in several diverse instances of organizational and social behavior.

Parallel problem solving: A complex problem has many plausible solutions, although it is difficult at the outset to judge which approach will yield good results. One of the challenges confronting a manager is how to structure the communication among his or her engineers. For example, should they have frequent meetings to share their ideas? Or should they work mostly on their own, so that information diffuses only slowly between them?

Complex problems and rugged problem spaces:

• A complex problem is one in which potential solutions have many dimensions that may be synergistic with respect to their impact on performance. Potential solutions may be viewed as a problem space in which each solution has a performance score associated with it.
• Solutions involve the conjunction of multiple activities, in which the impact of one dimension on performance is contingent on the value of other dimensions. One might imagine, for example, that activities A, B, and C each actually hurt performance unless all are performed simultaneously, in which case performance improves dramatically. The presence of such synergies produces local optima, such that any incremental change results in the deterioration of performance, but some large change could produce an improvement. In this example, if someone starts out not doing any of A, B, or C, the only way to improve is to do all three simultaneously.
• A problem space with many local optima is referred to as a “rugged” problem space, because the series of incremental changes needed to reach a better point typically requires moving through solutions with worse outcomes. Rugged problem spaces are hard to search because it is easy to get stuck in a local optimum.

What is of primary interest in understanding parallel problem solving is not so much how individuals solve problems by themselves as much as how individuals solve problems collectively. We assume that individuals affect collective success through a network of peers, in which the activities of a particular individual offer insight to others about the configuration of the problem space. If I see someone with a different solution and with performance superior to mine, I will make that non-incremental change. In solving a complex problem, the flow of information among the individuals is likely to affect their collective performance, as each individual can look at what some of the other individuals are doing and how they are performing. But the network structure linking those individuals will determine who has access to what information and therefore how well information about the solution to the problem is disseminated in the system.

Information cascades: The information cascade literature highlights how non- welfare-improving practices (fads) can spread through the system under the assumption that people observe adoption decisions but not the success of actors. Information cascades occur when an adoption sends a signal to other actors that they should adopt, leading to self-reinforcing processes, reflected in phenomena like stock bubbles and bank runs…. Unlike the diffusion literature, however, variation in network structure has not been deeply integrated into the information cascade research.

The issue of parallel problem solving can be seen as a balancing of exploration and exploitation.

• Exploration generally involves attempts to introduce new information, while exploitation leverages existing knowledge for some productive end.
• In parallel problem solving, each agent may either choose to try a novel solution (exploration) or emulate another actor with whom he or she has a connection (exploitation).
• The question this paper examines is how the structure of the social network affects the systemic balance between exploration and exploitation.
• The model will assume that individuals learn directly from each other via their network of communication, or from the environment itself, rather than learning from an organizational hub.

Great quote: “More generally, all social science research must do some violence to reality in order to reveal simple truths.” (p. 673)

Model design: Three key issues had to be specified in the model: (1) What does the problem space look like? (2) How do actors (individuals) make decisions? and (3) How do actors communicate?

The Problem Space

• We need to produce an arbitrarily large number of statistically identical “problems” for the simulated agents to solve.
• Use’s Kauffman’s (1995) NK model, where N is the number of traits, and K is the degree of epistasis. Here, N is the number of potential human activities (either present (1) or absent (0)), and K is the number of synergies among those activities. For example, for K = 3, the value of any given activity is contingent on the presence or absence of 3 other activities. 
• NOTE: See Kauffman (1993), pp. 40-45 for a clearer description of the NK model, and also the appendix. They normalized each NK space to the global maximum. However, this leads to clustering around moderately good values. They then used a transformation (raising each NK score to the power 8) so as to heavy skew the scores so that most are terrible and very few are good.

Behavioral Rules

• At any point in time, each actor has one solution in NK space.
• Each actor is connected to a set of other actors in a network.  
• Actors are myopic, unable to directly evaluate potential solutions that deviate greatly from their status quo solution. BUT, actors can see the performance levels of those others in their network.
• In each round, actors’ decisions proceed as follows:
• Each actor sees whether anyone in his network has a better solution than himself.
• If so, he copies the most successful strategy.
• Otherwise, he myopically searches for a better strategy. He examines the impact of randomly changing one digit of his solution, and if that offers an improvement, they change their solution.
• Manipulations
• Velocity: The probability that an agent will look at the solutions of the others in his network each round. This could be interpreted as individual preferences for exploration vs. exploitation (NOTE: or individual vs. social learning).
• Error rate: How accurately agents copy the solutions of others. Unclear how this was implemented.

Network Configuration

Four configurations examined: a linear network, a fully connected network, a variety of random networks, and a variety of small-world networks.

Assumed undirected graph: all communication is 2-way.

Data Generation and Analysis (Simulations)

• 100 actors with discrete time steps, randomly located in networks as above.
• Initial problem solutions are randomly generated.
• For NK mode, N = 20 and K = 5, except where noted.
• For each simulation, the population was run until it converged on a single solution. For each set of parameter values, the simulation was run on (the same) 1000 NK spaces, with the average performance reported, as a ratio of the global optimum.

Results

Linear vs. Totally connected networks

Figure 4 plots the average performance over 1000 simulations of linear networks versus totally connected networks over time. It shows a clear pattern: the totally connected network finds a good solution quickly and outperforms the linear network in the short run, but in the long run, the linear network performs significantly better.

The reason is that the number of unique solutions held by agents plummeted in the totally connected networks, while the linear network maintained diversity longer (Figure 5).

They also assessed a hub-spoke network (99 agents connected to a single hub), and a “caveman network” with communities of five totally connected nodes connected by a single edge to each other. The hub-spoke network performed similarly to the totally connected network (slightly worse in the short run, slightly better in the long run). The caveman network performed similarly to the linear (slightly better in the short run, slightly worse in the long run).

The totally connected network quickly drives out diversity, with only one or two unique strategies after the first round because 99 actors converge on the strategy of the best-performing actor. The system can, at best, only find the best local optimum that is reachable by climbing uphill from the best strategy that exists in the population when it is initially placed in the problem space.

The linear network eliminates diversity far more slowly, allowing exploration around a number of the better strategies that exist in the initial population set.

Random Networks

They generated sets of 1000 random networks with a density parameter between 0.01 and 0.5.

The results for all the random networks demonstrate a distinct inverted-U shape (Figure 6), but this is an artifact due to low densities creating distinct disconnected groups. As long as all actors are connected through some path, the fewer connections the better in the long run.

Small-world Networks

In a random network, increased density corresponds with improved diffusion of information, but the density of a network does not necessarily correspond with its effectiveness at diffusing information. A sparse network may be much more effective at diffusing information than a denser network, depending on its architecture.

They used a small-world network with degree 4 and a variable probability of rewirings. The average score decreased monotonically with the number of rewirings.

Ruggedness of the Problem Space

Set K = 0 (no synergies). Here, both linear and totally connected networks find the global maximum, but the totally connected network gets there faster. In this simple world, the system does not get caught in a local optimum (Figure 8).

Even a small degree of ruggedness confounds the totally connected network in the long run: it is eventually beaten by the linear network even when K = 1.

Velocity of Information

 Now each agent don’t always assess social information. Every actor looks around with the same average frequency, but the actual timing for each actor is stochastic.

Tested this on a fully connected network. Reducing velocity has a clear positive impact on long-run performance for the network at the expense of short-run performance (Figure 10). Reducing the flow of information preserves diversity, forcing actors to achieve improvements based on their initial solutions. The linear network demonstrated a similar, if not quite as dramatic, improvement.

Strategy Mixing or Error in Copying

Before, perfect copying was assumed. Here, when an actor copied another, it replaces each bit in its solution with probability (1 – e), otherwise the bit will remain in its original state. Thus, the likelihood of perfect transmission is (1 – e)^d, where d is the number of dissimilar bits.

Error in copying vastly expands the potential space examined by actors (and the number of search opportunities) because, in principle, any solution in the entire space between two strategies might be sampled during the copying process.

Error in copying reduces performance in the short run, because propagation of the most successful strategies in the beginning takes longer, but it increases performance in the long run, for all types of network configurations. An error rate of e = 0.2 was used. The authors claim that long-run success increased with the error rate, but this must have a limit, which was not explored.

Discussion

An efficient network positively affects information diffusion, which facilitates the spread of effective strategies, but negatively affects information diversity, which is also positively related to performance.