Representación justificada

Criterios para evaluar la equidad de los sistemas electorales

La representación justificada (RJ) es un criterio de equidad en la votación aprobatoria con múltiples ganadores . Puede considerarse como una adaptación del criterio de representación proporcional a la votación aprobatoria.

Fondo

La representación proporcional (RP) es una consideración importante en el diseño de sistemas electorales. Significa que los diversos grupos y sectores de la población deben estar representados en el parlamento en proporción a su tamaño. El sistema más común para asegurar la representación proporcional es el sistema de lista de partidos . En este sistema, los candidatos se dividen en partidos y cada ciudadano vota por un solo partido. Cada partido recibe un número de escaños proporcional al número de ciudadanos que votaron por él. Por ejemplo, para un parlamento con 10 escaños, si exactamente el 50% de los ciudadanos vota por el partido A, exactamente el 30% vota por el partido B y exactamente el 20% vota por el partido C, entonces la representación proporcional requiere que el parlamento contenga exactamente 5 candidatos del partido A, exactamente 3 candidatos del partido B y exactamente 2 candidatos del partido C. En realidad, las fracciones no suelen ser exactas, por lo que se debe utilizar algún método de redondeo, y esto se puede hacer mediante varios métodos de distribución .

En los últimos años, ha aumentado el descontento con el sistema de partidos. ^[1] Una alternativa viable a los sistemas de listas de partidos es permitir que los ciudadanos voten directamente a los candidatos, mediante papeletas de aprobación . Esto plantea un nuevo desafío: ¿cómo podemos definir la representación proporcional, cuando no hay grupos preestablecidos (partidos) que puedan merecer una representación proporcional? Por ejemplo, supongamos que un votante aprueba al candidato 1, 2, 3; otro votante aprueba a los candidatos 2, 4, 5; un tercer votante aprueba a los candidatos 1, 4. ¿Cuál es una definición razonable de "representación proporcional" en este caso? ^[2] Se han sugerido varias respuestas; se las conoce colectivamente como representación justificada.

Conceptos básicos

A continuación, denotamos el número de escaños por k y el número de votantes por n . La cuota Hare es n / k - el número mínimo de partidarios que justifica un solo escaño. En los sistemas de listas de partidos de RP, cada grupo de votantes de al menos L cuotas, que vota por el mismo partido, tiene derecho a L representantes de ese partido.

Una generalización natural de esta idea es un grupo L-cohesivo , definido como un grupo de votantes con al menos L cuotas, que aprueban al menos L candidatos en común.

Propiedades de representación justificada

Lo ideal sería exigir que, para cada grupo L-cohesivo, cada miembro tenga al menos L representantes. Esta condición, llamada Representación Justificada Fuerte (SJR) , podría ser inalcanzable, como lo muestra el siguiente ejemplo. ^[3]

Ejemplo 1. Hay k = 3 escaños y 4 candidatos {a, b, c, d}. Hay n = 12 votantes con conjuntos de aprobación: ab, b, b, bc, c, c, cd, d, d, da, a, a. Nótese que la cuota Hare es 4. El grupo {ab, b, b, bc} es 1-cohesivo, ya que contiene 1 cuota y todos los miembros aprueban al candidato b. La JR fuerte implica que el candidato b debe ser elegido. De manera similar, el grupo {bc, cc, cd} es 1-cohesivo, lo que requiere elegir al candidato c. De manera similar, el grupo {cd, d, d, da} requiere elegir a d, y el grupo {da, a, a, ab} requiere elegir a a. Entonces necesitamos elegir 4 candidatos, pero el tamaño del comité es solo 3. Por lo tanto, ningún comité satisface la JR fuerte.

Hay varias maneras de relajar la noción de JR fuerte.

Grupos unánimes

Una forma de hacerlo es garantizar la representación solo a un grupo L-unánime , definido como un grupo de votantes con al menos L cuotas, que aprueba exactamente el mismo conjunto de al menos L candidatos. Esta condición se denomina Representación Justificada Unánime (UJR) . Sin embargo, los grupos L-unánimes son bastante raros en los sistemas de votación de aprobación, por lo que la Representación Justificada Unánime no sería una garantía muy útil.

Grupos cohesionados

Si nos quedamos con grupos L-cohesivos, podemos relajar la garantía de representación de la siguiente manera. Definamos la satisfacción de un votante como el número de ganadores aprobados por ese votante. La JR fuerte requiere que, en cada grupo L-cohesivo, la satisfacción mínima de un miembro del grupo sea al menos L. En cambio, podemos exigir que la satisfacción media de los miembros del grupo sea al menos L. Esta condición más débil se denomina Representación Justificada Media (RMP) . ^[4] Desafortunadamente, esta condición puede seguir siendo inalcanzable. En el Ejemplo 1 anterior, al igual que la JR fuerte, la JR media requiere elegir a los 4 candidatos, pero solo hay 3 escaños. En cada comité de tamaño 3, la satisfacción media de algún grupo 1-cohesivo es solo 1/2.

