Reglas de votación de Phragmen

Cada candidato electo genera una "carga" de 1 unidad. Esta carga debe ser asumida por los votantes que lo apoyan. El objetivo es encontrar un comité que permita distribuir la carga entre los votantes de la manera más equitativa.

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. (utilizando la optimización lexicográfica max-min ).
• Leximin-Phragmen : Maximizar la carga mínima y, sujeto a ella, la segunda carga mínima, etc.
• Método de 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 , cuyo cálculo suele ser NP-difícil;
• 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 voraz ).

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, Seq-Phragmen ofrece las mejores garantías.

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

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

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

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 seleccionado varias veces, entre 0 y el número total de candidatos del partido. ^{[ 4 ]}

La regla Seq-Phragmen se adaptó al contexto más general del presupuesto participativo combinatorio . ^{[ 5 ]}

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

• La proporcionalidad degresiva se obtiene al suponer que los votantes que ya tienen más representantes ganan dinero a un ritmo más lento que aquellos que tienen menos;
• La proporcionalidad regresiva se implementa asumiendo que los candidatos que cuentan con la aprobación de más votantes cuestan menos que aquellos que obtuvieron menos aprobaciones.

El método secuencial de Phragmen puede utilizarse no solo 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 clasificaciones dinámicas . Motivados por las aplicaciones de preguntas y respuestas en línea, ^{[ 8 ]} asumen que algunos candidatos ya han sido elegidos y utilizan esta información para calcular la clasificación. Sugieren dos adaptaciones de la regla de Phragmen:

• Fragmentos dinámicos: 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 (saldo negativo). El cálculo de las deudas se puede realizar en 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, y un usuario solo puede comenzar a comprar nuevos candidatos 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 tiempo O ⁽ m²n² ⁾ .
• Myopic Phragmen: la "deuda" de cada usuario se calcula como en Dynamic Phragmen. Luego, en lugar de crear una clasificación completa ejecutando Sequential Phragmen, los candidatos se clasifican según la cantidad de "deuda" que crearán para los usuarios. Es decir: los candidatos se clasifican según su idoneidad para ser elegidos a continuación. La clasificación resultante no es necesariamente proporcional (en particular, cuando la secuencia está vacía, Myopic Phragmen 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 monotonicidad y equidad de estas adaptaciones, tanto desde un punto de vista teórico como empírico.

Para cada papeleta 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 denomina homogéneo si depende únicamente de las fracciones p _b . Por lo tanto, si el número de votos se multiplica 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}

Si se agrega cualquier número de candidatos a una boleta, 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.

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

También satisfacen otros criterios de monotonicidad . ^{[ 2 ] : Sec.14}

Para el método de votación por 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 boletas, y no ocurren otros cambios, entonces C sigue siendo elegido. Sin embargo, esta monotonicidad no se cumple para pares de candidatos, incluso si siempre aparecen juntos. Por ejemplo, es posible que los candidatos C y D aparezcan juntos en todas las boletas y obtengan dos escaños, pero si se agrega otra boleta para C y D, entonces juntos obtienen solo un escaño (por lo que uno de ellos pierde un escaño). ^{[ 2 ] : Ej.14.4, 14.5} De ​​manera similar, la monotonicidad no se cumple en la variante con partidos: un partido puede obtener más aprobaciones pero aun así obtener menos escaños. Por ejemplo: ^{[ 4 ]}

• Supongamos que hay k = 3 escaños y 3 candidatos: a, b, c. Los votos 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 votantes de b también aprueba a (de modo que los votos 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 método de votación por orden de preferencia de Phragmén : si un candidato C resulta elegido, y luego este candidato asciende en algunas de las papeletas o consigue nuevos votos, y no se producen otros cambios, entonces 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 provoque que C pierda su escaño. ^{[ 2 ] : Ex.13.16}

La regla de Fragmentos Secuenciales satisface un axioma conocido como Representación Justificada Proporcional (PJR). ^{[ 3 ]} Esto la convierte en uno de los pocos métodos que satisfacen tanto PJR como monotonicidad.

Sin embargo, incumple un axioma más fuerte conocido como Representación Justificada Extendida (EJR). Un ejemplo se da aquí: ^{[ 3 ]}

• Hay 14 candidatos: a, b, c1, ..., c12. Hay 12 puestos para 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 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.

Aquí se da otro ejemplo (para la determinación de las partes): ^{[ 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 y 3 aprueban a los 10 candidatos, pero los votantes 4, ..., 10 aprueban solo 5. Sin embargo, el grupo de votantes 4, 5, 6, 7, 8 y 9 están de acuerdo con el partido c, por lo que la EJR exige que al menos uno de ellos apruebe 6 candidatos, lo que incumple la EJR (nótese que la PJR no se incumple para ese grupo, ya que los 10 candidatos cuentan con la aprobación de al menos un miembro del grupo).

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

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

Leximan-Phragmen satisface tanto PJR como PER, pero aún no cumple con EJR.

Los métodos de Phragmén no satisfacen el criterio de consistencia . Además, no ignoran las papeletas completas: añadir 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}

Cuando hay un solo asiento ( k = 1):

• El método de votación por aprobación de Phragmén se reduce a una votación por 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 la votación por mayoría simple : siempre selecciona al candidato que ocupa el primer lugar según el mayor número de votantes.