El presupuesto participativo combinatorio, [1] también llamado presupuesto participativo indivisible [2] o elección social presupuestada , [3] es un problema de elección social . Hay varios proyectos candidatos , cada uno de los cuales tiene un costo fijo. Hay un presupuesto fijo , que no puede cubrir todos estos proyectos. Cada votante tiene diferentes preferencias con respecto a estos proyectos. El objetivo es encontrar una asignación presupuestaria , un subconjunto de los proyectos, con un costo total como máximo del presupuesto, que se financiará. El presupuesto participativo combinatorio es la forma más común de presupuesto participativo .
El PP combinatorio puede verse como una generalización de la votación del comité : la votación del comité es un caso especial de PP en el que el "costo" de cada candidato es 1, y el "presupuesto" es el tamaño del comité. Este supuesto se denomina a menudo el supuesto del coste unitario . El contexto en el que los proyectos son divisibles (pueden recibir cualquier cantidad de dinero) se denomina reparto, [4] [5] elección social fraccionaria o agregación de presupuesto-propuesta .
Las normas de presupuesto participativo tienen otras aplicaciones además de la elaboración adecuada de presupuestos. Por ejemplo: [6]
Una clase de reglas tiene como objetivo maximizar una función de bienestar social dada . En particular, la regla utilitaria tiene como objetivo encontrar una asignación presupuestaria que maximice la suma de las utilidades de los agentes. [7] Con la votación cardinal, encontrar una asignación presupuestaria utilitaria requiere resolver un problema de mochila , que es NP-hard en teoría pero se puede resolver fácilmente en la práctica. También hay algoritmos voraces que logran una aproximación de factor constante del bienestar máximo.
Existen muchas funciones de utilidad posibles para una papeleta determinada : [2] [8]
Sreedurga, Bhardwaj y Narahari estudian la regla igualitaria , que tiene como objetivo maximizar la utilidad más pequeña de un agente. [9] Demuestran que encontrar una asignación presupuestaria igualitaria es NP-hard, pero dan algoritmos de tiempo pseudo-polinomial y de tiempo polinomial cuando algunos parámetros naturales son fijos . Proponen un algoritmo que logra una aproximación aditiva para espacios restringidos de instancias, y muestran que da soluciones óptimas exactas en conjuntos de datos del mundo real. También prueban que la regla igualitaria satisface un nuevo axioma de equidad, al que llaman cobertura máxima .
Annick Laruelle estudia la maximización del bienestar en el marco de una votación ordinal débil, en la que se utiliza una regla de puntuación para traducir la clasificación en utilidad. Estudia una aproximación codiciosa al bienestar utilitarista y al bienestar de Chamberlin-Courant. Pon a prueba tres algoritmos con datos reales del PP de Portugalete en 2018; los resultados muestran que el algoritmo que incluye los costes del proyecto en la votación funciona mejor que los otros dos. [10]
Fluschnik, Skowron, Triphaus y Wilker estudian la maximización del bienestar utilitarista, el bienestar de Chamberlin-Courant y el bienestar de Nash, asumiendo utilidades cardinales. [11]
El método de presupuestación más común en la práctica es una solución codiciosa a una variante del problema de la mochila : los proyectos se ordenan por orden decreciente del número de votos que recibieron y se seleccionan uno por uno hasta que se agote el presupuesto. Alternativamente, si el número de proyectos es suficientemente pequeño, el problema de la mochila se puede resolver de manera exacta, seleccionando un subconjunto de proyectos que maximice la felicidad total de los ciudadanos. [12] [13] Dado que este método (llamado "el mejor de cada individuo") podría ser injusto para los grupos minoritarios, sugieren dos alternativas más justas:
Desafortunadamente, para los dominios de utilidad general, ambas reglas son NP-difíciles de calcular. [11] Sin embargo, la mochila diversa es resoluble polinomialmente en dominios de preferencia específicos, o cuando el número de votantes es pequeño.
La votación aprobatoria proporcional es una regla para la votación con múltiples ganadores, que fue adaptada al sistema PB por Pierczynski, Peters y Skowron. [6] Elige una regla que maximiza la puntuación total , que se define por una función armónica de la satisfacción basada en la cardinalidad. No es muy popular, ya que en el contexto del sistema PB no satisface las fuertes garantías de proporcionalidad como en el contexto de la votación con múltiples ganadores. [14]
En las reglas de compra secuencial, cada proyecto de un candidato debe ser "comprado" por los votantes, utilizando alguna moneda virtual. Se conocen varias reglas de este tipo.
Este método se describe en las reglas de Phragmen para las elecciones de comités . Los, Christoff y Grossi lo describen para las votaciones de aprobación como un proceso continuo: [14]
Esta regla es una adaptación de la regla secuencial de Phragmen, que permite una redistribución de las cargas en cada ronda. Fue introducida por primera vez como una regla de votación de múltiples ganadores por Sánchez-Fernández, Fernández-García, Fisteus y Brill. [15] Fue adaptada a PB por Aziz, Lee y Talmon (aunque la llaman 'regla de Phragmen'). [16] También presentan un algoritmo eficiente para calcularla.
Este método generaliza el método de las partes iguales para las elecciones de comités. La generalización al sistema de votación por partes iguales con papeletas cardinales fue realizada por Pierczynski, Peters y Skowron. [6]
Shapiro y Talmon [17] presentan un algoritmo de tiempo polinomial para hallar una asignación presupuestaria que satisfaga el criterio de Condorcet : la asignación presupuestaria seleccionada debe ser al menos tan buena como cualquier otro presupuesto propuesto, según la mayoría de los votantes (ningún cambio propuesto tiene el apoyo de la mayoría de los votantes). Su algoritmo utiliza conjuntos de Schwartz .
Skowron, Slinko, Szufa y Talmon presentan una regla llamada transferencias mínimas sobre costos que extiende el voto único transferible al presupuesto participativo. [18]
Aziz y Lee presentan una regla llamada regla de aprobaciones en expansión que utiliza el . [19] Pierczynski, Peters y Skowron presentan una variante del método de partes iguales para votaciones ordinales débiles y muestran que es una regla de aprobaciones en expansión.
Una consideración importante a la hora de elaborar un presupuesto es ser justo tanto con los grupos mayoritarios como con los minoritarios. Para ilustrar el desafío, supongamos que el 51% de la población vive en el norte y el 49% en el sur, y que todos los presupuestos posibles... supongamos que hay 10 proyectos en el norte y 10 proyectos en el sur, cada uno de ellos cuesta 1 unidad y el presupuesto disponible es de 10. La votación de los presupuestos por mayoría simple dará como resultado que se seleccionen los 10 proyectos en el norte, sin proyectos en el sur, lo que es injusto para los sureños. [11]
Para abordar parcialmente este problema, muchos municipios llevan a cabo un proceso de participación ciudadana independiente en cada distrito, para garantizar que cada uno reciba una representación proporcional. Pero esto introduce otros problemas. Por ejemplo, los proyectos en los límites de dos distritos sólo pueden ser votados por un distrito, y por lo tanto pueden no ser financiados incluso si son apoyados por muchas personas del otro distrito. Además, los proyectos sin una ubicación específica, que benefician a toda la ciudad, no pueden ser gestionados. Además, hay grupos que no son geográficos, como los padres o los ciclistas. [6]
La noción de equidad para los grupos se capta formalmente al extender los criterios de representación justificada de la votación de múltiples ganadores . La idea de estos criterios es que, si hay un grupo suficientemente grande de votantes que están de acuerdo en un grupo suficientemente grande de proyectos, entonces estos proyectos deberían recibir una parte suficientemente grande del presupuesto. Formalmente, dado un grupo N de votantes y un conjunto P de proyectos, definimos:
Con base en estas definiciones, se han definido muchas nociones de equidad; véase Rey y Maly [2] para una taxonomía de las diversas nociones de equidad. A continuación, la asignación presupuestaria elegida (el conjunto de proyectos elegidos para ser financiados) se denota por X .
La representación justificada extendida fuerte (SEJR) significa que, para cada grupo N de votantes que puede permitirse un conjunto P de proyectos, la utilidad de cada miembro de N de X es al menos tan alta como la utilidad potencial de N de P. En particular, con votaciones de aprobación y satisfacción cardinal, si N puede permitirse P y todos los miembros de N aprueban P , entonces para cada miembro i de N , al menos | P | proyectos aprobados por i deberían ser financiados.
Esta propiedad es demasiado fuerte, incluso en el caso especial de votaciones de aprobación y proyectos de costo unitario (elecciones de comité). Por ejemplo, supongamos que n = 4 y B = 2. Hay tres proyectos de costo unitario {x, y, z}. Las votaciones de aprobación son: {1: x, 2: y, 3: z, 4: xyz}. El grupo N = {1, 4} puede permitirse P = {x}, y su utilidad potencial de {x} es 1; de manera similar, {2, 4} puede permitirse {y}, y {3, 4} puede permitirse {z}. Por lo tanto, SEJR requiere que la utilidad de cada uno de los 4 agentes sea al menos 1. Esto solo se puede hacer financiando los 3 proyectos; pero el presupuesto es suficiente solo para 2 proyectos. Nótese que esto se cumple para cualquier función de satisfacción. [2] : Sec.5, fn.5
La representación plenamente justificada (RPP) significa que, para cada grupo N de votantes que pueden permitirse un conjunto P de proyectos, la utilidad de al menos un miembro de N de X es al menos tan alta como la utilidad potencial de N de P. En particular, con votaciones de aprobación y satisfacción cardinal, si N puede permitirse P , y cada miembro de N aprueba al menos k elementos de P , entonces para al menos un miembro i de N , al menos k proyectos aprobados por i deberían ser financiados.
La cláusula de "al menos un miembro" puede hacer que la propiedad FJR parezca débil, pero hay que tener en cuenta que debería ser válida para cada grupo N de votantes que pueden permitirse un conjunto P de proyectos, por lo que implica garantías de equidad para muchos votantes individuales.
Siempre existe una asignación presupuestaria FJR. [6] : Sec.4 Por ejemplo, en el ejemplo anterior, {a,b,c} satisface FJR: en {1,2,3} y {3,4,5} y {5,6,7} todos los agentes tienen una utilidad de al menos 1, y en {7,8,9} el votante n.° 7 tiene una utilidad de al menos 1. La prueba de existencia se basa en una regla llamada Regla Cohesiva Greedy (GCR) :
Es fácil ver que el GCR siempre selecciona una asignación presupuestaria factible: siempre que financia un conjunto P de proyectos, elimina un conjunto N de votantes que satisfacen . El número total de votantes eliminados es como máximo n ; por lo tanto, el costo total de los proyectos agregados es como máximo .
Para ver que GCR satisface FJR, considere cualquier grupo N que pueda permitirse un conjunto P , y tenga una utilidad potencial u(N,P). Sea i el miembro de N que fue eliminado primero. El votante i fue eliminado como miembro de algún otro grupo de votantes M , que podía permitirse un conjunto Q , con una utilidad potencial u(M,Q). Cuando se eliminó M , N estaba disponible; por lo que el orden del algoritmo implica que u(M,Q) ≥ u(N,P). Dado que todo el Q está financiado, cada agente en M -incluido el agente i- recibe una utilidad al menos u(M,Q), que es al menos u(N,P). Por lo tanto, la condición FJR se satisface para i . Nótese que la prueba se cumple incluso para utilidades monótonas no aditivas.
GCR se ejecuta en tiempo exponencial en n . De hecho, encontrar una asignación presupuestaria FJR es NP-difícil incluso si hay un solo votante. La prueba es por reducción del problema de la mochila . Dado un problema de la mochila, defina una instancia PB con un solo votante en la que el presupuesto es la capacidad de la mochila, y para cada artículo con peso w y valor v , hay un proyecto con costo w y utilidad v . Sea P la solución óptima para la instancia de la mochila. Dado que costo( P )=peso( P ) es como máximo el presupuesto, es asequible para el votante único. Por lo tanto, su utilidad en una asignación presupuestaria EJR debe ser al menos valor( P ). Por lo tanto, encontrar una asignación presupuestaria FJR produce una solución para la instancia de la mochila. La misma dificultad existe incluso con las papeletas de aprobación y la satisfacción basada en el costo, por reducción del problema de la suma de subconjuntos .
La representación justificada extendida (EJR) es una propiedad ligeramente más débil que la FJR. Significa que la condición FJR debería aplicarse solo a grupos que sean suficientemente "cohesivos". En particular, con las votaciones de aprobación, si N puede permitirse P y cada miembro de N aprueba todos los elementos de P , entonces para al menos un miembro i de N , la satisfacción del proyecto aprobado de i en X debería ser al menos tan alta como la satisfacción de P. En particular:
Dado que FJR implica EJR, siempre existe una asignación presupuestaria de EJR. Sin embargo, de manera similar a FJR, es NP-difícil encontrar una asignación de EJR. La NP-difícil se mantiene incluso con votaciones de aprobación, para cualquier función de satisfacción que aumente estrictamente con el costo. Pero con votaciones de satisfacción y aprobación basadas en cardinalidad, el método de partes iguales encuentra una asignación presupuestaria de EJR.
Además, verificar si una asignación presupuestaria dada satisface el EJR es extremadamente difícil incluso con costos unitarios. [20]
Es una pregunta abierta si se puede encontrar una asignación presupuestaria EJR o FJR en un polinomio de tiempo en n y B (es decir, tiempo pseudopolinomial ). [2] : 5.1.1.2
EJR hasta un proyecto (EJR-1) significa que, para cada grupo N de votantes que pueden costear un conjunto P de proyectos, existe al menos un miembro i en N tal que se cumple una de las siguientes condiciones:
Con papeletas cardinales, EJR-1 es más débil que EJR; con papeletas de aprobación y satisfacción cardinal, EJR-1 es equivalente a EJR. Esto se debe a que las utilidades de todos los proyectos son 0 o 1. Por lo tanto, si agregar un solo proyecto hace que la utilidad de i sea estrictamente mayor que u(N,P), entonces sin este solo proyecto, la utilidad de i es al menos u(N,P).
Pierczynski, Skowron y Peters [6] : Thm.2 demuestra que el método de partes iguales, que se ejecuta en tiempo polinomial, siempre encuentra una asignación presupuestaria EJR-1; por lo tanto, con votaciones de aprobación y satisfacción basada en cardinalidad, siempre encuentra una asignación presupuestaria EJR (incluso para costos no unitarios).
EJR hasta cualquier proyecto (EJR-x) significa que, para cada grupo N de votantes que pueden permitirse un conjunto P de proyectos, y para cada proyecto no financiado y en P , la utilidad de i de X + y es estrictamente mayor que la utilidad potencial de N de P . Claramente, EJR implica EJR-x que implica EJR-1. Brill, Forster, Lackner, Maly y Peters [21] demuestran que, para las papeletas de aprobación y para cualquier función de satisfacción con satisfacción normalizada (DNS) decreciente, si se aplica el método de partes iguales con esa función de satisfacción, el resultado es EJR-x.
Sin embargo, puede que no sea posible satisfacer EJR-x o incluso EJR-1 simultáneamente para diferentes funciones de satisfacción: hay casos en los que ninguna asignación presupuestaria satisface EJR-1 simultáneamente tanto para la satisfacción de costos como para la satisfacción de cardinalidad. [21]
La representación proporcional justificada (RPJ) significa que, para cada grupo N de votantes que pueden permitirse un conjunto P de proyectos, la utilidad de grupo de N a partir de la asignación presupuestaria -definida como- es al menos la utilidad potencial de N a partir de P. En particular, con las votaciones de aprobación, si N puede permitirse P , y cada miembro de N aprueba todos los elementos de P , entonces la satisfacción a partir del conjunto de todos los proyectos financiados que son aprobados por al menos un miembro de N debería ser al menos tan alta como la satisfacción a partir de P. En particular:
Como EJR implica PJR, siempre existe una asignación presupuestaria PJR. Sin embargo, de manera similar a EJR, es NP-difícil encontrar una asignación PJR incluso para un solo votante (usando la misma reducción de la mochila). Además, verificar si una asignación presupuestaria dada satisface PJR es coNP-difícil incluso con costos unitarios y boletas de aprobación. [20]
De manera análoga a EJR-x, se puede definir PJR-x , que significa PJR hasta cualquier proyecto. Brill, Forster, Lackner, Maly y Peters [21] demuestran que, para las votaciones de aprobación, la regla secuencial de Phragmen, la regla de soporte maximin y el método de partes iguales con satisfacción de cardinalidad, garantizan PJR-x simultáneamente para cada función de satisfacción DNS .
Aziz, Lee y Talmon [16] presentan variantes locales de los criterios JR anteriores, que pueden satisfacerse en tiempo polinomial. Para cada uno de estos criterios, también presentan una variante más débil donde, en lugar del límite presupuestario externo B , el denominador es W , que es la cantidad real utilizada para la financiación. Dado que normalmente W < B , las variantes W son más fáciles de satisfacer que sus variantes B. [16]
Aziz y Lee [19] extienden las nociones de representación justificada a las papeletas ordinales débiles, que contienen las papeletas de aprobación como un caso especial. Extienden la noción de un grupo cohesivo a una coalición sólida y definen dos nociones de proporcionalidad incomparables: Proporcionalidad Comparativa para Coaliciones Sólidas (CPSC) y Proporcionalidad de Inclusión para Coaliciones Sólidas (IPSC). La CPSC puede no existir siempre, pero la IPSC siempre existe y se puede encontrar en tiempo polinomial. Las partes iguales satisfacen la PSC, una noción más débil que la IPSC y la CPSC. [6]
Una forma de evaluar tanto la equidad como la estabilidad de las asignaciones presupuestarias es comprobar si un grupo determinado de votantes podría lograr una utilidad mayor si tomara su parte del presupuesto y la dividiera de una manera diferente. Esto se refleja en la noción de núcleo de la teoría de juegos cooperativos. Formalmente, una asignación presupuestaria X está en el núcleo débil si no hay un grupo N de votantes, y una asignación presupuestaria alternativa Z de , tal que todos los miembros de N prefieren estrictamente Z a X .
La equidad básica es más fuerte que la equidad basada en la justicia, que a su vez es más fuerte que la equidad basada en la justicia. Para ver la relación entre estas condiciones, nótese que, para el núcleo débil, es suficiente que, para cada grupo N de votantes, la utilidad de al menos un miembro de N de X sea al menos tan alta como la utilidad potencial de N de P ; no se requiere que N sea cohesivo.
Para el establecimiento de PB divisibles y papeletas cardinales, existen algoritmos eficientes para calcular una asignación presupuestaria básica para algunas clases naturales de funciones de utilidad. [22]
Sin embargo, en el caso de un PB indivisible , el núcleo débil podría estar vacío incluso con costos unitarios. Por ejemplo: [6] supongamos que hay 6 votantes y 6 proyectos con costos unitarios, y el presupuesto es 3. Las empresas de servicios públicos satisfacen las siguientes desigualdades:
Todas las demás utilidades son 0. Cualquier asignación presupuestaria factible contiene como máximo un proyecto {a, b, c} o como máximo un proyecto {d, e, f}. Supongamos lo primero y supongamos que b y c no reciben financiación. Entonces los votantes 2 y 3 pueden tomar su parte proporcional del presupuesto (que es 1) y financiar el proyecto c, lo que les dará a ambos una utilidad mayor. Nótese que el ejemplo anterior requiere solo 3 valores de utilidad (por ejemplo, 2, 1, 0).
Con sólo dos valores de utilidad (es decir, votos de aprobación), es una pregunta abierta si siempre existe una asignación de núcleo débil, con o sin costos unitarios; tanto con satisfacción de cardinalidad como con satisfacción de costos. [6]
Se pueden lograr algunas aproximaciones al núcleo: las partes iguales alcanzan una aproximación multiplicativa de . [6] Munagala, Shen, Wang y Wang [23] prueban que, para utilidades monótonas arbitrarias, existe una asignación de núcleo aproximada de 67 que se puede calcular en tiempo polinomial. Para utilidades aditivas, existe una asignación de núcleo aproximada de 9,27, pero no se sabe si se puede calcular en tiempo polinomial.
Jiang, Munagala y Wang [24] [25] consideran una noción diferente de aproximación llamada aproximación de titularidad ; demuestran que siempre existe un núcleo aproximado de 32 mediante esta noción.
La fijación de precios significa que [6] es posible asignar un presupuesto fijo a cada votante y dividir el presupuesto de cada votante entre los candidatos que aprueba, de modo que cada candidato elegido sea "comprado" por los candidatos que lo aprueban, y ningún candidato no elegido pueda ser comprado por el dinero restante de los votantes que lo aprueban. El MES puede verse como una implementación del equilibrio de Lindahl en el modelo discreto, con el supuesto de que los clientes que comparten un artículo deben pagar el mismo precio por el artículo. [26] La definición es la misma para las papeletas cardinales que para las papeletas de aprobación.
Una asignación con precio se calcula mediante las reglas de partes iguales (para votaciones cardinales), [6] Phragmen secuencial (para votaciones de aprobación), [14] y apoyo maximin (para votaciones de aprobación). [21]
Con las votaciones de aprobación, la posibilidad de precio implica PJR-x para la satisfacción basada en costos. Además, una noción de posibilidad de precio ligeramente más fuerte implica PJR-x simultáneamente para todas las funciones de satisfacción de DNS. Esta noción más fuerte se satisface en partes iguales con la satisfacción de cardinalidad, Phragmen secuencial y soporte maximin. [21]
La equidad laminar [27] [14] es una condición para las instancias de una estructura específica, llamadas instancias laminares . Un caso especial de una instancia laminar es una instancia en la que la población se divide en dos o más grupos disjuntos, de modo que cada grupo apoya un conjunto disjunto de proyectos. Las partes iguales y los Phragmen secuenciales son laminarmente proporcionales a los costos unitarios, [27] pero no a los costos generales. [14]
Maly, Rey, Endriss y Lackner [28] [29] definieron una nueva noción de equidad para el PB con papeletas de aprobación, que depende solo de la igualdad de recursos, y no de una función de satisfacción particular. La idea fue presentada por primera vez por Ronald Dworkin . [30] [31] Explican la lógica detrás de esta nueva noción de la siguiente manera: "no buscamos una distribución justa de la satisfacción , sino que nos esforzamos por invertir el mismo esfuerzo en satisfacer a cada votante. La ventaja es que la cantidad de recursos gastados es una cantidad que podemos medir objetivamente". Definen la parte de un agente i del conjunto P de proyectos financiados como: . Intuitivamente, esta cantidad representa la cantidad de recursos que la sociedad puso en satisfacer i . Para cada proyecto financiado x , el costo de x contribuye por igual a todos los agentes que aprueban x . Como ejemplo, supongamos que el presupuesto es 8, hay tres proyectos x,y,z con costos 6,2,2, cuatro agentes con papeletas de aprobación xy, xy, y, z.
Una asignación presupuestaria satisface la distribución equitativa (CE) si la distribución equitativa de cada agente es al menos min( B / n , distribución( A i , i )). Obviamente, una distribución equitativa puede no existir, por ejemplo, cuando hay dos agentes que desean cada uno un proyecto diferente, pero el presupuesto alcanza solo para un proyecto. Además, incluso una distribución equitativa de hasta un proyecto (CE-1) puede no existir. Por ejemplo, supongamos que B = 5, hay 3 proyectos con un costo de 3 y las papeletas de aprobación son xy, yz, zx. La distribución equitativa es 5/3. Pero en cualquier distribución factible, como máximo se financia un proyecto, por lo que hay un agente sin ningún proyecto financiado aprobado. Para este agente, incluso agregar un proyecto aumentaría su distribución a 3/2 = 1,5, que es menos de 5/3. Verificar si existe una distribución equitativa o una distribución equitativa de 1 proyecto es NP-difícil. En ejemplos prácticos de pabulib, es posible dar a cada agente entre el 45% y el 75% de su parte justa; las reglas MES dan una fracción mayor que las de Phragmen secuencial.
Una relajación más débil, llamada reparto justo local (Local-FS) , requiere que, para cada proyecto no financiado y , exista al menos un agente i que apruebe y y tenga share( X + y , i) > B / n . Local-FS se puede satisfacer mediante una variante del método de repartos iguales en el que la contribución de cada agente a la financiación de un proyecto x es proporcional a share({ x }, i ), en lugar de a u i ( x ).
Otra relajación es la Extended Justified Share (EJS) : significa que, para cualquier grupo de agentes N que pueden permitirse un conjunto de proyectos P , tales que cada miembro en N aprueba todos los elementos de P , hay al menos un miembro i en N para quien share( X , i ) ≥ share( P , i ). Parece similar a EJR, pero son independientes: hay casos en los que algunas asignaciones son EJS y no EJR, mientras que otras asignaciones son EJR y no EJS. Una asignación EJS siempre existe y se puede encontrar mediante la regla cohesiva voraz de tiempo exponencial, en el tiempo ; encontrar una asignación EJS es NP-difícil. Pero la variante anterior de MES satisface EJS hasta un proyecto (EJS-1). Está abierto si EJS hasta cualquier proyecto (EJS-x) se puede satisfacer en tiempo polinomial.
La equidad distrital es un concepto de equidad que se centra en los distritos predefinidos de una ciudad. Cada distrito i merece un presupuesto B i (una parte del presupuesto total de la ciudad), que suele ser proporcional al tamaño de la población del distrito. En muchas ciudades, hay un proceso de presupuesto participativo independiente en cada distrito. Puede resultar más eficiente realizar un único proceso de presupuesto participativo para toda la ciudad, pero es importante hacerlo de una manera que no perjudique a los distritos. Por lo tanto, una asignación presupuestaria para toda la ciudad es justa para los distritos si otorga a cada distrito i al menos el bienestar que podría obtener con una asignación óptima de B i .
Hershkowitz, Kahng, Peters y Procaccia [32] estudian el problema de la maximización del bienestar sujeto a la equidad distrital. Demuestran que encontrar una asignación determinista óptima es NP-hard, pero encontrar una asignación aleatoria óptima que sea justa para los distritos en expectativa se puede hacer de manera eficiente. Además, si se permite gastar en exceso (hasta un 65%), es posible encontrar una asignación que maximice el bienestar social y garantice la equidad distrital hasta en un proyecto.
Es natural esperar que, cuando cambian algunos parámetros de la instancia de PB, el resultado de una regla de PB cambie de manera predecible. En particular:
Se han estudiado las propiedades de monotonía para las reglas de maximización del bienestar y para sus variantes codiciosas. [7] [33] [34]
Una regla de PB se denomina a prueba de estrategias si ningún votante puede aumentar su utilidad informando preferencias falsas. Con costos unitarios, la regla que maximiza el bienestar utilitario (eligiendo los proyectos B con el mayor número de aprobaciones) es a prueba de estrategias. Esto no es necesariamente cierto con los costos generales. Con las votaciones de aprobación y la satisfacción de costos, el algoritmo voraz, que selecciona proyectos por el número de aprobaciones, es a prueba de estrategias hasta un proyecto. El resultado no se cumple para la satisfacción de cardinalidad. [35]
La regla utilitarista no es proporcional ni siquiera en el caso de los costos unitarios y las votaciones de aprobación. De hecho, incluso en las votaciones de comités, existe una disyuntiva fundamental entre la estrategia a prueba de errores y la proporcionalidad; véase votación de aprobación con múltiples ganadores#strategy .
A menudo, existen restricciones que impiden que algunos subconjuntos de proyectos sean el resultado del PP. Por ejemplo:
Rey, Endriss y de Haan [36] desarrollan un marco general para manejar cualquier restricción que pueda ser descrita por la lógica proposicional , codificando instancias PB como agregación de juicios . [37] Su marco permite restricciones de dependencia así como restricciones de categoría, con posibles categorías superpuestas.
Fain, Munagala y Shah [38] estudian una generalización del PB: la asignación de bienes públicos indivisibles, con posibles restricciones a la asignación. Consideran restricciones matroidales , restricciones de emparejamiento y restricciones de empaquetamiento (que corresponden a restricciones presupuestarias).
Jain, Sornat, Talmon y Zehavi [39] suponen que los proyectos se dividen en categorías disjuntas y que existe un límite presupuestario para cada categoría, además del límite presupuestario general. Estudian la complejidad computacional de maximizar el bienestar social sujeto a estas restricciones. En general, el problema es difícil, pero se ofrecen algoritmos eficientes para entornos con pocas categorías.
Patel, Khan y Louis [40] también suponen que los proyectos se dividen en categorías disjuntas, con cuotas superiores e inferiores en cada categoría. Presentan algoritmos de aproximación utilizando programación dinámica.
Chen, Lackner y Maly [41] suponen que los proyectos pertenecen a categorías posiblemente superpuestas, con cuotas superiores e inferiores en cada categoría.
Motamed, Soeteman, Rey y Endriss [42] muestran cómo manejar restricciones categóricas mediante reducción a PB con múltiples recursos.
Recientemente se han estudiado varias extensiones del modelo básico PB.
Rey, Endriss y de Haan consideran una etapa importante que ocurre, en las implementaciones de PB en la vida real, antes de la etapa de votación: la elección de una lista corta de proyectos que se presentarán a los votantes. Modelan esta etapa de preselección como un proceso de votación con múltiples ganadores en el que no hay límite en el tamaño total o el costo del resultado. Analizan varias reglas que se pueden utilizar en esta etapa para garantizar la diversidad de los proyectos seleccionados. También analizan posibles manipulaciones estratégicas en la etapa de preselección. [43]
Lackner, Maly y Rey señalan que, en realidad, el voto participativo no es un proceso que se produce una sola vez, sino que se repite todos los años. Aplican algunas nociones de imparcialidad del voto perpetuo al voto participativo. En particular, suponen que los votantes están divididos en tipos y tratan de lograr la imparcialidad para los tipos a lo largo del tiempo. [44]
Jain, Sornat y Talmon suponen que los proyectos pueden ser bienes sustitutos o bienes complementarios y, por lo tanto, la utilidad que un agente recibe de un conjunto de proyectos no es necesariamente la suma de las utilidades de cada proyecto. Analizan la complejidad computacional de la maximización del bienestar en este contexto extendido. En este trabajo, la estructura de interacción entre los proyectos es fija e idéntica para todos los votantes; [45] Jain, Talmon y Bulteau extienden el modelo aún más al permitir que los votantes especifiquen estructuras de interacción individuales. [46]
Lu y Boutilier consideran un modelo de elección social presupuestada, que es muy similar al modelo de presupuesto participativo. [3] En su contexto, el costo de cada proyecto es la suma de un costo fijo y un costo variable que aumenta con el número de agentes "asignados" al proyecto. Motamed, Soeteman, Rey y Endriss consideran costos multidimensionales, por ejemplo, costos en términos de dinero, tiempo y otros recursos. [42] Extienden algunas propiedades de equidad y propiedades estratégicas a este contexto, y consideran la complejidad computacional de la maximización del bienestar.
Baumeister, Boes y Laussmann suponen que los costes son inciertos: cada coste tiene una distribución de probabilidad y su coste real se revela solo cuando se completa. [47] Para reducir el riesgo, es posible implementar proyectos uno después del otro, de modo que si el primer proyecto cuesta demasiado, se pueden eliminar algunos proyectos posteriores. Pero podría causar que algunos proyectos se implementen muy tarde. Muestran que es imposible mantener un bajo riesgo de gasto excesivo y garantizar que todos los proyectos se completen en el tiempo debido. Adaptan los criterios de equidad, así como el método de partes iguales , a este contexto.
Proyectos que pueden ser financiados en diferentes grados. [1] Por ejemplo, un nuevo edificio para actividades juveniles podría tener 1, 2 o 3 pisos; puede ser pequeño o grande; puede ser construido de madera o piedra; etc. Esto puede verse como un punto intermedio entre el PP indivisible (que permite solo dos niveles) y el PP divisible (que permite continuamente muchos niveles). Formalmente, cada proyecto j puede ser implementado en cualquier grado entre 0 y t j , donde 0 significa "no implementado en absoluto" y tj es la implementación máxima posible. Cada grado de implementación tiene un costo. Las papeletas son papeletas de aprobación por rango , es decir: cada votante da, para cada proyecto, una cantidad mínima y máxima de dinero que debe invertirse en este proyecto.
Sreedurga [48] considera la maximización del bienestar utilitarista en este contexto. Considera cuatro funciones de satisfacción:
Para la satisfacción de cardinalidad, la maximización del bienestar utilitario se puede realizar en tiempo polinómico mediante programación dinámica . Para las demás funciones de satisfacción, la maximización del bienestar es NP-hard, pero se puede calcular en tiempo pseudopolinómico o aproximarse mediante un FPTAS , y también es manejable con parámetros fijos para algunos parámetros naturales.
Además, Sreedurga define varios axiomas de monotonía y consistencia para este contexto. Muestra que cada regla de maximización del bienestar satisface algunos de estos axiomas, pero ninguna regla los satisface todos.
{{cite journal}}: Requiere citar revista |journal=( ayuda )