Methods of searching for the Kemeny median for non-strict and partial orderings of alternatives

A. V. Kalach   ; Yu. V. Bugaev   ; B. E. Nikitin

Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematika, mehanika, fizika, Tome 16 (2024) no. 1, pp. 13-22

Résumé

This article describes an approximate algorithm for finding the Kemeny median for a set of non-strict orderings of alternatives. The study was carried out for choosing alternatives involving making an informed decision on the completion of the analysis and generalization of incoming information and reaching a threshold value for the decision criterion. The article offers a justification for choosing solutions to multi-criteria tasks in planning and management from an existing set of alternatives using expert assessments. Two algorithms for searching for the Kemeny median are proposed in the presence of non-strict and partial orderings in the initial profile and in the presence of alternatives that have not been evaluated by experts. The article discusses constructing the Kemeny median according to the algorithm using a numerical example. The article shows the validity of using the approximate algorithm to solve the express algorithm in comparison with the traditional exact algorithm. It is separately noted that in the case of several solutions, the algorithm guarantees finding an option that is close enough to an expert ordering of the expert assessment profile under consideration.

Détail

Mots-clés : alternatives
Keywords: ranking, Condorcet principle, Board procedure, Kemeny median, algorithm, experts.

Bibliographie

[1] K. Mallahi-Karai, A. Diederich, “Decision with Multiple Alternatives: Geometric Models in Higher Dimensions - the Cube Model”, Journal of Mathematical Psychology, 93 (2019), 102294 | DOI

[2] A. Diederich, K. Mallahi-Karai, “Cube Model: Predictions and Account for Best-Worst Choice Situations with Three Choice Alternatives”, Journal of Choice Modelling, 49 (2023), 100448 | DOI

[3] R.E. Allen, J. Rehbeck, “Revealed Stochastic Choice with Attributes”, Economic Theory, 75 (2023), 91–112 | DOI

[4] Tihanychev O.V., “About some Problems of the Decision Support Domain”, Programmnye produkty i sistemy, 2016, no. 3, 24–28 (in Russ.) | DOI

[5] Korneenko V., “Optimization Method of Selecting the Resulting Ranking of Objects Presented Inrank Scale of Measurement”, Large-Scale Systems Control, 2019, no. 82, 44–60 (in Russ.) | DOI

[6] P.L. Smith, “Stochastic Dynamic Models of Response Time and Accuracy: A Foundational Primer”, Journal of Mathematical Psychology, 44:3 (2000), 408–463 | DOI

[7] R. Ratcliff, L. Philip, S. Smith, D. Brown, G. McKoon, “Diffusion Decision Model: Current Issues and History”, Trends in Cognitive Sciences, 20:4 (2016), 260–281 | DOI

[8] J. Townsend, “Decision Field Theory: A Dynamic-Cognitive Approach to Decision Making in an Uncertain Environment”, Psychological review, 100:3 (1993), 432–459 | DOI

[9] S.A. Baker, T. Griffith, N.F. Lepora, “Degenerate Boundaries for Multiple-Alternative Decisions”, Nat. Commun., 13 (2022), 5066 | DOI

[10] P.D. Kvam, “A Geometric Framework for Modeling Dynamic Decisions among Arbitrarily Many Alternatives”, Journal of Mathematical Psychology, 91 (2019), 14–37 | DOI

[11] Bugaev Yu.V., Nikitin B.E., “An Approximate Method for Searching the Kemen's Median for Nonstrict Preferences”, Matematicheskie metody v tekhnologiiakh i tekhnike, 2021, no. 6, 37–41 (in Russ.) | DOI

[12] Bugaev Yu.V., Synthesis of Choice Models based on Two-Stage Majority Schemes, Dr. phys. and math. sci. diss., Voronezh, 2005, 343 pp. (in Russ.)

[13] Nogin V.D., Decision Making in a Multicriteria Environment: a Quantitative Approach, FIZMATLIT Publ, M., 2005, 176 pp. (in Russ.)

[14] J. G. Kemeny, J. Snell, Mathematical models in the social sciences, Blaisdell, New York, 1962, 145 pp.; Reprinted: MIT Press, Cambridge, 1972

[15] Litvak B.G., Expert Information. Methods of Obtaining and Analysis, Radio i svyaz' Publ, M., 1982, 184 pp. (in Russ.)

[16] Bugaev Yu.V., Mironova M.S., Nikitin B.E., “Probabilistic Method for Analyzing Procedures for Constructing Collective Expert Assessments”, Vestnik Voronezhskogo gosudarstvennogo universiteta, 2011, no. 2, 130–135 (in Russ.)

[17] Bugaev Yu.V., Nikitin B.E., Shurupova I.Y., “Analysis of Probabilistic Properties Rules of Construction Group Expert Estimations”, Iskusstvennyy intellekt i prinyatie resheniy, 2018, no. 2, 84–94 (in Russ.) | DOI

[18] Orlov A.I., Organizational and Economic Modeling, v. 2, Expert assessments, MGTU im. N.E. Baumana Publ, M., 2011, 486 pp. (in Russ.)

[19] Zhukov M. S., Orlov A. I., “The Problem of Research of Final Ranking for Group of Experts by Means of Kemeny Median”, Scientific Journal of KubSAU, 2016, no. 122(08), 785–806 (in Russ.)

[20] Chertok B.E. (Ed.), Cosmonautics of the XXI century. An attempt to forecast development up to 2101, RTSoft Publ, M., 2010, 864 pp. (in Russ.)

[21] Lipskiy V., Combinatorics for Programmers, Mir Publ, M., 1988, 213 pp. (in Russ.)

[22] Zakharova L.E., Algorithms for Discrete Mathematics: Textbook, Mosk. gos. in-t elektroniki i matematiki Publ, M., 2002, 120 pp. (in Russ.)