It is obvious that the truematch algorithm has runtime complexity O(K3) like the Hungarian method. The truematch heuristic also nicely translates into polynomial runtime.

The number of residuals calculated to reduce the matching table from k to k −1 is K2, thus the total number of residuals calculated is

$$K^{2}+(K-1)^{2}+(K-2)^{2}+\ldots+2^{2}={\frac{(K\cdot(K+1))\cdot(2K+1)}{6}}-1$$

and, therefore, the truematch heuristic has runtime complexity O(K3) and memory complexity O(K2) if the recursive nature of the algorithm is realized using a while-loop.

R package truecluster (Oehlschl¨agel, 2007a) implements the truematch algorithm in matchindex(method = "truematch") and the truematch heuristic in matchindex(method
= "tracemax") efficiently through underlying C-code.

Applying the truematch algorithm and the truematch heuristic to the above example gives identical results: as in standard trace maximization matching, we find 1% random matches in matching table 1, but for the 99% non-random matching cases, truematch generates two versions of matching tables, see Table 4. Both versions have shifted the majority of counts off-diagonal. Due to the probabilistic component in the 2nd step, this leads to the expected matching (Table 5) that has a weak trace. Under truematch, only systematic, non-random matches will result in a strong diagonal.

![0_image_0.png](0_image_0.png)

![0_image_1.png](0_image_1.png)

Table 4: Typical truematch (49.5% + 49.5%)

![0_image_2.png](0_image_2.png)

We can quantify the benefit of truematch in this case by comparing expected values of certain agreement indices, cf. Table 6. The *rand* index (Rand, 1971) and its random corrected version *crand* (Hubert and Arabie, 1985) are invariant against row/column permutations and, thus, do not differ. There is also no difference for *kappa* (Cohen, 1960). However, the big difference is on the simple non-random-corrected *diagonal* fraction of observations: while the trace maximization misleadingly results in an expected diagonal close to 1, truematch reduces the expectation of this non-random-corrected index close to zero.

In the next two sections, we will explore the benefit of truematch in a bagging context, where the main diagonal defines the matching but no random correction is available.