Votación de aprobación proporcional

Sistema electoral con múltiples ganadores

El voto de aprobación proporcional ( PAV ) es un sistema electoral proporcional para elecciones con múltiples ganadores . Es un método de aprobación de múltiples ganadores que extiende el método de promedios más altos de distribución comúnmente utilizado para calcular las distribuciones para la representación proporcional de listas de partidos . ^[1] Sin embargo, el PAV permite a los votantes apoyar solo a los candidatos que aprueban, en lugar de verse obligados a aprobar o rechazar a todos los candidatos en una lista de partido determinada . ^[2]

En el PAV, los votantes emiten boletas de aprobación que marcan a todos los candidatos que aprueban; la boleta de cada votante se considera como si todos los candidatos en la boleta estuvieran en su propia "lista de partido". Los escaños se reparten entre los candidatos de una manera que garantiza que todas las coaliciones estén representadas proporcionalmente.

Historia

El PAV es un caso especial de la regla de votación de Thiele , propuesta por Thorvald N. Thiele . ^{[3] [4]} Se utilizó en combinación con la votación por orden de preferencia en las elecciones suecas de 1909 a 1921 para distribuir escaños dentro de los partidos y en las elecciones locales. ^[4] El PAV fue redescubierto por Forest Simmons en 2001, ^[5] quien le dio el nombre de "votación de aprobación proporcional".

Método

Al igual que su primo cercano, el voto de aprobación por satisfacción , el PAV puede considerarse como la selección de un comité mediante la prueba de todos los comités posibles y la elección del comité con más votos. En el voto de aprobación por satisfacción, el voto de cada votante se divide equitativamente entre todos los candidatos que aprueba, lo que otorga votos a cada uno. Si los votantes son perfectamente estratégicos y solo apoyan a tantos candidatos como su partido tenga derecho a hacerlo, el SAV crea un resultado proporcional. ${\displaystyle r}$ ${\displaystyle 1/r}$

El PAV hace una modificación para eliminar esta necesidad de estrategia: sólo divide la papeleta de un votante después de que haya elegido a un candidato. Como resultado, los votantes pueden aprobar libremente a los candidatos perdedores sin diluir su papeleta. Los votantes aportan un voto entero al primer candidato que apoyan y que resulta elegido; medio voto al segundo candidato; y así sucesivamente.

Por lo tanto, si una votación aprueba a los candidatos que resultan elegidos, esa votación contribuye con el número armónico -ésimo al total de votos de ese comité. En otras palabras: ^{[5] [6]} ${\displaystyle r}$ ${\displaystyle r}$

${\displaystyle \mathrm {H} (r)=1+{\frac {1}{2}}+{\frac {1}{3}}+\cdots +{\frac {1}{r}}}$

La puntuación de un comité determinado se calcula como la suma de las puntuaciones obtenidas de todos los votantes. Luego, elegimos el comité con la puntuación más alta.

Formalmente, supongamos que tenemos un conjunto de candidatos , un conjunto de votantes y un comité de tamaño . Sea el conjunto de candidatos aprobados por los votantes . La puntuación PAV de un comité con tamaño se define como . PAV selecciona el comité con la puntuación máxima. ${\displaystyle C=\{c_{1},c_{2},\ldots ,c_{m}\}}$ ${\displaystyle N=\{1,2,\ldots ,n\}}$ ${\displaystyle k}$ ${\displaystyle A_{i}}$ ${\displaystyle i\in N}$ ${\displaystyle W\subseteq C}$ ${\displaystyle |W|=k}$ ${\displaystyle \textstyle \mathrm {sc} _{\mathrm {PAV} }(W)=\sum _{i=1}^{n}\mathrm {H} (|A_{i}\cap W|)}$ ${\displaystyle W}$

Ejemplo 1

Supongamos que hay 2 escaños por cubrir y que hay cuatro candidatos: Andrea (A), Brad (B), Carter (C) y Delilah (D), y 30 votantes. Las papeletas son:

• 5 votantes votaron por A y B
• 17 electores votaron por A y C
• 8 votantes votaron por D

Hay 6 resultados posibles: AB, AC, AD, BC, BD y CD.

Andrea y Carter son elegidos.

