Evaluation of the efficiency of decomposition of the linear Kemeny median problem based on majority graph analysis
Modelling and Data Analysis · 31.03.2026 · 16 (1) · 105-124
DOI: 10.17759/mda.2026160107 ↗Kurz gefasst
Fachartikel in der Zeitschrift Modelling and Data Analysis, online erschienen am 31.03.2026. Verfasst von V.N. Nefedov und 1 weiteren Autor:innen. Die Arbeit nennt 20 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-NC 4.0).
Abstract (Originalsprache)
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).
Zitieren
APA
Nefedov, V., & Silaeva, V. (2026). Evaluation of the efficiency of decomposition of the linear Kemeny median problem based on majority graph analysis. Modelling and Data Analysis, 16(1), 105-124. https://doi.org/10.17759/mda.2026160107
Vancouver
Nefedov V, Silaeva V. Evaluation of the efficiency of decomposition of the linear Kemeny median problem based on majority graph analysis. Modelling and Data Analysis. 2026;16(1):105-124. doi:10.17759/mda.2026160107
BibTeX
@article{Nefedov2026,
author = {Nefedov, V.N. and Silaeva, V.S.},
title = {Evaluation of the efficiency of decomposition of the linear Kemeny median problem based on majority graph analysis},
journal = {Modelling and Data Analysis},
year = {2026},
volume = {16},
number = {1},
pages = {105--124},
doi = {10.17759/mda.2026160107}
}
EUVIMED