El conjunto de Smith o Schwartz , [nota 1] a veces llamado ciclo superior , es un concepto de la teoría de los sistemas electorales que generaliza al ganador de Condorcet a los casos en los que tal ganador no existe . Lo hace permitiendo que ciclos de candidatos sean tratados de forma conjunta, como si fueran un único ganador del Condorcet.
El conjunto de Smith, que lleva el nombre de John H. Smith , es el conjunto más pequeño no vacío de candidatos en una elección particular, de modo que cada miembro derrota a todos los candidatos fuera del conjunto en una elección por pares. El conjunto de Smith proporciona un estándar de elección óptima para el resultado de una elección. Los sistemas de votación que siempre eligen a un candidato del conjunto de Smith pasan el criterio de Smith .
El conjunto de Smith se define formalmente como el conjunto más pequeño tal que cada candidato dentro del conjunto S está invicto por pares ante cada candidato fuera de S.
Alternativamente, se puede definir como el conjunto de todos los candidatos con un beatpath (no estricto) hacia cualquier candidato que los derrote.
Un conjunto de candidatos, cada uno de cuyos miembros derrota por pares a todos los candidatos fuera del conjunto, se conoce como conjunto dominante . Por tanto, el conjunto de Smith también se denomina conjunto dominante más pequeño .
El conjunto de Schwartz es equivalente al conjunto de Smith, excepto que ignora los votos empatados. Formalmente, el conjunto de Schwartz es el conjunto tal que cualquier candidato dentro del conjunto tiene un camino de paso estricto hacia cualquier candidato que lo derrote.
El conjunto de Smith se puede construir a partir del conjunto de Schwartz agregando repetidamente dos tipos de candidatos hasta que no existan más candidatos fuera del 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 dos conjuntos dominantes cualesquiera en una elección, uno es un subconjunto del otro.
Prueba: 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 , e ∈ E tales que d ∉ E y e ∉ D . Pero por hipótesis, d derrota a todos los candidatos que no están en D (incluido e ), mientras que e derrota a todos los candidatos que no están en 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 cuyaspuntuaciones de Copeland son al menos θ D. (La puntuación 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 está empatado).
Prueba: elija d como elemento de D con unapuntuación de Copeland mínima e identifique esta puntuación con θ D. Ahora supongamos que algún candidato e ∉ D tiene una puntuación de Copeland no menor que θ D . Entonces, dado que d pertenece a D y e no, se deduce que d derrota a e ; y para que la puntuación Copeland de e sea al menos igual a la de d , debe haber un tercer candidato f contra quien e obtenga una puntuación mejor que d . Si f ∈ D , entonces tenemos un elemento de D que no derrota a e , y si f ∉ D entonces tenemos un candidato fuera de D a quien d no derrota, lo que lleva a una contradicción en cualquier caso. ∎
El criterio de Smith se cumple mediante cualquier método de votación en el que el ganador siempre pertenece al conjunto de Smith. Cualquier método que satisfaga el criterio de Smith debe satisfacer también el criterio de Condorcet ; por lo tanto, cualquier método (como el IRV ) que no sea compatible con Condorcet tampoco debe cumplir el criterio de Smith. Minimax es el método de Condorcet más conocido que no cumple el criterio de Smith; Este fracaso llevó al desarrollo de las parejas clasificadas y el método Schulze , dos métodos que son muy similares al Minimax al elegir entre el conjunto de Smith.
El conjunto de Smith contiene al conjunto de Copeland como subconjunto.
También contiene el conjunto de Bancos y el conjunto Bipartidista .
Las propiedades lógicas de los conjuntos dominantes indicadas anteriormente se pueden utilizar para construir un algoritmo eficiente para calcular el conjunto de Smith. Hemos visto que los conjuntos dominantes están anidados por la puntuación de Copeland. De ello se deduce que ajustando el umbral de Copeland es posible trabajar a través de los conjuntos anidados en orden creciente de tamaño hasta alcanzar un conjunto dominante; y este conjunto es necesariamente el conjunto de Smith. Darlington esboza este método. [2]
Probar si un conjunto es dominante en cada etapa podría repetir algunos cálculos, pero esto puede evitarse con bastante facilidad y conducir a un algoritmo cuyo factor de trabajo sea cuadrático en el número de candidatos.
El algoritmo se puede presentar en detalle mediante un ejemplo. Supongamos que la matriz de resultados es la siguiente:
Aquí una entrada en la tabla principal es 1 si el primer candidato fue preferido al segundo por más votantes que los que prefirieron el segundo al primero; 0 si se cumple la relación opuesta; y1/2si hay empate. La última columna da la puntuación Copeland del primer candidato.
El algoritmo para calcular el conjunto de Smith es aglomerativo: comienza con el conjunto de Copeland, que se garantiza que es un subconjunto del mismo pero que a menudo será más pequeño, y agrega elementos hasta que no se necesitan más. El primer paso es ordenar a 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 es al menos tan alta, es decir, {A,D}. Estos ciertamente pertenecen al conjunto de Smith, y cualquier candidato a quien no derroten deberá ser agregado. Para encontrar candidatos invictos, miramos las celdas de la tabla debajo del cuadrado de 2 × 2 superior izquierdo que contiene {A,D} (este cuadrado se muestra con un borde roto): las celdas en cuestión están sombreadas en amarillo en la tabla. Necesitamos encontrar la entrada más baja (posicionalmente) distinta de cero 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 agregarse al conjunto, que se expande a {A,D,G}.
Ahora observamos las celdas nuevas que deben considerarse, que son las que se encuentran debajo del cuadrado superior izquierdo que contiene {A,D,G}, pero excluyendo aquellas en las dos primeras columnas que ya hemos contabilizado. Las celdas que necesitan atención están sombreadas en azul pálido. Como antes, ubicamos la entrada posicionalmente más baja distinta de cero entre las nuevas celdas, sumando todas las filas hasta ella, y todas las filas con la misma puntuación, al conjunto expandido, que ahora comprende {A,D,G,C} .
Repetimos la operación para las nuevas celdas debajo de los cuatro miembros que se sabe que pertenecen al conjunto de Smith. Estos están sombreados en rosa y nos permiten encontrar candidatos que no hayan sido derrotados por ninguno de {A,D,G,C}. De nuevo hay sólo uno, F, a quien añadimos al conjunto.
Las celdas que entran en consideración están sombreadas en verde pálido y, dado que todas sus entradas son cero, no necesitamos agregar ningún candidato nuevo al conjunto, que por lo tanto se fija como {A,D,G,C,F}. Y al notar que todas las entradas en el cuadro negro son cero, tenemos la confirmación de que todos los candidatos que están encima derrotan a todos los candidatos dentro de él.
La siguiente función de C ilustra el algoritmo al devolver la cardinalidad del conjunto de Smith para una matriz de resultados duplicados r dada y una matriz 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 r i j . Se supone que los candidatos están ordenados en orden decreciente según la puntuación de Copeland.
int smithset ( int ** r , int * s , int n ) { int fila , columna , izquierda , derecha ; for ( der = 1 , izquierdo = 0 ; izquierdo < derecho ; izquierdo = derecho , derecho = fila + 1 ) { para (; derecho < n && s [ derecho ] == s [ derecho - 1 ]; derecho ++ ); /* esta línea es opcional */ for ( col = rhs , fila = n ; col == rhs && fila >= rhs ; fila -- ) for ( col = lhs ; col < rhs && r [ fila - 1 ][ col ] == 0 ; columna ++ ); } devolver lhs ; }