El método Kemeny-Young es un sistema electoral que utiliza papeletas clasificadas y recuentos de comparación por pares para identificar las opciones más populares en una elección. Es un método Condorcet porque si hay un ganador Condorcet, siempre se clasificará como la opción más popular.
Este método asigna una puntuación a cada secuencia posible, donde cada secuencia considera qué opción podría ser la más popular, cuál podría ser la segunda más popular, cuál podría ser la tercera más popular, y así sucesivamente hasta llegar a cuál podría ser la menos popular. La secuencia que tiene la puntuación más alta es la secuencia ganadora, y la primera opción en la secuencia ganadora es la opción más popular. (Como se explica a continuación, los empates pueden ocurrir en cualquier nivel de clasificación).
El método Kemeny-Young también se conoce como la regla de Kemeny , el método de clasificación de popularidad de VoteFair , el método de máxima verosimilitud y la relación mediana .
El método Kemeny-Young utiliza papeletas preferenciales en las que los votantes clasifican las opciones según su orden de preferencia. A un votante se le permite clasificar más de una opción en el mismo nivel de preferencia. [ cita requerida ] Las opciones no clasificadas generalmente se interpretan como las menos preferidas.
Los cálculos de Kemeny-Young se realizan generalmente en dos pasos. El primer paso es crear una matriz o tabla que cuente las preferencias de los votantes por pares. El segundo paso es probar todas las clasificaciones posibles , calcular una puntuación para cada una de ellas y comparar las puntuaciones. Cada puntuación de clasificación es igual a la suma de los recuentos por pares que se aplican a esa clasificación.
La clasificación que tenga la puntuación más alta se identifica como la clasificación general. (Si más de una clasificación tiene la misma puntuación más alta, todas estas clasificaciones posibles están empatadas y, por lo general, la clasificación general implica uno o más empates).
Otra forma de ver el ordenamiento es que es el que minimiza la suma de las distancias tau de Kendall ( distancia de clasificación de burbuja ) a las listas de votantes.
Para demostrar cómo se convierte el orden de preferencia de un individuo en una tabla de recuento, vale la pena considerar el siguiente ejemplo. Supongamos que un solo votante tiene la opción de elegir entre cuatro candidatos (es decir, Elliot, Meredith, Roland y Selden) y tiene el siguiente orden de preferencia:
Estas preferencias se pueden expresar en una tabla de recuento. Una tabla de recuento, que organiza todos los recuentos por pares en tres columnas, es útil para contar (contar) las preferencias de voto y calcular las puntuaciones de clasificación. La columna central registra cuándo un votante indica más de una opción en el mismo nivel de preferencia. El orden de preferencia anterior se puede expresar como la siguiente tabla de recuento: [ cita requerida ]
Ahora supongamos que varios votantes han votado por esos cuatro candidatos. Una vez contados todos los votos, se puede utilizar el mismo tipo de tabla de recuento para resumir todas las preferencias de todos los votantes. A continuación se muestra un ejemplo para un caso en el que hay 100 votantes:
La suma de los recuentos en cada fila debe ser igual al número total de votos.
Una vez completada la tabla de recuento, se examinan por turnos las posibles clasificaciones de opciones y se calcula su puntuación sumando el número correspondiente de cada fila de la tabla de recuento. Por ejemplo, la clasificación posible:
satisface las preferencias Elliot > Roland, Elliot > Meredith, Elliot > Selden, Roland > Meredith, Roland > Selden y Meredith > Selden. Las puntuaciones respectivas, tomadas de la tabla, son
dando una puntuación de clasificación total de 30 + 60 + 60 + 70 + 60 + 40 = 320.
Una vez calculadas las puntuaciones de cada clasificación posible, se puede identificar la clasificación que tenga la puntuación más alta y se convierte en la clasificación general. En este caso, la clasificación general es:
con una puntuación de clasificación de 370.
Si hay ciclos o empates, más de una clasificación posible puede tener la misma puntuación máxima. Los ciclos se resuelven generando una única clasificación general en la que algunas de las opciones están empatadas. [ Aclaración necesaria ]
Una vez calculada la clasificación general, los recuentos de comparación por pares se pueden organizar en una matriz de resumen, como se muestra a continuación, en la que las opciones aparecen en el orden ganador desde la más popular (arriba y a la izquierda) hasta la menos popular (abajo y a la derecha). Este diseño de matriz no incluye los recuentos por pares de preferencias iguales que aparecen en la tabla de recuento: [1]
En esta matriz de resumen, la puntuación de clasificación más alta es igual a la suma de los recuentos en la mitad triangular superior derecha de la matriz (que se muestra aquí en negrita y con un fondo verde). Ninguna otra clasificación posible puede tener una matriz de resumen que arroje una suma mayor de números en la mitad triangular superior derecha (si la tuviera, esa sería la clasificación general).
En esta matriz de resumen, la suma de los números en la mitad triangular inferior izquierda de la matriz (mostrados aquí con un fondo rojo) son un mínimo. Los artículos académicos de John Kemeny y Peyton Young [2] [3] hacen referencia a la búsqueda de esta suma mínima, que se denomina puntaje de Kemeny y que se basa en cuántos votantes se oponen (en lugar de apoyar) a cada orden por pares:
Supongamos que Tennessee está celebrando unas elecciones para decidir la ubicación de su capital . La población está concentrada en torno a cuatro ciudades importantes. Todos los votantes quieren que la capital esté lo más cerca posible de ellos. Las opciones son:
Las preferencias de los votantes de cada región son:
Esta matriz resume los recuentos de comparación por pares correspondientes :
El método Kemeny-Young organiza los recuentos de comparación por pares en la siguiente tabla de recuento:
La puntuación de clasificación para la posible clasificación de Memphis en primer lugar, Nashville en segundo lugar, Chattanooga en tercer lugar y Knoxville en cuarto lugar es igual (el número sin unidades) a 345, que es la suma de los siguientes números anotados.
Esta tabla enumera todas las puntuaciones de clasificación:
La puntuación de clasificación más alta es 393, y esta puntuación está asociada con la siguiente clasificación posible, por lo que esta clasificación también es la clasificación general:
Si se necesita un único ganador, se elige la primera opción, Nashville. (En este ejemplo, Nashville es el ganador del Condorcet ).
La siguiente matriz de resumen organiza los recuentos por pares en orden desde el más popular (arriba y a la izquierda) al menos popular (abajo y a la derecha):
En esta disposición, la puntuación de clasificación más alta (393) es igual a la suma de los recuentos en negrita, que están en la mitad triangular superior derecha de la matriz (con un fondo verde).
En todos los casos en que no se produce un empate exacto, el método Kemeny-Young identifica la opción más popular, la segunda opción más popular, y así sucesivamente.
Puede producirse un empate en cualquier nivel de preferencia. Salvo en algunos casos en los que se produzcan ambigüedades circulares , el método Kemeny-Young solo produce un empate en un nivel de preferencia cuando el número de votantes con una preferencia coincide exactamente con el número de votantes con la preferencia opuesta.
Todos los métodos Condorcet, incluido el método Kemeny-Young, satisfacen estos criterios:
El método Kemeny-Young también satisface estos criterios:
Al igual que todos los métodos Condorcet, el método Kemeny-Young no cumple estos criterios (lo que significa que los criterios descritos no se aplican al método Kemeny-Young):
El método Kemeny-Young tampoco cumple estos criterios (lo que significa que los criterios descritos no se aplican al método Kemeny-Young):
No se conoce un algoritmo para calcular un polinomio de clasificación de Kemeny-Young en el tiempo en el número de candidatos, y es poco probable que exista ya que el problema es NP-hard [5] incluso si hay solo 4 votantes (par) [6] [7] o 7 votantes (impar). [8]
Se ha informado [9] que los métodos de cálculo basados en programación entera permitían a veces calcular clasificaciones completas de votos para hasta 40 candidatos en segundos. Sin embargo, ciertas elecciones Kemeny con 40 candidatos y 5 votantes generadas al azar no se pudieron resolver en un ordenador Pentium de 3 GHz en un tiempo útil en 2006. [9]
El método Kemeny-Young puede formularse como una instancia de un problema más abstracto, el de encontrar conjuntos de arcos de retroalimentación ponderados en gráficos de torneos . [10] Como tal, muchos métodos para el cálculo de conjuntos de arcos de retroalimentación pueden aplicarse a este problema, incluyendo una variante del algoritmo Held-Karp que puede calcular la clasificación Kemeny-Young de candidatos en tiempo , significativamente más rápido para muchos candidatos que el tiempo factorial de probar todas las clasificaciones. [11] [12] Existe un esquema de aproximación de tiempo polinomial para calcular una clasificación Kemeny-Young, [13] y también existe un algoritmo de tiempo subexponencial parametrizado con tiempo de ejecución O * (2 O( √ OPT ) ) para calcular dicha clasificación. [10]
El método Kemeny-Young fue desarrollado por John Kemeny en 1959. [2]
En 1978, Peyton Young y Arthur Levenglick caracterizaron axiomáticamente el método, mostrando que es el único método neutral que satisface la consistencia y el llamado criterio cuasi-Condorcet. [3] También se puede caracterizar utilizando la consistencia y una propiedad de monotonía. [14] En otros artículos, [15] [16] [17] [18] Young adoptó un enfoque epistémico para la agregación de preferencias: supuso que había un orden de preferencia objetivamente 'correcto', pero desconocido sobre las alternativas, y los votantes reciben señales ruidosas de este verdadero orden de preferencia (cf. Teorema del jurado de Condorcet ). Usando un modelo probabilístico simple para estas señales ruidosas, Young mostró que el método Kemeny-Young era el estimador de máxima verosimilitud del verdadero orden de preferencia. Young argumenta además que el propio Condorcet conocía la regla de Kemeny-Young y su interpretación de máxima verosimilitud, pero no pudo expresar claramente sus ideas.
En los artículos de John Kemeny y Peyton Young, los puntajes de Kemeny utilizan recuentos de cuántos votantes se oponen, en lugar de apoyar, cada preferencia por pares, [2] [3] pero el puntaje más pequeño identifica la misma clasificación general.
Desde 1991, el método ha sido promovido bajo el nombre de "clasificación de popularidad VoteFair" por Richard Fobes. [19]
La siguiente tabla compara el método Kemeny-Young con otros métodos electorales con ganador único:
