Decomposition of a Decision-Making Problem Into Levels of Preference of the Majority Graph
- Authors: Smerchinskaya S.O.1, Yashina N.P.1
-
Affiliations:
- Moscow Aviation Institute (National Research University), 125080, Moscow, Russia
- Issue: No 1 (2023)
- Pages: 106-122
- Section: СИСТЕМНЫЙ АНАЛИЗ И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
- URL: https://journals.rcsi.science/0002-3388/article/view/136856
- DOI: https://doi.org/10.31857/S0002338823010109
- EDN: https://elibrary.ru/JATRSU
- ID: 136856
Cite item
Abstract
Decision-making problems with a large number of alternatives are considered. It is proposed to preliminarily narrow the initial set of alternatives, excluding the obviously worse options. For this purpose, the decomposition of the original problem into preference levels of the majority graph is carried out. Graph levels containing the least preferred alternatives are removed. An algorithm for constructing an aggregated full quasi-order for ordering the set of best alternatives is developed. Majority graph preference levels are used to rank alternatives using Hamiltonian paths in a digraph. An algorithm for finding Hamiltonian paths in a digraph is proposed by raising the adjacency matrix to a power. An applied problem of ordering drone models using an algorithm for constructing a complete quasi-order is presented.
About the authors
S. O. Smerchinskaya
Moscow Aviation Institute (National Research University), 125080, Moscow, Russia
Email: svetlana_os@mail.ru
Россия, Москва
N. P. Yashina
Moscow Aviation Institute (National Research University), 125080, Moscow, Russia
Author for correspondence.
Email: nina_p_yashina@mail.ru
Россия, Москва
References
- Кормен Т., Лейсерзон Ч., Риверст Р., Штайн К. Алгоритмы. Построение и анализ. М.: Вильямс, 2006.
- Smerchinskaya S.O., Yashina N.P. Preference Levels for Clusters of Alternatives // Intern. J. Modeling, Simulation, and Scientific Computing. 2019. V. 10. Iss. 4. https://doi.org/10.1142/S1793962319500193
- Жуков М.С., Орлов А.И. Задача исследования и итогового ранжирования мнений группы экспертов с помощью медианы Кемени // Научный журнал КубГАУ. 2016. № 122(08).
- Мулен Э. Кооперативное принятие решений: Аксиомы и модели. М.: Мир, 1991.
- Schulze M. A New Monotonic, Clone-independent, Reversal Symmetric, and Condorcet-consistent Single-winner Election Method // Social Choice and Welfare. 2011. V. 36. P. 267–303.
- Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980.
- Миркин Б. Г. Проблема группового выбора. М.: Наука, 1974.
- Нефедов В.Н., Осипова В.А., Смерчинская С.О., Яшина Н.П. Непротиворечивое агрегирование отношений строгого порядка // Изв. вузов. Математика. 2018. № 5. С. 71–85.
- Нефедов В.Н., Смерчинская С.О., Яшина Н.П. Непротиворечивое агрегирование отношений квазипорядка // Прикладная дискретная математика. 2019. № 45. С. 113–126.
- Кофман А. Введение в прикладную комбинаторику. М.: Наука, 1975.
- Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978.