1. The “Diversity Trumps Ability” Result and Thompson’s Randomness Interpretation

Hong and Page’s (Reference Hong and Page2004) “Diversity Trumps Ability” result shows that on sufficiently hard problems “a randomly selected collection of problem solvers outperforms a collection of the best individual problem solvers” (Reference Page2007, 162). They show this by proving both a general mathematical theorem about agents using different search methods and a computational model. Here I will focus on the model.

In the model, groups of agents work their way around a ring of 2,000 spots, which I will call the ‘landscape’. We can think of the different spots in the landscape as being different candidate answers to the question the group is trying to answer. At any given moment, the entire group inhabits a single spot. They can move forward on the ring, and once they reach the end, they loop back to the beginning. Each of the 2,000 spots on the ring has a score associated with it. We can think of the score of a spot as being the epistemic payoff of accepting that answer (i.e., a measure of how good the answer is). In Hong and Page’s model, each of the spots is randomly assigned a real-number score between 0 and 100.Footnote ⁵

Agents each have a heuristic that they use to move around the ring. A heuristic consists of an ordered nonrepeating list of three integers {h ₁, h ₂, h ₃}. Agents use their heuristic in the following way: from wherever they are on the ring, they ask themselves if the spot h ₁ spots ahead has a higher score than their current spot. If so, they move, and if not, they stay. They then try the next number in their heuristic and repeat the process (looping back to h ₁ after trying h ₃) until no number in their heuristic takes them to a spot with a higher score. From every starting spot on the ring, there is a unique ending spot the agent will get to from any starting spot. An agent’s competence will be the average score the agent receives starting from any spot.

A group of agents will be an ordered list of agents {a ₁, a ₂, … , a_i}. Groups of agents move around a ring similarly to individual agents. From any given starting spot, the first agent uses his heuristic to take the group to the highest spot he can from the starting spot. The baton is then passed to the second agent, who leads the group from there using her own heuristic. The baton is passed around the group (looping back to a ₁ after a_i) until no agent can take the group any higher. A group’s competence will be the average score the group receives starting from any spot.

What the “diversity trumps ability” result says is that groups of agents with randomly selected distinct heuristics (“random groups”) typically outperform groups of agents with the individually highest-performing distinct heuristics (“expert groups”).Footnote ⁶ In my recreation of the model, with three heuristic numbers that range from 1 to 20, 10 agents in each group, and averaged over 1,000 runs, expert groups have an average competence of 93.79 (standard error = 0.041) whereas random groups have an average competence of 96.07 (standard error = 0.016). So the random groups performed significantly better (Welch t-test, $p<2.2\times {10}^{\mathrm{-16}}$).Footnote ⁷

Hong and Page explain this result in terms of the random groups being more functionally diverse than the expert groups. To precisify this, Hong and Page provide a measure of functional diversity: Let us say that two heuristics overlap in a spot when they share the same number in that spot in the heuristic. For example, {1, 2, 3} and {1, 4, 5} overlap in only the first spot; {1, 2, 3} and {4, 5, 6} do not overlap in any spots. Let δ_HP(h ₁, h ₂) be the percentage of places in which the two heuristics h ₁ and h ₂ do not overlap. Then

HP-diversity essentially measures the lack of overlap of heuristics of members in the group: the higher the HP-diversity, the less overlap there is among the heuristics.

As Hong and Page show, on average, the HP-diversity between expert groups and random groups differs in the same way their average competence differs. Expert groups have an average HP-diversity of 87.19% (standard error = 0.0006), whereas random groups have an average HP-diversity of 95.08% (standard error = 0.0014). Hong and Page conclude then that random groups do better because of their higher diversity. More diverse groups bring more skills to the table (here represented as bringing more nonoverlapping heuristics), which explains why “diversity trumps ability” (Reference Hong and Page2004, 16385).

2. Thompson’s Critique and Randomness Interpretation

Thompson (Reference Thompson2014) presents a number of worries for Hong and Page’s original paper. Chief among them is the worry that diversity cannot explain why random groups outperform expert groups. Hong and Page draw their conclusion that diversity explains the performance of random groups by showing that the HP-diversity of random groups is higher than that of expert groups. But a mere correlation of these values is not a strong enough reason to conclude that there is an explanatory connection, Thompson argues (1028). If it is diversity that is doing the work, then maximally diverse groups should be expected to perform well in general. But in Thompson’s reconstruction of the model, she reports that five distinct groups that were each maximally HP-diverse all performed worse than the median performance of 200 random groups. She concludes that it cannot be diversity that is doing the work (1028).

