The Borda Count as an Initial Threshold for Kemeny Ranking Aggregation

  1. Rico, Noelia 1
  2. Vela, Camino R. 1
  3. Pérez-Fernández, Raúl 1
  4. Díaz, Irene 1
  1. 1 Universidad de Oviedo
    info

    Universidad de Oviedo

    Oviedo, España

    ROR https://ror.org/006gksa02

Actas:
Joint Proceedings of the 19th World Congress of the International Fuzzy Systems Association (IFSA), the 12th Conference of the European Society for Fuzzy Logic and Technology (EUSFLAT), and the 11th International Summer School on Aggregation Operators (AGOP) - Atlantis Studies in Uncertainty Modelling

Editorial: Atlantis Press

ISSN: 2589-6644

Año de publicación: 2021

Páginas: 562-569

Congreso: 19th World Congress of the International Fuzzy Systems Association (IFSA), the 12th Conference of the European Society for Fuzzy Logic and Technology (EUSFLAT), and the 11th International Summer School on Aggregation Operators (AGOP)

Tipo: Aportación congreso

DOI: 10.2991/ASUM.K.210827.074 GOOGLE SCHOLAR lock_openAcceso abierto editor

Resumen

The need of establishing a consensus ranking from the preferences expressed by different voters arises in several contexts. The method proposed by Kemeny to this purpose is famously known due to its numerous fulfilled properties and intuitive interpretation, as it minimizes the number of pairwise comparisons in which the consensus ranking disagrees with the preferences given by the voters. Nevertheless, this method has a main drawback regarding its execution time, thus preventing its use in practice. There exist some other methods, such as the Borda Count, that can be computed in polynomial time, even though they do not fulfill as many intuitive properties as the Kemeny method.Here, we propose to use the Borda Count ranking as the initial solution of a Branchand-Bound algorithm for reducing the execution time of the Kemeny method. The presented experiments show that this approachleads to an improvement in execution time.

€ Ver financiación

Información de financiación

This research has been supported by Grant TIN2017-87600-P from the Spanish Government and PID2019-106263RB-I00. Noelia Rico is supported by the Severo Ochoa program (PA-20-PF-BP19-167).

Financiadores

  • Spanish Goverment Spain
    • TIN2017-87600-P
    • PID2019-106263RB-I00
  • Severo Ochoa program Spain
    • PA-20-PF-BP19-167

Referencias bibliográficas

  • A. Ali, M. Meila, Experiments with Kemeny ranking: What works when?, Mathematical Social Sciences 64 (1) (2012) 28 – 40, Computational Foundations of Social Choice.
  • S. Amodio, A. D’Ambrosio, R. Siciliano, 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) (2016) 667 – 676.
  • I. Azzini, G. Munda, A new approach for identifying the Kemeny median ranking, European Journal of Operational Research 281 (2020) 388–401.
  • J. P. Barthelemy, A. Guenoche, O. Hudry, Median linear orders: Heuristics and a branch and bound algorithm, European Journal of Operational Research 42 (1989) 313–325.
  • J. Bartholdi, C. A. Tovey, M. A. Trick, Voting schemes for which it can be difficult to tell who won the election, Social Choice and Welfare 6 (2) (1989) 157–165.
  • J. C. Borda, Mémoire sur les Élections au Scrutin, Histoire de l’Académie Royale des Sciences, Paris, 1781.
  • F. Brandt, V. Conitzer, U. Endriss, J. Lang, A. D. Procaccia (Eds.), Handbook of Computational Social Choice, Cambridge University Press, 2016.
  • M. Condorcet, Essai sur l’Application de l’Analyse à la Probabilité des Décisions Rendues à la Pluralité des Voix, De l’Imprimerie Royale, Paris, 1785.
  • D. Coppersmith, L. K. Fleischer, A. Rurda, Ordering by weighted number of wins gives a good ranking for weighted tournaments, ACM Transactions on Algorithms 6 (3) (2010) 1–13.
  • E. J. Emond, D. W. Mason, A new rank correlation coefficient with application to the consensus ranking problem, Journal of Multi-Criteria Decision Analysis 11 (1) (2002) 17–28.
  • K. Inada, The simple majority decision rule, Econometrica 37 (3) (1969) 490–506.
  • J. G. Kemeny, Mathematics without numbers, Daedalus 88 (4) (1959) 577–591.
  • K. O. May, A set of independent necessary and sufficient conditions for simple majority decision, Econometrica 20 (1952) 680–684.
  • S. V. Muravyov, Ordinal measurement, preference aggregation and interlaboratory comparisons, Measurement 46 (2013) 2927–2935.
  • D. Saari, Which is better: The Condorcet or Borda winner?, Social Choice and Welfare 26 (2006) 107–129.
  • D. G. Saari, V. R. Merlin, A geometric examination of Kemeny’s rule, Social Choice and Welfare 17 (3) (2000) 403–438.
  • T. N. Tideman, Independence of clones as a criterion for voting rules, Social Choice and Welfare 4 (3) (1987) 185–206.
  • H. P. Young, Condorcet’s theory of voting, American Political Science Review 82 (4) (1988) 1231–1244.