Proportionality Degree in Participatory Budgeting

Este estudio inicia la investigación del grado de proporcionalidad en la presupuestación participativa, demostrando mediante límites teóricos y evaluación experimental que, aunque el Método de Cuotas Iguales (MES) ofrece garantías axiomáticas más fuertes, tanto este como la Regula Secuencial de Phragmen comparten el mismo grado de proporcionalidad desde una perspectiva cuantitativa.

Lo esencial

¡Claro que sí! Imagina que este artículo es como una investigación sobre cómo repartir el dinero de una fiesta comunitaria de la manera más justa posible.

Aquí tienes la explicación de la investigación, traducida a un lenguaje sencillo y con algunas analogías divertidas:

🏛️ El Problema: La Fiesta del Presupuesto Participativo

Imagina que tu vecindario tiene una gran bolsa de dinero (el presupuesto) y una lista de ideas para mejorar el barrio: un parque, una biblioteca, pintar la escuela, etc. Cada vecino vota por las ideas que le gustan.

El reto es: ¿Cómo elegimos qué proyectos financiar para que nadie se sienta ignorado?

Si solo elegimos los proyectos que más votos tienen en total (la regla "greedy" o codiciosa), podría pasar que un grupo pequeño de vecinos muy apasionados por un proyecto específico no tenga ninguna representación, aunque sean muchos en número. Necesitamos reglas que garanticen que los grupos grandes obtengan una parte del presupuesto proporcional a su tamaño.

⚖️ Los Dos "Árbitros" en Competencia

Los autores del estudio compararon dos métodos famosos para tomar esta decisión, como si fueran dos árbitros diferentes en un partido:

1. El Método de las Cuotas Iguales (MES):

   • La analogía: Imagina que le das a cada vecino un vale de dinero ficticio (digamos, 100 euros). Si un grupo de vecinos quiere financiar un proyecto, deben "pagar" con sus vales. La regla es: nadie puede gastar más de lo que tiene. Si un proyecto cuesta 50 euros y lo apoyan 10 personas, cada una paga 5 euros. Si se quedan sin vales, se quedan fuera.
   • Su superpoder: Es muy justo teóricamente. Garantiza que los grupos grandes siempre tengan voz.

2. La Regla Secuencial de Phragmén:

   • La analogía: Imagina que el dinero no son vales, sino que llueve dinero sobre cada vecino a la misma velocidad (como una manguera). Cuando un grupo de vecinos junta suficiente agua (dinero) para pagar un proyecto, ¡ZAS! Se compra el proyecto y el agua de ese grupo se vacía (se gasta), mientras que los demás siguen llenando sus cubos.
   • Su superpoder: Es un poco más "rústico" en teoría, pero funciona muy rápido.

🔍 La Gran Sorpresa del Estudio

Los investigadores querían saber: ¿Cuál de los dos árbitros es realmente mejor para garantizar la proporcionalidad?

• Lo que se pensaba: Como el Método de las Cuotas Iguales (MES) tiene reglas teóricas más estrictas y complejas, se asumía que sería mucho mejor que Phragmén.
• Lo que descubrieron: ¡Falso! Ambos árbitros son igual de buenos.
  • Aunque MES tiene reglas más "elegantes" en papel, cuando se mide con números reales (cuánto presupuesto obtienen realmente los grupos), ambos métodos logran exactamente el mismo nivel de justicia.
  • Es como si dos coches diferentes (uno deportivo y uno familiar) llegaran a la meta a la misma velocidad, aunque usen motores distintos.

🧪 La Prueba en la Vida Real (Los Experimentos)

No se quedaron solo con la teoría. Los autores tomaron 100 casos reales de presupuestos participativos de ciudades de verdad (datos reales de gente votando por cosas reales).

• El resultado: En la práctica, los dos métodos (MES y Phragmén) funcionaron de maravilla y muy parecidos entre sí.
• El villano: Ambos métodos ganaron por goleada a la regla "codiciosa" (la que simplemente elige lo que tiene más votos sin importar la proporción). La regla codiciosa suele dejar fuera a grupos importantes.
• Un detalle curioso: A veces, Phragmén funcionó incluso un poquito mejor que MES, ¡aunque teóricamente se suponía que era el "menos perfecto"!