What does Thompson think is going on in the model then? Thompson thinks the success of random groups is best seen as an instance of a well-established theme in algorithms research that random algorithms outperform the best-known deterministic algorithms in many situations (Reference Thompson2014, 1028). As she points out, it is widely accepted that “randomization can improve algorithms, and often can improve them dramatically” (1028). Since the diverse groups are created by a random process in Hong and Page’s model, the natural explanation, Thompson suggests, is that the model is best understood as showing that “randomness trumps ability,” not that “diversity trumps ability.”

3. The Implausibility of Thompson’s Critique

The bulk of this section will be an argument against Thompson’s reason for thinking that maximally diverse groups do not perform well compared to random groups. But note that even if she were right about that, we should still be concerned about the plausibility of the randomness interpretation. Here is why:

Randomized algorithms differ from deterministic (and nondeterministic) algorithms in that randomized algorithms operate on a series of random bits in addition to a regular fixed input. This means that the same random algorithm can give different outputs on the same fixed input. As Thompson notes, randomized algorithms have received much praise in complexity research. The purported advantages of these algorithms are their simplicity (understood in terms of humans’ ability to grasp and implement them) and their efficiency over known deterministic algorithms.Footnote ⁸

But since the issue here is about performance rather than simplicity, we should think the randomness-based explanation of Hong and Page’s result is compelling only if random algorithms are thought to have performance benefits over deterministic algorithms in general, not just benefits over known deterministic algorithms. Otherwise, Hong and Page could just as easily be right that some fixed property of the randomly generated groups, like their diversity, is what explains their success, not the fact that they were randomly generated. It is not among the generally accepted benefits of random algorithms that the randomness itself explains their success, though.

The question of whether random algorithms are computationally more powerful than deterministic algorithms is often studied in terms of whether the complexity class of bounded-error probabilistic polynomial time algorithms (BPP) is reducible to the class of polynomial time algorithms (P). That question is still an open one (Greathouse Reference Greathouse2013; for a relevant survey, see Vadhan [Reference Vadhan2012]). But current research into derandomization shows that many particular random algorithms can be reduced to deterministic algorithms using techniques such as the methods of conditional expectations, pessimistic estimators, and bounded independence. Research on the complexity classes involving random algorithms also shows that many subclasses of random algorithms in BPP can be reduced to deterministic algorithms. In light of those results, most complexity researchers believe that the randomness of random algorithms is not essential to their performance (i.e., that P = BPP; Aaronson Reference Aaronson2017, conjucture 31). So even if Thompson is correct that HP-diversity does not explain the success of random groups, we should not think randomness explains it either. We should look for another property of the random groups that can explain their success.

So what is the property that explains why random groups perform better? Thompson argued that diversity cannot be that property because maximally HP-diverse groups do not perform well compared to random groups. I will show that Thompson was mistaken in asserting that, though: maximally HP-diverse groups do typically outperform random groups, and there is a natural explanation of why Thompson thought otherwise.

In arguing that maximally HP-diverse groups do not perform well compared to random groups, Thompson reported testing five maximally HP-diverse groups against the median performance of 200 random groups.Footnote ⁹ She found that all of them performed worse than the median of the random groups. My reconstruction of the result further confirms that the groups Thompson tested were in fact very weak compared to random groups. Testing Thompson’s groups against 100 random groups on each of 100 landscapes shows that Thompson’s groups lose to random groups 93.62% of the time.

So if Thompson’s selected groups were representative of maximally HP-diverse groups, it would be reasonable to conclude that maximally HP-diverse groups do not perform better than random groups. But that is not the result we see. In 1 million runs of randomly generated groups on random landscapes, the average competence of all groups was 96.04 (standard error = 0.0005, n = 1,000,000). The average competence of groups with maximal HP-diversity was 96.33 (standard error = 0.0278, n = 261). So maximally HP-diverse groups, on average, do perform better than random groups (Welch two-sample t-test, $p<2.2\times {10}^{\mathrm{-16}}$).Footnote ¹⁰ Moreover, when we look at all of the runs, we can see a clear correlation between HP-diversity and competence. Figure 1 shows a scatter plot of HP-diversity and group competence for 50,000 runs that are representative of a 1 million run sample.

