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).

1. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. (2005). Глава 22.4. Топологическая сортировка. В: И.В. Красикова (ред.). Алгоритмы: построение и анализ (с. 632—635). М.: Вильямс. URL: https://elibrary.ru/item.asp?id=19445496 (дата обращения: 13.02.2026)
   Cormen, T., Leiserson, C., Rivest, R., Stein, C. (2005). Chapter 22.4. Topological sorting. In: I.V. Krasikova (Ed.). Introduction to algorithms (pp. 632—635). Moscow: Williams. (In Russ). URL: https://elibrary.ru/item.asp?id=19445496 (viewed: 13.02.2026)
2. Корнеенко, В.П. (2018). Методы многокритериального оценивания объектов с многоуровневой структурой показателей эффективности. М.: МАКС Пресс. URL: https://www.elibrary.ru/item.asp?id=35669019 (дата обращения: 13.02.2026)
   Korneenko, V.P. (2018). Methods of multi-criteria evaluation of objects with a multilevel structure of performance indicators. Moscow: MAKS Press. (In Russ.). URL: https://www.elibrary.ru/item.asp?id=35669019 (viewed: 13.02.2026)
3. Литвак, Б.Г. (1982). Экспертная информация: методы получения и анализа. М.: Радио и связь. URL: https://www.elibrary.ru/item.asp?edn=qtwiuj (дата обращения: 13.02.2026)
   Litvak, B.G. (1982). Expert information: methods of obtaining and analyzing. Moscow: Radio i svyaz'. (In Russ.). URL: https://www.elibrary.ru/item.asp?edn=qtwiuj (viewed: 13.02.2026)
4. Миркин, Б.Г. (1974). Проблемы группового выбора. М.: Наука. https://doi.org/10.1007/BF02294167
   Mirkin, G. (1974). Problems of group choice. Moscow: Nauka. (In Russ.). https://doi.org/10.1007/BF02294167
5. Мулен, Э. (1991). Кооперативное принятие решений: Аксиомы и модели. М.: Мир. https://doi.org/10.1017/ccol0521360552
   Moulin, E. (1991). Cooperative decision-making: Axioms and models. Moscow: Mir. (In Russ.). https://doi.org/10.1017/ccol0521360552
6. Нефедов, В.Н. (2022). Медиана для нечетного числа отношений линейного порядка и ее использование в задачах группового выбора. ПДМ, 57, 98— https://doi.org/10.17223/20710410/57/7
   Nefedov, V.N. (2022). Median for an odd number of linear order relations and its use in group choice problems. Prikladnaya Diskretnaya Matematika, 57, 98—127. (In Russ.). https://doi.org/10.17223/20710410/57/7
7. Нефедов, В.Н., Осипова, В.А. (2022). Согласование индивидуальных ранжировок методом ветвей и границ. Известия РАН. Теория и системы управления, 6, 123— https://doi.org/10.31857/s0002338822060142
   Nefedov, V.N., Osipova, V.A. (2022). Coordination of individual rankings by the method of branches and boundaries. Journal of Computer and Systems Sciences International, 6, 123—132. (In Russ.). https://doi.org/10.31857/s0002338822060142
8. Нефедов, В.Н., Осипова, В.А., Смерчинская, C.О., Яшина, Н.П. (2018). Непротиворечивое агрегирование отношений строгого порядка. Изв. вузов. Математика, 5, 71— https://doi.org/10.17223/20710410/45/13
   Nefedov, V.N., Osipova, V.A., Smerchinskaya, S.O., Yashina, N.P. (2018). Consistent aggregation of strict order relations. Russian Mathematics (Iz. VUZ), 5, 71—85. (In Russ.). https://doi.org/10.17223/20710410/45/13
9. Петровский, А.Б. (2009). Теория принятия решений. М. ИЦ Академия. URL: https://www.elibrary.ru/item.asp?id=19459362 (дата обращения: 13.02.2026)
   Petrovsky, A.B. (2009). The theory of decision-making. M. IC Academy (In Russ.). URL: https://www.elibrary.ru/item.asp?id=19459362 (viewed: 13.02.2026)
10. Azzini, I., Munda, G. (2020). A new approach for identifying the Kemeny median ranking. European Journal of Operational Research, 2, 388-401, https://doi.org/10.1016/j.ejor.2019.08.033
11. Bartholdi, J., Tovey, C.A., Trick M.A. (1989). Voting schemes for which it can be difficult to tell who won the election. Social Choice and Welfare, 6(2), 157— https://doi.org/10.1007/bf00303169
12. Cook, W.D. (2006), Distance–based and Adhoc Consensus Models in Ordinal Preference Ranking. Europ. J. of Operational Research, 172, 369— https://doi.org/10.1016/j.ejor.2005.03.048
13. De, K., Mittal, H., Dey, P., Misra, N. (2024). Parameterized aspects of distinct Kemeny rank aggregation. Acta Informatica, 61, 401— https://doi.org/10.1007/s00236-024-00463-x
14. Dougherty, K., Heckelman, J.C. (2023). When ties are possible: Weak Condorcet winners and Arrovian rationality. Mathematical Social Sciences, 123, 45— https://doi.org/10.48550/arXiv.1704.06304
15. Hudry, O. (2012). On the computation of median linear orders, of median complete preorders and of median weak orders, Mathematical Social Sciences, 1, 2— https://doi.org/10.1016/j.mathsocsci.2011.06.004
16. Kemeny, J. (1959). Mathematics without numbers. Daedalus, 88, 577— URL: https://www.jstor.org/stable/20026529 (viewed: 18.02.2026)
17. Sharir, M. (1981). A Strong-Connectivity Algorithm and Its Applications in Data Flow Analysis. Computers & Mathematics with Applications, 7, 67-72. https://doi.org/10.1016/0898-1221(81)90008-0
18. Tarjan, R.E. (1972). Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1(2), 146— http://dx.doi.org/10.1137/0201010
19. Varol, Y.L., Rotem, D. (1981). An algorithm to generate all topological sorting arrangements. The Computer Journal, 24(1), 83— https://doi.org/10.1093/comjnl/24.1.83
20. Young, H.P. (1988). Condorcet’s Theory of Voting. American Political Science Review, 82, 1231— https://doi.org/10.2307/1961757