The research of possibilities for fast calculation of median consensus rankings

Authors

DOI:

https://doi.org/10.15587/1729-4061.2018.140686

Keywords:

collective expert estimation, median consensus rankings, assignment problem

Abstract

We investigated the possibility of fast computation of collective expert estimates of the median type. Despite the widespread use of the Kemeny-Snell and Cook-Seiford medians for calculating the collective expert estimates, the possibilities to reduce the time required to calculate median consensus ranking through the application of the assignment problem and known algorithms for solving it, have been insufficiently investigated. In contrast to the most known methods, the method proposed in this paper is not approximated and retains the original median axiomatics of Kemeny. We investigated a possibility for calculating the Kemeny-Snell and Cook-Seiford medians using the assignment problem applying methods of computer experiment. We estimated the time required to calculate median rankings by four different algorithms for solving the assignment problem. It was established that the proposed method, at a moderate number of alternatives (n<50), computes median rankings over the time close to a real time mode. It is also shown that, in contrast to other methods, the calculation of median rankings using the assignment problem does not depend on coherence degree of individual expert rankings. The results obtained are useful for the practical application of the examined procedure in network expert systems. In such systems, the computation time of a consensus ranking should be close to real time. In addition, in the network expertise systems, due to the random gathering of a team of experts, there is a possibility of the low level of coherence in individual rankings. For the examined procedure, that does not affect the duration of computation. This allows us to recommend the developed computational procedure for a fast search for median consensus rankings by Kemeny-Snell and Cook-Seiford for practical application in the systems of network collective expertise.

Author Biographies

Viktor Boltenkov, Institute of Computer Systems Odessa National Polytechnic University Shevchenka ave., 1, Odessa, Ukraine, 65044

PhD, Associate Professor

Department of Information Systems

Varvara Kuvaieva, Institute of Computer Systems Odessa National Polytechnic University Shevchenka ave., 1, Odessa, Ukraine, 65044

Postgraduate student

Department of Information Systems

Oleg Galchonkov, Institute of Computer Systems Odessa National Polytechnic University Shevchenka ave., 1, Odessa, Ukraine, 65044

PhD, Associate Professor

Department of Information Systems

Alesya Ishchenko, Institute of Computer Systems Odessa National Polytechnic University Shevchenka ave., 1, Odessa, Ukraine, 65044

Senior Lecturer

Department of Applied Mathematics and Information Technologies

