Reglas de votación de Phragmen

Método de recuento de votos y determinación de resultados

Las reglas de votación de Phragmén son reglas para la votación con múltiples ganadores . Permiten a los votantes votar por candidatos individuales en lugar de partidos, pero aún así garantizan la representación proporcional . Fueron publicadas por Lars Edvard Phragmén en francés y sueco entre 1893 y 1899, ^[1] y traducidas al inglés por Svante Janson en 2016. ^[2]

Fondo

En la votación de aprobación con múltiples ganadores, cada votante puede votar por uno o más candidatos y el objetivo es seleccionar un número fijo k de ganadores (donde k puede ser, por ejemplo, el número de miembros del parlamento). La pregunta es ¿cómo determinar el conjunto de ganadores?

• El método más sencillo es el voto múltiple intransferible , en el que se eligen a los k candidatos con mayor número de aprobaciones, pero este método tiende a seleccionar a k candidatos del partido mayoritario, dejando a los partidos menores sin representación alguna.
• En el siglo XIX se debatió mucho sobre los sistemas electorales que podían garantizar la representación proporcional . Una solución, defendida por ejemplo por D'Hondt en 1878, fue la de votar por listas de partidos en lugar de por candidatos individuales. Esta solución sigue siendo muy común hoy en día.

Phragmén quería mantener el voto para candidatos individuales, de modo que los votantes pudieran aprobar candidatos en función de sus méritos personales. En el caso especial en el que cada votante aprueba a todos y sólo a los candidatos de un único partido, los métodos de Phragmén dan los mismos resultados que el método de D'Hondt. ^{[2] : Sec.11} Sin embargo, el método de Phragmén puede manejar situaciones más generales, en las que los votantes pueden votar por candidatos de diferentes partidos (de hecho, el método ignora la información sobre qué candidato pertenece a qué partido).

Reglas de Phragmén para las votaciones de aprobación

El método de Phragmén para votaciones no ordenadas (de aprobación) se puede presentar de varias maneras equivalentes. ^{[2] : Sec.3}

Equilibrio de carga

Cada candidato electo genera una "carga" de 1 unidad. La carga de un candidato debe ser soportada por los votantes que lo apoyan. El objetivo es encontrar un comité para el cual la carga pueda ser dividida entre los votantes de la manera más "equilibrada".

Dependiendo de la definición exacta de "equilibrado" son posibles varias reglas: ^[3]

• Leximax-Phragmen: Minimizar la carga máxima, y ​​sujeto a ello la segunda carga máxima, etc. (usando optimización lexicográfica máx-mín ).
• Leximin-Phragmen : Maximizar la carga mínima, y ​​sujeto a ello la segunda carga mínima, etc.
• Método var-Phragmen o de Ebert : Minimizar la varianza de la carga.

Cada una de estas variantes tiene dos subvariantes:

• Una variante de optimización global , que normalmente es NP-difícil de calcular;
• Una variante secuencial , en la que los candidatos se seleccionan secuencialmente y, en cada turno, el siguiente candidato elegido es el que alcanza la medida óptima entre todos los candidatos (es decir, un algoritmo codicioso ).

El método original de Phragmen es el método secuencial que minimiza la carga máxima, que actualmente se conoce como Seq-Phragmen . ^[3]

En la práctica, las reglas que ofrecen las mejores garantías axiomáticas en la categoría de optimización global son leximax-Phragmen y var-Phragmen. Entre las variantes secuenciales, las que ofrecen las mejores garantías son Seq-Phragmen.

Phragmen ilustró su método representando a cada votante como un recipiente. Los candidatos ya elegidos están representados por el agua en los recipientes. Para elegir a otro candidato, se debe verter un litro de agua en los recipientes correspondientes a los votantes que votaron por ese candidato. El agua debe distribuirse de manera que la altura máxima del agua sea la menor posible.

Dinero virtual

Seq-Phragmen también se puede describir como el siguiente proceso continuo:

• Cada votante comienza con 0 dinero virtual y recibe dinero a un ritmo constante de 1 por día.
• En cada momento t , definimos a un candidato x aún no elegido como asequible si el dinero total en poder de los votantes que aprueban x es al menos 1.
• La primera vez que un candidato es asequible, elegimos arbitrariamente un candidato asequible y . Agregamos y al comité y reiniciamos el dinero virtual de los votantes que aprueban y (ya que ahora han "usado" su dinero virtual para financiar y ).
• Los votantes siguen ganando dinero virtual y financiando candidatos hasta que todos los miembros del comité k sean elegidos.

Ejemplos

El siguiente ejemplo simple se parece a una votación por lista de partidos. Hay k=6 escaños y 9 candidatos, denotados a,b,c,d,e,f,g,h,i. Hay 63 votantes con las siguientes preferencias: 31 votantes aprueban a,b,c; 21 votantes aprueban d,e,f; y 11 votantes aprueban g,h,i.

• Los votantes comienzan a ganar dinero a una tasa fija de 1 por día. Después de 1/31 de día (~0,0323 días), los 31 votantes de abc tienen 0,0323 cada uno, por lo que juntos pueden financiar a uno de sus candidatos aprobados. Se elige arbitrariamente uno de a,b,c; supongamos que es a.
• Después de 1/21 días (~0,0476 días), los 31 votantes de abc tienen solo ~0,015 cada uno, pero los 21 votantes de def tienen 0,0476 cada uno, por lo que juntos pueden financiar a uno de sus candidatos aprobados. Se elige uno de d, e, f de manera arbitraria; supongamos que es d.
• Después de aproximadamente 0,0646 días, los votantes de abc vuelven a tener 0,0323 cada uno, por lo que compran otro de sus candidatos aprobados, digamos b.
• Después de 1/11 días (~0,091 días) los votantes de ghi tienen 0,091 cada uno, por lo que juntos pueden financiar a uno de sus candidatos aprobados, digamos g (en este punto, los votantes de abc tienen solo 0,0264 cada uno y los votantes de def tienen 0,0434 cada uno, por lo que ninguno de ellos puede comprar otro candidato).
• Después del día 0,0952, los votantes def vuelven a tener 0,0476 cada uno, por lo que pueden comprar otro candidato, digamos e.
• Después del día 0,0969, los votantes de abc vuelven a tener 0,0323 cada uno, por lo que pueden comprar otro candidato, digamos c.

El comité final está formado por a, b, c; d, e; g. Nótese que cada "partido" está representado aproximadamente en proporción a su tamaño: 3 candidatos por 31 votantes, 2 candidatos por 21 votantes y 1 candidato por 11 votantes.

He aquí un ejemplo más complejo. Hay k = 3 escaños y 6 candidatos, representados por A, B, C, P, Q, R. Las papeletas son: 1034 votos para ABC, 519 votos para PQR, 90 votos para ABQ, 47 votos para APQ. Los ganadores son elegidos secuencialmente de la siguiente manera:

• En primer lugar, calculamos para cada candidato el valor requerido de t para que el candidato pueda obtener un poder de voto total de 1. Este valor es 1/1171 para A (ya que A aparece en 1171 papeletas); 1/1124 para B; 1/1034 para C; 1/566 para P; 1/656 para Q; 1/519 para R. Por lo tanto, A es elegido primero.
• Ahora, volvemos a calcular para cada candidato el valor requerido de t de modo que el candidato pueda obtener un poder de voto total de 1, teniendo en cuenta que hay que deducir 1/1171 de cada votante que haya aprobado A. El valor requerido para B es 1/1124+1/1171, ya que hay 1124 votantes que aprueban B, y todos ellos ya aprobaron A. De manera similar, el valor requerido para C es 1/1034+1/1171; para Q es 1/656+(137/656)/1171, ya que 137 de los 656 votantes de Q ya votaron por A; para P es 1/566+(47/566)/1171; y para R es 1/519. El valor es el más pequeño para Q, por lo que es elegido como el segundo ganador.
• De manera similar, B es elegido como el tercer ganador.

Cálculo

Var-Phragmen y Leximax-Phragmen son NP-difíciles de calcular, incluso cuando cada agente aprueba 2 candidatos y cada candidato es aprobado por 3 votantes. La prueba se realiza mediante reducción a partir del conjunto independiente máximo en grafos cúbicos . ^[3]

Leximax-Phragmen se puede calcular mediante una secuencia de como máximo 2 n programas lineales de números enteros mixtos con O( nm + n ² ) variables cada uno (donde n es el número de votantes y m el número de candidatos); consulte Optimización máxima-mínima lexicográfica .

Var-Phragmen se puede calcular resolviendo un programa cuadrático de números enteros mixtos con O( nm ) variables.

Seq-Phragmen se puede calcular en tiempo polinomial. Un cálculo ingenuo muestra que el tiempo de ejecución es O( kmn ): hay k pasos (uno por cada candidato electo); en cada paso, tenemos que comprobar todos los candidatos para ver cuál de ellos puede ser financiado; y para cada candidato, tenemos que comprobar todos los votantes para ver cuál de ellos puede financiarlo. Sin embargo, para ser precisos, necesitamos trabajar con números racionales, y su magnitud crece hasta k log n . Dado que los cálculos en b bits pueden requerir un tiempo O( b ² ), el tiempo de ejecución total es O( k ³ mn log ² n).

Reglas de Phragmén para votaciones por orden de preferencia

Las reglas de Phragmén se utilizan comúnmente con las papeletas de aprobación (es decir, votación de aprobación con múltiples ganadores ), pero tienen variantes que utilizan papeletas con clasificación (es decir, votación con clasificación con múltiples ganadores ). Una Comisión Real sobre el Método de Elección Proporcional propuso una adaptación para Seq-Phragmen en 1913. El método se ha utilizado en las elecciones suecas para la distribución de escaños dentro de los partidos desde 1921. ^{[2] : Sec.9}

En la versión adaptada, en cada ronda, cada votante vota efectivamente sólo por el candidato que tenga la puntuación más alta. Nuevamente, cuando un candidato es elegido, su "carga" de 1 unidad debe distribuirse entre los candidatos que votan por él (es decir, colocarlo en primer lugar); la división de la carga debe minimizar la carga máxima de un votante.

Variantes

Votación de partidos

Es posible utilizar el método de Phragmen para los partidos. Cada votante puede aprobar uno o más partidos. El procedimiento es el mismo que antes, excepto que ahora cada partido puede ser elegido varias veces, entre 0 y el número total de candidatos del partido. ^[4]

Presupuesto participativo

La regla Seq-Phragmen fue adaptada al contexto más general del presupuesto participativo combinatorio . ^[5]

Proporcionalidad degresiva y regresiva

Jaworski y Skowron ^[6] construyeron una clase de reglas que generalizan seq-Phragmen para proporcionalidad degresiva y regresiva. Intuitivamente:

• La proporcionalidad degresiva se obtiene asumiendo que los electores que ya tienen más representantes ganan dinero a un ritmo más lento que los que tienen menos;
• La proporcionalidad regresiva se implementa asumiendo que los candidatos que son aprobados por más votantes cuestan menos que aquellos que obtienen menos aprobaciones.

Utilizando el método de Phragmen para clasificar alternativas

El método secuencial de Phragmen puede utilizarse no sólo para seleccionar un subconjunto, sino también para crear una clasificación de alternativas, según el orden en que se eligen. Brill e Israel ^[7] extienden este método a las clasificaciones dinámicas . Motivados por las aplicaciones de preguntas y respuestas en línea, ^[8] suponen que algunos candidatos ya fueron elegidos y utilizan esta información para calcular la clasificación. Sugieren dos adaptaciones de la regla de Phragmen:

• Phragmen dinámico: en cada paso, se recorre la secuencia de candidatos ya elegidos y se divide su "costo" entre sus partidarios. Esto crea, para cada usuario, una "deuda" potencial: un saldo negativo. El cálculo de las deudas se puede realizar en un tiempo O( mn ² ), donde m es el número de candidatos y n el número de usuarios. Luego, los usuarios comienzan a acumular dinero como de costumbre, donde un usuario puede comenzar a comprar nuevos candidatos solo después de haber pagado su "deuda". Los usuarios compran candidatos secuencialmente, hasta que se calcula la nueva clasificación. La nueva clasificación es proporcional. El cálculo de la nueva secuencia se puede realizar en un tiempo O( m ² n ² ).
• Phragmen miope: la "deuda" de cada usuario se calcula como en Phragmen dinámico. Luego, en lugar de crear una clasificación completa ejecutando Phragmen secuencial, los candidatos se clasifican por la cantidad de "deuda" que crearán con los usuarios. Es decir: los candidatos se clasifican por su idoneidad para ser elegidos a continuación. La clasificación resultante no es necesariamente proporcional (en particular, cuando la secuencia está vacía, Phragmen miope coincide con la votación de aprobación utilitaria ). El cálculo de la nueva secuencia se puede realizar en tiempo O( mn ² ).

Analizan las propiedades de monotonía y equidad de estas adaptaciones, tanto teórica como empíricamente.

Propiedades

Homogeneidad

Para cada votación posible b , sea v _b el número de votantes que votaron exactamente b (por ejemplo: aprobaron exactamente el mismo conjunto de candidatos). Sea p _b la fracción de votantes que votaron exactamente b (= v _b / el número total de votos). Un método de votación se llama homogéneo si depende solo de las fracciones p _b . Por lo tanto, si los números de votos se multiplican todos por la misma constante, el método devuelve el mismo resultado. Los métodos de Phragmén son homogéneos en ese sentido. ^{[2] : Rem.2.1}

Independencia de candidatos no electos

Si se añade cualquier número de candidatos a una votación, pero ninguno de ellos es elegido (incluso si algunos de ellos son votados), entonces el resultado no cambia. ^{[2] : Sec.6} Esto reduce un incentivo para la manipulación estratégica: agregar candidatos "ficticios" para atraer votos.

Monotonía

Seq-Phragmén asigna los escaños uno por uno, por lo que satisface la propiedad de monotonía del comité : cuando se agregan más escaños, el conjunto de ganadores aumenta (ningún ganador pierde un escaño). ^{[2] : Sec.5}

También satisfacen varios otros criterios de monotonía . ^{[2] : Sec.14}

Para el método de votación de aprobación de Phragmén : si un candidato C es elegido, y luego el candidato C obtiene algunas aprobaciones ya sea de nuevos votantes que votan por C , o de votantes existentes que agregan C a sus papeletas, y no ocurren otros cambios, entonces C sigue siendo elegido. Sin embargo, esta monotonía no se cumple para pares de candidatos, incluso si siempre aparecen juntos. Por ejemplo, es posible que los candidatos C, D aparezcan juntos en todas las votaciones y obtengan dos escaños, pero si se agrega otra votación para C, D, entonces obtienen juntos solo un escaño (por lo que uno de ellos pierde un escaño). ^{[2] : Ej.14.4, 14.5} De ​​manera similar, la monotonía no se cumple en la variante con partidos: un partido puede obtener más aprobaciones pero aún así obtener menos escaños. Por ejemplo: ^[4]

• Supongamos que hay k = 3 escaños y 3 candidatos: a, b, c. Las papeletas son: 4 para a, 7 para b, 1 para a+b, 16 para a+c, 4 para b+c. Entonces el comité electo es {a, b, a}. Pero, si uno de los b votantes también aprueba a a (de modo que las papeletas son: 4 para a, 6 para b, 2 para a+b, 16 para a+c, 4 para b+c), entonces el comité electo es {a, c, b}. Por lo tanto, el partido a obtuvo una aprobación pero perdió un escaño.

En el caso del método de votación por orden de preferencia de Phragmén , si un candidato C es elegido y luego el candidato C es promovido en algunas de las votaciones o gana algunos votos nuevos y no se producen otros cambios, C sigue siendo elegido. Sin embargo, si se producen otros cambios simultáneamente, C podría perder su escaño. Por ejemplo, es posible que algunos votantes cambien de opinión y, en lugar de votar por A y B, voten por C y D, y este cambio haga que C pierda su escaño. ^{[2] : Ej. 13.16}

Representación justificada