• La votación por aprobación proporcional garantiza a cada grupo L-cohesivo una satisfacción media mayor que L -1. Tiene una variante llamada Local-Search-PAV, que se ejecuta en tiempo polinomial, y también garantiza una satisfacción media mayor que L -1. ^{[5] : Teoría 1, Prop. 1} Esta garantía es óptima: para cada constante c > 0, no existe ninguna regla que garantice una satisfacción media al menos L -1+ c . ^{[5] : Prop. 2}
• La regla de Nash se puede cumplir con los comités fraccionales , es decir, comités en los que los miembros pueden desempeñarse durante una fracción de un mandato o recibir votos ponderados. En particular, la regla de Nash cumple con la regla de Nash. ^[6]

Podemos debilitar aún más el requisito al exigir que la satisfacción máxima de un miembro del grupo sea al menos L. En otras palabras, en cada grupo L-cohesivo, al menos un miembro debe tener L representantes aprobados. Esta condición se llama Representación Justificada Extendida (EJR) ; fue introducida y analizada por Aziz, Brill, Conitzer, Elkind , Freeman y Walsh . ^[3] Hay una condición aún más débil, que requiere que EJR se cumpla solo para L = 1 (solo para grupos 1-cohesivos); se llama Representación Justificada. ^[3] Varios métodos conocidos satisfacen EJR:

• Todo comité con una satisfacción media superior a L -1 satisface la regla EJR (según el principio del pigeonhole ). ^[5] Por lo tanto, PAV y Local-Search-PAV satisfacen la regla EJR. PAV es la única de las reglas de votación de Thiele que satisface la regla EJR. ^[3]
• El método de partes iguales ^[7] es otra regla computable en tiempo polinomial que satisface EJR.
• Otro algoritmo politemporal que garantiza EJR es EJR-Exact. ^[5]
• Un algoritmo simple que encuentra una asignación de EJR se llama "Greedy EJR". Este algoritmo, que recorre L desde k hacia abajo hasta 1, verifica si existe un subconjunto L-cohesivo de votantes. Si es así, elige un subconjunto L-cohesivo más grande y agrega algunos candidatos L que son aprobados por todos ellos. ^{[8] : Algoritmo 1}
• El PAV secuencial satisface EJR solo para grupos 1-cohesivos y solo para k ≤ 5. Para k ≥ 6, no satisface EJR incluso para grupos 1-cohesivos.
• La regla de Monroe no le hace justicia a EJR
• Es co-NP-completo verificar si un comité determinado satisface EJR.

Un debilitamiento adicional de la EJR es la representación proporcional justificada (PJR) . Esto significa que, para cada L ≥ 1, en cada grupo de votantes L -cohesivo, la unión de sus conjuntos de aprobación contiene algunos ganadores L. Fue introducida y analizada por Sanchez-Fernandez, Elkind , Lackner, Fernandez, Fisteus, Val y Skowron . ^[4]

• EJR implica PJR, pero no viceversa. Por ejemplo, ^{[9] : Sec.4} considere un escenario con 2 k candidatos y k votantes. El votante i aprueba al candidato i , así como a los candidatos k +1,...,2 k . Nótese que la cuota es un votante, y cada L votantes son un grupo L -cohesivo. El comité 1,..., k satisface PJR, ya que para cada L votantes, la unión de sus conjuntos de aprobación contiene L ganadores. Pero no satisface EJR, ya que cada votante tiene solo 1 ganador aprobado. En contraste, el comité k +1,...,2 k satisface EJR.
• PAV satisface la regla EJR, por lo que también satisface la regla PJR; y también es la única regla de votación de aprobación basada en peso que satisface la regla PJR. Sin embargo, la PAV secuencial viola la regla PJR.
• Algunas de las reglas de votación de Phragmen satisfacen PJR, a saber: el Leximax Phragmen, que es NP-difícil de calcular, y el Sequential Phragmen, que es computable en tiempo polinomial y, además, satisface la monotonía del comité . ^[10]
• Cuando k divide a n , Monroe y Greedy Monroe satisfacen la regla PJR. Sin embargo, cuando k no divide a n , tanto Monroe como Greedy Monroe podrían violar la regla PJR, excepto cuando L=1. ^[4]
• Otra regla que es computable tanto en PJR como en politiempo es la regla de soporte maximin . ^[11]
• Es co-NP-completo verificar si un comité determinado satisface PJR. ^[5]