Figure 1.

Comparison of HP-diversity to competence for 50,000 runs. Includes linear regression (error bars too small to be visible). Average score of all random groups marked by dashed line.

We can see from figure 1 that HP-diversity is correlated with competence (Pearson correlation = .224, 99.99% confidence interval [CI] [0.220, 0.228]), pace Thompson (Reference Thompson2014). Moreover, though it is not clear in the scatter plot, there are maximally HP-diverse groups that perform markedly better than random groups, like this one:

The Super-MaxHP Group almost never loses to random groups. On 100,000 random landscapes, facing a new random group on each, the Super-MaxHP Group lost only 42 times. Moreover, when it won, it won by 0.897 on average (standard deviation = 0.364); but when it lost, it lost by only 0.041 (standard deviation = 0.038). So the Super-MaxHP is the polar opposite of what Thompson’s maximally HP-diverse groups were like.

What happened with Thompson’s groups then? Inspecting an example of one of Thompson’s groups will be helpful in answering that question. Consider this one (from personal communication with unpublished code referred to in Thompson [Reference Thompson2014]):

It is easy to check that this group is maximally HP-diverse, since no two heuristics have the same heuristic number in the same location. Is this group really diverse (rather than just HP-diverse) though? The maximum heuristic number used in these runs was 20, even though the maximum heuristic in Thompson’s group is 12. So 40% of the possible heuristic numbers do not even show up in this group, even though nine heuristic numbers are each repeated three times. Given that, it seems like there is a sense in which this group is not very diverse at all. HP-diversity does not track this other sense of diversity, the sense that can be measured by the proportion of the heuristic numbers present in the group. I will call this sense of diversity ‘coverage diversity’ since it measures how much of the heuristic space is covered by the group’s combined heuristics.

The example group has a C-diversity of 60%, the minimum possible C-diversity of a maximally HP-diverse group.

In fact, all of the groups Thompson tested have a C-diversity of 60%; C-diversities that low are very uncommon among maximally HP-diverse groups at these parameters, though. In a test of 1 million random-generated maximally HP-diverse groups, only 0.0131% had a C-diversity less than 0.7, and none had a C-diversity the same as Thompson’s (0.6). So it would be incredibly unlikely for Thompson to have selected five groups with 0.6 C-diversity at random from the set of maximally HP-diverse groups. If one were to construct a maximally HP-diverse group by hand, though, a natural way to do it would be to avoid overlaps by intentionally repeating the same number in different places in different heuristics in the group. Doing this will result in a maximally HP-diverse group that uses only a small percentage of the available heuristic numbers (since it guarantees repeats of the used numbers). Presumably this is why Thompson’s maximally HP-diverse groups were so unrepresentative of the whole class.

So Thompson’s reason for rejecting the diversity interpretation of Hong and Page’s result is flawed. Maximally HP-diverse groups do generally perform better than random groups. Thompson missed this, I hypothesize, because the groups she presumably made by hand are unrepresentative of the whole class of maximally HP-diverse groups.

4. It Is Diversity, Not Randomness

Once we reject Thompson’s argument for thinking that HP-diversity cannot explain the random groups’ successes and notice that randomness is not a good option either, we are back in the dialectical position created by Hong and Page (Reference Hong and Page2004): HP-diversity is the presumptive best candidate to explain the success of random groups. But why think it is high HP-diversity rather than some other property of random groups? One mark in favor of HP-diversity is its correlation with group competence (detailed above), but might there be another property that can explain the success of random groups?

In fact, C-diversity can explain the success of random groups much better than HP-diversity. Compare the scatter plot of C-diversity and group competence in figure 2 to the previous plot of HP-diversity and group competence (fig. 1). Here again the 50,000 runs are representative of a 1 million run sample. In the whole sample, the Pearson correlation between C-diversity and group competence is .553 (99.99% CI [.551, .554]). Compared to the correlation between HP-diversity and competence (r = .224), C-diversity is significantly more correlated with competence (Williams’s test of dependent correlations, t = 356; Steiger’s z = 341). So knowing the C-diversity of a group gives us significantly more information about the group’s ability than knowing the HP-diversity does.

Figure 2.

Comparison of C-diversity to competence for 50,000 runs. Includes linear regression (error bars too small to be visible). Average score of all random groups marked by dashed line.