Tenga en cuenta que la Aprobación simple muestra que Andrea tiene 22 votos, Carter tiene 17 votos, Delilah tiene 8 votos y Brad tiene 5 votos. En este caso, la selección de Andrea y Carter por PAV coincide con la secuencia de Aprobación simple. Sin embargo, si los votos anteriores se modifican ligeramente de modo que A y C reciban 16 votos y D reciba 9 votos, entonces Andrea y Delilah son elegidos ya que la puntuación de A y C ahora es 29 mientras que la puntuación de A y D permanece en 30. Además, la secuencia creada mediante el uso de Aprobación simple permanece sin cambios. Esto muestra que PAV puede dar resultados que son incompatibles con el método que simplemente sigue la secuencia implícita en la Aprobación simple.

Ejemplo 2

Supongamos que hay 10 escaños por elegir y hay tres grupos de candidatos: candidatos rojos , azules y verdes . Hay 100 votantes:

• 60 electores votaron por todos los candidatos azules ,
• 30 electores votaron por todos los candidatos rojos ,
• 10 electores votaron por todos los candidatos verdes .

En este caso, el PAV seleccionaría 6 candidatos azules , 3 rojos y 1 verde . La puntuación de dicho comité sería Todos los demás comités reciben una puntuación inferior. Por ejemplo, la puntuación de un comité que consta únicamente de candidatos azules sería $${\displaystyle 60\cdot \mathrm {H} (6)+30\cdot \mathrm {H} (3)+10\cdot \mathrm {H} (1)=60\cdot \left(1+{\tfrac {1}{2}}+\ldots +{\tfrac {1}{6}}\right)+30\cdot \left(1+{\tfrac {1}{2}}+{\tfrac {1}{3}}\right)+10\cdot 1=147+55+10=212{\text{.}}}$$

${\displaystyle 60\cdot \mathrm {H} (10)+30\cdot \mathrm {H} (0)+10\cdot \mathrm {H} (0)=60\cdot \left(1+{\tfrac {1}{2}}+\ldots +{\tfrac {1}{10}}\right)\approx 175.73{\text{.}}}$

En este ejemplo, el resultado del método PAV es proporcional : el número de candidatos seleccionados de cada grupo es proporcional al número de votantes que votan por el grupo. Esto no es una coincidencia: si los candidatos forman grupos disjuntos, como en el ejemplo anterior (los grupos pueden considerarse como partidos políticos), y cada votante vota exclusivamente por todos los candidatos dentro de un solo grupo, entonces el método PAV actuará de la misma manera que el método D'Hondt de representación proporcional por lista de partidos . ^[1]

Propiedades

Esta sección describe las propiedades axiomáticas de la votación de aprobación proporcional.

Comités de tamaño uno

En una elección con un solo ganador, el PAV funciona exactamente de la misma manera que el voto de aprobación , es decir, selecciona el comité integrado por el candidato que obtenga la aprobación de la mayoría de los votantes.

Proporcionalidad

La mayoría de los sistemas de representación proporcional utilizan listas de partidos . El PAV fue diseñado para tener tanto representación proporcional como votos personales (los votantes votan por candidatos, no por una lista de partido). Merece ser llamado un sistema "proporcional" porque si los votos resultan seguir un esquema partidista (cada votante vota por todos los candidatos de un partido y ningún otro), entonces el sistema elige un número de candidatos en cada partido que es proporcional al número de votantes que eligieron a este partido (ver Ejemplo 2). ^[1] Además, bajo supuestos moderados (simetría, continuidad y eficiencia de Pareto ), el PAV es la única extensión del método D'Hondt que permite votos personales y satisface el criterio de consistencia . ^[2]

Incluso si los votantes no siguen el esquema partidista, la regla proporciona garantías de proporcionalidad. Por ejemplo, PAV satisface la propiedad de equidad fuerte llamada representación justificada extendida ^[6] , así como la propiedad relacionada representación justificada proporcional ^[7] . También tiene un grado de proporcionalidad óptimo ^{[8] [9]} Todas estas propiedades garantizan que cualquier grupo de votantes con preferencias cohesivas (similares) estará representado por un número de candidatos que es al menos proporcional al tamaño del grupo. PAV es el único método que satisface tales propiedades entre todos los métodos de optimización similares a PAV (que pueden usar números distintos de los números armónicos en su definición). ^[6]

