En la ciencia electoral , un método de votación satisface el criterio de sumabilidad si es posible contar los resultados electorales localmente por distrito electoral y luego calcular los resultados sumando todos los votos. Más formalmente, la complejidad de compilación o suma de un sistema de votación mide la dificultad del conteo de votos para distritos electorales individuales y es igual al número más pequeño de bits necesarios para resumir todos los votos. [1] Un método de votación se denomina sumable si el número de bits crece como una función polinómica del número de candidatos.
A menudo, un grupo tiene que aceptar una decisión, pero no todos los votos pueden reunirse en un solo lugar. En tal situación, necesitamos tomar los votos de los votantes presentes y resumirlos de manera que, cuando lleguen los demás votos, podamos determinar el ganador. La complejidad de compilación de una regla de votación es el número más pequeño de bits necesarios para el resumen.
Los métodos no sumables como el voto alternativo (elección por orden de preferencia) pueden terminar siendo prohibitivamente costosos de implementar, lo que a menudo conduce a su rechazo por parte de los votantes ( como en el Reino Unido ) o su derogación (ver RCV en Estados Unidos ).
Una ventaja clave de la baja complejidad de la compilación es que facilita la verificación de los resultados de la votación. La baja complejidad de compilación nos permite resumir el resultado en cada mesa de votación por separado, lo cual es fácil de verificar haciendo que los representantes de cada partido cuenten las papeletas en cada mesa de votación. Luego, cualquier votante puede verificar el resultado final sumando los resultados de las 1.000 mesas de votación. Esta verificabilidad es importante para que el público confíe y acepte los resultados. [1] La información publicada públicamente de cada distrito electoral puede ser utilizada por auditores electorales independientes para identificar cualquier evidencia de fraude electoral con técnicas estadísticas.
La complejidad de la compilación también es algorítmicamente útil para calcular el ganador de inducción hacia atrás en los juegos de votación de Stackelberg . [2] [ se necesita aclaración ]
Sea r una regla de votación : una función que toma como entrada una lista de n papeletas clasificadas , que representan las preferencias de n votantes, y devuelve un resultado. Hay algunos k < n votantes cuyos votos se conocen . Una función de compilación es una función f que toma como entrada una lista de k boletas clasificadas y devuelve una salida tal que, dado cualquier número u := n - k de boletas clasificadas adicionales, la salida de r en todo el conjunto de boletas puede ser calculado exactamente.
La complejidad de compilación de una regla r es el número de bits en el peor de los casos en la salida de la función de compilación más eficiente f . [1] Este número suele ser una función de n (el número de votantes), k (el número de votos conocidos) yc ( el número de candidatos). Sin embargo, nos centramos únicamente en c por simplicidad, ya que normalmente nos interesa el caso con un número muy grande de votos desconocidos.
El número de votos posibles para cualquier regla de votación clasificada es , lo que proporciona un límite superior a la complejidad. Sin embargo, la mayoría de las reglas tienen una complejidad de compilación mucho menor. [1]
En sistemas de votación posicional como pluralidad o Borda , cualquier conjunto de votos se puede resumir registrando la puntuación total de cada candidato (por ejemplo, el número de veces que un candidato aparece primero en pluralidad ). Luego se puede encontrar el ganador sumando las puntuaciones en cada recinto, dando un límite de . Un argumento similar se aplica a la votación por puntuación y a la votación por aprobación . [1]
El gráfico de mayoría ponderada de un perfil de votante es un gráfico dirigido en el que los nodos son los candidatos, y hay un borde dirigido de x a y si una mayoría de votantes prefiere x a y . El peso de esta ventaja es el número de votantes que prefieren xay . Muchas reglas se basan únicamente en el gráfico mayoritario; el número de clases de equivalencia de tales reglas es como máximo el número de gráficos de mayoría ponderada posibles. Este número se denota por T( k , c ): el número de torneos ponderados en c vértices que se pueden obtener de k votantes. Por lo tanto, la complejidad de la compilación es como máximo log(T( k , c )). Un límite superior de log(T( k , c )) es , ya que es suficiente mantener, para cada par de candidatos x,y, el número de votantes que prefieren xey, y este número está entre 0 y k . [1] [2]
La complejidad de la compilación de la votación en dos vueltas (el voto contingente ) está en . Tenga en cuenta que esto es mayor que la complejidad de compilación de la votación de Borda, aunque la complejidad de comunicación de la votación de dos rondas es menor que la de la votación de Borda. [3]
La complejidad de compilación del voto único transferible está en , lo que lo hace no sumable. [1]
La votación STAR también está de moda . [4]
Para la votación de Bucklin, la complejidad de la compilación es . [2] Para las reglas de votación de mediana más alta estrechamente relacionadas , la complejidad de una boleta que incluye posibles calificaciones es .
Karia y Lang estudian la complejidad de la compilación de varias reglas de votación con múltiples ganadores , ya sea con boletas clasificadas o con boletas de aprobación . Por ejemplo:
