stringtranslate.com

Reglas de votación de Phragmen

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?

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]

Cada una de estas variantes tiene dos subvariantes:

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:

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.

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:

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 2 ) 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 2 ), el tiempo de ejecución total es O( k 3 mn log 2 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:

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:

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]

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]

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

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):

Lectura adicional

Implementaciones y demostraciones

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

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. ^ abcdefghijk Janson, Svante (12 de octubre de 2018). "Métodos de elección de Phragmén y Thiele". arXiv : 1611.08826 [math.HO].
  3. ^ abcde 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. ^ ab 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.