Grupos parcialmente cohesionados

Las condiciones anteriores sólo son válidas para grupos L-cohesivos, pero estos grupos pueden ser bastante raros en la práctica. ^[12] Las condiciones anteriores no garantizan nada en absoluto para los grupos que son "casi" cohesivos, lo que motiva la búsqueda de nociones más sólidas de JR que garanticen algo también para los grupos parcialmente cohesivos.

Una de esas nociones, que es muy común en la teoría de juegos cooperativos, es la estabilidad del núcleo (CS). ^[3] Significa que, para cualquier grupo de votantes con L cuotas (no necesariamente cohesivo), si este grupo se desvía y construye un comité más pequeño con L escaños, entonces para al menos un votante, el número de miembros del comité que aprueba no es mayor que en el comité original. La EJR puede verse como una variante débil de la CS, en la que solo se permite desviarse a los grupos L-cohesivos. La EJR requiere que, para cualquier grupo L-cohesivo, al menos un miembro no quiera desviarse, ya que su satisfacción actual ya es L, que es la máxima satisfacción posible con L representantes.

• A partir de 2023, queda abierta la pregunta de si siempre existirá un comité de CS.

Peters, Pierczyński y Skowron ^[13] presentan un debilitamiento diferente de la cohesión. Dados dos enteros L y B ≤ L , un grupo S de votantes se llama (L,B)-débilmente cohesivo si contiene al menos L cuotas, y hay un conjunto C de L candidatos, tal que cada miembro de S aprueba al menos B candidatos de C . Nótese que ( L , L )-débilmente cohesivo es equivalente a L-cohesivo. Un comité satisface la Representación Justificada Completa (FJR) si en cada grupo (L,B)-débilmente cohesivo, hay al menos un miembro que aprueba algunos ganadores de B. Claramente, FJR implica EJR.

• FJR siempre puede satisfacerse mediante la regla cohesiva codiciosa (que no es politemporal); está abierto si existen algoritmos politemporales que satisfagan FJR.

Brill y Peters ^[14] presentan un debilitamiento diferente de la cohesión. Dado un comité electo, definamos un grupo como L-privado si contiene al menos L cuotas y, además, al menos un candidato no electo es aprobado por todos los miembros. Un comité satisface EJR+ si para cada grupo de votantes L-privado, la satisfacción máxima es al menos L (al menos un miembro del grupo aprueba al menos L ganadores); un comité satisface PJR+ si para cada grupo L-privado, la unión de sus conjuntos de aprobación contiene algunos L ganadores. Claramente, EJR+ implica EJR y PJR+, y PJR+ implica PJR.

• PAV, local-search-PAV y MES satisfacen EJR+; las pruebas son las mismas que las pruebas originales, ya que las pruebas originales no utilizan cohesión; solo utilizan el hecho de que un candidato aprobado por todos los miembros del grupo no es elegido.
• También existe un algoritmo codicioso de múltiples tiempos que encuentra un comité EJR+: la Regla del Candidato Justificado Codicioso.
• PJR+ se puede verificar en tiempo polinomial mediante reducción a optimización submodular , a diferencia de PJR, que es coNP-difícil de verificar.
• La verificación de la EJR+ se puede realizar en tiempo polinomial mediante el siguiente algoritmo simple: para cada L entre 1 y k, y para cada candidato no electo c: contar el número de votantes que aprueban c y aprueban menos de L ganadores. Si el número de dichos votantes es al menos L cuotas, entonces el comité viola la EJR+.
• EJR+ satisface una forma débil de monotonía de comité : para todo k , hay un comité EJR+ W de tamaño k y un candidato no elegido c , de modo que sumar c a W da como resultado un comité EJR+ (de tamaño k +1).

Representación perfecta

Una propiedad diferente, no relacionada, es la representación perfecta (PER) . Significa que existe una asignación de cada votante a un único ganador aprobado por él, de modo que cada ganador representa exactamente a n / k votantes. Si bien puede no existir una representación perfecta, esperamos que, si existe, entonces será elegido por la regla de votación. ^[4]

• PER es compatible con PJR y JR: para cada instancia que admite una representación perfecta, existe un comité que satisface PJR. Sin embargo, PER no es compatible con EJR: hay instancias en las que existen representaciones perfectas, pero ninguna de ellas satisface EJR. PER se satisface con la regla de Monroe y con la regla de Leximax-Phragmen ^[10] , pero es violada por Greedy Monroe, PAV secuencial y PAV ^{[4] .}

Ver también: Representación totalmente proporcional .

Trascendencia