Los comités devueltos por PAV podrían no estar en el núcleo . ^{[ jerga ] [6] [10]} Sin embargo, garantiza una aproximación de 2 del núcleo, ^{[ jerga ]} que es la relación de aproximación óptima que se puede lograr mediante una regla que satisface el principio de transferencias de Pigou-Dalton . ^[10] Además, PAV satisface la propiedad del núcleo si hay suficientes candidatos similares en una elección. ^[11]

El PAV no cumple con la capacidad de precio (es decir, la elección del PAV no siempre se puede explicar a través de un proceso en el que los votantes están dotados de una cantidad fija de dinero virtual y gastan este dinero en comprar candidatos que les gustan) y no cumple con la proporcionalidad laminar. ^[10] Dos reglas alternativas que satisfacen la capacidad de precio y la proporcionalidad laminar, y que tienen propiedades relacionadas con la proporcionalidad comparativamente buenas a las del PAV son el método de las partes iguales y las reglas secuenciales de Phragmén . ^[12] Estos dos métodos alternativos también son computables en tiempo polinomial , pero no cumplen con la eficiencia de Pareto .

Otras propiedades

Además de las propiedades relativas a la proporcionalidad, PAV satisface los siguientes axiomas:

• Eficiencia de Pareto
• Consistencia
• Monotonía de apoyo (si el apoyo a un candidato ganador aumenta, es decir, más votantes votan por este candidato, entonces este candidato sigue ganando) ^[13]
• Principio de Pigou-Dalton ^[10]

PAV no cumple las siguientes propiedades:

• Monotonía de la casa . ^[12] Dos métodos alternativos que satisfacen la monotonía de la casa y que tienen propiedades relacionadas con la proporcionalidad comparativamente buenas con PAV son la votación de aprobación proporcional secuencial y las reglas secuenciales de Phragmén . ^[12] Estos dos métodos alternativos también son computables en tiempo polinomial , pero fallan en la eficiencia de Pareto , la consistencia y el principio de Pigou-Dalton . ^[12]

Cálculo

Una formulación de programación lineal entera para calcular los comités ganadores según el PAV. La variable indica si el candidato es seleccionado o no. La variable indica si el votante aprueba al menos a los candidatos seleccionados. ^{[12] [14]} ${\displaystyle y_{c}}$ ${\displaystyle c}$ ${\displaystyle x_{i,\ell }}$ ${\displaystyle i}$ ${\displaystyle \ell }$

Las soluciones PAV y su calidad se pueden verificar en tiempo polinomial , ^{[15] [16]} lo que facilita la transparencia. Sin embargo, la complejidad temporal del peor caso es NP-completa , lo que significa que para algunas elecciones puede ser difícil o imposible encontrar una solución exacta que garantice todas las propiedades teóricas de PAV.

En la práctica, el resultado del PAV se puede calcular con exactitud para comités de tamaño mediano (menos de 50 candidatos) utilizando solucionadores de programación entera (como los que se proporcionan en el paquete de Python abcvoting). Encontrar una solución exacta tiene complejidad temporal con k escaños y n votantes. ${\displaystyle O(nm^{k})}$

Desde la perspectiva de la complejidad parametrizada , el problema de calcular PAV es teóricamente difícil fuera de unos pocos casos fáciles excepcionales. ^{[15] [17] [18]} Afortunadamente, estos casos son a menudo buenas aproximaciones de elecciones reales, lo que permite utilizarlos como heurísticas que reducen drásticamente el esfuerzo computacional de encontrar una solución correcta. Por ejemplo, los resultados electorales exactos se pueden resolver en tiempo polinomial en el caso en que los votantes y candidatos se encuentren a lo largo de un espectro político unidimensional, ^[14] y en tiempo lineal cuando los votantes son partidarios fuertes (es decir, votan por listas de partidos en lugar de candidatos).

Aproximaciones deterministas

