Votación de aprobación fraccionada

En la elección social fraccionaria , la votación de aprobación fraccionaria se refiere a una clase de sistemas electorales que utilizan papeletas de aprobación (cada votante selecciona una o más alternativas de candidato), en las que el resultado es fraccionario : para cada alternativa j hay una fracción p _j entre 0 y 1, de modo que la suma de p _j es 1. Puede verse como una generalización de la votación de aprobación : en esta última, un candidato gana ( p _j = 1) y los otros candidatos pierden ( p _j = 0). Las fracciones p _j pueden interpretarse de varias maneras, según el contexto. Algunos ejemplos son:

• Tiempo compartido : cada alternativa j se implementa una fracción p _j del tiempo (por ejemplo, cada candidato j sirve en el cargo una fracción p _j del mandato). ^[1]
• Distribución presupuestaria : cada alternativa j recibe una fracción p _j del presupuesto total. ^[2]
• Probabilidades : después de calcular los resultados fraccionarios, se realiza una lotería para seleccionar un solo candidato, donde cada candidato j es elegido con una probabilidad p _j . ^[1]
• Derechos : los resultados fraccionarios se utilizan como derechos (también llamados ponderaciones ) en reglas de reparto , ^[3] o en algoritmos de división justa con diferentes derechos .

La votación aprobatoria fraccionada es un caso especial de elección social fraccionada en el que todos los votantes tienen preferencias dicotómicas . Aparece en la literatura bajo muchos términos diferentes: lotería, ^[1] reparto, ^[4] repartición, ^[3] mezcla ^[5] y distribución. ^[2]

Definiciones formales

Hay un conjunto finito C de candidatos (también llamados: resultados o alternativas ), y un conjunto finito N de n votantes (también llamados: agentes ). Cada votante i especifica un subconjunto A _i de C , que representa el conjunto de candidatos que el votante aprueba .

Una regla de votación de aprobación fraccionaria toma como entrada el conjunto de conjuntos A _i , y devuelve como salida una mezcla (también llamada: distribución o lotería ) - un vector p de números reales en [0,1], un número para cada candidato, tal que la suma de los números es 1.

Se supone que cada agente i obtiene una utilidad de 1 de cada candidato en su conjunto de aprobación A _i , y una utilidad de 0 de cada candidato que no está en A _i . Por lo tanto, el agente i obtiene de cada mezcla p , una utilidad de . Por ejemplo, si la mezcla p se interpreta como una distribución presupuestaria, entonces la utilidad de i es el presupuesto total asignado a los resultados que le gustan. ${\displaystyle \sum _{j\in A_{i}}p_{j}}$

Propiedades deseadas

Propiedades de eficiencia

La eficiencia de Pareto (EP) significa que ninguna mezcla proporciona una utilidad mayor a un agente y al menos igual de alta a todos los demás.

La EP ex post es una propiedad más débil, relevante solo para la interpretación de una mezcla como una lotería. Significa que, después de la lotería, ningún resultado da una utilidad más alta a un agente y al menos una utilidad tan alta a todos los demás (en otras palabras, es una mezcla sobre los resultados de EP). Por ejemplo, supongamos que hay 5 candidatos (a, b, c, d, e) y 6 votantes con conjuntos de aprobación (ac, ad, ae, bc, bd, be). Seleccionar a cualquier candidato es EP, por lo que cada lotería es EP ex post. Pero la lotería que selecciona c, d, e con una probabilidad de 1/3 cada uno no es EP, ya que da una utilidad esperada de 1/3 a cada votante, mientras que la lotería que selecciona a, b con una probabilidad de 1/2 cada uno da una utilidad esperada de 1/2 a cada votante.

La EP siempre implica EP ex post. Lo contrario también es cierto en los siguientes casos:

• Cuando hay como máximo 4 electores, o como máximo 3 candidatos. ^{[4] : Lem.1, 2}
• Cuando los candidatos pueden ordenarse en una línea de tal manera que cada conjunto de aprobación sea un intervalo (de manera análoga a las preferencias de un solo pico ). ^{[5] : Lema 1}

Propiedades de equidad

Los requisitos de equidad se reflejan en variantes del concepto de participación justa (PC) .

Individual - FS ^[5] (también llamado Fair Welfare Share ^[1] ) significa que la utilidad de cada votante i es al menos 1/ n , es decir, al menos 1/ n del presupuesto se asigna a candidatos aprobados por i .

Individual-Outcome-FS ^[1] significa que la utilidad de cada votante i es al menos su utilidad en una lotería que selecciona un candidato aleatoriamente, es decir, al menos k /| C |, donde k es el número de candidatos aprobados por i .

• Los modelos de resultados individuales y de resultados individuales son insuficientes porque ignoran a grupos de votantes. Por ejemplo, si el 99% de los votantes aprueba X y el 1% aprueba Y, entonces ambas propiedades permiten dar la mitad del presupuesto a X y la otra mitad a Y. Esto es injusto para el grupo de partidarios de Y.

Voto único-FS (también llamado fiel ^[3] ) significa que, si cada votante aprueba a un solo candidato, entonces la fracción asignada a cada candidato j es igual al número de votantes que aprueban a j dividido por n .

• El voto único es un requisito básico, pero es insuficiente porque no dice nada sobre el caso en que los electores puedan aprobar a dos o más candidatos.

Unánime-FS ^[5] significa que, para cada conjunto S de votantes con preferencias idénticas , la utilidad de cada miembro en S es al menos | S |/ n.

• El sistema de aprobación unánime implica un sistema de aprobación con un solo voto, pero aún es insuficiente ya que no dice nada acerca de los grupos de agentes cuyos conjuntos de aprobación se superponen.

Grupo-FS ^{[1] : borrador de 2002} (también llamado reparto proporcional ^[4] ) significa que, para cada grupo de votantes S , el presupuesto total asignado a los candidatos aprobados por al menos un miembro de S , es al menos | S |/ n.

• El voto grupal implica el voto unánime, el voto único y el voto individual.
• El grupo-FS es equivalente a una propiedad llamada descomponibilidad : ^[2] es posible descomponer la distribución en n distribuciones de suma 1/ n , tales que la distribución recomendada al agente i sea positiva solo en candidatos aprobados por i .

La utilidad media-FS ^[5] significa que, para cada conjunto de votantes S con al menos un candidato aprobado en común, la utilidad media de los votantes en S es al menos | S |/ n.

Core-FS significa que, para cada conjunto de votantes S , no existe otra distribución de su presupuesto | S |/ n , lo que otorga a todos los miembros de S una utilidad mayor.

• Core-FS implica Group-FS.

Propiedades estratégicas

Se han estudiado varias variantes de la estrategia a prueba de errores (SP) para las reglas de votación:

• SP individual significa que un votante individual, que reporta preferencias poco sinceras, no puede obtener una utilidad mayor.
• SP de grupo débil significa que un grupo de votantes, que expresan preferencias poco sinceras en coordinación, no puede obtener una utilidad mayor para todos ellos.
• Grupo-SP significa que un grupo de votantes, que expresan preferencias insinceras en coordinación, no puede obtener una utilidad mayor para al menos uno de ellos, y al menos una utilidad igual de alta para todos ellos.
• La monotonía de preferencias significa que si un votante que antes no apoyaba a un candidato determinado X comienza a apoyar a X, las preferencias de los demás candidatos no aumentan. Esto implica preferencia individual.

Una variante más débil de SP es SP excluible . Es relevante en situaciones en las que es posible excluir a los votantes de utilizar algunas alternativas de los candidatos. Por ejemplo, si los candidatos se reúnen en horarios, entonces es posible excluir a los votantes de participar en la reunión en horarios que no aprueben. Esto hace que sea más difícil de manipular y, por lo tanto, el requisito es más débil. ^[5]

Propiedades de participación

Las normas deben alentar a los electores a participar en el proceso de votación. Se han estudiado varios criterios de participación :

• Participación débil : la utilidad de un votante cuando participa es al menos tan alta como su utilidad cuando no participa (esta es la negación de la paradoja de la no presentación ).
• Participación estricta : ^[5] la utilidad de un votante cuando participa es estrictamente mayor que la que obtiene cuando no participa. En particular, un votante se beneficia de participar incluso si tiene "clones" (votantes con preferencias idénticas).

Se requiere una propiedad más fuerte en los entornos de presupuesto participativo en los que el presupuesto a distribuir es donado por los propios votantes:

• Participación en fondo común : ^[6] la utilidad de un votante cuando dona a través del mecanismo es al menos tan alta como su utilidad cuando dona por su cuenta.

Normas

Regla utilitarista

La regla utilitaria tiene como objetivo maximizar la suma de utilidades y, por lo tanto, distribuye todo el presupuesto entre los candidatos aprobados por el mayor número de votantes. En particular, si hay un candidato con el mayor número de votos, entonces este candidato obtiene 1 (es decir, todo el presupuesto) y los demás obtienen 0, como en la votación de aprobación de un solo ganador . Si hay algunos k candidatos con el mismo mayor número de votos, entonces el presupuesto se distribuye equitativamente entre ellos, dando 1/ k a cada uno de esos candidatos y 0 a todos los demás. La regla utilitaria tiene varias propiedades deseables: ^{[1] : Prop.1} es anónima, neutral, EP, individual-SP y preferencia-monótona. También es fácil de calcular.

Sin embargo, no es justo para las minorías: viola el principio de equidad individual (así como todas las variantes más fuertes del principio de equidad). Por ejemplo, si el 51% de los votantes aprueba X y el 49% de los votantes aprueba Y, entonces la regla utilitarista otorga todo el presupuesto a X y ningún presupuesto a Y, por lo que el 49% que vota por Y obtiene una utilidad de 0. En otras palabras, permite la tiranía de la mayoría .

La regla utilitaria tampoco es una regla de grupo débil (y, por lo tanto, no es una regla de grupo débil). Por ejemplo, supongamos que hay 3 candidatos (a, b, c) y 3 votantes, cada uno de ellos aprueba a un solo candidato. Si votan sinceramente, entonces la mezcla utilitaria es (1/3, 1/3, 1/3) por lo que la utilidad de cada agente es 1/3. Si un solo votante vota de manera poco sincera (por ejemplo, el primero vota tanto por a como por b), entonces la mezcla es (0, 1, 0), lo que es peor para el votante poco sincero. Sin embargo, si dos votantes se confabulan y votan de manera poco sincera (por ejemplo, los dos primeros votantes votan por los dos primeros resultados), entonces la mezcla utilitaria es (1/2, 1/2, 0), lo que es mejor para ambos votantes poco sinceros.

Regla óptima de Nash

La regla óptima de Nash maximiza la suma de los logaritmos de las utilidades. Es anónima y neutral, y satisface las siguientes propiedades adicionales:

• Educación Física;
• Grupo-FS (descomponibilidad), Promedio-FS, Núcleo-FS; ^{[5] [7]}
• Participación conjunta (y participación estricta); ^[6]
• Ninguna otra propiedad de seguridad estratégica (falla incluso con SP excluible);

La regla óptima de Nash se puede calcular resolviendo un programa convexo . Existe otra regla, llamada utilitarista justa , que satisface propiedades similares (EP y grupo-FS) pero es más fácil de calcular. ^{[1] : Teoría 3 en el borrador de 2002}

Gobierno igualitario

La regla igualitaria (leximin) maximiza la utilidad más pequeña, luego la siguiente más pequeña, etc. Es anónima y neutral, y satisface las siguientes propiedades adicionales: ^[5]