El siguiente diagrama ilustra las relaciones de implicación entre las distintas condiciones: SJR implica que AJR implica que EJR; CS implica que FJR implica que EJR; y EJR+ implica que EJR y PJR+. EJR implica que PJR, lo que implica que UJR y JR. UJR y JR no se implican entre sí.

EJR+ es incomparable a CS y a FJR. ^{[14] : Rem.2}

PER considera únicamente los casos en los que existe una representación perfecta. Por lo tanto, PER no implica, ni está implicado por, ninguno de los otros axiomas.

Verificación

Dadas las preferencias de los votantes y un comité específico, ¿podemos comprobar eficientemente si se satisface alguno de estos axiomas? ^[5]

• JR se puede verificar en tiempo polinomial;
• PJR y EJR son coNP-completos para verificar;
• PER es NP-difícil de verificar (decidir si existe una representación perfecta es NP-completo).

Satisfacción media - grado de proporcionalidad

La satisfacción de un votante, dado un determinado comité, se define como el número de miembros del comité aprobados por ese votante. La satisfacción media de un grupo de votantes es la suma de sus niveles de satisfacción, dividida por el tamaño del grupo. Si un grupo de votantes es L -cohesivo (es decir, su tamaño es al menos L * n / k y aprueban al menos L candidatos en común), entonces:

• Cada comité JR tiene un nivel de satisfacción promedio de al menos 1 - 1/ L + 1/( Ln ). Lo mismo se aplica a cada comité PJR.
• Cada comité de EJR tiene una satisfacción media de al menos ( L -1)/2. Esquema de la prueba : EJR garantiza a al menos un miembro de un grupo L -cohesivo una satisfacción de al menos L . Una vez que se elimina este miembro, el grupo restante es al menos ( L -1)-cohesivo, por lo que al menos un miembro restante tiene garantizada una satisfacción de al menos L -1. Procediendo de esta manera se obtiene una satisfacción media de L+(L-1)+..., que es mayor que ( L -1)/2.
• Por lo tanto, EJR ofrece una garantía de satisfacción en el peor de los casos mucho más sólida que PJR. ^[4]
• Todo comité con un promedio de satisfacción mayor a L -1 satisface EJR.

La votación por aprobación proporcional garantiza una satisfacción media mayor que L -1. Tiene una variante llamada Local-Search-PAV, que se ejecuta en tiempo polinomial y también garantiza una satisfacción media mayor que L -1 (por lo tanto, es EJR). ^{[5] : Teoría 1, Prop. 1} Esta garantía es óptima: para cada constante c > 0, no hay ninguna regla que garantice una satisfacción media de al menos L -1 + c (véase el Ejemplo 1 anterior). ^{[5] : Prop. 2}

Skowron ^[15] estudia el grado de proporcionalidad de las reglas de votación con múltiples ganadores: un límite inferior en la satisfacción promedio de todos los grupos de un cierto tamaño.

Número variable de ganadores

Freeman, Kahng y Pennock ^[16] adaptan el concepto de satisfacción media a la votación con múltiples ganadores, con un número variable de ganadores. Argumentan que los otros axiomas de JR no son atractivos con un número variable de ganadores, mientras que la satisfacción media es una noción más sólida. La adaptación implica los siguientes cambios:

• Cada votante obtiene satisfacción, no sólo de un candidato elegido que aprueba, sino también de un candidato no elegido que no aprueba (esto hace que el problema sea similar a la votación multitema , donde cada candidato es un tema binario).
• Un grupo es L-grande si contiene al menos L * n / m votantes (donde m es el número total de candidatos), y L-cohesivo si además los miembros del grupo están de acuerdo en la ubicación de al menos L candidatos (es decir: la intersección de A _i más la intersección de C \ A _i es al menos L ).
• Un comité es r-AS (r-satisfacción media) si para cada grupo L -cohesivo, la media de satisfacción de los miembros es al menos r*L . Las condiciones JR, PJR y EJR se generalizan de forma similar.
• La regla PAV elige un comité que maximiza la suma de Harmonic(sat _i ), donde sat _i es la satisfacción del votante i . La regla secuencial de Phragmen y el método de partes iguales dividen la carga de cada candidato electo entre los votantes que lo aprueban, y la carga de cada candidato no electo entre los votantes que no lo aprueban. Todas estas reglas satisfacen la PJR. MES viola la EJR; no se sabe si las otras dos la satisfacen.
• Una regla determinista no puede garantizar r -AS para r = (m-1)/m+epsilon, para cualquier epsilon > 0. PAV, Phragmen y MES no pueden garantizar r -AS para r = 1/2+epsilon. Pero existe una regla aleatoria que satisface (29/32)-AS.