La regla de Phragmen secuencial satisface un axioma conocido como Representación Proporcional Justificada (PJR). ^[3] Esto la convierte en uno de los únicos métodos que satisfacen tanto la PJR como la monotonía.

Sin embargo, no cumple con un axioma más fuerte conocido como Representación Justificada Extendida (EJR). Aquí se ofrece un ejemplo: ^[3]

• Hay 14 candidatos: a, b, c1, ..., c12. Hay 12 puestos por cubrir.
• Hay 24 votantes: dos votantes aprueban {a,b,c1}; dos votantes aprueban {a,b,c2}; 6 votantes aprueban {c1,c2,...,c12}; 5 votantes aprueban {c2,c3,...,c12); 9 votantes aprueban {c3,c4,...,c12}.
• Seq-Phragmen selecciona c1,...,c12. Viola la regla EJR para los cuatro votantes que aprueban {a,b,c1} y {a,b,c2}: este grupo tiene 2 cuotas y es 2-cohesivo, pero ningún miembro tiene 2 ganadores aprobados.

Otro ejemplo se da aquí (para la configuración de las fiestas): ^[9]

• Hay 3 partidos candidatos y 10 escaños por cubrir.
• Hay 10 votantes, con conjuntos de aprobación ab,ab,ab; ac,ac,ac,ac; bc,bc; b.
• Seq-Phragmen elige a (en el tiempo 1/7); luego b; luego a,b,a,b,a,b,a,b.
• Los votantes 1, 2, 3 aprueban a los 10 candidatos, pero los votantes 4,...,10 aprueban solo a 5 candidatos. Sin embargo, el grupo de votantes 4, 5, 6, 7, 8, 9 está de acuerdo con el partido c, por lo que EJR requiere que al menos uno de ellos apruebe a 6 candidatos, por lo que se viola EJR (nótese que PJR no se viola para ese grupo, ya que los 10 candidatos son aprobados por al menos un miembro del grupo).

Seq-Phragmen también falla en un axioma diferente e incompatible llamado Representación Perfecta (PER).

Var-Phragmen satisface PER, pero falla PJR y EJR (excepto en el caso L=1).

Leximan-Phragmen satisface tanto PJR como PER, pero aún falla en EJR.

Consistencia

Los métodos de Phragmén no satisfacen el criterio de consistencia . Además, no ignoran las papeletas completas: agregar votantes que votan por todos los candidatos (y por lo tanto son totalmente indiferentes) podría afectar el resultado. ^{[2] : Ej. 15.4, 15.6, 15.8, 15.9}

Casos especiales

Cuando hay un solo escaño ( k =1):

• El método de votación de aprobación de Phragmén se reduce a una votación de aprobación : siempre selecciona al candidato con el mayor número de aprobaciones.
• El método de votación por orden de preferencia de Phragmén se reduce a una votación por pluralidad : siempre selecciona al candidato clasificado en primer lugar por el mayor número de votantes.

Lectura adicional

• Hay más información disponible sobre los métodos de Phragmén en. ^[10]
• Propiedades matemáticas de los métodos de Phragmen vs. los métodos de Thiele. ^[11]
• Los métodos de Enestrom y Phragmen. ^[12]

Implementaciones y demostraciones

• Algunas de las reglas de votación de Phragmén están implementadas en el paquete Python abcvoting.
• Algunas de las reglas de votación de Phragmén se pueden probar en línea en el sitio web pref.tools.
• Tanto la versión simple como la complicada ^{[13] [14]} se utilizan en el sustrato de la criptomoneda Polkadot . ^[15]

Generalizaciones

Motamed, Soeteman, Rey y Endriss ^[16] presentan un mecanismo de equilibrio de carga secuencial , que generaliza la regla de Phragmen al presupuesto participativo con múltiples recursos.

Véase también

• Voto único transferible
• Regla de aprobaciones en expansión
• Método de partes iguales
• Reglas de votación de Thiele

Referencias

