El método Kemeny-Young es un sistema electoral que utiliza papeletas clasificadas y recuentos comparativos 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 aparecerá como la opción más popular.
Este método asigna una puntuación para cada secuencia posible, donde cada secuencia considera qué opción podría ser la más popular, qué opción podría ser la segunda más popular, qué opción podría ser la tercera más popular, y así sucesivamente hasta llegar a cuál opción podría ser la menos popular. 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 regla de Kemeny , ranking de popularidad VoteFair , método de máxima verosimilitud y relación de la mediana .
El método Kemeny-Young utiliza papeletas preferenciales en las que los votantes clasifican las opciones según su orden de preferencia. Un votante puede clasificar más de una opción en el mismo nivel de preferencia. [ cita necesaria ] Las opciones no clasificadas generalmente se interpretan como las menos preferidas.
Los cálculos de Kemeny-Young suelen realizarse 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.
El ranking que tiene mayor puntuación se identifica como ranking general. (Si más de una clasificación tiene la misma puntuación máxima, 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 orden es que es el que minimiza la suma de las distancias tau de Kendall ( distancia de clasificación de burbujas ) a las listas de votantes.
Para demostrar cómo se convierte un orden de preferencia individual en una tabla de conteo, vale la pena considerar el siguiente ejemplo. Supongamos que un solo votante puede 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 conteo. Una tabla de conteo, que organiza todos los conteos por pares en tres columnas, es útil para contar (contar) las preferencias de las boletas y calcular las puntuaciones de clasificación. La columna central rastrea cuando 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 conteo: [ cita necesaria ]
Ahora supongamos que varios votantes hubieran votado por esos cuatro candidatos. Una vez contadas todas las papeletas, se puede utilizar el mismo tipo de tabla de conteo para resumir todas las preferencias de todos los votantes. Aquí hay un ejemplo para un caso que tiene 100 votantes:
La suma de los conteos en cada fila debe ser igual al número total de votos.
Una vez completada la tabla de conteo, cada posible clasificación de opciones se examina por turno y su puntaje de clasificación se calcula sumando el número apropiado de cada fila de la tabla de conteo. Por ejemplo, la posible clasificación:
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 para cada clasificación posible, se puede identificar la clasificación que tiene 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 un ranking posible puede tener la misma puntuación mayor. Los ciclos se resuelven produciendo una clasificación general única en la que algunas de las opciones están empatadas. [ se necesita aclaración ]
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 e izquierda) hasta la menos popular (abajo y derecha). Este diseño de matriz no incluye los conteos por pares de igual preferencia que aparecen en la tabla de conteo: [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, con un fondo verde). Ninguna otra clasificación posible puede tener una matriz resumen que produzca una suma mayor de números en la mitad triangular superior derecha. (Si así fuera, 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 (que se muestra aquí con un fondo rojo) es mínima. Los artículos académicos de John Kemeny y Peyton Young [2] [3] se refieren a encontrar esta suma mínima, que se llama puntuación 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 elecciones sobre la ubicación de su capital . La población se concentra en cuatro ciudades principales. 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 correspondientes recuentos de comparación por pares :
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 primero, Nashville segundo, Chattanooga tercero y Knoxville cuarto es igual (el número sin unidades) 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 solo 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 desde el más popular (arriba a la izquierda) hasta el menos popular (abajo y 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 se encuentran en la mitad triangular superior derecha de la matriz (con un fondo verde).
En todos los casos que no dan como resultado un empate exacto, el método Kemeny-Young identifica una opción más popular, la segunda opción más popular, etc.
Un empate puede ocurrir en cualquier nivel de preferencia. Excepto en algunos casos en los que intervienen ambigüedades circulares , el método Kemeny-Young sólo 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, cumplen estos criterios:
El método Kemeny-Young también satisface estos criterios:
Al igual que todos los métodos de Condorcet, el método Kemeny-Young no cumple con 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):
Se desconoce un algoritmo para calcular una clasificación de Kemeny-Young en el polinomio temporal del número de candidatos, y es poco probable que exista ya que el problema es NP-difícil [5] incluso si solo hay 4 votantes (pares) [6] [7 ] o 7 votantes (impar). [8]
Se ha informado [9] que los métodos de cálculo basados en programación de números enteros permitían a veces calcular clasificaciones completas de votos de hasta 40 candidatos en segundos. Sin embargo, ciertas elecciones Kemeny de 40 candidatos y 5 votantes generadas al azar no se pudieron resolver en una computadora Pentium de 3 GHz en un tiempo útil determinado en 2006. [9]
El método Kemeny-Young puede formularse como un ejemplo de un problema más abstracto, el de encontrar conjuntos de arcos de retroalimentación ponderados en gráficos de torneos . [10] Como tal, se pueden aplicar a este problema muchos métodos para el cálculo de conjuntos de arcos de retroalimentación, incluida una variante del algoritmo Held-Karp que puede calcular la clasificación Kemeny-Young de candidatos en el 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 de Kemeny-Young, [13] y también existe un algoritmo de tiempo subexponencial parametrizado con tiempo de ejecución O * (2 O( √ OPT ) ) para calcular tal 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, demostrando que es el único método neutral que satisface la consistencia y el llamado criterio cuasi-Condorcet. [3] También se puede caracterizar mediante la consistencia y una propiedad de monotonicidad. [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 que los votantes reciben señales ruidosas de este orden de preferencia verdadero (cf. teorema del jurado de Condorcet ). Utilizando un modelo probabilístico simple para estas señales ruidosas, Young demostró que el método Kemeny-Young era el estimador de máxima verosimilitud del orden de preferencia verdadero. Young sostiene además que el propio Condorcet era consciente de la regla 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, las puntuaciones de Kemeny utilizan recuentos de cuántos votantes se oponen, en lugar de apoyar, a cada preferencia por pares, [2] [3] pero la puntuación más pequeña identifica la misma clasificación general.
Desde 1991, Richard Fobes promueve el método con el nombre de "Ranking de popularidad VoteFair". [19]
La siguiente tabla compara el método Kemeny-Young con otros métodos electorales de un solo ganador:
