Votación sobre múltiples cuestiones

La votación sobre cuestiones múltiples es un escenario en el que se deben decidir varias cuestiones mediante votación . La votación sobre cuestiones múltiples plantea varias consideraciones que no son relevantes en la votación sobre una sola cuestión.

La primera consideración es lograr justicia tanto para la mayoría como para las minorías. Para ilustrarlo, considere un grupo de amigos que decide cada noche si ir al cine o a un restaurante. Supongamos que el 60% de los amigos prefiere el cine y el 40% prefiere el restaurante. En una votación única, el grupo probablemente aceptará la preferencia mayoritaria e irá al cine. Sin embargo, tomar la misma decisión una y otra vez cada día es injusto, ya que satisface al 60% de los amigos el 100% de las veces, mientras que el otro 40% nunca está satisfecho. Considerar este problema como una votación multitemática permite alcanzar una secuencia justa de decisiones yendo el 60% de las noches al cine y el 40% de las noches a un restaurante. El estudio de mecanismos de votación multitemática justa a veces se denomina toma de decisiones pública justa. ^[1] El caso especial en el que las diferentes cuestiones son decisiones en diferentes períodos de tiempo, y el número de períodos de tiempo no se conoce de antemano, se llama votación perpetua. ^{[2] [3] [4]}

La segunda consideración es la dependencia potencial entre los diferentes temas. Por ejemplo, supongamos que los temas son dos sugerencias para financiar proyectos públicos. Un votante puede apoyar la financiación de cada proyecto por separado, pero oponerse a la financiación de ambos proyectos simultáneamente, debido a su influencia negativa en el presupuesto de la ciudad. Si sólo hay unos pocos temas, es posible pedir a cada votante que clasifique todas las combinaciones posibles de candidatos. Sin embargo, el número de combinaciones aumenta exponencialmente en el número de temas, por lo que no es práctico cuando hay muchos temas. El estudio de este escenario a veces se llama votación combinatoria . ^[5]

Definiciones

Hay varias cuestiones sobre las que hay que decidir. Para cada cuestión t , hay un conjunto C _t de candidatos o alternativas entre los que elegir. Para cada cuestión t , se debe elegir un único candidato de C _t . Los votantes pueden tener diferentes preferencias con respecto a los candidatos. Las preferencias pueden ser numéricas ( votaciones cardinales ), jerarquizadas ( votaciones ordinales ) o binarias ( votaciones de aprobación ). En entornos combinatorios, los votantes pueden tener preferencias sobre combinaciones de candidatos.

Una regla de votación multitema es una regla que toma las preferencias de los votantes como entrada y devuelve el candidato elegido para cada tema. La votación multitema puede realizarse en línea o fuera de línea :

• En el entorno offline , las preferencias de los agentes se conocen de antemano sobre todos los temas, por lo que las decisiones sobre todos los temas se pueden tomar simultáneamente. Este entorno suele denominarse toma de decisiones pública .
• En el entorno en línea , las cuestiones representan decisiones en diferentes momentos; cada cuestión t ocurre en el momento t. Las preferencias de los votantes por la cuestión t se conocen solo en el momento t . Esta configuración se suele denominar votación perpetua . Una regla de votación perpetua es una regla que, en cada ronda t , toma como entrada las preferencias de los votantes, así como la secuencia de ganadores en las rondas 1,..., t -1, y devuelve un elemento de C _t que se elige en el momento t .
  • Algunos autores ^[6] distinguen entre un entorno semi-online , en el que se conoce de antemano el número de rondas y solo se desconocen las preferencias en cada ronda, y un entorno completamente en línea , en el que incluso se desconoce el número de rondas.

Preferencias cardinales

En las papeletas cardinales , cada votante asigna una utilidad numérica a cada alternativa en cada ronda. La utilidad total de un votante es la suma de las utilidades que asigna a los candidatos elegidos en cada ronda.

Votaciones de cardenales fuera de línea

Conitzer, Freeman y Shah ^[1] estudiaron la votación multitemática con papeletas cardinales fuera de línea (introdujeron el término toma de decisiones públicas ). Se centran en la equidad hacia los agentes individuales . Un requisito de equidad natural en este contexto es la división proporcional , por la cual cada agente debería recibir al menos 1/ n de su utilidad máxima. Dado que la proporcionalidad podría no ser alcanzable, sugieren tres relajaciones:

• Proporcionalidad hasta un tema (PROP1) : para cada votante, existe una ronda tal que, si la decisión en esa ronda cambiara hacia el mejor candidato del votante en esa ronda, el votante tendría su parte justa.
• Participación en el sistema round robin (RRS) : cada votante recibe al menos tanta utilidad como la que podría obtener si las rondas se dividieran mediante la asignación de ítems en el sistema round robin y él jugara el último.
• Participación proporcional pesimista (PPS) .

Estas relajaciones tienen sentido cuando el número de votantes es pequeño y el número de cuestiones es grande, por lo que una diferencia de una cuestión es pequeña con respecto a 1/ n . Muestran que la solución de Bienestar Máximo de Nash (maximizar el producto de las utilidades de todos los agentes) satisface o se aproxima a las tres relajaciones. También proporcionan algoritmos de tiempo polinomial y resultados de dureza para encontrar asignaciones que satisfacen estos axiomas, con o sin eficiencia de Pareto .

Votaciones de cardenales en línea