References

  1. Dopazo, E., Martínez-Céspedes, M. L. (2017). Rank aggregation methods dealing with ordinal uncertain preferences. Expert Systems with Applications, 78, 103–109. doi: https://doi.org/10.1016/j.eswa.2017.01.051
  2. Dodonov, A. G., Lande, D. V., Cyganok, V. V., Andreychuk, O. V., Kadenko, S. V., Grayvoronskaya, A. N. (2017). Raspoznavanie informacionnyh operaciy. Kyiv: OOO «Inzhiniring», 282.
  3. Gubanov, D., Korgin, N., Novikov, D., Raikov, A. (2014). E-Expertise: modern collective intelligence. Springer, 147. doi: https://doi.org/10.1007/978-3-319-06770-4
  4. Breslin, J., Bojars, U., Aleman-Meza, B., Boley, H., Mochol, M., Nixon, L. J. B. et. al. (2007). Finding experts using internet-based discussions in online communities and associated social networks. Proceedings of the 1st International Expert Finder Workshop at Knowledge Web General Assembly, 38–47.
  5. Wei, C.-P., Lin, W.-B., Chen, H.-C., An, W.-Y., Yeh, W.-C. (2015). Finding experts in online forums for enhancing knowledge sharing and accessibility. Computers in Human Behavior, 51, 325–335. 325–335. doi: https://doi.org/10.1016/j.chb.2015.04.055
  6. Kemeny, J. G., Snell, L. J. (1962). Preference ranking: an axiomatric approach, in: Mathematical Models in the Social Sciences. Ginn and Company, New York, 9–23.
  7. Cook, W. D., Seiford, L. M. (1978). Priority Ranking and Consensus Formation. Management Science, 24 (16), 1721–1732. doi: https://doi.org/10.1287/mnsc.24.16.1721
  8. Armstrong, R. D., Cook, W. D., Seiford, L. M. (1982). Priority Ranking and Consensus Formation: The Case of Ties. Management Science, 28 (6), 638–645. doi: https://doi.org/10.1287/mnsc.28.6.638
  9. Burkard, R. (2009). Assignment Problems. Society for Industrial and Applied Mathematics. Philadelphia, 382.
  10. Procaccia, A. D. (2011). Computational social choice. XRDS: Crossroads, The ACM Magazine for Students, 18 (2), 31. doi: https://doi.org/10.1145/2043236.2043249
  11. Moulin, H. (1983). The strategy of social choice. Vol. 18. Advanced Textbooks in Economics. Elsevier, 226.
  12. Heckelman, J., Miller, N. (2015). Handbook of social choice and voting. Edward Elgar Publishing, 424. doi: https://doi.org/10.4337/9781783470730
  13. 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–165. doi: https://doi.org/10.1007/bf00303169
  14. Bury, H., Wagner, D. (2008). Group judgement with ties. Distance-based methods. New Approaches in Automation and Robotics, 153–172. doi: https://doi.org/10.5772/5393
  15. Ali, A., Meilă, M. (2012). Experiments with Kemeny ranking: What works when? Mathematical Social Sciences, 64 (1), 28–40. doi: https://doi.org/10.1016/j.mathsocsci.2011.08.008
  16. D’Ambrosio, A., Mazzeo, G., Iorio, C., Siciliano, R. (2017). A differential evolution algorithm for finding the median ranking under the Kemeny axiomatic approach. Computers & Operations Research, 82, 126–138. doi: https://doi.org/10.1016/j.cor.2017.01.017
  17. Aledo, J. A., Gámez, J. A., Molina, D. (2013). Tackling the rank aggregation problem with evolutionary algorithms. Applied Mathematics and Computation, 222, 632–644. doi: https://doi.org/10.1016/j.amc.2013.07.081
  18. Jackson, B. N., Schnable, P. S., Aluru, S. (2008). Consensus Genetic Maps as Median Orders from Inconsistent Sources. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 5 (2), 161–171. doi: https://doi.org/10.1109/tcbb.2007.70221
  19. D'Ambrosio, A., Amodio, S., Iorio, C. (2015). Two algorithms for finding optimal solutions of the Kemeny rank aggregation problem for full rankings. Electronic Journal of Applied Statistical Analysis, 8 (2), 198–213. doi: https://doi.org/10.1285/i20705948v8n2p198
  20. Betzler, N., Fellows, M. R., Guo, J., Niedermeier, R., Rosamond, F. A. (2009). Fixed-parameter algorithms for Kemeny rankings. Theoretical Computer Science, 410 (45), 4554–4570. doi: https://doi.org/10.1016/j.tcs.2009.08.033
  21. Nápoles, G., Dikopoulou, Z., Papageorgiou, E., Bello, R., Vanhoof, K. (2015). Aggregation of Partial Rankings – An Approach Based on the Kemeny Ranking Problem. Lecture Notes in Computer Science, 343–355. doi: https://doi.org/10.1007/978-3-319-19222-2_29
  22. Kuhn, H. W. (1955). The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2 (1-2), 83–97. doi: https://doi.org/10.1002/nav.3800020109
  23. Pentico, D. W. (2007). Assignment problems: A golden anniversary survey. European Journal of Operational Research, 176 (2), 774–793. doi: https://doi.org/10.1016/j.ejor.2005.09.014
  24. Munkres, J. (1957). Algorithms for the Assignment and Transportation Problems. Journal of the Society for Industrial and Applied Mathematics, 5 (1), 32–38. doi: https://doi.org/10.1137/0105003
  25. Lelyakova, L. V., Haritonova, A. G., Chernyshova, G. D. (2017). Prikladnye zadachi o naznacheniyah (modeli, algoritmy resheniya). Vestnik VGU, Seriya: Sistemniy analiz i informacionnye tekhnologii, 2, 22–27.
  26. Samohvalov, Yu. Ya., Naumenko, E. M. (2007). Ekspertnoe ocenivanie. Metodicheskiy aspekt. Kyiv: DUIKT, 262.
  27. Boltenkov, V. A., Kuvaeva, V. I., Poznyak, A. V. (2017). Analiz mediannyh metodov konsensusnogo agregirovaniya rangovyh predpochteniy. Informatyka ta matematychni metody v modeliuvanni, 7 (4), 307–317.
  28. Mack, C. (1969). The Bradford method for the assignment problem. New Journal of Statistics and Operational Research, 1, 17–29.
  29. Jonker, R. (1989). Teaching linear assignment by Mack’s algorithm. Twenty-Five Years of Operations Research in the Netherlands: Papers Dedicated to Gijs de Leve, CWI Tract, 70, 54–60.
  30. Eddous, M., Stensfild, R.; Eliseeva, I. I. (Ed.) (1997). Metody prinyatiya resheniy. Moscow: Audit, YuNITI, 590.
  31. Ramshaw, L., Tarjan, R. E. (2012). On Minimum-Cost Assignments in Unbalanced Bipartite Graphs. HP Laboratories, HPL-2012-40R1, 91.
  32. Jonker, R., Volgenant, A. (1987). A shortest augmenting path algorithm for dense and sparse linear assignment problems. Computing, 38 (4), 325–340. doi: https://doi.org/10.1007/bf02278710
  33. Brauner, N., Echahed, R., Finke, G., Gregor, H., Prost, F. (2004). A complete assignment algorithm and its application in constraint declarative languages. Cahier du laboratoire Leibniz No. 111, 60.
  34. Bast, H., Mehlhorn, K., Schafer, G., Tamaki, H. (2005). Matching Algorithms Are Fast in Sparse Random Graphs. Theory of Computing Systems, 39 (1), 3–14. doi: https://doi.org/10.1007/s00224-005-1254-y
  35. Amodio, S., D’Ambrosio, A., Siciliano, R. (2016). Accurate algorithms for identifying the median ranking when dealing with weak and partial rankings under the Kemeny axiomatic approach. European Journal of Operational Research, 249 (2), 667–676. doi: https://doi.org/10.1016/j.ejor.2015.08.048
  36. Critchlow, D. E., Fligner, M. A., Verducci, J. S. (1991). Probability models on rankings. Journal of Mathematical Psychology, 35 (3), 294–318. doi: https://doi.org/10.1016/0022-2496(91)90050-4
  37. Farhadzade, E. M., Muradaliev, A. Z., Farzaliev, Yu. Z., Rafieva, T. K., Abdullaeva, S. A. (2017). Ocenka vzaimosvyazi tekhniko-ekonomicheskih pokazateley ob'ektov EES. Elektronnoe modelirovanie, 39 (6), 93–106.
  38. Antosiak, P. P. (2008). Dekompozytsiyni protsedury u zadachi znakhodzhennia strohoho rezultuiuchoho ranzhuvannia obiektiv u vyhliadi mediany Kemeni-Snella. Naukovyi visnyk Uzhhorodskoho universytetu, 17, 29–36.
  39. Sprent, P., Smeeton, N. C. (2007). Applied nonparametric statistical methods. CRC Press Taylor & Francis Group, 544.
  40. Kraska-Miller, M. (2013). Nonparametric statistics for social and behavioral sciences. CRC Press, 260. doi: https://doi.org/10.1201/b16188
  41. Kobzar', A. I. (2006). Prikladnaya matematicheskaya statistika. Dlya inzhenerov i nauchnyh rabotnikov. Moscow: FIZMATLIT, 816.
  42. Schach, S. (1979). An Alternative to the Friedman Test with Certain Optimality Properties. The Annals of Statistics, 7 (3), 537–550. doi: https://doi.org/10.1214/aos/1176344675
  43. Quade, D. (1979). Using Weighted Rankings in the Analysis of Complete Blocks with Additive Block Effects. Journal of the American Statistical Association, 74 (367), 680. doi: https://doi.org/10.2307/2286991

