“Calculating competitive intransitivity: Computational challenges”

Posted on

Robert A. Laird and Brandon S. Schamp (Apr 2018)

The DOI will be http://dx.doi.org/10.1086/696266

Intransitivity indices based on competitive reversals can only be computed exactly for species-poor systems

A hypothetical competitive ‘tournament’, giving the outcomes of asymmetric competition among 12 species (one of approximately 1.54 × 10¹¹ unique configurations). Nodes (circles) represent species and directed edges (arrows) point from competitive subordinate to competitive dominant. It takes a minimum of 16 hypothetical reversals (where the direction of an arrow is reversed), out of a maximum of 22, to convert this intransitive assemblage to a perfect hierarchy, a result that took 147 seconds to compute algorithmically. Determining the minimum number of reversals for much more species-rich assemblages is computationally unfeasible.
(Credit: Robert Laird and Brandon Schamp)

In ‘intransitive’ competition within a group of species, species cannot be listed in a strict hierarchy in which those higher on the list outcompete those lower on the list but never vice versa; rather, in intransitive competition, species form loops, where, for example, species A outcompetes species B, and B outcompetes C, but C outcompetes A. Thus, intransitive competition can be likened to the familiar game of rock-paper-scissors (‘RPS’). Intransitive competition is found in numerous natural systems, such as in plant communities, in lizard populations, in bacterial films, and in coral reefs. Moreover, it is important in community ecology because it may promote species coexistence through the phenomenon of indirect facilitation (i.e., ‘the enemy of my enemy is my friend’). Real communities usually have more than three species, leading to many more possible competitive interrelationships that the simple ‘hierarchy versus RPS’ scenario. Measuring competitive intransitivity in species-rich communities is therefore an important task. In such systems, one way of measuring intransitivity is to consider the minimum number of hypothetical reversals (i.e., converting ‘A outcompetes B’ to ‘B outcompetes A’) that would need to be applied to an assemblage to make it a perfect hierarchy—systems that require more reversals are relatively more intransitive than those that require fewer. While such an approach is intuitively appealing, Robert Laird (University of Lethbridge) and Brandon Schamp (Algoma University) demonstrate that a previous attempt at creating such an index had incorrect formulas. More broadly, by connecting this ‘reversal-based method’ with an equivalent problem from graph theory, Laird and Schamp show that there is no feasible way to compute an exact number of reversals for anything but species-poor communities. For this reason, they emphasize other intransitivity indices, based on the proportion of three-species subsets that engage in rock-paper-scissors competition, as viable (and computable) alternatives.


Intransitive, or ‘rock-paper-scissors’ competition is compelling because it promotes species coexistence and because recent work suggests it may be common in natural systems. One class of intransitivity indices works by considering s, the minimum number of competitive reversals to convert a given competitive community (i.e., a ‘tournament’) to a hierarchy. The most straightforward example of such ‘reversal-based’ indices is Petraitis’ index, t = 1 − s/M, where M is the maximum s across all possible n-species tournaments. Using exhaustive searches, we prove that Petraitis’ formula for M (and, therefore, t) does not hold for n ≥ 7. Furthermore, the determination of s for even moderate values of n may prove difficult, as the equivalent graph-theoretical problem is NP-hard; there is no known computationally feasible way to compute an exact answer for anything but small values of n, let alone a closed-form solution. Petraitis’ t is a valuable index of intransitivity; however, at present its use is limited to relatively species-poor systems. More broadly, reversal-based indices, while intuitive, may be problematic because of this computability issue.