Criterio de sumabilidad

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 recuento de votos para distritos electorales individuales y es igual al menor número 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 es posible reunir todos los votos en un único 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 la menor cantidad de bits necesarios para el resumen.

Una ventaja clave de la baja complejidad de la compilación es que facilita la verificación de los resultados de las votaciones. La baja complejidad de la compilación nos permite resumir el resultado en cada mesa de votación por separado, lo que 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 1000 mesas de votación. Esta verificabilidad es importante para que el público confíe en los resultados y los acepte. ^[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 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] [ aclaración necesaria ]}

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 son conocidos . Una función de compilación es una función f que toma como entrada una lista de k papeletas clasificadas y devuelve algún resultado tal que, dado cualquier número u  := n - k de papeletas clasificadas adicionales, el resultado de r en todo el conjunto de papeletas se puede calcular con exactitud.

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 es típicamente una función de n (el número de votantes), k (el número de votos conocidos) y c (el número de candidatos). Sin embargo, nos centramos solo en c para simplificar, ya que generalmente nos interesa el caso con un número muy grande de votos desconocidos.

El número de votaciones posibles para cualquier regla de votación por orden de preferencia es , lo que proporciona un límite superior para la complejidad. Sin embargo, la mayoría de las reglas tienen una complejidad de compilación mucho menor. ^[1]${\displaystyle \Theta (c!)}$

En sistemas de votación posicional como el de pluralidad o el de 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 el sistema de pluralidad ). Luego, se puede encontrar al ganador sumando las puntuaciones en cada distrito electoral, lo que da un límite de . Un argumento similar se aplica a la votación por puntuación y la votación de aprobación . ^[1]${\displaystyle \Theta (c)}$

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 una arista dirigida de x a y si y solo si una mayoría de votantes prefiere x a y . El peso de esta arista es el número de votantes que prefieren x a y . Muchas reglas se basan solo en el gráfico de mayoría; 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 compilación es como máximo log(T( k , c )). Un límite superior en log(T( k , c )) es , ya que es suficiente mantener, para cada par de candidatos x,y, el número de votantes que prefieren x a y, y este número está entre 0 y k . ^{[1] [2]}${\displaystyle {\frac {c(c-1)}{2}}}$

La complejidad de compilación de la votación en dos rondas (el voto contingente ) es de . Nótese 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 en dos rondas es menor que la de la votación de Borda. ^[3]${\displaystyle \Theta (c^{2})}$

La complejidad de compilación del voto único transferible es de , lo que lo hace no sumable. ^[1]${\displaystyle \Theta \left(2^{c}c\right)}$

La votación STAR también está disponible . ^[4]${\displaystyle \Theta (c^{2})}$

Para la votación de Bucklin, la complejidad de compilación es . ^{[2] Para las} reglas de votación de mediana más alta estrechamente relacionadas , la complejidad de una votación que incluye posibles calificaciones es . ${\displaystyle \Theta (c^{2})}$${\displaystyle k}$${\displaystyle \Theta (ck)}$

Karia y Lang estudian la complejidad de compilación de varias reglas de votación con múltiples ganadores , ya sea con papeletas de votación por orden de preferencia o con papeletas de votación por aprobación . Por ejemplo:

• En el caso del voto único intransferible , la complejidad está en .${\displaystyle \Theta (c)}$
• Para Borda, la complejidad está en . ^[5]${\displaystyle \Theta (c\log {kc})}$

• Recopilación de conocimiento : compilar una parte de la información de entrada fuera de línea, de modo que cuando llegue la información en línea, la salida se pueda calcular rápidamente. En este caso, el objetivo de la compilación es ahorrar tiempo , en lugar de ahorrar espacio .
• Complejidad de la terminación de la elicitación: dada una regla de votación, un conjunto de votos conocidos y un conjunto de nuevos votantes, ¿el resultado de la votación ya está determinado a partir de los votos conocidos? Claramente, si el resultado ya está determinado, la complejidad de compilación es pequeña, ya que solo tenemos que conservar este resultado.
• Cálculo de los ganadores posibles y necesarios: dada una regla de votación, un conjunto de votos incompletos ( órdenes parciales sobre el conjunto de candidatos), ¿quiénes son los candidatos que todavía pueden ganar la elección, y hay algún candidato que la gane con seguridad? Claramente, si hay un ganador seguro, entonces la complejidad de compilación es muy pequeña: solo tenemos que mantener la identidad de este ganador seguro.
• Complejidad de la comunicación : dada una regla de votación y un conjunto de votantes, ¿cuál es el número mínimo de bits que se deben transferir entre los votantes y el centro para calcular el resultado de la elección? Conitzer y Sandholm estudian la complejidad de la comunicación de algunas reglas de votación comunes. ^[3] La complejidad de compilación puede verse como una complejidad de comunicación de una sola ronda. ^[1]

• Sistema de votación
• Complejidad espacial