Fast Kemeny Consensus by Searching over Standard Matrices Distanced to the Averaged Expert Ranking by Minimal Difference

Authors

DOI:

https://doi.org/10.20535/1810-0546.2016.1.59784

Keywords:

Ranking, Kemeny consensus, Averaged expert ranking

Abstract

Background. The problem of ranking a finite set of objects is considered.

Objective. The goal is to develop an algorithm that would let speed up the search of the Kemeny consensus along with substantiation of a metric to compare rankings.

Methods. An approach for aggregating experts’ rankings is suggested and substantiated. Also a metric to compare rankings is suggested and substantiated.

Results. The developed algorithm finds a set of Kemeny rankings much faster than the classical straightforward search. Also this set often contains a single Kemeny consensus, what fails by the straightforward search. Besides, a single Kemeny consensus is determined at one stroke if the averaged expert ranking turns out acyclic. Thus the problem of selecting a single Kemeny consensus is solved.

Conclusions. For 10 objects and more, where most known approaches become intractable, the algorithm still is tractable due to searching over only those standard matrices whose distance to the first ranking differs minimally from the distance between this ranking and the averaged expert ranking.

Author Biography

Вадим Васильович Романюк, Khmelnitskiy National University

Vadim V. Romanuke,

doctor of sciences (engineering), associate professor, professor

References

N. Betzler et al., “Fixed-parameter algorithms for Kemeny rankings”, Theor. Comp. Sci., vol. 410, iss. 45, pp. 4554–4570, 2009. http://dx.doi.org/10.1016/j.tcs.2009.08.033

C. Dwork et al., “Rank aggregation methods for the Web”, in Proc. 10th Int. Conf. WWW10, Hong Kong, May 1–5, 2001, pp. 613–622. http://dx.doi.org/10.1145/371920.372165

E. Hemaspaandra et al., “The complexity of Kemeny elections”, Theor. Comp. Sci., vol. 349, iss. 3, pp. 382–391, 2005. http://dx.doi.org/10.1016/j.tcs.2005.08.031

J. Flum and M. Grohe, Parameterized Complexity Theory. SpringerBerlinHeidelberg, 2006, 495 p.

A. van Zuylen and D. P. Williamson, “Deterministic algorithms for rank aggregation and other ranking and clustering problems”, in Proc. 5th Int. Workshop WAOA 2007,Eilat,Israel, October 11–12, 2007, pp. 260–273. http://dx.doi.org/10.1007/ 978-3-540-77918-6_21

C. Kenyon-Mathieu and W. Schudy, “How to rank with few errors”, in Proc. 39th Annual ACM Symp. STOC’07,San Diego,California,USA, June 11–13, 2007, pp. 95–103. http://dx.doi.org/10.1145/1250790.1250806

A. Davenport and J. Kalagnanam, “A computational study of the Kemeny rule for preference aggregation”, in Proc. 19th National Conf. AAAI’04, San Jose, California, USA, July 25–29, 2004, pp. 697–702.

V. Conitzer et al., “Improved bounds for computing Kemeny rankings”, in Proc. 21st National Conf. AAAI’06, Boston, Massachusetts, USA, July 16–20, 2006, pp. 620–626.

N. Betzler et al., “Fixed-parameter algorithms for Kemeny scores”, in Proc. 4th Int. Conf. AAIM 2008, Shanghai, China, June 23–25, 2008, pp. 60–71. http://dx.doi.org/10.1007/978-3-540-68880-8_8

N. Betzler et al., “How similarity helps to efficiently compute Kemeny rankings”, in Proc. 8th Int. Conf. AAMAS 2009,Budapest,Hungary, May 10–15, 2009, pp. 657–664.

W.D. Cook et al., “A general framework for distance-based consensus in ordinal ranking models”, Europ. J. Operational Res., vol. 96, iss. 2, pp. 392–397, 1997. http://dx.doi.org/10.1016/0377-2217(95)00322-3

L. Roselló et al., “Using consensus and distances between generalized multi-attribute linguistic assessments for group decision-making”, Inform. Fusion, vol. 17, pp. 83–92, 2014. http://dx.doi.org/10.1016/j.inffus.2011.09.001

B. Can, “Weighted distances between preferences”, J. Math.Economics, vol. 51, pp. 109–15, 2014. http://dx.doi.org/10.1016/ j.jmateco.2014.01.002

I. Contreras, “Emphasizing the rank positions in a distance-based aggregation procedure”, Decision Support Systems, vol. 51, iss. 1, pp. 240–245, 2011. http://dx.doi.org/10.1016/j.dss.2010.12.012

Downloads

Published

2016-03-10

Issue

No. 1 (2016): Engineering

Section

Art

License

Copyright (c) 2017 NTUU KPI Authors who publish with this journal agree to the following terms:

    1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under CC BY 4.0 that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.

    2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.

    3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work