El conjunto de Smith o Schwartz , [nota 1] a veces llamado ciclo superior , generaliza la idea de un ganador de Condorcet a los casos en los que no existe tal ganador . Lo hace permitiendo que los ciclos de candidatos sean tratados conjuntamente, como si fueran un único ganador de Condorcet. [1]
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 cumplen el criterio de Smith . Un criterio alternativo, más estricto, lo proporciona el conjunto de Landau .
El conjunto de Smith se define formalmente como el conjunto más pequeño tal que cada candidato dentro del conjunto S es invencible, de dos en dos, para cada candidato fuera de S.
Alternativamente, puede definirse como el conjunto de todos los candidatos con una trayectoria de derrota (no estricta) hacia cualquier candidato que los derrote.
Un conjunto de candidatos en el que cada uno de sus miembros derrota por pares a todos los candidatos que se encuentran fuera del conjunto se denomina conjunto dominante . Por lo tanto, el conjunto de Smith también se denomina el 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 una trayectoria de victoria estricta frente a 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 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 un 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 todo candidato que no esté en D (incluido e ) mientras que e derrota a todo candidato que no esté en E (incluido d ), lo que constituye una contradicción. ∎
Corolario: 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 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).
Demostración: Elijamos d como un elemento de D con puntuación Copeland mínima, e identifiquemos esta puntuación con θ D . Ahora supongamos que algún candidato e ∉ D tiene una puntuación Copeland no menor que θ D . Entonces, como d pertenece a D y e no, se sigue que d derrota a e ; y para que la puntuación Copeland de e sea al menos igual a la de d , debe haber algún tercer candidato f contra el cual e obtenga una mejor puntuación 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 al que d no derrota, lo que lleva a una contradicción en ambos sentidos. ∎
El criterio de Smith es un criterio de sistema de votación que formaliza una idea de la regla de la mayoría más sólida que la de Condorcet . Un sistema de votación satisface el criterio de Smith si siempre elige un candidato del conjunto de Smith.
Un criterio alternativo, más estricto, lo proporciona la definición de toe, que exige el subconjunto más pequeño que cumpla las otras condiciones. El conjunto de Smith no es {B, C} porque B no es el preferido por la mayoría sobre A; el 65 % clasifica a A sobre B. (Etc.)
En este ejemplo, bajo minimax, A y D empatan; bajo Smith//Minimax, A gana.
En el ejemplo anterior, los tres candidatos del conjunto Smith están en un ciclo de mayoría de "piedra/papel/tijera" : A supera a B por una mayoría del 65%, B supera a C por una mayoría del 75% y C supera a A por una mayoría del 60%.
Cualquier método de elección que cumpla con el criterio de Smith también cumple con el criterio de 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 de perdedor de Condorcet , porque un perdedor de Condorcet nunca caerá 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. [3]
El criterio de Smith se satisface mediante los pares clasificados , el método de Schulze , el método de Nanson y varios otros métodos. [ cita requerida ] Además, cualquier método de votación se puede modificar para satisfacer el criterio de Smith, encontrando el conjunto de Smith y eliminando cualquier candidato fuera de él. Por ejemplo, el método de votación Smith//Minimax aplica Minimax a los candidatos en el conjunto de Smith. Otro enfoque es elegir al miembro del conjunto de Smith que esté más alto en el orden de llegada 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 conjunto de Smith contiene el conjunto de Copeland como subconjunto.
También contiene el conjunto Banks y el conjunto Bipartisan .
El conjunto de Smith se puede calcular con el algoritmo de Floyd-Warshall en el tiempo Θ ( n 3 ) o el algoritmo de Kosaraju en el tiempo Θ ( n 2 ).
El algoritmo puede presentarse 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/2 Si hay un empate, la última columna indica 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 de él, pero que a menudo será más pequeño, y va añadiendo 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 es al menos tan alta, es decir {A, D}. Estos pertenecen ciertamente al conjunto de Smith, y cualquier candidato al que no derroten deberá agregarse. Para encontrar candidatos invictos, observamos las celdas en 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 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 tenerse en cuenta, que son las que se encuentran debajo del cuadrado superior izquierdo que contiene {A, D, G}, pero excluyendo las de las dos primeras columnas que ya hemos tenido en cuenta. Las celdas que requieren atención están sombreadas en azul pálido. Como antes, ubicamos la entrada distinta de cero posicionalmente más baja entre las celdas nuevas, agregando todas las filas hasta ella y todas las filas con el mismo puntaje al conjunto expandido, que ahora incluye {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 candidatos que no hayan sido derrotados por ninguno de {A, D, G, C}. Nuevamente, solo hay uno, F, que agregamos al conjunto.
Las celdas que se tienen en cuenta están sombreadas en verde pálido y, dado que todas sus entradas son cero, no necesitamos agregar nuevos candidatos al conjunto, que, por lo tanto, queda fijado 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 derrotan a todos los candidatos que están dentro de él.
La siguiente función C ilustra el algoritmo devolviendo la cardinalidad del conjunto de Smith para una matriz de resultados duplicada dada r 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 prefieren j a i , 1 si los números son iguales y 0 si más votantes prefieren j a i que prefieren 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 de puntuación de Copeland.
int smithset ( int ** r , int * s , intn ) { int fila , columna , izq . , der .; para ( der. = 1 , izq. = 0 ; izq . < der.; izq. = der . , der . = fila + 1 ) { para ( ; der. < n && s [ der . ] == s [ der. - 1 ]; der. ++ ); /* esta línea es opcional */ para ( col = der. , fila = n ; col == der. && fila >= der .; fila -- ) para ( col = izq .; col < der. && r [ fila - 1 ][ col ] == 0 ; col ++ ); } return der .; }