Evaluation of the efficiency of decomposition of the linear Kemeny median problem based on majority graph analysis

Context and relevance. The problem of aggregating individual preferences into a group ranking is fundamental to decision theory. The Kemeny median is one of the most axiomatically valid criteria for consensus, but its calculation belongs to the class of NP-hard problems and requires searching through n! possible options. The decomposition method based on a majority graph allows the original problem to be broken down into independent subtasks within strongly connected components (SCCs), which theoretically reduces the complexity to O(n_max!), where n_max is the size of the maximum SCC. The practical effectiveness of this approach remains insufficiently studied. Objective. To estimate the probability and depth of majority graph decomposition depending on the extent of agreement of expert opinions. Hypothesis. The efficiency of decomposition (the size of the maximum SCC) is directly related to the group's internal coherence: the method should be most effective when internal contradictions are minimal. Methods and materials. Statistical modelling was performed on three increasingly complex data models: (M1) independent random linear orders; (M2) linear orders with p pairs permuted from the reference order; (M3) tournaments with controlled deviation (r — extent of deviation of individual opinions from the reference tournament). For each set of parameters (n = 35, m = {3,5,7,9}, N = 100 000 for M1 and M2, n = 35, m = {5,6,7,8}, N = 10 000 for M3), a majority graph was constructed, SCCs were identified, and the size of the maximum component was recorded. Results. In model M1, the decomposition is statistically insignificant (E[n_max] = n ̃≈ n-1). In model M2, the effectiveness of the method increases sharply with decreasing p (for m = 9 at p = 10: n ̃= 25,580, and at p = 5: n ̃= 10,285). In model M3, a stable inverted U-shaped dependence of n ̃on the degree of deviation r is found: minimum values (high efficiency) are achieved at r → 0 (consensus) and r → 1 (polarization), maximum values (low efficiency) — in the region r ≈ 0,5 (minimum coherence). Conclusions. The decomposition method has been proven to be most useful for highly consistent groups (both in terms of consensus with the reference and polarization from the reference) and ineffective for groups with highly diverse opinions. A quick analysis of the SCC of the majority graph can be used as a diagnostic tool for a pre-assessment of the complexity of the task: the value of n_max allows for a reasonable choice between exact algorithms (for small n_max) and heuristic ones (for large n_max).