• Educación Física;
• FS individual, pero no FS unánime;
• SP individual excluible, pero no SP individual;
• Participación débil, pero no estricta (ya que los "clones" – votantes con preferencias idénticas – son tratados como un solo votante).

Otras reglas del bienestar

Para cualquier función f que aumenta monótonamente , se puede maximizar la suma de f ( u _i ). La regla utilitaria es un caso especial donde f( x )= x , y la regla de Nash es un caso especial donde f( x )=log( x ). Toda regla de maximización de f es EP y tiene las siguientes propiedades adicionales: ^{[1] : Prop.5, 6, 7}

• Si f es cualquier función cóncava del logaritmo, entonces garantiza un FS individual.
• Si y sólo si f es la función logarítmica en sí, entonces garantiza un FS grupal y unánime (esto corresponde a la regla óptima de Nash).
• Si y sólo si f es una función lineal, entonces es SP individual (esto corresponde a la regla utilitaria).
• Si y sólo si se trata de la regla utilitaria o de la igualitaria, satisface la SP excluible;
• Si y sólo si NO es la regla utilitarista ni la igualitaria, satisface la participación estricta.

Reglas de prioridad

Una regla de prioridad (también llamada dictadura serial ) está parametrizada por una permutación de los votantes, lo que representa un orden de prioridad. Selecciona un resultado que maximiza la utilidad del agente de mayor prioridad; sujeto a eso, maximiza la utilidad del segundo agente de mayor prioridad; y así sucesivamente. Toda regla de prioridad es neutral, PE, SP de grupo débil y monótona de preferencia. Sin embargo, no es anónima y no satisface ninguna noción de equidad.

La regla de prioridad aleatoria selecciona una permutación de votantes de manera uniforme y aleatoria y luego implementa la regla de prioridad para esa permutación. Es anónima, neutral y satisface las siguientes propiedades adicionales: ^{[1] : Prop.5}

• PE ex post, pero no PE (ex ante).
  • En el caso análogo de las preferencias de un solo pico (los candidatos se ordenan en una línea y cada votante aprueba un intervalo), la prioridad aleatoria es PE. ^[5]
• Grupo débil-SP.
• Grupo-FS.

