Reduciendo el tiempo computacional para el método de Kemeny al explotar las propiedades de Condorcet
Autores: Rico, Noelia; Vela, Camino R.; Pérez-Fernández, Raúl; Díaz, Irene
Idioma: Inglés
Editor: MDPI
Año: 2021
Acceso abierto
Artículo científico
2021
Reduciendo el tiempo computacional para el método de Kemeny al explotar las propiedades de Condorcet
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Agregación
Clasificación
Método de Kemeny
Teoría de la elección social
NP-duro
Algoritmos
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 31
Citaciones: Sin citaciones
La agregación de preferencias y en particular la agregación de rankings son principalmente estudiadas por el campo de la teoría de la elección social, pero son ampliamente aplicadas en una variedad de contextos. Entre los métodos más prominentes para la agregación de rankings, el método de Kemeny ha demostrado ser el único que satisface algunas propiedades deseables como neutralidad, consistencia y la condición de Condorcet al mismo tiempo. Desafortunadamente, el problema de encontrar un ranking de Kemeny es NP-duro, lo que impide a los profesionales utilizarlo en problemas de la vida real. El estado del arte de los algoritmos exactos para la computación del ranking de Kemeny experimentó un gran impulso el año pasado con la presentación de un algoritmo que proporciona garantía de tiempo de búsqueda de hasta 13 alternativas. En este trabajo, proponemos una versión mejorada de este algoritmo basada en podar el espacio de búsqueda cuando se cumplen algunas propiedades de Condorcet. Esta versión mejorada mejora significativamente el rendimiento en términos de consumo de tiempo de ejecución.
Descripción
La agregación de preferencias y en particular la agregación de rankings son principalmente estudiadas por el campo de la teoría de la elección social, pero son ampliamente aplicadas en una variedad de contextos. Entre los métodos más prominentes para la agregación de rankings, el método de Kemeny ha demostrado ser el único que satisface algunas propiedades deseables como neutralidad, consistencia y la condición de Condorcet al mismo tiempo. Desafortunadamente, el problema de encontrar un ranking de Kemeny es NP-duro, lo que impide a los profesionales utilizarlo en problemas de la vida real. El estado del arte de los algoritmos exactos para la computación del ranking de Kemeny experimentó un gran impulso el año pasado con la presentación de un algoritmo que proporciona garantía de tiempo de búsqueda de hasta 13 alternativas. En este trabajo, proponemos una versión mejorada de este algoritmo basada en podar el espacio de búsqueda cuando se cumplen algunas propiedades de Condorcet. Esta versión mejorada mejora significativamente el rendimiento en términos de consumo de tiempo de ejecución.