Precio de la representación justificada

El precio de la representación justificada es la pérdida de satisfacción media debida a la exigencia de tener una representación justificada. Es análogo al precio de la justicia . ^[8]

Estudio empírico

Bredereck, Faliszewski, Kaczmarczyk y Niedermeier ^[12] realizaron un estudio experimental para comprobar cuántos comités satisfacen varios axiomas de representación justificada. Encontraron que los grupos cohesivos son raros y, por lo tanto, una gran fracción de los comités JR seleccionados al azar también satisfacen PJR y EJR.

Adaptaciones

Los axiomas de representación justificada se han adaptado a diversos entornos más allá de la simple votación de comités.

Votación de aprobación del partido

Brill, Golz, Peters, Schmidt-Kraepelin y Wilker adaptaron los axiomas de JR a la votación de aprobación de partidos . En este contexto, en lugar de aprobar candidatos individuales, los votantes deben aprobar partidos enteros. Este contexto es un punto intermedio entre las elecciones por lista de partidos, en las que los votantes deben elegir un solo partido, y la votación de aprobación estándar, en la que los votantes pueden elegir cualquier conjunto de candidatos. En la votación de aprobación de partidos, los votantes pueden elegir cualquier conjunto de partidos, pero no pueden elegir candidatos individuales dentro de un partido. Algunos axiomas de JR se adaptan a este contexto de la siguiente manera. ^[17]

Un grupo de votantes se denomina L-cohesivo si es L-grande y todos los miembros del grupo aprueban al menos un partido en común (a diferencia de la configuración anterior, no necesitan aprobar L partidos, ya que se supone que cada partido contiene al menos L candidatos y todos los votantes que aprueban el partido, automáticamente aprueban a todos estos candidatos). En otras palabras, un grupo L-cohesivo contiene L cuotas de votantes que están de acuerdo con al menos un partido:

• PJR significa que, por cada L ≥ 1, en cada grupo de votantes L -cohesionado, a los partidos en la unión de sus conjuntos de aprobación se les asignan al menos L escaños.
• EJR significa que, por cada número entero L ≥ 1, en cada grupo de votantes L -cohesionado, los partidos aprobados por al menos un votante obtienen al menos L escaños.
• CS significa que, para cualquier grupo de votantes de tamaño L * n / k votantes (no necesariamente cohesivo), si este grupo se desvía y construye un comité más pequeño con L escaños, entonces, para al menos un votante, el número de miembros del comité de los partidos que aprueba no es mayor que en el comité original.

El siguiente ejemplo ^[17] ilustra la diferencia entre CS y EJR. Supongamos que hay 5 partidos {a, b, c, d, e}, k = 16 escaños y n = 16 votantes con las siguientes preferencias: 4*ab, 3*bc, 1*c, 4*ad, 3*de, 1*e. Consideremos el comité con 8 escaños para el partido a, 4 para el partido c y 4 para el partido e. Los números de representantes de los votantes son: 8, 4, 4, 8, 4, 4. No es CS: consideremos el grupo de 14 votantes que aprueban ab, bc, ad, de. Pueden formar un comité con 4 escaños para el partido a, 5 escaños para el partido b y 5 escaños para el partido d. Ahora, los números de representantes son: 9, 5, [0], 9, 5, [0], por lo que todos los miembros de la coalición desviada están estrictamente más contentos. Sin embargo, el comité original satisface EJR. Téngase en cuenta que la cuota es 1. El L más grande para el cual existe un grupo L -cohesivo es L = 8 (los votantes ab y ad), y a este grupo se le asignan 8 escaños.

Elecciones basadas en el rango

El concepto de JR se origina a partir de un concepto anterior, introducido por Michael Dummett para las elecciones basadas en el rango. Su condición es que, para cada entero L ≥ 1, para cada grupo de tamaño al menos L * n / k , si clasifican a los mismos L candidatos en la parte superior, entonces estos L candidatos deben ser elegidos. ^[18]

Papeletas tricotómicas

Talmon y Page ^[19] extienden algunos axiomas de JR de las papeletas de aprobación a las papeletas tricotómicas (de tres opciones), lo que permite a cada votante expresar sentimientos positivos, negativos o neutrales hacia cada candidato. Presentan dos clases de generalizaciones: más fuertes ("Clase I") y más débiles ("Clase II").

Proponen algunas reglas de votación adaptadas a las papeletas tricotómicas y muestran mediante simulaciones hasta qué punto sus reglas satisfacen los axiomas JR adaptados.

Proporcionalidad degresiva y regresiva