Freeman, Zahedi y Conitzer ^[7] estudian la votación multitemática con papeletas cardinales en línea . Presentan dos algoritmos voraces que apuntan a maximizar el bienestar de Nash a largo plazo (producto de las utilidades de todos los agentes). Evalúan sus algoritmos en datos recopilados de una aplicación de sistemas informáticos.

Preferencias de aprobación

Votación de aprobación offline: un candidato por ronda

La configuración más simple de votación de múltiples cuestiones es aquella en la que hay un conjunto de cuestiones y cada agente vota a favor o en contra de cada una de ellas (en efecto, hay un único candidato en cada ronda). Amanatidis, Barrot, Lang, Markakis y Ries ^[8] presentan varias reglas de votación para esta configuración, basadas en la distancia de Hamming :

• La regla utilitaria (a la que llaman "minisum") simplemente sigue el voto mayoritario de cada tema independientemente de los demás. Esta regla puede ser injusta para las minorías, pero es a prueba de estrategias .
• La regla igualitaria (a la que llaman "minimax") acepta un subconjunto de cuestiones que minimizan la distancia máxima de Hamming a las papeletas de los votantes (es decir, minimizan el desacuerdo). Podría decirse que esta regla otorga demasiado poder a las minorías; además, no es a prueba de estrategias.
• Se puede utilizar una familia de reglas basadas en el promedio ponderado ordenado para interpolar entre la regla utilitaria y la igualitaria. Esta familia permite alcanzar un equilibrio entre la equidad hacia las minorías y la protección contra estrategias.

Barrot, Lang y Yokoo ^[9] estudian la manipulabilidad de estas reglas basadas en OWA. Demuestran que la única regla OWA a prueba de estrategias con pesos no crecientes es la regla utilitaria. También estudian empíricamente una subfamilia de reglas basadas en OWA. Su familia se caracteriza por un parámetro p , que representa una propiedad llamada " orness " de la regla OWA. p = 0,5 produce AV utilitario, mientras que p = 1 produce AV igualitario. Demuestran empíricamente que aumentar p da como resultado una fracción mayor de perfiles aleatorios que pueden ser manipulados por al menos un votante.

Freeman, Kahng y Pennock ^[10] estudian la votación de aprobación con múltiples ganadores , con un número variable de ganadores. De hecho, tratan a cada candidato como una cuestión binaria (sí/no), por lo que su escenario puede verse como una votación de múltiples cuestiones con un candidato por ronda. Adaptan los conceptos de representación justificada a este escenario de la siguiente manera:

• Cada votante obtiene satisfacción no sólo de un candidato electo que aprueba, sino también de un candidato no electo que no aprueba (esto hace que el problema sea similar a la votación sobre múltiples cuestiones, donde cada candidato es una cuestión binaria).
• 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.

Skowron y Gorecki ^[11] estudian un escenario similar: votación multitema con votación de aprobación offline, donde en cada ronda t hay un solo candidato (una sola decisión sí/no). Su principal axioma de imparcialidad es la proporcionalidad : cada grupo de tamaño k debería poder influir al menos en una fracción k / n de las decisiones. Esto contrasta con los axiomas de representación justificada, que consideran solo grupos cohesivos . Esta diferencia es importante, ya que los estudios empíricos muestran que los grupos cohesivos son raros. ^[12] Formalmente, definen dos nociones de imparcialidad, para la votación sin abstenciones :

• Proporcionalidad : en cada grupo de tamaño k , la utilidad de al menos un votante debe ser mayor que ( m /2)*( k / n )-1. El factor multiplicativo de 1/2 es esencial; como un ejemplo simple, supongamos que n/2 votantes siempre votan "sí" y los otros n/2 votantes siempre votan "no". Entonces, cualquier regla justa debe decidir "sí" exactamente m /2 veces, por lo que la utilidad de cada votante sería m /2. Por lo tanto, para el grupo de todos los votantes ( k = n ), no podemos garantizar una utilidad mayor que ( m /2)*( k / n ).
• Representación media proporcional : una función d ( * ) tal que, en cada grupo de votantes con tamaño k , la satisfacción media es al menos d ( k / n )

Para votar con abstención, las definiciones deben adaptarse (ya que si todos los votantes se abstienen en todos los temas, su utilidad será necesariamente 0): en lugar de m , el factor cambia al número de temas en los que todos los miembros del grupo no se abstienen.

Estudian dos reglas:

• Voto aprobatorio proporcional (PAV) : sin abstenciones, garantiza la máxima representación media posible, que es d(r)=(m/2)*r-1; esto implica que es proporcional. Además, para grupos cohesionados tiene una representación media d(L) > 3L/4-1. Es proporcional también en votaciones con abstenciones.
• y el método de partes iguales (MES) : sin abstenciones, es proporcional y tiene una representación promedio d(r)>((m+1)/3)*r-1. Con abstenciones, la implementación ingenua del MES no es proporcional; pero tiene una variante que sí lo es (el método de subastas coordinadas con partes iguales).

Votación de aprobación offline: múltiples candidatos por ronda

Brill, Markakis, Papasotiropoulos y Jannik Peters ^[13] extendieron los resultados de Skowron y Gorecki a cuestiones con múltiples candidatos por ronda y posibles dependencias entre las cuestiones; véase más abajo, la subsección sobre Equidad en la votación combinatoria.

