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




Ranking, Kemeny consensus, Averaged expert ranking


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


N. Betzler et al., “Fixed-parameter algorithms for Kemeny rankings”, Theor. Comp. Sci., vol. 410, iss. 45, pp. 4554–4570, 2009.

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.

E. Hemaspaandra et al., “The complexity of Kemeny elections”, Theor. Comp. Sci., vol. 349, iss. 3, pp. 382–391, 2005.

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. 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.

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.

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.

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.

B. Can, “Weighted distances between preferences”, J. Math.Economics, vol. 51, pp. 109–15, 2014. 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.