Resumen Técnico: Una Teoría General de la Proporcionalidad con Utilidades Aditivas

1. Planteamiento del Problema

El artículo aborda el problema de seleccionar un subconjunto factible de candidatos de un conjunto $C$ basado en las preferencias de los votantes, sujeto a restricciones de factibilidad general definidas por una familia de subconjsets $\mathcal{F} \subseteq 2^C$. Este marco generaliza varios modelos establecidos en la teoría de la elección social, incluyendo:

• Elecciones de comités: Seleccionar un número fijo de candidatos.
• Presupuesto Participativo (PB): Seleccionar proyectos dentro de un presupuesto total.
• Toma de decisiones públicas y agregación de juicios: Tomar decisiones sobre múltiples problemas independientes.
• Restricciones de diversidad: Garantizar propiedades estructurales específicas (por ejemplo, equilibrio de género) en el conjunto seleccionado.

Si bien se han definido axiomas de proporcionalidad (como la Representación Justificada) para este modelo general, las reglas existentes están diseñadas principalmente para boletas de aprobación (donde los votantes asignan utilidad 0 o 1). El artículo se centra en el escenario más complejo de las utilidades aditivas, donde cada votante $i$ asigna una utilidad numérica $u_i(c) \geq 0$ a cada candidato $c$. El objetivo es diseñar reglas que aseguren la representación justa para grupos cohesivos de votantes bajo estas restricciones generales y utilidades cardinales.

2. Metodología

Los autores proponen dos enfoques algorítmicos primarios inspirados en el concepto de los votantes "comprando" candidatos con moneda virtual.

2.1 La Regla PropRank

PropRank es una regla secuencial inspirada en la regla secuencial de Phragmén, pero adaptada para utilidades aditivas.

• Mecanía: Los votantes ganan dinero virtual a una tasa constante a lo largo del tiempo. La regla simula un proceso de compra donde los votantes deciden cuánto gastar en candidatos.
• Mecanismo de Previsión (Foresight): A diferencia de los enfoques ávidos (greedy) estándar, los votantes en PropRank anticipan oportunidades futuras. Calculan un "factor de escala" $\lambda_i$ basado en la mejor relación posible entre pago y utilidad que podrían lograr si esperaran a un candidato más deseable que sea asequible.
• Función de Gasto: Un votante $i$ acuerda gastar como máximo $x_i(c, r)$ en el candidato $c$ en la ronda $r$, definida por una fórmula que involucra su presupuesto actual, la utilidad del candidato y el factor de escala. Esto asegura que la relación pago-utilidad no exceda la mejor compra fraccionaria disponible.
• Ranking: El algoritmo construye un ranking completo de candidatos mediante sus marcas de tiempo de compra. Dado que los candidatos no factibles no se eliminan durante el proceso (solo al final de la construcción del ranking para tamaños de comité específicos), cada prefijo del ranking satisface la proporcionalidad.

2.2 Método Generalizado de Partes Iguales (MES)

Los autores extienden el Método de Partes Iguales (originalmente para PB) a restricciones generales.

• Estructura: El algoritmo opera en rondas. En cada ronda, determina la cantidad máxima de dinero que se puede asignar a los votantes de tal manera que la subrutina de "Partes Iguales" pueda comprar un conjunto de candidatos sin violar las restricciones de factibilidad.
• Previsión en MES: De manera similar a PropRank, el MES generalizado incorpora un mecanismo de previsión. Calcula límites superiores de gasto ($capi$) para evitar que los votantes gasten demasiado pronto en candidatos que podrían ser menos eficientes que los disponibles en iteraciones futuras.
• Heurísticas de Retroceso (Backtracking): El artículo introduce variantes heurísticas (PropRankRem, PropRankBacktrack) que reinician el procedimiento o retroceden cuando se eliminan candidatos, con el objetivo de reducir los presupuestos no gastados y mejorar el rendimiento práctico, aunque carecen de las mismas garantías teóricas que las reglas base.
• Gasto Limitado (BOS): Se propone una adaptación del método BOS para restricciones generales, donde el algoritmo identifica la marca de tiempo válida más grande para la compra antes de que se viole la factibilidad.

3. Contribuciones Clave

3.1 Marco Teórico