💡 ¿Qué significa esto para nosotros?

1. Justicia Cuantitativa: No importa si usas un método matemático complejo (MES) o uno más simple (Phragmén); si tu objetivo es que los grupos grandes obtengan su parte justa del presupuesto, ambos funcionan igual de bien.
2. Evita la "Tiranía de la Mayoría": Ambos métodos aseguran que si tienes un grupo grande de gente que quiere algo, conseguirán su parte del dinero, en lugar de que un grupo pequeño con muchos votos individuales se lleve todo el pastel.
3. Confianza: Ahora sabemos que podemos usar cualquiera de los dos con confianza. No hace falta usar el más complicado si el más simple da el mismo resultado.

En resumen

El estudio nos dice que, en el mundo de la democracia participativa, dos caminos diferentes pueden llevar al mismo destino justo. Tanto el "Método de las Cuotas Iguales" como la "Regla de Phragmén" son excelentes herramientas para asegurar que el dinero público se reparta de forma equitativa, superando con creces a los métodos tradicionales que solo miran quién tiene más votos.

¡Es una buena noticia para la democracia! 🗳️✨

Resumen técnico

1. El Problema

La Presupuestación Participativa (PB) es un proceso democrático donde los ciudadanos proponen y seleccionan proyectos para financiar dentro de un presupuesto fijo. Aunque existen métodos axiomáticos para garantizar la equidad (como la Representación Justificada Extendida - EJR), estos son binarios: una regla o cumple el axioma o no lo cumple.

El artículo aborda la necesidad de una medida cuantitativa de la equidad, conocida como Grado de Proporcionalidad. Este concepto mide hasta qué punto un grupo cohesivo de votantes (un grupo que apoya un conjunto de proyectos) puede asegurar una parte del presupuesto proporcional a su tamaño.

• Brecha de investigación: Mientras que el grado de proporcionalidad ha sido estudiado en votación de múltiples ganadores (MWV), no se había analizado sistemáticamente en el contexto específico de la PB, especialmente para reglas modernas como el Método de Cuotas Iguales (MES) y la Regla Secuencial de Phragmén.
• Objetivo: Determinar los límites teóricos (superiores e inferiores) del grado de proporcionalidad de estas reglas y compararlas empíricamente.

2. Metodología

Los autores combinan un análisis teórico riguroso con una evaluación experimental extensa.

A. Marco Teórico

• Definiciones Clave:
  • Grupo T-cohesivo: Un grupo de votantes $V$ que aprueba un conjunto de proyectos $T$ tal que el costo de $T$ es proporcional al tamaño del grupo ($cost(T)/B \le |V|/n$).
  • Grado de Proporcionalidad ($d_f(T)$): El límite inferior del peor caso sobre la satisfacción promedio de los votantes en un grupo cohesivo $V$ respecto al tamaño de $T$.
• Reglas Analizadas:
  1. Método de Cuotas Iguales (MES): Asigna una cuota inicial de presupuesto a cada votante y selecciona proyectos secuencialmente basándose en la capacidad de pago de los votantes que los aprueban. Cumple EJR.
  2. Regla Secuencial de Phragmén: Los votantes acumulan "créditos" en el tiempo. Cuando un grupo de votantes que aprueba un proyecto acumula créditos suficientes para pagar su costo, el proyecto se selecciona y sus créditos se reinician. Cumple PJR pero no EJR.
• Técnicas de Prueba:
  • Uso de funciones de potencial y construcciones de ordenamientos de votantes para acotar los pagos máximos.
  • Construcción de instancias adversarias (casos límite) para demostrar cotas superiores.
  • Análisis de casos con y sin "agotamiento" (exhaustion), donde el presupuesto sobrante se asigna mediante una regla codiciosa (greedy).

B. Evaluación Experimental

• Datos: Se utilizaron 100 instancias reales de la biblioteca Pabulib.
• Muestreo: Dado que el número de subconjuntos de proyectos es exponencial, se muestrearon aleatoriamente 5,000 subconjuntos de tamaños $k \in \{1, \dots, 15\}$ para cada instancia.
• Reglas Comparadas:
  1. MES (sin agotamiento).
  2. Phragmén (sin agotamiento).
  3. MES con agotamiento (MES-Exh).
  4. Phragmén con agotamiento (Phragmén-Exh).
  5. Regla Codiciosa (Greedy Approval): Selecciona proyectos por puntuación de aprobación acumulada.

3. Contribuciones Clave

Resultados Teóricos

1. Cotas Ajustadas para MES y Phragmén:
   Los autores derivan cotas inferiores y superiores (hasta factores constantes pequeños) para el grado de proporcionalidad de ambas reglas.

   • Resultado Sorprendente: A pesar de que MES satisface axiomas más fuertes (EJR) y Phragmén solo satisface PJR, ambas reglas tienen el mismo grado de proporcionalidad desde una perspectiva cuantitativa.
   • Cota Inferior (Teorema 1 y 4): Para un conjunto de proyectos $T$, el grado de proporcionalidad es al menos:
     $$d(T) \ge \frac{1}{2} \left( \frac{cost(T)}{\max_{t \in T} cost(t)} - 1 \right)$$
   • Cota Superior (Teorema 2 y 5): Existe una instancia donde el grado de proporcionalidad es a lo sumo:
     $$d(T) \le \frac{1}{2} \left( \frac{cost(T)}{\max_{t \in T} cost(t)} + 1 \right)$$
   • Esto demuestra que, cuantitativamente, la superioridad axiomática de MES no se traduce en una mayor proporcionalidad garantizada en el peor caso.

2. Generalización para reglas EJR:
   Se establece una cota general para cualquier regla que satisfaga EJR en instancias "ordinarias" (donde ningún proyecto es excesivamente barato), mostrando que la garantía depende de la relación entre el costo mínimo y máximo de los proyectos.

Resultados Experimentales

1. Rendimiento Práctico:
   • Tanto MES-Exh como Phragmén-Exh muestran un rendimiento comparable y superior en la mayoría de los conjuntos de datos.
   • Phragmén (incluso sin agotamiento) a menudo supera ligeramente a MES en la práctica, contradiciendo la intuición de que EJR garantiza un mejor desempeño cuantitativo en todos los escenarios.
2. Comparación con la Regla Codiciosa:
   • Todas las variantes de MES y Phragmén superan claramente a la regla Greedy en términos de grado de proporcionalidad.
   • La regla codiciosa solo fue la mejor en 2 de los 100 conjuntos de datos, y en esos casos, la diferencia con las otras reglas fue marginal.

4. Resultados Principales

• Equivalencia Cuantitativa: MES y Phragmén, aunque difieren en sus propiedades axiomáticas (EJR vs. PJR), ofrecen garantías idénticas de proporcionalidad cuantitativa.
• Optimalidad Conjeturada: Los autores conjeturan que estas reglas son óptimas para el problema, ya que la cota superior teórica para cualquier regla es aproximadamente el doble de la cota inferior obtenida (dentro de un factor constante).
• Efecto del Agotamiento: La implementación de "agotamiento" (usar el presupuesto restante con una regla greedy) mejora el rendimiento de ambas reglas, pero Phragmén mantiene una ventaja competitiva incluso sin esta característica.

5. Significado e Impacto

• Validación de Prácticas: El estudio proporciona evidencia teórica y empírica sólida para el uso de MES y Phragmén en la implementación real de presupuestos participativos, desplazando a métodos más simples como el greedy.
• Puente entre Axiomas y Métricas: Demuestra que las garantías axiomáticas fuertes (como EJR) no siempre implican mejores métricas cuantitativas en el peor caso, sugiriendo que la estructura subyacente de estas reglas es más similar de lo que se pensaba.
• Guía para Diseñadores: Ofrece a los responsables políticos y diseñadores de sistemas una comprensión matizada de que, aunque MES es teóricamente más "justo" en términos de axiomas, Phragmén es una alternativa igualmente robusta y a veces superior en escenarios prácticos reales.

En conclusión, el artículo cierra una brecha importante en la literatura de computación social, estableciendo que, para la presupuestación participativa, la proporcionalidad cuantitativa es una métrica donde las reglas más avanzadas (MES y Phragmén) convergen en su rendimiento óptimo, superando significativamente a las heurísticas tradicionales.