This point is strengthened when we look at the informativeness of HP-diversity in sets of cases in which C-diversity is held constant. Figure 3 shows a collection of scatter plots. In each plot, the C-diversity of each group is the same and the HP-diversity of the group is plotted against its competence.

Figure 3.

Comparison of HP-diversity to competence for 2,000 representative runs of each C-diversity in a 1 million run sample when n ≥ 2,000. Includes linear regression (error bars too small to be visible).

From the definition of HP-diversity, it follows that the HP-diversity of a group is higher when pairs of heuristics in the group either do not share the same heuristic numbers or share the same heuristic numbers but in a different order. Since C-diversity tracks when the heuristics contain more heuristic numbers, changes in HP-diversity when C-diversity is held fixed must be explained by changes in the ordering of either heuristics in the group or heuristic numbers in particular heuristics. As such, we can see the scatter plots in figure 3 as showing the impact on group competence of a third kind of diversity, namely, diversity of order, or O-diversity.

What figure 3 shows us is that C-diversity (almost entirely) screens off HP-diversity; that is, when C-diversity is held fixed, HP-diversity gives us very little (if any) new information about group competence (partial Pearson correlation = .0019, p < .05). From that, we can infer that O-diversity does not track competence—it is not diversity in terms of the order of agents or how they use their heuristic numbers that explains the success of groups.

We can also see the power of C-diversity as an indicator of group competence by flipping the plots and looking at the correlation between C-diversity and competence when HP-diversity is held fixed. In figure 4, we see that holding constant HP-diversity, C-diversity still correlates with group competence almost as much as it did without holding HP-diversity fixed (partial Pearson correlation = .5188, $p<2.2\times {10}^{\mathrm{-16}}$).

Figure 4.

Comparison of C-diversity to competence for 2,000 representative runs for each HP-diversity in a 1 million run sample when n ≥ 2,000. Includes linear regression (error bars too small to be visible).

All together, these data show that C-diversity is a much better indicator of group competence than HP-diversity. But why? One possibility is that, because the landscapes are completely random, groups that have the collective ability to see more of the spots ahead are less likely to miss a peak. Or perhaps it is that highly C-diverse groups will not get stuck in some places that less C-diverse groups would.Footnote ¹¹ If either of these were the right description of the mechanism, then it really would be that random groups bringing more heuristics to the problem is what explains their success. Unlike what Hong and Page thought, order would be completely irrelevant. These stories are likely missing some details, though. If it were only about groups not missing any peaks or not getting stuck, it would seem that the order of the heuristics in the group should matter, since an agent without any low-valued heuristics may cause the group to jump over a nearby peak. So further research into the complex dynamics of the model is necessary to fully answer this question.

Might there be even better measures of diversity (or other properties) that beat C-diversity in predicting success in this model? Perhaps a measure that tracks coverage as well as whether high- and low-valued heuristics are evenly spread out in the group? I imagine measures like this would do better, but I will not attempt to discover those here. Here the goal was only to show that diversity of some kind is a better explanation of the success of random groups than randomness. Being more C-diverse means bringing more skills, methods of problem solving, background knowledge, perspectives, and so forth to the table, and the advantage of random groups can be given a (partial) explanation in those terms, contra Thompson.

There is a broader point to be drawn from this discussion, though. The formal models mentioned above are part of a larger discussion about the epistemic and practical import of functionally diverse groups and, less directly, identity diverse groups.Footnote ¹² In this discussion, we often assume that measuring diversity is obvious and straightforward. It is often measured as simply the lack of uniformity. The lesson is that we undermine our understanding of the issues in employing such anemic conceptions of functional diversity.Footnote ¹³ What we should learn from Thompson’s critique is that we should not be so casual about measuring this central notion.

Neither Zollman (Reference Zollman2010) nor Thoma (Reference Thoma2015) gives a measure of diversity in their discussions, but there are natural candidates that the authors gesture at in both cases.Footnote ¹⁴ When we measure diversity in models like these, we should ask why we think that we are measuring an interesting notion of diversity rather than mere difference or nonuniformity. As I have shown in the case of Hong and Page’s model, we have the tools to understand what counts as diversity that fosters the desired values. So, inasmuch as we aim to justify theory or policy with results from these models, getting clear about what counts as diversity should be an essential part of the project.