Una desventaja de esta regla es que es computacionalmente difícil encontrar las probabilidades exactas (ver Mecanismo de dictadura#Cálculo ).

Regla utilitarista condicional

En la regla utilitarista condicional , ^[5] cada agente recibe 1/ n del presupuesto total. Cada agente encuentra, entre los candidatos que aprueba, aquellos que son apoyados por el mayor número de otros agentes, y divide su presupuesto equitativamente entre ellos. Es anónimo y neutral, y satisface las siguientes propiedades adicionales:

• Individual-SP;
• Grupo-FS;
• PE ex post pero no PE (ex ante).
  • Es más eficiente que la prioridad aleatoria, tanto en teoría como en simulaciones.
  • Siempre encuentra una distribución que es PE entre el subconjunto de distribuciones de grupo-FS. ^[2]

Gobierno mayoritario

La regla mayoritaria ^[8] tiene como objetivo concentrar tanto poder como sea posible en manos de unos pocos candidatos, garantizando al mismo tiempo la imparcialidad. Se lleva a cabo en rondas. Inicialmente, todos los candidatos y votantes están activos. En cada ronda, la regla selecciona un candidato activo c que es aprobado por el conjunto más grande de votantes activos, N _c . Luego, la regla "asigne" estos votantes N _c a c , es decir, supone que los votantes en N _c votaron solo por c , y asigna a c la fracción |N _c |/n. Luego, el candidato c y los votantes en N _c se vuelven inactivos, y la regla procede a la siguiente ronda. Nótese que la regla utilitarista condicional es similar, excepto que los votantes en N _c no se vuelven inactivos.

La regla mayoritaria es anónima, neutral, garantiza el voto individual y el voto único. ^{[ aclaración necesaria ]}

Resultados de imposibilidad

Algunas combinaciones de propiedades no pueden obtenerse simultáneamente.

• La PE ex post y la SP grupal son incompatibles (para ≥3 votantes y ≥3 candidatos). ^{[1] : Prop.2}
• El anonimato, la neutralidad, la PE ex post y la SP débilmente agrupada son incompatibles (para ≥4 votantes y ≥6 candidatos). ^{[1] : Prop.3}
  • Si eliminamos una de estas propiedades, se pueden obtener las tres restantes.
• La PE ex post, la SP individual y la FS por resultado individual son incompatibles (para ≥3 votantes y ≥3 candidatos). ^{[1] : Prop.4}
  • Si eliminamos una de estas propiedades, se pueden obtener las dos restantes.
  • Sin embargo, si debilitamos el FS de resultado individual al permitir dar a cada agente solo ε veces su parte justa de resultado, para algún ε > 0, la imposibilidad permanece.
• El anonimato, la neutralidad, la PE, el SP individual y el FS individual son incompatibles (para ≥5 votantes y ≥17 candidatos). ^{[1] : Prop.6}
  • Si eliminamos PE o SP-individual o FS-individual, entonces se pueden obtener las cuatro propiedades restantes.
  • Si eliminamos el anonimato y la neutralidad, la imposibilidad sigue siendo válida, pero es mucho más difícil de probar. ^[2]
  • Por el contrario, en el análogo de las preferencias de un solo pico (los candidatos se ordenan en una línea y cada votante aprueba un intervalo), todas las propiedades se obtienen por prioridad aleatoria.
  • Si debilitamos el SP individual a SP excluible, las propiedades son satisfechas por la regla igualitaria.
  • No está claro si la PE y la SP excluible son compatibles con la participación estricta y/o la FS unánime. ^[5]
• La PE, la monotonía de preferencias y la participación positiva (una propiedad más débil que la FS individual) son incompatibles (para ≥6 votantes y ≥6 candidatos). ^{[1] : Prop.7}
• El anonimato, la neutralidad, la PE, el SP individual y el FS grupal son incompatibles (para ≥5 votantes y ≥4 candidatos). ^[4]
  • Si eliminamos PE o SP-individual o FS-grupal, entonces se pueden obtener las cuatro propiedades restantes.
  • Si eliminamos el anonimato y la neutralidad, la imposibilidad sigue siendo válida, pero es mucho más difícil de probar. ^[2]
  • Cuando hay como máximo 4 votantes o como máximo 3 candidatos, una variante simple de dictadura aleatoria cumple las 5 propiedades: se elige un dictador al azar y se elige el resultado más popular que le guste. Esta regla es anónima, neutral, EP ex post, SP individual, FS grupal y EP ex post; pero con como máximo 4 votantes o como máximo 3 candidatos, la EP ex post implica EP.
• El PE, el SP individual y el share positivo son incompatibles (para ≥6 votantes y ≥4 candidatos). Esto se demostró con la ayuda de un solucionador SAT que utiliza 386 perfiles diferentes. ^[2]
  • Con el anonimato y la neutralidad como propiedades adicionales, la incompatibilidad ya se cumple para ≥5 votantes y ≥4 candidatos, y la prueba es mucho más sencilla.

Tabla resumen

En la siguiente tabla, el número en cada celda representa la "fuerza" de la propiedad: 0 significa ninguna (la propiedad no se satisface); 1 corresponde a la variante débil de la propiedad; 2 corresponde a una variante más fuerte; etc.

Véase también

• Representación justificada : una propiedad similar a la de reparto justo, pero para resultados discretos.
• Votación de aprobación de partidos : los candidatos son partidos y la fracción asignada a cada partido corresponde a la fracción de escaños que debería obtener en el parlamento.
• Algoritmos de presupuesto participativo : otros enfoques para distribuir un presupuesto de manera justa.
• Algunos autores han estudiado el precio de la equidad de diversas reglas de distribución. ^{[9] [10]}
• El problema de la distribución también se ha estudiado en el contexto más desafiante en el que los agentes tienen utilidades aditivas . ^[11]

Referencias

1. Bogomolnaia, Anna; Moulin, Hervé; Stong, Richard (1 de junio de 2005). "Elección colectiva bajo preferencias dicotómicas" (PDF) . Revista de teoría económica . 122 (2): 165–184. doi :10.1016/j.jet.2004.05.005. ISSN  0022-0531.
2. Brandl, Florian; Brandt, Felix; Peters, Dominik; Stricker, Christian (18 de julio de 2021). "Reglas de distribución bajo preferencias dicotómicas: dos de tres no está mal". Actas de la 22.ª Conferencia de la ACM sobre economía y computación . EC '21. Nueva York, NY, EE. UU.: ACM. págs. 158–179. doi : 10.1145/3465456.3467653 . ISBN . 9781450385541. Número de identificación del sujeto  232109303.Un vídeo de la charla de la conferencia EC'21
3. 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.
4. Duddy, Conal (1 de enero de 2015). "Reparto justo bajo preferencias dicotómicas". Ciencias Sociales Matemáticas . 73 : 1–5. doi : 10.1016/j.mathsocsci.2014.10.005 . ISSN  0165-4896.
5. 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. Phoenix, AZ, EE. UU.: Association for Computing Machinery. págs. 753–781. doi :10.1145/3328526.3329552. ISBN 978-1-4503-6792-9.S2CID 7436482  .
6. Brandl, Florian; Brandt, Felix; Greger, Matthias; Peters, Dominik; Stricker, Christian; Suksompong, Warut (1 de octubre de 2021). "Financiación de proyectos públicos: un caso a favor de la regla del producto de Nash". Revista de economía matemática . 99 : 102585. arXiv : 2005.07997 . doi :10.1016/j.jmateco.2021.102585. S2CID  213188260.
7. A. Guerdjikova y K. Nehring (2014). "Ponderación de expertos, ponderación de fuentes" (PDF) .
8. Speroni di Fenizio, Pietro; Gewurz, Daniele A. (1 de abril de 2019). "El espacio de todos los sistemas de votación proporcional y el más mayoritario entre ellos". Elección social y bienestar . 52 (4): 663–683. doi : 10.1007/s00355-018-1166-9 . ISSN  1432-217X.
9. Michorzewski, Marcin; Peters, Dominik; Skowron, Piotr (3 de abril de 2020). "Precio de la justicia en la división presupuestaria y la elección social probabilística". Actas de la Conferencia AAAI sobre Inteligencia Artificial . 34 (2): 2184–2191. doi : 10.1609/aaai.v34i02.5594 . ISSN  2374-3468.
10. Tang, Zhongzheng; Wang, Chenhao; Zhang, Mengqi (2020). "Precio de la justicia en la división presupuestaria para el bienestar social igualitario". En Wu, Weili; Zhang, Zhongnan (eds.). Optimización combinatoria y aplicaciones . Apuntes de clase en informática. Vol. 12577. Cham: Springer International Publishing. págs. 594–607. arXiv : 2010.09637 . doi :10.1007/978-3-030-64843-5_40. ISBN 978-3-030-64843-5. Número de identificación del sujeto  224710712.
11. Fain, Brandon; Goel, Ashish; Munagala, Kamesh (2016). "El núcleo del problema del presupuesto participativo". En Cai, Yang; Vetta, Adrian (eds.). Web and Internet Economics . Apuntes de clase en informática. Vol. 10123. Berlín, Heidelberg: Springer. págs. 384–399. arXiv : 1610.03474 . doi :10.1007/978-3-662-54110-4_27. ISBN 978-3-662-54110-4.S2CID13443635  .​