logo móvil
Contáctanos

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

Descargar PDF

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


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.

Otros recursos que podrían interesarte

Temas Virtualpro