• Axiomas de Proporcionalidad para Utilidades Aditivas: El artículo generaliza axiomas como la Representación Justificada Extendida (EJR) y la Representación Justificada Proporcional (PJR) al entorno de utilidades aditivas con restricciones generales.
• Grado de Proporcionalidad: Los autores definen y analizan el "grado de proporcionalidad", cuantificando la satisfacción promedio de un grupo cohesivo. Establecen la relación entre EJR y el grado de proporcionalidad, mostrando que para restricciones generales, la garantía depende del tamaño del grupo cohesivo ($\gamma = |S|/n$).

3.2 Garantías Teóricas

• Garantías de PropRank:
  • Para restricciones de Presupuesto Participativo, PropRank satisface un grado de proporcionalidad de $d(\alpha) = (\alpha - u_{max})/2$.
  • Para restricciones generales, satisface un grado de $d(\alpha) \geq \alpha \cdot \frac{1-\gamma}{2} - \frac{u_{max}}{2}$.
  • Para restricciones de Matroide, satisface un grado de proporcionalidad débil de $(\alpha - u_{max})/2$.
• Garantías de PJR: Las reglas satisfacen garantías de grado de PJR de $d(\alpha) = (\alpha - u_{max})/(\kappa + 1)$, donde $\kappa$ es un parámetro que controla la flexibilidad del gasto.

3.3 Extensiones Algorítmicas

• El artículo proporciona la primera generalización del Método de Partes Iguales a restricciones de factibilidad arbitrarias con utilidades aditivas.
• Introduce heurísticas (PropRankRem, PropRankBacktrack) para abordar el problema de los presupuestos no gastados en escenarios prácticos.

4. Resultados Experimentales

Los autores evaluaron sus reglas en más de 1,300 instancias reales de presupuestos participativos del conjunto de datos Pabulib.

• Métricas: La evaluación se basó en las violaciones de EJR+ (proporcionalidad), la Tasa de Exclusión (fracción de votantes con utilidad cero) y el Costo-Satisfacción promedio (eficiencia utilitaria).
• Hallazgos:
  • Parámetro $\kappa$: Los experimentos indican que PropRank con $\kappa = 1$ (que permite un gasto más flexible) funciona significativamente mejor en términos de proporcionalidad (menos violaciones de EJR+) que $\kappa = 0$.
  • Heurísticas: Las variantes heurísticas (PropRankRem, PropRankBacktrack) combinadas con $\kappa = 0$ mostraron muy pocas violaciones de EJR+ y tasas de exclusión favorables, superando a menudo al PropRank base en métricas prácticas a pesar de carecer de pruebas formales para estas heurísticas específicas.
  • Adaptación de BOS: El Método de Partes Iguales adaptado con Gasto Limitado (BOS) funcionó excepcionalmente bien, superando al BOS-PB original en violaciones de EJR+ y igualándolo en tasa de exclusión y utilidad. También se señaló como el más eficiente computacionalmente entre las técnicas propuestas.
  • Comparación: Las reglas propuestas generalmente lograron un costo-satisfacción comparable o mejor que las reglas existentes específicas de PB (MES-PB, BOS-PB) mientras manejaban restricciones generales.

5. Significado y Reivindicaciones

El artículo afirma proporcionar una teoría general de la proporcionalidad que cierra la brecha entre modelos específicos (como elecciones de comités y PB) y el panorama más amplio de problemas de selección restringida.

• Generalización: Demuestra que los métodos establecidos (Phragmén y Partes Iguales) pueden extenderse a restricciones de factibilidad arbitrarias y utilidades aditivas sin perder sus propiedades centrales de proporcionalidad.
• Ranking: Una contribución significativa es la capacidad de generar rankings proporcionales (donde cada prefijo es un comité proporcional) en el entorno de utilidades aditivas, abordando un vacío en la literatura.
• Practicidad: Aunque las garantías teóricas son sólidas, los autores señalan modestamente que las variantes heurísticas, que sacrifican algo de trazabilidad teórica por un mejor rendimiento práctico (reduciendo los presupuestos no gastados), son altamente efectivas.
• Limitaciones: El artículo reconoce que las técnicas de prueba para los algoritmos base no se extienden directamente a las variantes heurísticas, y que la complejidad computacional de las heurísticas de retroceso puede ser exponencial (mitigada por un parámetro $\sigma$).

En resumen, el trabajo establece una base teórica robusta para la representación proporcional bajo restricciones generales y utilidades aditivas, ofreciendo tanto algoritmos con garantías probables como heurísticas prácticas que funcionan bien con datos reales.