La proporcionalidad degresiva (a veces, proporcionalidad progresiva) otorga a los grupos más pequeños más representantes de los que proporcionalmente les corresponden y es utilizada por el Parlamento Europeo . Por ejemplo, Penrose ha sugerido que cada grupo debería estar representado en proporción a la raíz cuadrada de su tamaño.

El extremo de la proporcionalidad degresiva es la diversidad , lo que significa que el comité debe representar a la mayor cantidad posible de votantes. La regla de votación de Chamberlin-Courant (CC) tiene como objetivo maximizar la diversidad. Estas ideas son particularmente atractivas para la democracia deliberativa , cuando es importante escuchar tantas voces diversas como sea posible.

Por otro lado, la proporcionalidad regresiva significa que a los grupos grandes se les debe dar una representación por encima de la proporcional. El extremo de la proporcionalidad regresiva es la excelencia individual , lo que significa que el comité debe contener miembros apoyados por el mayor número de votantes. ^{[9] : Sec.4.5} La regla de votación por aprobación en bloque (AV) maximiza la excelencia individual.

Lackner y Skowron ^[20] muestran que las reglas de votación de Thiele pueden utilizarse para interpolar entre proporcionalidad regresiva y degresiva: PAV es proporcional; las reglas en las que la pendiente de la función de puntuación es superior a la de PAV satisfacen la proporcionalidad regresiva; y las reglas en las que la pendiente de la función de puntuación es inferior a la de PAV satisfacen la proporcionalidad degresiva. Además, ^[21] si la puntuación de satisfacción del i -ésimo candidato aprobado es (1/ p ) ⁱ , para varios valores de p , obtenemos todo el espectro entre CC y AV.

Jaworski y Skowron ^[22] construyeron una clase de reglas que generalizan la regla de votación secuencial de Phragmén . Intuitivamente, se obtiene una variante degresiva al suponer que los votantes que ya tienen más representantes ganan dinero a un ritmo menor que los que tienen menos. La proporcionalidad regresiva se implementa al suponer que los candidatos que son aprobados por más votantes cuestan menos que los que obtuvieron menos aprobaciones.

Bienes divisibles

Bei, Lu y Suksompong ^[23] extienden el modelo de elección de comité a un contexto en el que hay un continuo de candidatos, representado por un intervalo real [0, c ], como en el corte de torta justo . El objetivo es seleccionar un subconjunto de este intervalo, con una longitud total de k como máximo , donde aquí k y c pueden ser cualquier número real con 0< k < c . Para generalizar las nociones de JR a este contexto, consideran grupos L -cohesivos para cualquier número real L (no necesariamente un entero): ^{[23] : App.A}

• EJR significa que, en cualquier grupo L-cohesivo, hay al menos un agente que aprueba un subconjunto de longitud al menos L de la pieza seleccionada.
• PJR significa que, para cualquier grupo L-cohesivo, la unión de sus conjuntos de aprobación contiene un subconjunto de longitud al menos L de la pieza seleccionada.

Consideran dos soluciones: la solución leximin no satisface ni PJR ni EJR, pero es veraz . Por el contrario, la regla de Nash, que maximiza la suma de log(u _i ), satisface EJR y, por lo tanto, PJR. Obsérvese que la regla de Nash puede verse como un análogo continuo de la votación de aprobación proporcional , que maximiza la suma de Harmonic(u _i ). Sin embargo, Nash no es veraz. La relación igualitaria de ambas soluciones es k /( n - nk+k ).

Lu, Peters, Aziz, Bei y Suksompong ^[24] extienden estas definiciones a configuraciones con candidatos mixtos divisibles e indivisibles: hay un conjunto de m candidatos indivisibles, así como una torta [0, c ]. La definición extendida de EJR, que permite grupos L-cohesivos con L no entero, puede ser inalcanzable. Definen dos relajaciones:

• EJR-M garantiza a cualquier grupo L-cohesivo, cuando hay un conjunto de recursos de tamaño total exactamente L , que al menos un miembro del grupo recibe una utilidad al menos L . EJR-M se reduce a EJR tanto en entornos con solo candidatos indivisibles como en entornos con solo un candidato divisible.
• EJR-b (para cualquier número real b) garantiza a cualquier grupo L-cohesivo que al menos un miembro del grupo recibe una utilidad mayor que Lb.

Demuestran que:

• Para cualquier b<1, EJR-b puede ser inalcanzable.
• La regla de Nash no satisface EJR-b para ningún b.
• Una regla llamada Greedy-EJR satisface EJR-M, pero se ejecuta en tiempo exponencial y tiene un grado de proporcionalidad ~ L /2.
• Una generalización de partes iguales satisface EJR-1 pero no EJR-M, pero satisface EJR para instancias solo divisibles y tiene un grado de proporcionalidad ~ L /2.
• Una generalización de PAV, utilizando una extensión analítica a la serie armónica, satisface EJR-1 pero no EJR-M, no satisface EJR para instancias solo divisibles y tiene un grado de proporcionalidad mayor que L -1.