Page, Shapiro y Talmon ^[14] estudiaron un caso especial en el que los "temas" son los cargos del gabinete. Para cada cargo, hay un conjunto de candidatos; todos los conjuntos son disjuntos por pares. Cada votante debe votar por un solo candidato por cargo. El objetivo es elegir un solo ministro por cargo. A diferencia del contexto de toma de decisiones públicas, ^[1] aquí el número de votantes es grande y el número de temas es pequeño. Presentan dos generalizaciones de la propiedad de representación justificada :

• La generalización más débil es la representación justificada proporcional global (G-PJR) : para cada grupo S de agentes de tamaño Ln / k , cuyos conjuntos de aprobación en todos los cargos tienen una intersección no vacía, hay al menos L cargos en los que el candidato elegido es aprobado por al menos un miembro de S. Siempre existe una asignación G-PJR (usando un algoritmo cohesivo-codicioso en el tiempo superpolinomial), y es manejable con parámetros fijos con respecto al número de votantes.
• La generalización más fuerte es la representación justificada proporcional parcial (P-PJR) : para cada grupo S de agentes de tamaño Ln / x , cuyos conjuntos de aprobación en algunos x de k cargos tienen una intersección no vacía, hay al menos L cargos en los que el candidato elegido es aprobado por al menos un miembro de S. Siempre existe una asignación P-PJR (usando un algoritmo cohesivo-codicioso en el tiempo superpolinomial).

Generalizan el escenario considerando que diferentes cuestiones (cargos) tienen diferente peso (importancia, poder). Consideran tanto una función de poder objetiva como funciones de poder subjetivas . Para una función de poder objetiva, definen una generalización de la representación justificada, a la que llaman asignación de poder más importante . Luego presentan una versión codiciosa de PAV y muestran mediante simulaciones que garantiza una representación justificada a las minorías en muchos casos.

Votación de aprobación en línea: múltiples candidatos por ronda

En la votación de aprobación en línea, es común suponer que en cada ronda t hay múltiples candidatos; el conjunto de candidatos se denota por C _t . Cada votante j aprueba un subconjunto de A _t,j de C _t .

Martin Lackner ^[2] estudió la votación perpetua con papeletas de aprobación en línea y definió los siguientes conceptos:

• La satisfacción de un elector es el número de rondas en las que uno de sus candidatos aprobados es elegido.
• El apoyo de un votante en una ronda es la fracción de votantes que apoyan a uno de sus candidatos aprobados.
• La cuota de un votante es la suma de sus apoyos en todas las rondas anteriores.

Basándose en estos conceptos, definió tres axiomas de equidad:

1. Proporcionalidad simple - en cualquier caso simple, en el que cada agente vota por el mismo candidato cada vez, la satisfacción de cada agente debería ser al menos su cuota (esto significa que cada grupo de votantes que apoya al mismo candidato debería ver a su candidato elegido un número de veces proporcional al tamaño del grupo).
2. Independencia de las decisiones unánimes: si hay un tema en el que todos los votantes están de acuerdo, entonces la decisión sobre ese tema no debe afectar las decisiones futuras (este axioma evita manipulaciones obvias al añadir temas no controvertidos a la agenda).
3. Períodos de sequía acotados: cada votante debe estar satisfecho con al menos una decisión en un período de tiempo determinado (acotado). El límite puede depender del número de votantes.

También define dos propiedades cuantitativas:

1. Cumplimiento perpetuo de cuotas inferiores/superiores : la probabilidad de que un votante esté satisfecho con una fracción proporcional de las decisiones;
2. Coeficiente de influencia de Gini : la desigualdad en el grado de influencia de los diferentes votantes.

Definió una clase de reglas de votación perpetua, denominada votación de aprobación ponderada . A cada votante se le asigna un peso, que normalmente se inicializa en 1. En cada ronda, se elige al candidato con la suma más alta de pesos de aprobación (deshaciendo los empates mediante un orden fijo predefinido). Los pesos de los votantes que aprobaron al candidato ganador se reducen y los pesos de los demás votantes se incrementan. Algunos esquemas de ponderación comunes son:

• PAV perpetuo - como en la votación aprobatoria proporcional secuencial : el peso de un votante con satisfacción actual k es 1/( k +1). Satisface la proporcionalidad simple, pero no los períodos de sequía acotados ni el cumplimiento de cuotas.
• Coste unitario perpetuo: el peso de un votante satisfecho permanece igual mientras que el peso de un votante insatisfecho aumenta en 1. Por lo tanto, el peso de un votante con satisfacción actual k en el tiempo t es t - k .
• Reinicio perpetuo: el peso de un votante satisfecho cae a 1, mientras que el peso de un votante insatisfecho aumenta en 1.
• Igualdad perpetua: el peso de un votante con satisfacción k es n ^-k . Por lo tanto, el voto de un votante con satisfacción k es mayor que todos los votos de los votantes con una satisfacción mayor que k .
• Consenso perpetuo: el peso de un votante insatisfecho aumenta en 1. Los pesos de todos los votantes aumentan en 1; luego, el peso total de los votantes satisfechos disminuye n (el peso de cada votante satisfecho disminuye en n / s , donde s es el número de votantes satisfechos). Esta regla logra los mejores resultados en el análisis axiomático: es la única regla que satisface los tres axiomas (proporcionalidad simple, independencia de decisiones unánimes y períodos secos acotados: ningún agente tiene un período seco de longitud ( n ² +3 n )/4. Esta regla está relacionada con un método de distribución de Frege . ^[3]
• Regla de Phragmen perpetuo: en cada ronda, el presupuesto de cada votante aumenta continuamente hasta que un grupo de votantes puede "comprar" un candidato. Satisface la proporcionalidad simple y los períodos de sequía acotados: ningún agente tiene un período de sequía de longitud 2 n -1. Esta regla está relacionada con las reglas de votación de Phragmen . Se puede calcular en tiempo polinomial.
• Cuota perpetua: el peso de un votante es la diferencia entre la satisfacción de este votante y su cuota. Esta regla satisface la proporcionalidad simple y la independencia de las decisiones unánimes, pero no la sequía limitada. Sin embargo, funciona mejor en la evaluación experimental, en las dos métricas: cumplimiento perpetuo de la cuota inferior y coeficiente de influencia de Gini.
• Nash perpetuo: maximiza el producto de las puntuaciones de satisfacción de los votantes.

Maly y Lackner ^[3] analizan las clases generales de reglas de votación perpetua simples para votaciones de aprobación en línea y los axiomas que pueden satisfacerse con las reglas de cada clase. En particular, analizan el Phragmen perpetuo , la cuota perpetua y el consenso perpetuo.

Bulteau, Hazon, Page, Rosenfeld y Talmon ^[4] se centran en las nociones de equidad para grupos de votantes, en lugar de para votantes individuales. Adaptan algunas propiedades de representación justificada a este contexto. En particular, definen dos variantes de representación justificada proporcional (PJR). En ambas variantes, decimos que un grupo de agentes está de acuerdo en la ronda t si hay al menos un candidato en C _t que todos ellos aprueban.

• La variante más débil es all-periods-intersection-PJR . Requiere que, por cada grupo S de agentes de tamaño Ln / T que estén de acuerdo en todas las T rondas, haya al menos L rondas en las que el candidato elegido sea aprobado por al menos un miembro de S .
• La variante más fuerte es some-periods-intersection-PJR . Requiere que, por cada grupo S de agentes de tamaño Ln / k que están de acuerdo en algunas k de las T rondas, haya al menos L rondas en las que el candidato elegido sea aprobado por al menos un miembro de S . Esta variante es más fuerte, ya que no requiere que el grupo esté de acuerdo en todas las T rondas. Sin embargo, si están de acuerdo en menos rondas, entonces su "derecho" es proporcionalmente menor.

Demuestran que estos axiomas pueden cumplirse tanto en un contexto estático (donde las preferencias de los votantes son las mismas en cada ronda) como en un contexto dinámico (donde las preferencias de los votantes pueden cambiar entre rondas). También informan sobre un estudio en humanos para identificar qué resultados se consideran deseables a los ojos de la gente común.

Chandak, Goel y Peters ^[6] refuerzan ambos axiomas de PJR a EJR (la diferencia es que, en EJR, debe haber al menos L rondas en las que el candidato elegido sea aprobado por el mismo miembro de S ). Llaman a sus nuevos axiomas "EJR" y "strong-EJR". También adaptan tres reglas de votación a este contexto:

• La regla del Phragmen secuencial es completamente en línea: toma decisiones ronda por ronda y no necesita saber el número total de decisiones. Funciona de la siguiente manera. Para cada votante i , mantenemos una variable x _i , que llamamos la carga de i . Inicialmente, todas las cargas se establecen en 0. En cada ronda t , para cada candidato c en C _t , verificamos cómo dividir una carga total de 1 entre los votantes que aprueban c en esa ronda, de modo que la carga total máxima asignada a un solo votante sea lo más pequeña posible (en sentido figurado, uno puede pensar en cada votante como una botella llena con x _i litros de agua; tenemos que verter 1 litro de agua en las botellas que sostienen c , de modo que la altura máxima del agua sea lo más baja posible). En cada ronda t , elegimos al candidato para el cual la carga total máxima sea lo más pequeña posible. La regla se puede calcular en tiempo polinomial. La regla se puede calcular en tiempo polinomial. ^[3] Satisface la PJR fuerte (PJR de intersección de algunos períodos), pero falla incluso en la EJR débil (EJR de intersección de todos los períodos). ^{[6] : 4.1}
• El método de las partes iguales es semi-online –necesita saber el número total de rondas, pero aún funciona ronda por ronda. Para cada votante i , mantenemos una variable b _i , que llamamos el presupuesto de i . Inicialmente, todos los presupuestos se establecen en 1. En cada ronda t , para cada candidato c en C _t , verificamos cómo dividir un costo total de n / T entre los votantes que aprueban c en esa ronda. Elegimos al candidato por el cual el precio máximo que debe pagarse es lo más pequeño posible. Si, en alguna ronda t , ningún candidato es asequible para los votantes que lo aprueban, entonces elegimos un candidato que minimice la cantidad que deben pagar los votantes que no lo aprueban y ponga a cero el presupuesto de los votantes que lo aprueban. La regla se puede calcular en tiempo polinomial. Satisface la EJR débil, pero no la PJR fuerte (y la EJR fuerte).
• La votación por aprobación proporcional no está en línea. Elige la secuencia de decisión que maximiza el puntaje PAV, que es la suma de todos los votantes i del número armónico de candidatos electos aprobados por i . Satisface el EJR fuerte. Encontrar la secuencia óptima es NP-hard; sin embargo, utilizando la búsqueda local , es posible encontrar una secuencia localmente óptima que también satisfaga el EJR fuerte.
• Queda abierto si existe una regla completamente en línea que satisfaga la EJR (implicaría la existencia de una regla EJR que satisfaga la monotonía de House , que es otro problema abierto).
• Las variantes más fuertes de estas propiedades, en las que los grupos de votantes pueden tener un tamaño ligeramente menor o acordar menos rondas, pueden ser imposibles de satisfacer. ^{[6] : Sec.5}
• Compararon empíricamente varias reglas para su utilidad promedio ( valor utilitario ), utilidad percentil del 25% (inspirada en el valor igualitario ) y coeficiente de Gini . Para la utilidad promedio, la votación de aprobación utilitaria es la mejor; el orden entre las reglas proporcionales fue: PAV > Seq.Phragmen > MES > Cuota perpetua > Consenso perpetuo, pero las diferencias son pequeñas. Para el valor igualitario y el coeficiente de Gini, la votación de aprobación utilitaria es la peor; no hay una diferencia consistente entre las reglas proporcionales. Los conjuntos de datos fueron (a) aleatorios, (b) tomados de datos de votación de EE. UU., (c) tomados de modelos de aprendizaje automático entrenados en el conjunto de datos Moral Machine .

Votación perpetua de múltiples ganadores

Bredereck, Fluschnik y Kaczmarczyk ^[15] estudian la votación perpetua con múltiples ganadores : en cada ronda, cada votante vota por un solo candidato. El objetivo es elegir un comité de un tamaño determinado. Además, la diferencia entre el nuevo comité y el comité anterior debe ser limitada: en el modelo conservador, la diferencia está limitada desde arriba (dos comités consecutivos deben tener una ligera diferencia simétrica ), y en el modelo revolucionario, la diferencia está limitada desde abajo (dos comités sucesivos deben tener una diferencia simétrica considerable). Ambos modelos son NP-hard, incluso para un número constante de agentes.

Preferencias combinatorias

Una complicación en la votación sobre múltiples cuestiones es que puede haber dependencias entre las preferencias de los agentes sobre diferentes cuestiones. Por ejemplo, supongamos que las cuestiones sobre las que se debe decidir son diferentes tipos de alimentos que pueden darse en una comida. Supongamos que el pan puede ser negro o blanco y el plato principal puede ser hummus o tahini . Un agente puede querer pan negro con hummus o pan blanco con tahini, pero no al revés. Este problema se llama no separabilidad .

Obtener preferencias no separables

Existen varios enfoques para conocer las preferencias de los votantes cuando no son separables:

1. Si sólo hay unos pocos temas, es posible pedir a cada votante que clasifique todas las combinaciones posibles de candidatos. Sin embargo, el número de combinaciones aumenta exponencialmente con el número de temas, por lo que no es práctico cuando hay muchos temas. Hay algunas investigaciones sobre lenguajes para la representación concisa de las preferencias. ^[16]
2. Es posible preguntar por la alternativa favorita de cada votante en cada tema por separado. Esta opción es más simple, pero podría llevar a paradojas de elecciones múltiples, donde la decisión colectiva es peor para todos los agentes. Por ejemplo, supongamos que hay tres temas y para cada tema hay dos candidatos: 1 y 0. Supongamos que la primera opción de Alice es (1, 1, 0), la primera opción de Bob es (1, 0, 1), la primera opción de Chana es (0, 1, 1), y la última opción de todos los agentes es (1, 1, 1). Una mayoría que votara en cada tema por separado llevaría al resultado (1,1,1), que es peor para todos los votantes. ^[17]
3. En la votación secuencial , ^{[18] [19]} las cuestiones se deciden en orden, de modo que cada agente puede votar sobre una cuestión en función de los resultados de cuestiones decididas previamente. Este método es útil cuando existe un orden natural de dependencia de las cuestiones. Sin embargo, si algunas cuestiones dependen de decisiones en cuestiones futuras, los votantes tendrán dificultades para decidir qué votar. ^[20]
4. En la votación iterativa , ^{[21] [22]} preguntamos por la alternativa favorita de cada votante en cada tema por separado, pero les permitimos revisar su voto en función de los votos de otras personas. Los votantes pueden actualizar solo un tema a la vez. El problema es que la dinámica iterativa puede no converger. Sin embargo, en ciertos casos especiales, existe un equilibrio de Nash . ^[5] La votación iterativa puede mejorar el bienestar social y evitar algunas de las paradojas de las elecciones múltiples; esto se demostró tanto mediante simulaciones por computadora ^[23] como mediante experimentos de laboratorio. ^[24]

Lang y Xia (2016) ofrecen una encuesta sobre la votación en dominios combinatorios. ^[25]

Equidad en la votación combinatoria

Brill, Markakis, Papasotiropoulos y Jannik Peters ^[13] estudian la votación multitemática offline con un dominio no binario y las posibles dependencias entre las cuestiones, donde el objetivo principal es la representación justa. Definen generalizaciones de PAV y MES que manejan votaciones condicionales; las denominan PAV condicional y MES condicional . Demuestran que:

• Bajo diferentes supuestos, el PAV condicional y el MES condicional satisfacen la proporcionalidad alfa, para un alfa que depende del grado máximo de los gráficos de dependencia y del número máximo de candidatos por problema.
• Calcular el ganador del MES condicional es NP-hard incluso cuando todos los votantes tienen un gráfico de dependencia común; y cuando los votantes pueden tener diferentes gráficos de dependencia, incluso cuando el grado de entrada de cada gráfico de dependencia es constante. Pero con un gráfico de dependencia común y un grado de entrada acotado, el resultado se puede calcular en tiempo polinomial. Lo mismo ocurre si cada componente conectado del gráfico de dependencia global tiene como máximo un número constante de vértices.

Generalizaciones

Presupuesto participativo

Lackner, Maly y Rey ^[26] extienden el concepto de votación perpetua al presupuesto participativo . Una ciudad que aplica el sistema de presupuesto participativo todos los años puede querer asegurarse de que los resultados sean justos a lo largo del tiempo, no solo en cada aplicación individual.

Asignación justa de bienes públicos indivisibles

En la asignación justa de bienes públicos indivisibles (FAIPG) , la sociedad tiene que elegir un conjunto de bienes públicos indivisibles, donde existen restricciones de viabilidad sobre qué subconjuntos de elementos pueden elegirse. Fain, Munagala y Shah ^[27] se centran en tres tipos de restricciones:

• Restricciones de matroide : hay un matroide fijo M sobre los elementos, y los elementos elegidos deben formar una base de M. Este problema de toma de decisiones públicas justas ^[1] es un caso especial en el que cada tema es una categoría (que contiene todos los candidatos para ese tema) y hay una restricción de matroide de partición tal que se debe seleccionar un solo candidato para cada tema.
• Restricciones de coincidencia : hay un gráfico fijo G = ( V , E ), donde los elementos son los bordes y los elementos elegidos deben formar una coincidencia en G.
• Restricciones de empaquetamiento : hay una matriz fija A y un vector fijo b , y el vector indicador de los ítems x debe satisfacer la desigualdad A x ≤ b . El problema del presupuesto participativo es un caso especial en el que la matriz A tiene una sola fila que contiene los costos de los ítems, y b es el presupuesto. Las restricciones de empaquetamiento permiten un escenario de presupuesto más general, en el que hay diferentes tipos de recursos, cada uno de los cuales tiene un presupuesto diferente.

Fain, Munagala y Shah ^[27] presentan una noción de equidad para FAIPG, basada en el núcleo . Proporcionan algoritmos de tiempo polinomial que encuentran una aproximación aditiva al núcleo, con una pequeña pérdida multiplicativa. Con restricciones matroidales, la aproximación aditiva es 2. Con restricciones de coincidencia, hay un límite aditivo constante. Con restricciones de empaquetamiento, con restricciones leves, la aproximación aditiva es logarítmica en el ancho del politopo. Los algoritmos se basan en el programa convexo para maximizar el bienestar social de Nash.

Garg, Kulkarni y Murhekar ^[28] estudian FAIPG con restricciones presupuestarias. Muestran reducciones de tiempo polinomial para las soluciones de máximo bienestar de Nash y leximin, entre los modelos de bienes privados, bienes públicos y toma de decisiones públicas. Demuestran que las asignaciones de máximo bienestar de Nash son Prop1, RRS y Pareto-eficientes . Sin embargo, encontrar dichas asignaciones, así como las asignaciones leximin, es NP-difícil incluso con muchos agentes constantemente o valoraciones binarias. Diseñan algoritmos de tiempo pseudopolinomial para calcular una asignación MNW exacta o leximin-óptima para muchos agentes constantemente y para muchos bienes constantemente con valoraciones aditivas. También presentan una aproximación de O(n)-factor para máximo bienestar de Nash, que también satisface RRS, Prop1 y 1/2-Prop.

Banerjee, Gkatzelis, Hossain, Jin, Micah y Shah ^[29] estudian el FAIPG con predicciones: en cada ronda, llega un bien público, cada agente revela su valor para el bien y el algoritmo debe decidir cuánto invertir en el bien (sujeto a una restricción presupuestaria total). Hay predicciones aproximadas del valor total de cada agente para todos los bienes. El objetivo es lograr una equidad proporcional para los grupos. Con valoraciones binarias y presupuesto unitario, se puede lograr una equidad proporcional sin predicciones. Con valoraciones generales y presupuesto, las predicciones son necesarias para lograr una equidad proporcional.

Manipulación estratégica

Las reglas de votación que abordan múltiples cuestiones son propensas a la manipulación estratégica. Una forma particularmente simple de manipulación es el problema del oportunista : algunos votantes pueden oponerse falsamente a una opinión popular en una cuestión, para recibir una mayor consideración en otras cuestiones. Lackner, Maly y Nardi ^[30] estudian este problema en detalle. Demuestran que:

• Casi todas las reglas basadas en el promedio ponderado ordenado o en las reglas de Thiele , ya sea que utilicen optimización global o elecciones voraces secuenciales, son propensas al oportunismo. La única excepción es la regla utilitaria , que no es justa con las minorías.
• En el caso de la regla OWA o de la regla de Thiele basada en la optimización global (excepto la regla utilitaria), es NP-difícil calcular el resultado; además, incluso cuando se conoce al ganador de una cuestión, es NP-difícil determinar si es posible el parasitismo (es decir, si un solo agente puede retirar su aprobación al ganador sin cambiarlo). Sin embargo, el parasitismo nunca puede ser perjudicial.
• En el caso de las reglas secuenciales de OWA y Thiele, el cálculo del ganador de cada problema se puede realizar en tiempo polinomial y, por lo tanto, es fácil saber si es posible el oportunismo. Sin embargo, el oportunismo en un problema puede reducir la utilidad del oportunista en los problemas siguientes; es NP-difícil saber si esto sucederá o no y se requiere información completa sobre todos los problemas. Sin información completa, es imposible saber con certeza si el oportunismo es beneficioso o perjudicial.
• Los experimentos de simulación consideran variantes de las reglas de OWA y Thiele parametrizadas por un factor x ; x = 0 es la regla utilitaria, y un valor x mayor significa que la regla es más justa. A medida que x aumenta, la proporción de votantes que pueden beneficiarse del oportunismo aumenta de 0 a aproximadamente el 50%; pero la proporción de votantes que pueden perder por el oportunismo también aumenta, de 0 a más del 10%.

Véase también

• Votación de múltiples ganadores
• Votos almacenables : otra forma en que las minorías pueden obtener una parte justa del poder: almacenando votos estratégicamente y gastándolos más tarde.
• Votación dinámica ^{[31] [32]} : votación sobre un solo tema, en la que las preferencias de los votantes cambian con el tiempo.
• Dilema discursivo : contradicción entre las decisiones mayoritarias sobre cada asunto por separado y las decisiones mayoritarias sobre el resultado final.

Enlaces externos

• Código Python para algunas reglas y experimentos de votación perpetua

Referencias

1. Conitzer, Vincent; Freeman, Rupert; Shah, Nisarg (20 de junio de 2017). "Toma de decisiones públicas justa". Actas de la Conferencia ACM de 2017 sobre economía y computación . EC '17. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 629–646. arXiv : 1611.04034 . doi :10.1145/3033274.3085125. ISBN 978-1-4503-4527-9. Número de identificación del sujeto  30188911.
2. Lackner, Martin (3 de abril de 2020). "Votación perpetua: imparcialidad en la toma de decisiones a largo plazo". Actas de la Conferencia AAAI sobre Inteligencia Artificial . 34 (2): 2103–2110. doi : 10.1609/aaai.v34i02.5584 . ISSN  2374-3468. S2CID  209527302.
3. Lackner, Martin; Maly, Jan (30 de abril de 2021). "Voto perpetuo: la lente axiomática". arXiv : 2104.15058 [cs.GT].
4. 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.
5. Ahn, David S.; Oliveros, Santiago (2012). "Voto combinatorio". Econometrica . 80 (1): 89–141. doi :10.3982/ECTA9294. ISSN  0012-9682. JSTOR  41336582.
6. Chandak, Nikhil; Goel, Shashwat; Peters, Dominik (2023). "Agregación proporcional de preferencias para la toma de decisiones secuencial". arXiv : 2306.14858 [cs.GT].
7. Freeman, Rupert; Zahedi, Seyed Majid; Conitzer, Vincent (19 de agosto de 2017). Elección social justa y eficiente en entornos dinámicos. Melbourne, Australia: AAAI Press. pp. 4580–4587. ISBN 978-0-9992411-0-3.
8. Amanatidis, Georgios; Barrot, Nathanaël; Lang, Jérôme; Markakis, Evangelos; Ries, Bernard (4 de mayo de 2015). Referendos múltiples y elecciones con múltiples ganadores utilizando distancias de Hamming: complejidad y manipulación. Richland, SC: Fundación Internacional para Agentes Autónomos y Sistemas Multiagente. pp. 715–723. ISBN 978-1-4503-3413-6.
9. Barrot, Nathanaël; Lang, Jérôme; Yokoo, Makoto (8 de mayo de 2017). "Manipulación de la votación de aprobación basada en Hamming para referendos múltiples y elecciones de comités". Richland, SC: Fundación Internacional para Agentes Autónomos y Sistemas Multiagente: 597–605. {{cite journal}}: Requiere citar revista |journal=( ayuda )
10. 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. Yokohama, Yokohama, Japón. págs. 132–138. ISBN 978-0-9992411-6-5.{{cite book}}: Mantenimiento de CS1: falta la ubicación del editor ( enlace )
11. Skowron, Piotr; Górecki, Adrian (28 de junio de 2022). "Decisiones públicas proporcionales". Actas de la Conferencia AAAI sobre Inteligencia Artificial . 36 (5): 5191–5198. doi : 10.1609/aaai.v36i5.20454 . ISSN  2374-3468. S2CID  250293245.
12. Bredereck, Robert; Faliszewski, Piotr; Kaczmarczyk, Andrzej; Niedermeier, Rolf (10 de agosto de 2019). Una visión experimental sobre los comités que proporcionan representación justificada. Macao, China: Prensa AAAI. págs. 109-115. ISBN 978-0-9992411-4-1.
13. https://www.ijcai.org/proceedings/2023/0282.pdf
14. Page, Rutvik; Shapiro, Ehud; Talmon, Nimrod (2020). "Elección del poder ejecutivo". arXiv : 2009.09734 [cs.MA].
15. Bredereck, Robert; Fluschnik, Till; Kaczmarczyk, Andrzej (julio de 2022). "Cuando los votos cambian y los comités (no) deberían hacerlo" (PDF) . Actas de la 31.ª Conferencia Conjunta Internacional sobre Inteligencia Artificial . págs. 144–150. doi :10.24963/ijcai.2022/21. ISBN. 978-1-956792-00-3. S2CID  250636565 . Consultado el 27 de abril de 2023 .
16. Lang, Jérôme (6 de enero de 2007). "Voto y agregación en dominios combinatorios con preferencias estructuradas". Actas de la 20.ª Conferencia conjunta internacional sobre inteligencia artificial . IJCAI'07. San Francisco, CA, EE. UU.: Morgan Kaufmann Publishers Inc.: 1366–1371.
17. Lacy, Dean; Niou, Emerson MS (1 de enero de 2000). "Un problema con los referendos". Revista de política teórica . 12 (1): 5–31. doi :10.1177/0951692800012001001. ISSN  0951-6298. S2CID  153344141.
18. Lang, Jérôme; Xia, Lirong (1 de mayo de 2009). "Composición secuencial de reglas de votación en dominios multitemáticos". Ciencias Sociales Matemáticas . 57 (3): 304–324. doi :10.1016/j.mathsocsci.2008.12.010. ISSN  0165-4896. S2CID  35194669.
19. Xia, Lirong; Conitzer, Vincent; Lang, Jérôme (5 de junio de 2011). "Votación secuencial estratégica en dominios de múltiples cuestiones y paradojas de elecciones múltiples". Actas de la 12.ª conferencia de la ACM sobre comercio electrónico. EC '11. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 179–188. doi :10.1145/1993574.1993602. ISBN 978-1-4503-0261-6.S2CID6105649  .​
20. Conitzer, Vincent; Lang, Jérôme; Xia, Lirong (11 de julio de 2009). "¿Qué tan difícil es controlar las elecciones secuenciales a través de la agenda?". San Francisco, CA, EE. UU.: Morgan Kaufmann Publishers Inc.: 103–108. {{cite journal}}: Requiere citar revista |journal=( ayuda )
21. Meir, Reshef; Polukarov, María; Rosenschein, Jeffrey; Jennings, Nicolás (4 de julio de 2010). "Convergencia a los equilibrios en la votación plural". Actas de la Conferencia AAAI sobre Inteligencia Artificial . 24 (1): 823–828. doi : 10.1609/aaai.v24i1.7624 . ISSN  2374-3468. S2CID  15254323.
22. Kavner, Joshua; Meir, Reshef; Rossi, Francesca; Xia, Lirong (20 de enero de 2023). "Convergencia de la votación iterativa sobre múltiples cuestiones en condiciones de incertidumbre". arXiv : 2301.08873 [cs.GT].
23. Bowman, Clark; Hodge, Jonathan K.; Yu, Ada (1 de junio de 2014). "El potencial de la votación iterativa para resolver el problema de separabilidad en las elecciones de referéndum". Teoría y decisión . 77 (1): 111–124. doi :10.1007/s11238-013-9383-2. ISSN  1573-7187. S2CID  255110514.
24. Grandi, Umberto; Lang, Jérôme; Ozkes, Ali I.; Airiau, Stéphane (10 de diciembre de 2022). "Comportamiento electoral en referendos únicos e iterativos múltiples". Elección social y bienestar . doi :10.1007/s00355-022-01436-0. ISSN  1432-217X.
25. Lang, Jérôme; Xia, Lirong (2016). "Votación en dominios combinatorios". Manual de elección social computacional. págs. 197–222. doi :10.1017/CBO9781107446984.010. ISBN 9781107060432.
26. Lackner, Martin; Maly, Jan; Rey, Simon (3 de mayo de 2021). Equidad en el presupuesto participativo a largo plazo. Richland, SC: Fundación Internacional para Agentes Autónomos y Sistemas Multiagente. págs. 1566–1568. ISBN 978-1-4503-8307-3.
27. Fain, Brandon; Munagala, Kamesh; Shah, Nisarg (11 de junio de 2018). "Asignación justa de bienes públicos indivisibles". 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. 575–592. doi :10.1145/3219166.3219174. ISBN 978-1-4503-5829-3. Número de identificación del sujeto  3331859.
28. Garg, Jugal; Kulkarni, Pooja; Murhekar, Aniket (21 de julio de 2021). "Sobre la asignación justa y eficiente de bienes públicos indivisibles". arXiv : 2107.09871 [cs.GT].
29. Banerjee, Siddhartha; Gkatzelis, Vasilis; Hossain, Safwan; Jin, Billy; Micha, Evi; Shah, Nisarg (30 de septiembre de 2022). "Asignación proporcionalmente justa en línea de bienes públicos con predicciones". arXiv : 2209.15305 [cs.GT].
30. Lackner, Maly y Nardi. "El aprovechamiento gratuito de decisiones sobre cuestiones múltiples". Actas de la AAMAS 2023.
31. Tennenholtz, Moshe (17 de mayo de 2004). "Votación transitiva". Actas de la quinta conferencia de la ACM sobre comercio electrónico . EC '04. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 230–231. doi :10.1145/988772.988808. ISBN 978-1-58113-771-2.S2CID10062678  .​
32. Parkes, David; Procaccia, Ariel (30 de junio de 2013). "Elección social dinámica con preferencias en evolución". Actas de la Conferencia AAAI sobre Inteligencia Artificial . 27 (1): 767–773. doi : 10.1609/aaai.v27i1.8570 . ISSN  2374-3468. S2CID  12490400.