Votación de aprobación proporcional

Sistema electoral de múltiples ganadores

La votación 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 amplía el método de prorrateo de promedios más altos comúnmente utilizado para calcular los prorrateos para la representación proporcional de listas de partidos . ^[1] Sin embargo, 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 de una lista de partido determinada . ^[2]

En PAV, los votantes emiten votos de aprobación marcando a todos los candidatos que aprueban; La boleta de cada votante se trata entonces como si todos los candidatos en la boleta estuvieran en su propia "lista de partido". Luego, los escaños se reparten entre los candidatos de manera que se garantice que todas las coaliciones estén representadas proporcionalmente.

Historia

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 importancia en las elecciones suecas de 1909 a 1921 para distribuir escaños dentro de los partidos y en las elecciones locales. ^[4] 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, la votación de aprobación por satisfacción , se puede considerar que PAV selecciona un comité probando todos los comités posibles y luego elige el comité con más votos. En la votación de aprobación de satisfacción, la boleta de cada votante se divide en partes iguales entre todos los candidatos que aprueban, otorgando votos a cada uno. Si los votantes son perfectamente estratégicos y sólo apoyan a tantos candidatos como su partido tiene derecho, SAV crea un resultado proporcional. ${\displaystyle r}$ ${\displaystyle 1/r}$

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

Por lo tanto, si una votación aprueba a los candidatos elegidos, esa votación aporta el -ésimo número armónico 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 el tamaño del comité . Denotemos el conjunto de candidatos aprobados por el votante . La puntuación PAV de un comité con tamaño se define como . La APV selecciona el comité con la máxima puntuación. ${\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 PAV de Andrea y Carter coincide con la secuencia de Aprobación Simple. Sin embargo, si los votos anteriores se cambian ligeramente para que A y C reciban 16 votos y D reciba 9 votos, entonces Andrea y Delilah son elegidas 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 Aprobación simple permanece sin cambios. Esto muestra que PAV puede dar resultados 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 seleccionar y que hay tres grupos de candidatos: candidatos rojos , azules y verdes . Hay 100 votantes:

• 60 votantes votaron por todos los candidatos azules ,
• 30 votantes votaron por todos los candidatos rojos ,
• Diez votantes votaron por todos los candidatos verdes .

En este caso, APV seleccionaría 6 candidatos azules , 3 rojos y 1 verde . La puntuación de dicho comité 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 de 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 separados, como en el ejemplo anterior (los grupos pueden considerarse partidos políticos), y cada votante vota exclusivamente por todos los candidatos dentro de un solo grupo, entonces PAV actuará de la misma manera. manera como 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, la PAV funciona exactamente de la misma manera que la votación de aprobación . Es decir, selecciona el comité formado por el candidato aprobado por el mayor número de votantes.

Proporcionalidad

La mayoría de los sistemas de representación proporcional utilizan listas de partidos . PAV fue diseñado para tener representación proporcional y votos personales (los votantes votan por candidatos, no por una lista de partido). Merece ser llamado sistema "proporcional" porque si los votos siguen un esquema partidista (cada votante vota por todos los candidatos de un partido y no por 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 este partido (ver Ejemplo 2). ^[1] Además, bajo supuestos leves (simetría, continuidad y eficiencia de Pareto ), PAV es la única extensión del método D'Hondt que permite votos personales y satisface el criterio de coherencia . ^[2]

Incluso si los electores no siguen el esquema partidista, la norma ofrece 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 sea 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 utilizar números distintos de los números armónicos en su definición). ^[6]

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

El PAV falla en la preciobilidad (es decir, la elección del PAV no siempre puede explicarse 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 gusten) y falla en la proporcionalidad laminar. ^[10] Dos reglas alternativas que satisfacen la fijación de precios y la proporcionalidad laminar, y que tienen propiedades relacionadas con la proporcionalidad comparablemente buenas con las del PAV son el método de 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 del 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 falla las siguientes propiedades:

• Monotonicidad de la casa . ^[12] Dos métodos alternativos que satisfacen la monotonicidad de la casa y que tienen propiedades relacionadas con la proporcionalidad comparablemente buenas con respecto al 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 no cumplen con 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 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 polinómico , ^{[15] [16],} lo que facilita la transparencia. Sin embargo, la complejidad temporal del peor de los casos es NP-completa , lo que significa que para algunas elecciones puede resultar difícil o imposible encontrar una solución exacta que garantice todas las propiedades teóricas de PAV.

En la práctica, el resultado de PAV se puede calcular exactamente para comités de tamaño mediano (<50 candidatos) utilizando solucionadores de programación de enteros (como los proporcionados en el paquete abcvoting de Python). 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 suelen ser buenas aproximaciones a elecciones reales, lo que permite utilizarlos como heurísticas que reducen drásticamente el esfuerzo computacional necesario para encontrar una solución correcta. Por ejemplo, los resultados electorales exactos se pueden resolver en tiempo polinómico en el caso en que los votantes y candidatos se encuentran 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 codicioso para aproximar el resultado. SPAV tiene un índice de aproximación al 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 polinómico y el resultado de las elecciones podría determinarse manualmente. Un enfoque diferente que incluye el redondeo desaleatorizado (con el método de probabilidades condicionales ) da una relación de aproximación en el peor de los casos de 0,7965; ^[19] según los supuestos estándar en la teoría de la complejidad, esta es la mejor relación de aproximación que se puede lograr para PAV en tiempo polinomial. ^[19] El problema de aproximación del PAV también se puede formular como un problema de minimización (en lugar de maximizar queremos minimizar ), en cuyo caso la relación de aproximación mejor 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)}$