Downloads

Published

2018-08-16

How to Cite

Boltenkov, V., Kuvaieva, V., Galchonkov, O., & Ishchenko, A. (2018). The research of possibilities for fast calculation of median consensus rankings. Eastern-European Journal of Enterprise Technologies, 4(4 (94), 27–35. https://doi.org/10.15587/1729-4061.2018.140686

Issue

Vol. 4 No. 4 (94) (2018): Mathematics and Cybernetics - applied aspects

Section

Mathematics and Cybernetics - applied aspects

License

Copyright (c) 2018 Viktor Boltenkov, Varvara Kuvaieva, Oleg Galchonkov, Alesya Ishchenko

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

The consolidation and conditions for the transfer of copyright (identification of authorship) is carried out in the License Agreement. In particular, the authors reserve the right to the authorship of their manuscript and transfer the first publication of this work to the journal under the terms of the Creative Commons CC BY license. At the same time, they have the right to conclude on their own additional agreements concerning the non-exclusive distribution of the work in the form in which it was published by this journal, but provided that the link to the first publication of the article in this journal is preserved.

A license agreement is a document in which the author warrants that he/she owns all copyright for the work (manuscript, article, etc.).
The authors, signing the License Agreement with TECHNOLOGY CENTER PC, have all rights to the further use of their work, provided that they link to our edition in which the work was published.
According to the terms of the License Agreement, the Publisher TECHNOLOGY CENTER PC does not take away your copyrights and receives permission from the authors to use and dissemination of the publication through the world's scientific resources (own electronic resources, scientometric databases, repositories, libraries, etc.).
In the absence of a signed License Agreement or in the absence of this agreement of identifiers allowing to identify the identity of the author, the editors have no right to work with the manuscript.
It is important to remember that there is another type of agreement between authors and publishers – when copyright is transferred from the authors to the publisher. In this case, the authors lose ownership of their work and may not use it in any way.