Conjunto Smith

El conjunto de Schwartz es equivalente al conjunto de Smith, con la excepción de que ignora los empates. Formalmente, el conjunto de Schwartz es aquel en el que cualquier candidato dentro del conjunto tiene una ruta de victorias directa hacia cualquier candidato que lo derrote.

El conjunto de Smith se puede construir a partir del conjunto de Schwartz añadiendo repetidamente dos tipos de candidatos hasta que no existan más candidatos de ese tipo fuera del conjunto:

• candidatos que están empatados por pares con candidatos en el conjunto,
• candidatos que derrotan a un candidato en el conjunto.

Tenga en cuenta que los candidatos del segundo tipo solo pueden existir después de que se hayan agregado los candidatos del primer tipo.

Teorema: Los conjuntos dominantes están anidados ; es decir, de cualesquiera dos conjuntos dominantes en una elección, uno es un subconjunto del otro.

Demostración: Supongamos, por el contrario, que existen dos conjuntos dominantes, D y E , ninguno de los cuales es subconjunto del otro. Entonces deben existir candidatos d ∈ D y e ∈ E tales que d ∉ E y e ∉ D. Pero por hipótesis , d derrota a todo candidato que no pertenece a D (incluido e ), mientras que e derrota a todo candidato que no pertenece a E (incluido d ), lo cual es una contradicción. ∎

Corolario: De ello se deduce que el conjunto de Smith es el conjunto dominante no vacío más pequeño y que está bien definido.

Teorema: Si D es un conjunto dominante, entonces existe un umbral θ _D tal que los elementos de D son precisamente los candidatos cuyas puntuaciones de Copeland son al menos θ _D . (La puntuación de Copeland de un candidato es el número de otros candidatos a los que derrota más la mitad del número de otros candidatos con los que empata).

Demostración: Elija d como un elemento de D con la puntuación mínima de Copeland e identifique esta puntuación con θ _D. Ahora suponga que algún candidato e ∉ D tiene una puntuación de Copeland no menor que θ _D. Entonces, como d pertenece a D y e no, se deduce que d vence a e ; y para que la puntuación de Copeland de e sea al menos igual a la de d , debe haber algún tercer candidato f contra quien e obtenga una mejor puntuación que d . Si f ∈ D , entonces tenemos un elemento de D que no vence a e , y si f ∉ D, entonces tenemos un candidato fuera de D al que d no vence, lo que lleva a una contradicción en ambos casos. ∎

Cualquier método de elección que cumpla con el criterio de Smith también cumple con el criterio del ganador de Condorcet , ya que si hay un ganador de Condorcet, entonces es el único candidato en el conjunto de Smith. Los métodos de Smith también cumplen con el criterio del perdedor de Condorcet , porque un perdedor de Condorcet nunca estará en el conjunto de Smith. También implica el criterio de mayoría mutua , ya que el conjunto de Smith es un subconjunto del conjunto MMC. ^{[ 2 ]} Por el contrario, cualquier método que no cumpla con alguno de esos tres criterios mayoritarios (mayoría mutua, perdedor de Condorcet o ganador de Condorcet) tampoco cumplirá con el criterio de Smith.

El criterio de Smith se cumple con los métodos de pares ordenados , Schulze , Nanson y otros. Además, cualquier método de votación puede modificarse para satisfacer el criterio de Smith, encontrando el conjunto de Smith y eliminando a los candidatos que no pertenecen a él.

Por ejemplo, el método de votación Smith//Minimax aplica Minimax a los candidatos del conjunto Smith. Otro ejemplo es el método alternativo Tideman , que alterna entre eliminar candidatos fuera del conjunto Smith y eliminar al candidato que obtuvo la mayoría simple (similar a la segunda vuelta instantánea ), hasta encontrar un ganador Condorcet. Un enfoque diferente consiste en elegir al miembro del conjunto Smith que se encuentre en la posición más alta en el orden de finalización del método de votación.