1. 1. "Om proporcionalella val". (Resumen de una conferencia pública). Stockholms Dagblad, 14 de marzo de 1893. 2. "Sur une m ́ethode nouvelle pour r ́ealiser, dansles ́elections, la repr ́esentation proporcionalelle des partis". ¨Ofversigt avKongl. Vetenskaps-Akademiens F ̈orhandlingar 1894, N:o 3, Estocolmo, 133–137. 3. "Proportionella val. En valteknisk estudio." Svenskasp ̈orsm ̊al 25, Lars H ̈okersbergs f ̈orlag, Estocolmo, 1895. 4. "Sur la th ́eorie des ́elections multiples", ̈Ofversigt avKongl. Vetenskaps-Akademiens F ̈orhandlingar 1896, N:o 3, Estocolmo, 181–191. 5. "Till fr ̊agan om en proporcionalell valmetod". Statsvetenskaplig Tidskrift2 (1899), n.º 2, 297–305. http://cts.lub.lu.se/ojs/index.php/st/article/view/1949
2. Janson, Svante (12 de octubre de 2018). "Métodos de elección de Phragmén y Thiele". arXiv : 1611.08826 [math.HO].
3. Brill, Markus; Freeman, Rupert; Janson, Svante; Lackner, Martin (6 de marzo de 2023). "Métodos de votación de Phragmén y representación justificada". Programación matemática . 203 (1–2): 47–76. arXiv : 2102.12305 . doi : 10.1007/s10107-023-01926-8 . ISSN  1436-4646. PMC 10858002 . PMID  38344413. 
4. Mora, Xavier; Oliver, María (28 de julio de 2015). "Eleccions mitjançant el vot d'aprovació. El mètode de Phragmén i algunes variantes". Butlletí de la Societat Catalana de Matemàtiques (en catalán). 30 (1): 57-101. ISSN  2013-9829.
5. Los, Maaike; Christoff, Zoé; Grossi, Davide (2022). "Asignaciones presupuestarias proporcionales: hacia una sistematización". arXiv : 2203.12324 [cs.GT].
6. Jaworski, Michal; Skowron, Piotr (2022). "Reglas de Phragmén para proporcionalidad degresiva y regresiva". arXiv : 2201.04248 [cs.GT].
7. Israel, Jonas; Brill, Markus (2021). «Ranking proporcional dinámico». arXiv : 2105.08043 [cs.GT].
8. Aplicaciones de preguntas y respuestas como slido, mentimeter, pigeonhole live o speakup.
9. Chandak, Nikhil; Goel, Shashwat; Peters, Dominik (2023). "Agregación proporcional de preferencias para la toma de decisiones secuencial". arXiv : 2306.14858 [cs.GT].
10. Peters, Dominik; Skowron, Piotr (13 de julio de 2020). "Proporcionalidad y los límites del bienestarismo". Actas de la 21.ª Conferencia de la ACM sobre economía y computación . EC '20. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 793–794. arXiv : 1911.11747 . doi :10.1145/3391403.3399465. ISBN . 978-1-4503-7975-5.S2CID208291203  .​
11. Janson, Svante; Öberg, Anders (2017). "Un sistema dinámico contractivo por partes y métodos de elección". arXiv : 1709.06398 [math.DS].
12. Camps, Rosa; Mora, Xavier; Saumell, Laia (2019). "El método de Eneström y Phragmén para elecciones parlamentarias mediante voto aprobatorio". arXiv : 1907.10590 [econ.TH].
13. "consensus/NPoS en master · w3f/consensus". GitHub . 17 de octubre de 2021.
14. https://aaai.org/ocs/index.php/AAAI/AAAI17/paper/download/14757/13791 ^{[ URL desnuda PDF ]}
15. "Método secuencial Phragmén · Wiki Polkadot". wiki.polkadot.network . 30 de junio de 2023.
16. Motamed, Nima; Soeteman, Arie; Rey, Simon; Endriss, Ulle (2022). "Presupuesto participativo con múltiples recursos". En Baumeister, Dorothea; Rothe, Jörg (eds.). Sistemas multiagente . Apuntes de clase en informática. Cham: Springer International Publishing. págs. 330–347. doi :10.1007/978-3-031-20614-6_19. ISBN 978-3-031-20614-6. Número de identificación del sujeto  252357719.