We consider the problem of constructing a median for an odd set of linear order relations defined on a finite set A = {a1,a2,..., an}, which is also sought in the class of linear order relations. We arrive at a similar problem when considering some group choice problems. The distance between binary relations is the Hamming distance between their adjacency matrices. In the case under consideration, the binary relation ρ, which has the minimum total distance to the given set of binary relations, is the median for these relations and, moreover, is unique. However, this median is not always transitive (and in this case is neither linear order, nor even a quasi-order), and therefore cannot be taken as a solution to a given problem. However, the median ρ necessarily belongs to the set LA[n] (of linear asymmetric binary relations on A), to which, in particular, all linear orders on A also belong. Some properties of binary relations from LA[n] are investigated. The concepts of “almost optimal” and Δ-optimal relations are introduced, which are linear orders and, at the same time, exact solutions of the stated problem. Algorithms for finding them are given, based on the obtained statements about binary relations from LA[n] and having polynomial computational complexity. An equivalence relation on the set LA[n] is considered, which allows one to divide this set into equivalence classes, the number of which Kn is much less than the number of elements in LA[n]. For example, |LA[5] | = 1024, K5 = 12. Thus, each binary relation from LA[n] is equivalent to exactly one of the Kn representatives of the equivalence classes and, therefore, has its main properties. But then the study of a wide class of problems can be reduced to considering a relatively small set of them. The process of finding the specified set of equivalence class representatives is illustrated for n = 2,3,4, 5. A method for solving the problem posed is also given, using the representation of binary relations in the form of graphs (the method of selecting the minimum sets of contour representatives in the median ρ), which has exponential computational complexity.
Download file
Counter downloads: 29
- Title Median for an odd number of linear order relations and its use in group choice problems
- Headline Median for an odd number of linear order relations and its use in group choice problems
- Publesher
Tomsk State University
- Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 57
- Date:
- DOI 10.17223/20710410/57/7
Keywords
median of relations, linear order relation, linear relations, asymmetric relations, Hamming distance, equivalence classes, group choice problemAuthors
References
Миркин Б. Г. Проблема группового выбора. М.: Наука, 1974. 256с.
Мулен Э. Кооперативное принятие решений: Аксиомы и модели. М.: Мир, 1991. 464с.
Young H. P. Condorcet’s theory of voting // Amer. Political Sci. Rev. 1988. No. 82. P. 12311244.
Осипова В. А., Подиновский В. В., Яшина Н. П. О непротиворечивом расширении отношений предпочтения в задачах принятия решений // Журн. вычисл. матем. и матем. физ. 1984. Т. 24. №6. С. 831-839.
Schulze M. A new monotonic, clone-independent, reversal symmetric, and Condorcet-con-sistent single-winner election method // Social Choice and Welfare. 2011. No.36. P.267-303.
Нефедов В. Н., Осипова В. А., Смерчинская C. О., Яшина Н. П. Непротиворечивое агрегирование отношений строгого порядка // Изв. вузов. Математика. 2018. №5. С. 71-85.
Нефедов В. Н., Смерчинская C. О., Яшина Н. П. Непротиворечивое агрегирование отношений квазипорядка // Прикладная дискретная математика. 2019. №45. С. 113-126.
Жуков М. С., Орлов А. И. Задача исследования и итогового ранжирования мнений группы экспертов с помощью медианы Кемени // Научный журнал КубГАУ. 2016. №122. С. 784-805.
Алексеев Н. С., Осипова В. А. Методика построения полной порядковой классификации при наличии информации о сравнительной важности критериев // Научно-технич. вестник Поволжья. 2020. №11. С. 7-11.
Смерчинская C. О., Яшина Н. П. Агрегирование предпочтений с учетом важности критериев // Труды МАИ. 2015. №84. https://mai.ru/upload/iblock/c72/smerchinskaya_yashina_rus.pdf.
Smerchinskaya S. O. and Yashina N. P. An algorithm for pairwise comparison of alternatives in multi-criteria problems // Intern. J. Modeling Simulation Scientific Computing. 2018. V. 9. No. 1. https://www.worldscientific.com/doi/10.1142/S179396231850006X.
Берж К. Теория графов и ее применение. М.: ИЛ, 1962.
Нефедов В. Н. Некоторые свойства линейно упорядоченной медианы для нечетного числа линейных асимметричных отношений. МАИ. Деп. в ВИНИТИ. №62-В2021 от 08.11.2021. 50с.
Кемени Дж., Снелл Дж. Кибернетическое моделирование. М.: Сов. радио, 1972.
Корнеенко В. П. Методы многокритериального оценивания объектов с многоуровневой структурой показателей эффективности. М.: МАКС Пресс, 2018. 296 с.

Median for an odd number of linear order relations and its use in group choice problems | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2022. № 57. DOI: 10.17223/20710410/57/7
Download full-text version
Counter downloads: 126