Los métodos que no cumplen el criterio de Condorcet tampoco cumplen el criterio de Smith. Sin embargo, algunos métodos de Condorcet (como Minimax ) pueden no cumplir el criterio de Smith.

El algoritmo se puede presentar en detalle mediante un ejemplo. Supongamos que la matriz de resultados es la siguiente:

En la tabla principal , un valor es 1 si el primer candidato fue preferido al segundo por más votantes que el segundo; 0 si ocurre lo contrario; y 1/2 si hay empate . La última columna muestra la puntuación Copeland del primer candidato.

El algoritmo para calcular el conjunto de Smith es aglomerativo: comienza con el conjunto de Copeland, que está garantizado que es un subconjunto de este, pero que a menudo será más pequeño, y agrega elementos hasta que no se necesiten más. El primer paso es ordenar los candidatos según su puntuación:

Observamos la puntuación más alta (5) y consideramos a los candidatos (ganadores de Copeland) cuya puntuación sea al menos igual a esta, es decir, {A, D}. Estos pertenecen sin duda al conjunto de Smith, y cualquier candidato al que no derroten deberá añadirse. Para encontrar candidatos invictos, observamos las celdas de la tabla debajo del cuadrado superior izquierdo de 2×2 que contiene {A, D} (este cuadrado se muestra con un borde discontinuo): las celdas en cuestión están sombreadas en amarillo en la tabla. Necesitamos encontrar la entrada distinta de cero (posicionalmente) más baja entre estas celdas, que es la celda en la fila G. Todos los candidatos hasta esta fila, y cualquier fila inferior con la misma puntuación, deben añadirse al conjunto, que se expande a {A, D, G}.

Ahora analizamos las nuevas celdas que debemos considerar, es decir, las que se encuentran debajo del cuadrado superior izquierdo que contiene {A, D, G}, excluyendo las de las dos primeras columnas que ya hemos analizado. Las celdas que requieren atención están sombreadas en azul claro. Como antes, localizamos la entrada distinta de cero con la posición más baja entre las nuevas celdas, y añadimos todas las filas hasta ella, así como todas las filas con la misma puntuación, al conjunto ampliado, que ahora comprende {A, D, G, C}.

Repetimos la operación para las nuevas celdas que se encuentran debajo de los cuatro miembros que se sabe que pertenecen al conjunto de Smith. Estas están sombreadas en rosa y nos permiten encontrar cualquier candidato que no sea derrotado por ninguno de {A, D, G, C}. Nuevamente, solo hay uno, F, al que agregamos al conjunto.

Las celdas que se consideran están sombreadas en verde pálido, y como todas sus entradas son cero, no necesitamos agregar ningún candidato nuevo al conjunto, que por lo tanto queda fijo como {A, D, G, C, F}. Y al observar que todas las entradas en el recuadro negro son cero, tenemos la confirmación de que todos los candidatos que están por encima de él descartan a todos los candidatos que están dentro.

La siguiente función en C ilustra el algoritmo devolviendo la cardinalidad del conjunto de Smith para una matriz de resultados duplicada r y un arreglo s de puntuaciones de Copeland duplicadas. Hay n candidatos; r _{i  j} es 2 si más votantes prefieren i a j que j a i , 1 si los números son iguales y 0 si más votantes prefieren j a i que i a j  ; s _i es la suma sobre j de los r _{i  j}  . Se supone que los candidatos están ordenados en orden descendente de puntuación de Copeland.

int smithset ( int ** r , int * s , int n ) { int row , col , lhs , rhs ; for ( rhs = 1 , lhs = 0 ; lhs < rhs ; lhs = rhs , rhs = row + 1 ) { for (; rhs < n && s [ rhs ] == s [ rhs - 1 ]; rhs ++ ); /* esta línea es opcional */ for ( col = rhs , row = n ; col == rhs && row >= rhs ; row -- ) for ( col = lhs ; col < rhs && r [ row - 1 ][ col ] == 0 ; col ++ ); } return lhs ; }