Votación sobre múltiples temas

Conitzer, Freeman y Shah ^{[ 1 ]} estudiaron la votación sobre múltiples temas con papeletas cardinales fuera de línea (introdujeron el término toma de decisiones pública ). Se centran en la equidad hacia los agentes individuales . Un requisito natural de equidad 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 flexibilizaciones:

• Proporcionalidad hasta un tema (PROP1) : para cada votante, existe una ronda tal que, si la decisión en esa ronda cambiara al mejor candidato del votante en esa ronda, el votante tendría su parte justa.
• Reparto rotatorio (RRS) : cada votante recibe al menos tanta utilidad como la que podría obtener si las rondas se dividieran mediante la asignación rotatoria de elementos y él jugara la última.
• 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, de modo que una diferencia de una cuestión es pequeña con respecto a 1/ n . Demuestran que la solución de bienestar de Nash máximo (que maximiza 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 dificultad para encontrar asignaciones que satisfagan estos axiomas, con o sin eficiencia de Pareto .

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

El escenario de votación de múltiples temas más simple consiste en un conjunto de temas, donde cada agente vota a favor o en contra de cada tema (en efecto, hay un solo candidato en cada ronda). Amanatidis, Barrot, Lang, Markakis y Ries ^{[ 8 ]} presentan varias reglas de votación para este escenario, basadas en la distancia de Hamming :

• La regla utilitarista (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 manipulación estratégica .
• La regla igualitaria (que denominan «minimax») acepta un subconjunto de cuestiones que minimiza la distancia de Hamming máxima a las papeletas de los votantes (es decir, minimiza el desacuerdo). Esta regla podría, sin duda, otorgar demasiado poder a las minorías; además, no es inmune a la manipulación estratégica.
• Se puede utilizar una familia de reglas basada en el promedio ponderado ordenado para interpolar entre la regla utilitarista y la igualitaria. Esta familia permite lograr un equilibrio entre la equidad hacia las minorías y la resistencia a la manipulación estratégica.

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 utilitaria, mientras que p = 1 produce AV igualitaria. Muestran empíricamente que aumentar p resulta en una mayor fracción 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 y un número variable de ganadores. De hecho, tratan a cada candidato como una cuestión binaria (sí/no), por lo que su configuración puede considerarse como una votación de múltiples cuestiones con un candidato por ronda. Adaptan los conceptos de representación justificada a esta configuración de la siguiente manera:

• Cada votante obtiene satisfacción no solo de un candidato electo que aprueba, sino también de un candidato no electo que no aprueba (esto hace que el problema sea similar al de la votación sobre múltiples temas, 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 promedio) si para cada grupo L- cohesivo, el promedio de la satisfacción de los miembros es al menos r*L . Las condiciones JR, PJR y EJR se generalizan de manera 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 reparto equitativo 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 PJR. MES viola EJR; se desconoce 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 de múltiples temas con votación de aprobación fuera de línea, donde en cada ronda t hay un solo candidato (una sola decisión de sí/no). Su principal axioma de equidad 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 cohesionados . Esta diferencia es importante, ya que los estudios empíricos muestran que los grupos cohesionados son raros. ^{[ 12 ]} Formalmente, definen dos nociones de equidad 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 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 promedio proporcional : una función d ( * ) tal que, en cada grupo de votantes de tamaño k , la satisfacción promedio es al menos d ( k / n ).

Para la votación con abstenciones, 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 no se abstienen todos los miembros del grupo.

Estudian dos reglas:

• Votación de aprobación proporcional (VAP) : sin abstenciones, garantiza la máxima representación promedio posible, que es d(r)=(m/2)*r-1; esto implica que es proporcional. Además, para grupos cohesionados, tiene una representación promedio d(L) > 3L/4-1. También es proporcional 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).

Teh, Elkind y Neoh ^{[ 13 ]} estudian la optimización del bienestar utilitario y el bienestar igualitario en la toma de decisiones públicas con personas que prefieren la aprobación.

Brill, Markakis, Papasotiropoulos y Jannik Peters ^{[ 14 ]} 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 adelante la subsección sobre Equidad en la votación combinatoria .

Page, Shapiro y Talmon ^{[ 15 ]} estudiaron un caso especial en el que los "asuntos" son los cargos ministeriales. 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 la toma de decisiones públicas, ^{[ 1 ]} aquí el número de votantes es grande y el número de asuntos es pequeño. Presentan dos generalizaciones de la propiedad de representación justificada :

• La generalización más débil es la representación proporcional justificada 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 electo es aprobado por al menos un miembro de S. Siempre existe una asignación G-PJR (utilizando un algoritmo cohesivo-voraz de tiempo superpolinomial), y es tratable con parámetros fijos con respecto al número de votantes.
• La generalización más fuerte es la representación proporcional justificada parcial (P-PJR) : para cada grupo S de agentes de tamaño Ln / x , cuyos conjuntos de aprobación en algunas x de k oficinas tienen una intersección no vacía, hay al menos L oficinas en las que el candidato electo es aprobado por al menos un miembro de S. Siempre existe una asignación P-PJR (utilizando un algoritmo cohesivo-voraz de tiempo superpolinomial).

Generalizan el escenario considerando que los distintos temas (cargos) tienen diferente peso (importancia, poder). Consideran tanto una función de poder objetiva como subjetiva . Para la función de poder objetiva, definen una generalización de la representación justificada, a la que denominan asignación de poder más importante . A continuación, presentan una versión voraz de la asignación de poder justificada y demuestran mediante simulaciones que garantiza la representación justificada de las minorías en muchos casos.

En la votación de aprobación en línea, es común suponer que en cada ronda t hay varios 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 boletas de aprobación en línea . Definió los siguientes conceptos:

• La satisfacción de un votante se mide por el número de rondas en las que resulta elegido uno de sus candidatos aprobados.
• El apoyo de un votante en una ronda electoral determinada 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 sencillo, 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 existe un tema en el que todos los votantes están de acuerdo, entonces la decisión sobre ese tema no debería afectar las decisiones futuras (este axioma evita manipulaciones obvias al agregar temas poco controvertidos a la agenda).
3. Periodos de inactividad limitados: cada votante debe quedar satisfecho con al menos una decisión en un periodo de tiempo determinado (limitado). 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 generalmente se inicializa en 1. En cada ronda, se elige al candidato con la mayor suma de pesos de aprobación (los empates se resuelven según un orden fijo predefinido). Los pesos de los votantes que aprobaron al candidato ganador disminuyen, y los pesos de los demás votantes aumentan. Algunos esquemas de ponderación comunes son:

• El sistema de votación proporcional perpetua (PAV, por sus siglas en inglés) tiene como peso el voto de un elector con un nivel de satisfacción k = 1/( k + 1). Satisface la proporcionalidad simple, pero no los periodos de inactividad electoral limitados ni el cumplimiento de cuotas.
• Costo 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 disminuye 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 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 las decisiones unánimes y períodos de inactividad limitados: ningún agente tiene un período de inactividad de duración ( n ² +3 n )/4). Esta regla está relacionada con un método de reparto de Frege . ^{[ 3 ]}
• Phragmen perpetuo: en cada ronda, el presupuesto de cada votante aumenta continuamente hasta que algún grupo de votantes pueda "comprar" a un candidato. Satisface la proporcionalidad simple y los periodos de inactividad limitados: ningún agente tiene un periodo de inactividad de duración 2n - 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 su satisfacción y su cuota. Esta regla satisface la proporcionalidad simple y la independencia de las decisiones unánimes, pero no el período de sequía limitado. Sin embargo, en la evaluación experimental, ofrece los mejores resultados 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 clases generales de reglas de votación perpetuas simples para boletas de aprobación en línea y estudian los axiomas que pueden satisfacer las reglas de cada clase. En particular, analizan Perpetual Phragmen , Perpetual Quota y Perpetual Consensus.

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 aprueban.

• La variante más débil es all-periods-intersection-PJR . Requiere que, para 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, para cada grupo S de agentes de tamaño Ln / k que coinciden en k de las T rondas, haya al menos L rondas en las que el candidato electo sea aprobado por al menos un miembro de S. Esta variante es más fuerte, ya que no requiere que el grupo coincida en las T rondas. Sin embargo, si coinciden en menos rondas, su "derecho" es proporcionalmente menor.

Demuestran que estos axiomas se cumplen tanto en un escenario estático (donde las preferencias de los votantes son las mismas en cada ronda) como en uno dinámico (donde las preferencias de los votantes pueden cambiar entre rondas). Además, presentan un estudio realizado con participantes humanos para identificar qué resultados se consideran deseables para 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 electo sea aprobado por el mismo miembro de S ). Llaman a sus nuevos axiomas "EJR" y "EJR fuerte". También adaptan tres reglas de votación a este contexto:

• La regla de Fragmentos Secuenciales 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 a c en esa ronda, de manera que la carga total máxima asignada a un solo votante sea lo más pequeña posible (figurativamente, se 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 a c , de manera 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 es lo más pequeña posible. La regla se puede calcular en tiempo polinomial. La regla se puede calcular en tiempo polinomial. ^{[ 3 ]} Satisface PJR fuerte (PJR de intersección de algunos períodos), pero falla incluso EJR débil (EJR de intersección de todos los períodos). ^{[ 6 ] : 4.1}
• El método de reparto equitativo es semi-en línea: necesita conocer el número total de rondas, pero aun así 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 a c en esa ronda. Elegimos al candidato para 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 minimiza la cantidad que deben pagar los votantes que no lo aprueban, y ponemos a cero el presupuesto de los votantes que lo aprueban. La regla se puede calcular en tiempo polinomial. Satisface la regla débil de reparto equitativo (EJR), pero no la regla fuerte de reparto equitativo (PJR) (ni la regla fuerte de reparto equitativo, EJR).
• El sistema de votación por aprobación proporcional funciona fuera de línea. Selecciona la secuencia de decisiones que maximiza la puntuación PAV, que es la suma, sobre todos los votantes i, del número armónico del número de candidatos electos aprobados por i . Satisface la regla de la elección equitativa fuerte (strong-EJR). Encontrar la secuencia óptima es un problema NP-difícil; sin embargo, mediante una búsqueda local , es posible encontrar una secuencia localmente óptima que también satisfaga la regla de la elección equitativa fuerte.
• Queda por determinar si existe una regla totalmente en línea que satisfaga EJR (lo que implicaría la existencia de una regla EJR que satisfaga la monotonicidad de House , que es otro problema abierto).
• Las variantes más estrictas de estas propiedades, donde los grupos de votantes pueden tener un tamaño ligeramente menor o ponerse de acuerdo en menos rondas, pueden ser imposibles de satisfacer. ^{[ 6 ] : Sec.5}
• Compararon empíricamente varias reglas para su utilidad promedio ( valor utilitario ), utilidad del percentil 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 de Moral Machine .

Bredereck, Fluschnik y Kaczmarczyk ^{[ 16 ]} estudian la votación perpetua con múltiples ganadores : en cada ronda, cada votante vota por un único candidato. El objetivo es elegir un comité de un tamaño determinado. Además, la diferencia entre el nuevo comité y el anterior debe estar acotada: en el modelo conservador, la diferencia está acotada superiormente (dos comités consecutivos deben tener una ligera diferencia simétrica ), y en el modelo revolucionario , la diferencia está acotada inferiormente (dos comités sucesivos deben tener una diferencia simétrica considerable). Ambos modelos son NP-difíciles, incluso para un número constante de agentes.

Existen varios métodos para obtener las preferencias de los votantes cuando estas no son separables:

1. Si hay 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. Existen algunas investigaciones sobre lenguajes para la representación concisa de preferencias. ^{[ 17 ]}
2. Es posible solicitar la alternativa preferida de cada votante para cada tema por separado. Esta opción es más sencilla, pero podría dar lugar a paradojas de elecciones múltiples, donde la decisión colectiva es la peor para todos los agentes. Por ejemplo, supongamos que hay tres temas y que para cada tema hay dos candidatos: 1 y 0. Supongamos que la primera opción de Alice es (1, 1, 0), la de Bob es (1, 0, 1) y la de Chana es (0, 1, 1), y la última opción de todos los agentes es (1, 1, 1). Una votación mayoritaria para cada tema por separado daría como resultado (1,1,1), que es la peor para todos los votantes. ^{[ 18 ]}
3. En la votación secuencial , ^{[ 19 ] [ 20 ]} los temas se deciden en orden, de modo que cada agente puede votar sobre un tema basándose en los resultados de los temas previamente decididos. Este método es útil cuando existe un orden natural de dependencia entre los temas. Sin embargo, si algunos temas dependen de decisiones en temas futuros, a los votantes les resultará difícil decidir qué votar. ^{[ 21 ]}
4. En la votación iterativa , ^{[ 22 ] [ 23 ]} solicitamos a cada votante su alternativa favorita para cada tema por separado, pero les permitimos revisar su voto en función de los votos de los demás. Los votantes solo pueden actualizar un tema a la vez. El problema es que la dinámica iterativa podría no converger. Sin embargo, en ciertos casos especiales, existe un equilibrio de Nash . ^{[ 5 ]} La votación iterativa puede mejorar el bienestar social y prevenir algunas de las paradojas de las elecciones múltiples; esto se ha demostrado tanto mediante simulaciones por ordenador ^{[ 24 ]} como mediante experimentos de laboratorio. ^{[ 25 ]}

^{Lang y Xia, 2016 [ 26 ]} presentan un estudio sobre la votación en dominios combinatorios.

Brill, Markakis, Papasotiropoulos y Jannik Peters ^{[ 14 ]} estudian la votación fuera de línea de múltiples temas con un dominio no binario y posibles dependencias entre los temas, donde el objetivo principal es la representación justa. Definen generalizaciones de PAV y MES que manejan boletas condicionales; las llaman PAV condicional y MES condicional . Demuestran que:

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

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

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

• Restricciones de matroid : 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 asunto es una categoría (que contiene todos los candidatos para ese asunto), y hay una restricción de matroide de partición tal que se debe seleccionar un único candidato para cada asunto.
• Restricciones de coincidencia : hay un grafo fijo G = ( V , E ), donde los elementos son las aristas, y los elementos elegidos deben formar una coincidencia en G.
• Restricciones de empaquetamiento : existe una matriz fija A y un vector fijo b , y el vector indicador de los elementos 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 elementos, y b es el presupuesto. Las restricciones de empaquetamiento permiten un entorno presupuestario más general, en el que existen diferentes tipos de recursos, cada uno con un presupuesto distinto.

Fain, Munagala y Shah ^{[ 28 ]} 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 de matroide, la aproximación aditiva es 2. Con restricciones de emparejamiento, hay una cota aditiva 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 ^{[ 29 ]} estudian FAIPG con restricciones presupuestarias. Muestran reducciones de tiempo polinomial para las soluciones de bienestar de Nash máximo y leximin, entre los modelos de bienes privados, bienes públicos y toma de decisiones públicas. Demuestran que las asignaciones de bienestar de Nash máximo son Prop1, RRS y Pareto-eficientes . Sin embargo, encontrar tales asignaciones, así como las asignaciones leximin, es NP-difícil incluso con un número constante de agentes o valoraciones binarias. Diseñan algoritmos de tiempo pseudopolinomial para calcular una asignación MNW o leximin-óptima exacta para un número constante de agentes y para un número constante de bienes con valoraciones aditivas. También presentan una aproximación de factor O(n) para el bienestar de Nash máximo, que también satisface RRS, Prop1 y 1/2-Prop.

Banerjee, Gkatzelis, Hossain, Jin, Micah y Shah ^{[ 30 ]} estudian 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 él (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, la equidad proporcional se puede lograr sin predicciones. Con valoraciones y presupuesto generales, las predicciones son necesarias para lograr la equidad proporcional.