Los algoritmos de aproximación pueden encontrar soluciones "suficientemente buenas" muy rápidamente en la práctica. La votación de aprobación proporcional secuencial modifica el PAV, utilizando un algoritmo voraz para aproximar el resultado. SPAV tiene una razón de aproximación en el peor de los casos de , por lo que la puntuación PAV del comité resultante es al menos el 63% del óptimo. ^[16] Este método se puede calcular en tiempo polinomial, y el resultado de la elección podría determinarse potencialmente a mano. Un enfoque diferente que incluye el redondeo desaleatorizado (con el método de probabilidades condicionales ) da una razón de aproximación en el peor de los casos de 0,7965; ^[19] bajo los supuestos estándar en la teoría de la complejidad, esta es la mejor razón de aproximación que se puede lograr para PAV en tiempo polinomial. ^[19] El problema de aproximación de PAV también se puede formular como un problema de minimización (en lugar de maximizar queremos minimizar ), en cuyo caso la mejor razón de aproximación conocida es 2,36. ^[20] ${\displaystyle 1-1/e\approx 0.63}$ ${\displaystyle \textstyle \mathrm {sc} _{\mathrm {PAV} }(W)}$ ${\displaystyle \textstyle \sum _{i\in N}\mathrm {H} (k)-\mathrm {sc} _{\mathrm {PAV} }(W)}$

Lectura adicional

• Lackner, Martin; Skowron, Piotr (2023). Votación de múltiples ganadores con preferencias de aprobación . SpringerBriefs in Intelligent Systems. arXiv : 2007.01795 . doi :10.1007/978-3-031-09016-5. ISBN . 978-3-031-09015-8.S2CID244921148  .​
• Piotr Faliszewski, Piotr Skowron, Arkadii Slinko, Nimrod Talmon (26 de octubre de 2017). "Votación de múltiples ganadores: un nuevo desafío para la teoría de la elección social". En Endriss, Ulle (ed.). Tendencias en la elección social computacional . AI Access. ISBN 978-1-326-91209-3.{{cite book}}: CS1 maint: multiple names: authors list (link)

Véase también

• Método de partes iguales
• Método D'Hondt
• Votación aprobatoria proporcional secuencial
• Reglas de votación de Phragmen

Referencias

