representación totalmente proporcional

La representación totalmente proporcional (RTP) es una familia de sistemas de votación multiganadores que amplía las ventajas de la representación proporcional (RP) al exigir que la representación se base en todas las preferencias de los votantes, en lugar de solo en su primera opción o en una única preferencia de menor rango. La RTP combina la RP con el requisito de rendición de cuentas : cada votante sabe con exactitud qué candidato electo lo representa, y cada candidato sabe con exactitud 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 de representación proporcional (RP) existentes se basan únicamente en las preferencias de primera elección 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 pertenecer al partido A. Esto ignora el hecho de que los votantes pueden tener preferencias diferentes a su primera opción.

Otra deficiencia de los sistemas de representación proporcional existentes, como los sistemas de listas de partidos , es la falta de rendición de cuentas : ^{[ 3 ]} no existe una conexión directa entre los votantes y los candidatos electos, ya que estos últimos son elegidos a través de su partido. Reglas como el voto único transferible y la regla de aprobación ampliada buscan mitigar este problema al permitir que las personas clasifiquen directamente a los candidatos; sin embargo, aún resulta difícil determinar qué miembro representa a cada votante.

Las normas del FPR pretenden subsanar simultáneamente ambas deficiencias: se basan en las preferencias de los votantes sobre todos los candidatos y crean una conexión explícita entre los candidatos electos 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 CC eligen k representantes y asocian a cada votante con un representante único (es decir, calculan una partición de los votantes entre los representantes). La principal diferencia es la siguiente:

• La regla de Monroe exige que cada miembro esté asociado con exactamente n / k votantes (redondeando hacia arriba o hacia abajo si no es un número entero).
• El reglamento del Comité de Coordinación no contempla tal requisito: cada miembro puede representar a un número diferente de votantes (pero esto debe tenerse en cuenta posteriormente, durante el funcionamiento del comité, por ejemplo, mediante el uso de la representación interactiva o la representación directa en la cámara).

Ambas reglas buscan maximizar una medida global de satisfacción , que se basa en las preferencias individuales. La satisfacción de un votante con un comité determinado se determina mediante una función de puntuación fija. Dos funciones de puntuación comunes son:

• Recuento de Borda : si un votante está representado por su primera preferencia, entonces su satisfacción es m -1; si un votante está representado por su candidato menos preferido, entonces su satisfacción es 0.
• Votos de aprobación : si un votante está representado por un miembro que aprueba, su satisfacción es 1; de lo 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. Basándose en estas funciones de puntuación, ambas reglas tienen varias variantes:

• La regla utilitarista busca encontrar un comité que maximice la suma de los niveles de satisfacción de todos los votantes (por ejemplo, con las papeletas de aprobación: maximizar el número de votantes representados por un candidato que aprueban); una variante alternativa busca minimizar la suma de los niveles de insatisfacción de todos los votantes.
• Las reglas igualitarias buscan encontrar un comité que maximice el nivel mínimo de satisfacción de un votante (por ejemplo, con el método de Borda: encontrar el rango óptimo r tal que todos los votantes tengan un representante que clasifiquen con r o mejor); una variante alternativa busca minimizar el mayor nivel 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 votos 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 en las variantes basadas en la insatisfacción: demuestran la tratabilidad con parámetros fijos para el parámetro "número de candidatos", pero la intratabilidad con parámetros fijos para el "número de ganadores". Estudian las funciones de aprobación, Borda y de puntuación sin restricciones.

Algunos problemas se simplifican para dominios de preferencia restringidos:

• Para preferencias de un solo pico , Betzler, Slinko y Uhlmann ^{[ 3 ]} demuestran que la regla clásica de Monroe sigue siendo NP-difícil, pero existe un algoritmo polinomial para Monroe igualitario. Las variantes CC son ambas polinomiales.
• Para preferencias de cruce simple , Skowron, Yu, Failszewski y Elkind ^{[ 5 ]} demuestran que la regla CC es politemporal, pero Monroe sigue siendo NP-difícil. Para preferencias narcisistas de cruce simple (cada candidato es clasificado primero por al menos un votante), existe un algoritmo eficiente para la regla Monroe igualitaria.

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

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

• Para la satisfacción utilitaria Monroe con puntuación de Borda, una aproximación (0,715-epsilon);
• Para la satisfacción utilitaria Monroe con puntuación posicional arbitraria , una aproximación de 0,63;
• Para la satisfacción utilitaria CC con puntuación de Borda, un PTAS .
• No existe una aproximación de factor constante para las versiones utilitarias 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 realizados con datos reales de agregación de preferencias demuestran que estos algoritmos rápidos, en muchos casos, encuentran soluciones casi perfectas.

Nótese que, una vez elegidos los k representantes, encontrar la representación real (qué votante está representado por qué candidato) se puede hacer en tiempo polinomial utilizando algoritmos de flujo de red . ^{[ 3 ]}

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