Median for an odd number of linear order relations and its use in group choice problems

V. N. Nefedov

Prikladnaâ diskretnaâ matematika, no. 3 (2022), pp. 98-127.

Résumé

We consider the problem of constructing a median for an odd set of linear order relations defined on a finite set $A = \{ a_1, a_2, \ldots , a_n \}$, 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 $\tilde{\rho}$, 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 $\tilde{\rho}$ 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 $\Delta$-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 $K_n$ is much less than the number of elements in $LA[n]$. For example, $|LA[5]|=1024$, $K_5=12$. Thus, each binary relation from $LA[n]$ is equivalent to exactly one of the $K_n$ 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 $\tilde{\rho}$), which has exponential computational complexity.

Détail

Keywords: median of relations, linear order relation, linear relations, asymmetric relations, Hamming distance, group choice problem.
Mots-clés : equivalence classes

Bibliographie

[1] Mirkin B. G., Group Choice, V.H. Winston and Sons Publ., 1979, 252 pp. | MR | MR

[2] Moulin E., Axioms of Cooperative Decision Making, Cambridge University Press, Cambridge, 1988 | MR | Zbl

[3] Young H. P., “Condorcet's theory of voting”, Amer. Political Sci. Rev., 1988, no. 82, 1231–1244 | DOI | MR

[4] Osipova V. A., Podinovskiy V. V., and Yashina N.P., “On non-contradictory extension of preference relations in decision-making problems”, USSR Comput. Math. and Math. Physics, 24:3 (1984), 128–134 | DOI | MR | Zbl

[5] Schulze M., “A new monotonic, clone-independent, reversal symmetric, and Condorcet-consistent single-winner election method”, Social Choice and Welfare, 36 (2011), 267–303 | DOI | MR | Zbl

[6] Nefedov V. N., Osipova V. A., Smerchinskaya S. O., and Yashina N. P., “Non-contradictory aggregation of strict order relations”, Russian Math., 62 (2018), 61–73 | DOI | MR

[7] Nefedov V. N., Smerchinskaya S. O., and Yashina N. P., “Non-contradictory aggregation of quasi-order relations”, Prikladnaya Diskretnaya Matematika, 2019, no. 45, 113–126 (in Russian) | Zbl

[8] Zhukov M. S. and Orlov A. I., “The problem of research of final ranking for group of experts by means of Kemeny median”, Scientific J. KubSAU, 2016, no. 122, 784–805 (in Russian)

[9] Alekseev N. S. and Osipova V. A., “Methodology for building a full order classification with information about comparative importance of criteria”, Nauchno-Tekhnich. Vestnik Povolzh'ya, 2020, no. 11, 7–11 (in Russian) | Zbl

[10] Smerchinskaya S. O. and Yashina N. P., “Aggregation of preferences taking into account the importance of criteria”, Proc. MAI, 2015, no. 84 (in Russian)

[11] Smerchinskaya S. O. and Yashina N. P., “An algorithm for pairwise comparison of alternatives in multi-criteria problems”, Intern. J. Modeling Simulation Scientific Computing, 9:1 (2018) | DOI

[12] Berge C., Theorie des Graphes et ses Applications, DUNOD, Paris, 1958 | MR

[13] Nefedov V. N., Some properties of a linearly ordered median for an odd number of linear asymmetric binary relations, Dep. VINITI No 62–B2021, 08.11.2021, MAI, 50 pp. (in Russian) | Zbl

[14] Kemeny J. and Snell J., Mathematical Models in the Social Sciences, Blaisdell Publ. Comp., N.Y., 1963 | MR

[15] Korneenko V. P., Methods for Multi-Criteria Evaluation of Objects with a Multi-Level Structure of Performance Indicators, MAKS Press, M., 2018 (in Russian)