1. Brill, Markus; Laslier, Jean-François; Skowron, Piotr (2018). "Reglas de aprobación de múltiples ganadores como métodos de distribución". Revista de política teórica . 30 (3): 358–382. arXiv : 1611.08691 . doi :10.1177/0951629818775518. S2CID  10535322.
2. Lackner, Martin; Skowron, Piotr (2021). "Reglas de múltiples ganadores basadas en la aprobación consistente". Revista de teoría económica . 192 : 105173. arXiv : 1704.02453 . doi :10.1016/j.jet.2020.105173. S2CID  232116881.
3. Thiele, Thorvald N. (1895). "Om Flerfoldsvalg". Supervisión de Det Kongelige Danske Videnskabernes Selskabs Forhandlinger : 415–441.
4. Janson, Svante (2016). "Métodos de elección de Phragmén y Thiele". arXiv : 1611.08826 [math.HO].
5. Kilgour, D. Marc (2010). "Votación de aprobación para elecciones con múltiples ganadores". En Jean-François Laslier; M. Remzi Sanver (eds.). Manual sobre votación de aprobación . Saltador. págs. 105-124. ISBN 978-3-642-02839-7.
6. Aziz, Haris; Brill, Markus; Conitzer, Vincent; Elkind, Edith; Freeman, Rupert; Walsh, Toby (2017). "Representación justificada en la votación de comités basada en la aprobación". Elección social y bienestar . 48 (2): 461–485. arXiv : 1407.8269 . doi :10.1007/s00355-016-1019-3. S2CID  8564247.
7. Sánchez-Fernández, Luis; Elkind, Edith; Lackner, Martín; Fernández, Norberto; Fisteo, Jesús; Val, Pablo Basanta; Skowron, Piotr (10 de febrero de 2017). "Representación Proporcional Justificada". Actas de la Conferencia AAAI sobre Inteligencia Artificial . 31 (1). doi : 10.1609/aaai.v31i1.10611 . hdl : 10016/26166 . ISSN  2374-3468. S2CID  17538641.
8. Aziz, Haris; Elkind, Edith; Huang, Shenwei; Lackner, Martin; Sánchez Fernández, Luis; Skowron, Piotr (2018). "Sobre la complejidad de la representación justificada extendida y proporcional". Actas de la Conferencia AAAI sobre Inteligencia Artificial . 32 (1): 902–909. doi : 10.1609/aaai.v32i1.11478 . S2CID  19124729.
9. Skowron, Piotr (2021). "Grado de proporcionalidad de las reglas de múltiples ganadores". Actas de la 22.ª Conferencia de la ACM sobre economía y computación . EC-21. págs. 820–840. arXiv : 1810.08799 . doi :10.1145/3465456.3467641. ISBN. 9781450385541. Número de identificación del sujeto  53046800.
10. Peters, Dominik; Skowron, Piotr (2020). "Proporcionalidad y los límites del bienestarismo". Actas de la 21.ª Conferencia de la ACM sobre economía y computación . EC'20. págs. 793–794. arXiv : 1911.11747 . doi :10.1145/3391403.3399465. ISBN. 9781450379755.S2CID208291203  .​
11. Brill, Markus; Gölz, Paul; Peters, Dominik; Schmidt-Kraepelin, Ulrike; Wilker, Kai (2019). "Asignación basada en la aprobación". Actas de la Conferencia AAAI sobre Inteligencia Artificial . 34 (2): 1854–1861. arXiv : 1911.08365 . doi :10.1609/aaai.v34i02.5553. S2CID  208158445.
12. Lackner, Martin; Skowron, Piotr (2023). Votación de múltiples ganadores con preferencias de aprobación . SpringerBriefs in Intelligent Systems. arXiv : 2007.01795 . doi :10.1007/978-3-031-09016-5. ISBN . 978-3-031-09015-8.S2CID244921148  .​
13. Sánchez Fernández, Luis; Fisteus, Jesús (2019). "Axiomas de monotonicidad en las reglas de votación de múltiples ganadores basadas en la aprobación" (PDF) : 485–493. arXiv : 1710.04246 . {{cite journal}}: Requiere citar revista |journal=( ayuda )
14. Peters, Dominik (2018). "Pico único y unimodularidad total: nuevos algoritmos de tiempo polinomial para elecciones con múltiples ganadores": 1169–1176. arXiv : 1609.03537 . {{cite journal}}: Requiere citar revista |journal=( ayuda )
15. Aziz, Haris; Gaspers, Serge; Gudmundsson, Joachim; Mackenzie, Simon; Mattei, Nicholas; Walsh, Toby (2015). Aspectos computacionales de la votación de aprobación con múltiples ganadores . págs. 107–115. arXiv : 1407.3247 . ISBN 978-1-4503-3413-6.
16. Skowron, Piotr; Faliszewski, Piotr; Lang, Jérôme (2016). "Encontrar un conjunto colectivo de elementos: de la multirrepresentación proporcional a la recomendación grupal". Inteligencia artificial . 241 : 191–216. arXiv : 1402.3044 . doi :10.1016/j.artint.2016.09.003. S2CID  11313941.
17. Bredereck, Robert; Faliszewski, Piotr; Kaczmarczyk, Andrzej; Knop, Dusan; Niedermeier, Rolf (2020). "Algoritmos parametrizados para encontrar un conjunto colectivo de elementos". Actas de la Conferencia AAAI sobre Inteligencia Artificial . 34 (2): 1838–1845. doi : 10.1609/aaai.v34i02.5551 . S2CID  213963505.
18. Godziszewski, Michal; Batko, Pawel; Skowron, Piotr; Faliszewski, Piotr (2021). "Análisis de las reglas de los comités basados ​​en la aprobación para elecciones euclidianas 2D". Actas de la Conferencia AAAI sobre Inteligencia Artificial . 35 (6): 5448–5455. doi : 10.1609/aaai.v35i6.16686 . S2CID  235306592.
19. Dudycz, Szymon; Manurangsi, Pasin; Marcinkowski, Jan; Sornat, Krzysztof (2020). "Aproximación estricta para votación de aprobación proporcional". Actas de la vigésimo novena conferencia conjunta internacional sobre inteligencia artificial . IJCAI-20. págs. 276–282. doi : 10.24963/ijcai.2020/39 . ISBN. 978-0-9992411-6-5.S2CID220484671  .​
20. Byrka, Jaroslaw; Skowron, Piotr; Sornat, Krzysztof (2017). Votación de aprobación proporcional, k-mediana armónica y asociación negativa . Vol. 107. págs. 26:1–26:14. arXiv : 1704.02183 . doi : 10.4230/LIPIcs.ICALP.2018.26 . ISBN . 9783959770767. Número de identificación del sujeto  3839722.

Enlaces externos

• Herramienta en línea para calcular el PAV y otros métodos de múltiples ganadores basados ​​en la aprobación
• Paquete Python abcvoting que contiene una implementación de PAV (pypi)