Representación totalmente proporcional

La representación totalmente proporcional (RPP) es una propiedad de los sistemas de votación con múltiples ganadores . Amplía la propiedad de la representación proporcional (RP) al exigir que la representación se base en todas las preferencias de los votantes, en lugar de en su primera opción. Además, el requisito combina la RP con el requisito de rendición de cuentas : cada votante sabe exactamente qué candidato electo lo representa, y cada candidato sabe exactamente a qué votantes representa.

El término fue acuñado en 1995 por Burt L. Monroe, ^[1] pero una idea similar apareció ya en 1983 en un artículo de John R. Chamberlin y Paul N. Courant . ^[2] Las dos reglas de votación que se sabe que satisfacen esta propiedad se conocen, respectivamente, como la regla de votación de Monroe y la regla de votación de Chamberlin-Courant (CC) .

La mayoría de los sistemas electorales existentes de representación proporcional (RP) se basan únicamente en las primeras preferencias de los votantes, por ejemplo: si el 40% vota por el partido A como su primera opción, entonces el 40% de los miembros del parlamento deberían ser del partido A. Esto ignora el hecho de que los votantes pueden tener diferentes preferencias por debajo de su primera opción.

Otra deficiencia de los sistemas existentes de representación proporcional, por ejemplo, los sistemas de listas de partidos , es la falta de rendición de cuentas : ^[3] no hay una conexión directa entre los votantes y los candidatos elegidos, ya que los candidatos son elegidos a través de su partido. Reglas como el voto único transferible y la regla de aprobación ampliada tienen como objetivo mitigar este problema al permitir que las personas clasifiquen a los candidatos directamente; sin embargo, todavía es difícil decir qué candidato representa exactamente a qué votante.

Las reglas del FPR apuntan a corregir simultáneamente ambas deficiencias: se basan en las preferencias de los votantes entre todos los candidatos y crean una conexión explícita entre los candidatos elegidos y los votantes: cada votante conoce a sus representantes y cada representante sabe a qué votantes representa.

Sea k el número requerido de representantes (miembros del comité), m el número de candidatos y n el número de votantes. Cada votante presenta una clasificación de los candidatos. Tanto la regla de Monroe como la regla de CC eligen k representantes y asocian a cada votante a un representante único (en otras palabras, calculan una partición de los votantes entre los representantes). La principal diferencia es la siguiente:

• La regla de Monroe requiere que cada candidato esté asociado con exactamente n / k votantes (redondeado hacia arriba o hacia abajo si no es un número entero).
• La regla del CC no tiene tal requisito: cada candidato puede representar un número diferente de votantes (pero esto debe tenerse en cuenta más adelante, durante el funcionamiento del comité, por ejemplo, aplicando la votación ponderada ).

Ambas reglas tienen como objetivo maximizar una medida global de satisfacción , que se basa en las preferencias individuales. La satisfacción de un votante de un comité determinado está determinada por una función de puntuación fija. Dos funciones de puntuación comunes son:

• Recuento de Borda : si un votante está representado por su mejor candidato, entonces su satisfacción es m -1; si un votante está representado por su peor candidato, entonces su satisfacción es 0.
• Votaciones de aprobación : si un elector está representado por un candidato que aprueba, entonces su satisfacción es 1; en caso contrario, su satisfacción es 0.

Las variantes alternativas de estas reglas utilizan una función de insatisfacción en lugar de una función de satisfacción. En función de estas funciones de puntuación, ambas reglas tienen varias variantes:

• La regla utilitarista tiene como objetivo encontrar un comité que maximice la suma de los niveles de satisfacción de todos los votantes (por ejemplo, con papeletas de aprobación: maximizar el número de votantes representados por un candidato que aprueban); una variante alternativa tiene como objetivo minimizar la suma de los niveles de insatisfacción de todos los votantes.
• Las reglas igualitarias tienen como objetivo encontrar un comité que maximice el nivel más pequeño de satisfacción de un votante (por ejemplo, con el recuento de Borda: encontrar el rango óptimo r tal que todos los votantes tengan un representante que ocupe un rango r o mejor); una variante alternativa tiene como objetivo minimizar el mayor de los niveles de insatisfacción de todos los votantes.

Procaccia, Rosenschein y Zohar ^[4] demostraron que determinar el ganador de la regla de votación de Monroe es NP-difícil, incluso con boletas de aprobación . Sin embargo, cuando el número de ganadores ( k ) es constante, el problema se puede resolver en tiempo polinomial.

Betzler, Slinko y Uhlmann ^[3] investigan la complejidad parametrizada de la determinación del ganador de las variantes basadas en la insatisfacción: demuestran la manejabilidad de parámetros fijos para el parámetro "número de candidatos", pero la intratabilidad de parámetros fijos para el parámetro "número de ganadores". Estudian la aprobación, Borda y las funciones de puntuación sin restricciones.

Algunos problemas se vuelven más fáciles para los dominios de preferencia restringida:

• Para preferencias de un solo pico , Betzler, Slinko y Uhlmann ^[3] demuestran que la regla clásica de Monroe sigue siendo NP-hard, pero existe un algoritmo polinómico para Monroe igualitario. Las variantes CC son ambas polinómicas.
• Para las preferencias de cruce simple , Skowron, Yu, Failszewski y Elkind ^[5] prueban que la regla CC es politemporal, pero Monroe sigue siendo NP-hard. Para las preferencias narcisistas de cruce simple (cada candidato ocupa el primer lugar por al menos un votante), existe un algoritmo eficiente para la regla igualitaria de Monroe.

Lu y Boutilier ^{[6] presentaron un} algoritmo voraz de aproximación de factor politemporal de 0,63 para la satisfacción óptima de la regla CC.

Skowron, Faliszewski y Slinko ^[7] proporcionan algoritmos de aproximación y resultados de inaproximabilidad :

• Para satisfacción utilitaria Monroe con puntuación de Borda, una aproximación (0,715-épsilon);
• Para la satisfacción utilitaria de Monroe con puntuación posicional arbitraria , una aproximación de 0,63;
• Para satisfacción utilitaria CC con puntuación Borda, un PTAS .
• No existe una aproximación de factores constantes para las versiones utilitaristas e igualitarias basadas en la insatisfacción de Monroe y CC, ni para las versiones igualitarias basadas en la satisfacción.

Los algoritmos de aproximación son aplicables incluso con papeletas truncadas. Los experimentos con datos de agregación de preferencias de la vida real muestran que estos algoritmos rápidos encuentran en muchos casos soluciones casi perfectas.

Obsérvese que, una vez elegidos los k representantes, la búsqueda de la representación real (qué votante está representado por qué candidato) se puede realizar en politiempo utilizando algoritmos de flujo de red . ^[3]

Lu y Boutilier ^[6] generalizaron la regla CC a la elección social presupuestada .