Otras adaptaciones

• Bulteau, Hazon, Page, Rosenfeld y Talmon ^[25] adaptaron los axiomas de JR a la votación multitemática (también llamada: votación perpetua, toma de decisiones pública o toma de decisiones secuencial). Su trabajo fue ampliado posteriormente por Chandak, Sashwat y Peters. ^[26]
• Aziz, Lee y Talmon ^[27] adaptaron los axiomas de JR al presupuesto participativo .
• Brill, Laslier y Skowron ^[28] adaptaron JR a la proporcionalidad degresiva , asignando más peso a las minorías.
• Mavrov, Munagala y Shen ^[29] estudian el núcleo y los axiomas JR cuando existen restricciones en el comité.
• Munagala, Shen, Wang y Wang ^[30] estudian una aproximación multiplicativa del núcleo cuando los agentes pueden tener funciones de satisfacción no aditivas.

Véase también

• Proporcionalidad para coaliciones sólidas : un análogo de la representación proporcional para sistemas de votación con papeletas clasificadas.
• Representación totalmente proporcional : una condición que combina la representación proporcional y la rendición de cuentas.

Referencias

1. https://www.nytimes.com/2023/09/21/us/politics/politics-discontent.html
2. 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 . Lulu.com. ISBN 978-1-326-91209-3.{{cite book}}: CS1 maint: multiple names: authors list (link)
3. 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.
4. 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). arXiv : 1611.09928 . doi : 10.1609/aaai.v31i1.10611 . ISSN  2374-3468. S2CID  17538641.
5. Aziz, Haris; Elkind, Edith; Huang, Shenwei; Lackner, Martin; Sanchez-Fernandez, Luis; Skowron, Piotr (25 de abril de 2018). "Sobre la complejidad de la representación justificada extendida y proporcional". Actas de la Conferencia AAAI sobre Inteligencia Artificial . 32 (1). doi : 10.1609/aaai.v32i1.11478 . ISSN  2374-3468. S2CID  19124729.
6. Aziz, Haris; Bogomolnaia, Anna; Moulin, Hervé (17 de junio de 2019). "Mezcla justa: el caso de las preferencias dicotómicas" (PDF) . Actas de la Conferencia ACM de 2019 sobre economía y computación . EC '19. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 753–781. doi :10.1145/3328526.3329552. ISBN 978-1-4503-6792-9.S2CID 7436482  .
7. Grzegorz, Pierczyński; Piotr, Skowron; Dominik, Peters (6 de diciembre de 2021). "Presupuesto participativo proporcional con utilidades aditivas". Avances en sistemas de procesamiento de información neuronal . 34 . arXiv : 2008.13276 .
8. Elkind, Edith; Faliszewski, Piotr; Igarashi, Ayumi; Manurangsi, Pasin; Schmidt-Kraepelin, Ulrike; Suksompong, Warut (2024). "El precio de la representación justificada". ACM Transactions on Economics and Computation . 12 (3): 1–27. arXiv : 2112.05994 . doi :10.1145/3676953.
9. Lackner, Martin; Skowron, Piotr (2023). Votación de múltiples ganadores con preferencias de aprobación. Springer Nature. hdl :20.500.12657/60149. ISBN 978-3-031-09016-5.
10. 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. 
11. Sánchez-Fernández, Luis; Fernández, Norberto; Fisteus, Jesús A.; Genial, Markus (5 de septiembre de 2018). "El método de apoyo Maximin: una extensión del método D'Hondt a elecciones de múltiples ganadores basadas en la aprobación". arXiv : 1609.05370 [cs.GT].
12. Bredereck, Robert; Faliszewski, Piotr; Kaczmarczyk, Andrzej; Niedermeier, Rolf (10 de agosto de 2019). "Una visión experimental sobre los comités que proporcionan una representación justificada". Actas de la 28.ª Conferencia conjunta internacional sobre inteligencia artificial . IJCAI'19. Macao, China: AAAI Press: 109–115. ISBN 978-0-9992411-4-1.
13. Peters, Dominik; Pierczyński, Grzegorz; Skowron, Piotr (2021). "Presupuesto participativo proporcional con utilidades aditivas". Avances en sistemas de procesamiento de información neuronal . 34 . Curran Associates, Inc.: 12726–12737. arXiv : 2008.13276 .
14. Brill, Markus; Peters, Jannik (2023). "Axiomas de proporcionalidad robustos y verificables para la votación con múltiples ganadores". arXiv : 2302.01989 [cs.GT].
15. Skowron, Piotr (18 de julio de 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. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 820–840. arXiv : 1810.08799 . doi :10.1145/3465456.3467641. ISBN . 978-1-4503-8554-1. Número de identificación del sujeto  53046800.
16. Freeman, Rupert; Kahng, Anson; Pennock, David M. (7 de enero de 2021). "Proporcionalidad en elecciones basadas en la aprobación con un número variable de ganadores". Actas de la 29.ª Conferencia Conjunta Internacional sobre Inteligencia Artificial . IJCAI'20. Yokohama, Yokohama, Japón: 132–138. ISBN 978-0-9992411-6-5.
17. Brill, Markus; Gölz, Paul; Peters, Dominik; Schmidt-Kraepelin, Ulrike; Wilker, Kai (3 de abril de 2020). "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. ISSN  2374-3468. S2CID  208158445.
18. Dummett, Michael (1984). Procedimientos de votación. Oxford University Press, Reino Unido.
19. Talmon, Nimrod; Page, Rutvik (2021). "Proporcionalidad en la selección de comités con sentimientos negativos". arXiv : 2101.01435 [cs.GT].
20. Lackner, Martin; Skowron, Piotr (11 de junio de 2018). "Reglas de múltiples ganadores basadas en la aprobación consistente". Actas de la Conferencia ACM de 2018 sobre economía y computación . EC '18. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 47–48. arXiv : 1704.02453 . doi :10.1145/3219166.3219170. ISBN . 978-1-4503-5829-3.
21. Lackner, Martin; Skowron, Piotr (1 de noviembre de 2020). "Garantías utilitaristas de bienestar y representación de reglas de múltiples ganadores basadas en la aprobación". Inteligencia artificial . 288 : 103366. arXiv : 1801.01527 . doi :10.1016/j.artint.2020.103366. ISSN  0004-3702.
22. Jaworski, Michal; Skowron, Piotr (2022). "Reglas de Phragmén para proporcionalidad degresiva y regresiva". arXiv : 2201.04248 [cs.GT].
23. Bei, Xiaohui; Lu, Xinhang; Suksompong, Warut (28 de junio de 2022). "Compartir la torta con veracidad". Actas de la Conferencia AAAI sobre Inteligencia Artificial . 36 (5): 4809–4817. arXiv : 2112.05632 . doi :10.1609/aaai.v36i5.20408. ISSN  2374-3468.
24. Lu, Xinhang; Peters, Jannik; Aziz, Haris; Bei, Xiaohui; Suksompong, Warut (26 de junio de 2023). "Votación basada en la aprobación con bienes mixtos". Actas de la Conferencia AAAI sobre Inteligencia Artificial . 37 (5): 5781–5788. arXiv : 2211.12647 . doi : 10.1609/aaai.v37i5.25717 . ISSN  2374-3468.
25. Bulteau, Laurent; Hazon, Noam; Page, Rutvik; Rosenfeld, Ariel; Talmon, Nimrod (2021). "Representación justificada para el voto perpetuo". IEEE Access . 9 : 96598–96612. Bibcode :2021IEEEA...996598B. doi : 10.1109/ACCESS.2021.3095087 . ISSN  2169-3536. S2CID  235966019.
26. Chandak, Nikhil; Goel, Shashwat; Peters, Dominik (26 de junio de 2023). "Agregación proporcional de preferencias para la toma de decisiones secuencial". arXiv : 2306.14858 [cs.GT].
27. Aziz, Haris; Lee, Barton E.; Talmon, Nimrod (9 de julio de 2018). "Presupuesto participativo proporcionalmente representativo: axiomas y algoritmos". Actas de la 17.ª Conferencia internacional sobre agentes autónomos y sistemas multiagente . AAMAS '18. Richland, SC: Fundación Internacional para Agentes Autónomos y Sistemas Multiagente: 23–31. arXiv : 1711.08226 .
28. Brill, Markus; Laslier, Jean-François; Skowron, Piotr (1 de julio de 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. ISSN  0951-6298. S2CID  10535322.
29. Mavrov, Ivan-Aleksandar; Munagala, Kamesh; Shen, Yiheng (2023). "Elecciones justas con múltiples ganadores y restricciones de asignación". arXiv : 2305.02868 [cs.GT].
30. Munagala, Kamesh; Shen, Yiheng; Wang, Kangning; Wang, Zhiyi (2021). "Núcleo aproximado para la selección de comités mediante extensión multilineal y compensación de mercado". arXiv : 2110.12499 [cs.GT].