Otras lecturas

• Lackner, Martín; Skowron, Piotr (2023). Votación de múltiples ganadores con preferencias de aprobación . SpringerBriefs en sistemas inteligentes. arXiv : 2007.01795 . doi :10.1007/978-3-031-09016-5. ISBN 978-3-031-09015-8. S2CID  244921148.
• 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 . Acceso a IA. ISBN 978-1-326-91209-3.{{cite book}}: CS1 maint: multiple names: authors list (link)

Ver también

• Método de partes iguales
• método d'hondt
• Votación de aprobación 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 reparto". Revista de Política Teórica . 30 (3): 358–382. arXiv : 1611.08691 . doi :10.1177/0951629818775518. S2CID  10535322.
2. Lackner, Martín; Skowron, Piotr (2021). "Reglas consistentes de múltiples ganadores basadas en aprobación". 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). "Los métodos electorales de Phragmén y Thiele". arXiv : 1611.08826 [matemáticas 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; Genial, Markus; Conitzer, Vicente; Elkind, Edith; Freeman, Ruperto; Walsh, Toby (2017). "Representación justificada en la votación del comité 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, Martín; 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 ACM sobre Economía y Computación . CE-21. págs. 820–840. arXiv : 1810.08799 . doi :10.1145/3465456.3467641. ISBN 9781450385541. S2CID  53046800.
10. Peters, Dominik; Skowron, Piotr (2020). "Proporcionalidad y los límites del bienestarismo". Actas de la 21ª Conferencia ACM sobre Economía y Computación . CE'20. págs. 793–794. arXiv : 1911.11747 . doi :10.1145/3391403.3399465. ISBN 9781450379755. S2CID  208291203.
11. Genial, Markus; Gölz, Paul; Peters, Dominik; Schmidt-Kraepelin, Ulrike; Wilker, Kai (2019). "Prorrateo basado en 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, Martín; Skowron, Piotr (2023). Votación de múltiples ganadores con preferencias de aprobación . SpringerBriefs en sistemas inteligentes. arXiv : 2007.01795 . doi :10.1007/978-3-031-09016-5. ISBN 978-3-031-09015-8. S2CID  244921148.
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}}: Citar diario requiere |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}}: Citar diario requiere |journal=( ayuda )
15. Aziz, Haris; Gaspers, Serge; Gudmundsson, Joachim; Mackenzie, Simón; Mattei, Nicolás; Walsh, Toby (2015). Aspectos computacionales de la votación de aprobación de 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 ítems: 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). "Un análisis de las reglas del comité basado 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, enero; Sornat, Krzysztof (2020). "Aproximación estricta para la votación de aprobación proporcional". Actas de la XXIX Conferencia Internacional Conjunta sobre Inteligencia Artificial . IJCAI-20. págs. 276–282. doi : 10.24963/ijcai.2020/39 . ISBN 978-0-9992411-6-5. S2CID  220484671.
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. S2CID  3839722.

enlaces externos

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