IDP 2016: Intelligent Data Processing pp 44-57

# On a Metric Kemeny’s Median

• Sergey Dvoenko
• Denis Pshenichny
Conference paper
Part of the Communications in Computer and Information Science book series (CCIS, volume 794)

## Abstract

The Kemeny’s median represents the coordinated ranking as the opinion of an expert group. Such an opinion is the least different from others in the group and is free of some contradictions (Arrow’s paradox) in the well-known majority rule problem. The new problem of building the Kemeny’s median with metric characteristics is being developed in this paper. It is assumed, rankings represented by pairwise distances between them are immersed as a set in some Euclidean space. In this case, we can define the mean element as the center of this set. Such central element is a ranking as well and must be similar to the Kemeny’s median. The mathematically correct Kemeny’s median needs to be seen as the center in its distances to other elements. A new procedure is developed to build the modified loss matrix and find the metric Kemeny’s median.

## Keywords

Kemeny’s median Rank aggregation Majority rule Arrow’s paradox Pairwise comparison Metrics

## Notes

### Acknowledgments

This research was partially supported by the Russian Foundation for Basic Research (RFBR) grants 15-05-02228, 15-07-08967, 17-07-00319, 17-07-00436.

## References

1. 1.
Litvak, B.G.: Expert Information: Methods of Acquisition and Analysis, 184 p. Radio i svyaz, Moscow (1982). (in Russian)Google Scholar
2. 2.
Charon, I., Guenoche, A., Hudry, O., Woirgard, F.: New results on the computation of median orders. Discrete Math. 165(166), 139–153 (1997).
3. 3.
Biedl, T., Brandenburg, F.J., Deng, X.: Crossings and permutations. In: Healy, P., Nikolov, N.S. (eds.) GD 2005. LNCS, vol. 3843, pp. 1–12. Springer, Heidelberg (2006).
4. 4.
Conitzer, V., Davenport, A., Kalagnanam, J.: Improved bounds for computing Kemeny rankings. In: Proceedings of the 21st National Conference on Artificial Intelligence, vol. 1, pp. 620–626 (2006). http://www.cs.cmu.edu/conitzer/kemenyAAAI06.pdf
5. 5.
Nogin, V.D.: Reducing of Pareto Set: an Axiomatic Approach. Fizmatlit, Moscow (2016). (in Russian)Google Scholar
6. 6.
Larichev, O.I., Moshkovich, E.M.: Qualitative Methods of Decision Making. Verbal Analysis of Decisions. Nauka, Fizmatlit, Moscow (1996). (in Russian)
7. 7.
Jiao, Y., Korba, A., Sibony, E.: Controlling the distance to a Kemeny consensus without computing it. In: Balcan, M.F., Weinberger, K.Q. (eds.) Proceedings of The 33rd International Conference on Machine Learning. PMLR, vol. 48, pp. 2971–2980 (2016)Google Scholar
8. 8.
Dvoenko, S.D., Pshenichny, D.O.: Optimal correction of metrical violations in matrices of pairwise comparisons. JMLDA 1(7), 885–890 (2014). (in Russian)Google Scholar
9. 9.
Dvoenko, S.D., Pshenichny, D.O.: On metric correction of matrices of pairwise comparisons. JMLDA 1(5), 606–620 (2013). (in Russian)Google Scholar
10. 10.
Dvoenko, S.D., Pshenichny, D.O.: A recovering of violated metrics in machine learning. In: Proceedings of the Seventh Symposium on Information and Communication Technology (SoICT’16), pp. 15–21. ACM, New York (2016).
11. 11.
Kemeny, J., Snell, J.: Mathematical Models in the Social Sciences. Blaisdell, New York (1963)
12. 12.
Mirkin, B.G.: The Problem of a Group Choice. Nauka, Moscow (1974). (in Russian)Google Scholar
13. 13.
Kemeny, J.: Mathematics without numbers. Daedalus 88(4), 577–591 (1959)Google Scholar
14. 14.
Young, G., Housholder, A.S.: Discussion of a set of points in terms of their mutual distances. Psychometrica 3(1), 19–22 (1938).
15. 15.
Torgerson, W.S.: Theory and Methods of Scaling, 460 p. Wiley, New York (1958).
16. 16.
Dvoenko, S.D.: Clustering and separating of a set of members in terms of mutual distances and similarities. Trans. MLDM 2(2), 80–99 (2009)Google Scholar
{"extraction_info": {"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.8443123698234558, "perplexity": 10080.183752102304}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2019-51/segments/1575540515344.59/warc/CC-MAIN-20191208230118-20191209014118-00465.warc.gz"}