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

Вадим Васильович Романюк

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.

Keywords


Ranking; Kemeny consensus; Averaged expert ranking

Full Text:

PDF

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


GOST Style Citations


  1. Fixed-parameter algorithms for Kemeny rankings / N. Betzler, M.R. Fellows, J. Guo et al. // Theor. Comp. Sci. – 2009. – 410, iss. 45. – P. 4554–4570. http://dx.doi.org/10.1016/j.tcs.2009.08.033

  2. Rank aggregation methods for the Web / C. Dwork, R. Kumar, M. Naor, D. Sivakumar // Proc. 10th Int. Conf. WWW10, May 1–5, 2001,Hong Kong. – ACMNew York, 2001. – P. 613–622. http://dx.doi.org/10.1145/371920.372165

  3. Hemaspaandra E., Spakowski H., Vogel J. The complexity of Kemeny elections // Theor. Comp. Sci. – 2005. – 349, iss. 3. – P. 382–391. http://dx.doi.org/10.1016/j.tcs.2005.08.031

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

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

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

  7. Davenport A., Kalagnanam J. A computational study of the Kemeny rule for preference aggregation // Proc. 19th National Conf. AAAI’04, July 25–29, 2004,San Jose,California,USA. – The AAAI Press, 2004. – P. 697–702.

  8. Conitzer V., Davenport A., Kalagnanam J. Improved bounds for computing Kemeny rankings // Proc. 21st National Conf. AAAI’06, July 16–20, 2006,Boston,Massachusetts,USA. – The AAAI Press, 2006. – P. 620–626.

  9. Fixed-parameter algorithms for Kemeny scores / N. Betzler, M.R. Fellows, J. Guo et al. // Proc. 4th Int. Conf. AAIM 2008, June 23–25, 2008,Shanghai,China. – Springer-Verlag BerlinHeidelberg, 2008. – P. 60–71. http://dx.doi.org/10.1007/978-3-540-68880-8_8

  10. How similarity helps to efficiently compute Kemeny rankings / N. Betzler, M.R. Fellows, J. Guo et al. // Proc. 8th Int. Conf. AAMAS 2009, May 10–15, 2009, Budapest, Hungary. – P. 657–664.

  11. Cook W.D., Kress M., Seiford L.M. A general framework for distance-based consensus in ordinal ranking models // Europ. J. Operational Res. – 1997. – 96, iss. 2. – P. 392–397. http://dx.doi.org/10.1016/0377-2217(95)00322-3

  12. Using consensus and distances between generalized multi-attribute linguistic assessments for group decision-making / L. Ro­selló, M. Sánchez, N. Agell et al. // Inform. Fusion. – 2014. – 17. – P. 83–92. http://dx.doi.org/10.1016/j.inffus.2011.09.001

  13. Can B. Weighted distances between preferences // J. Math. Economics. – 2014. – 51. – P. 109–115. http://dx.doi.org/10.1016/ j.jmateco.2014.01.002

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




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

Refbacks

  • There are currently no refbacks.


Copyright (c) 2017 NTUU KPI