Resumen Técnico: Representación Proporcional en la Agregación de Rankings

Definición del Problema

El artículo aborda el problema de la agregación de rankings, donde el objetivo es combinar un perfil de rankings de entrada ponderados en un único ranking de salida. En este contexto, un perfil $R$ consiste en un conjunto de candidatos $C$ y una función que mapea cada ranking posible $\succ$ a un peso $R(\succ) \in [0, 1]$, de tal manera que la suma de todos los pesos sea igual a 1. Estos pesos representan la importancia de diferentes criterios (por ejemplo, precio frente a calificación en la reserva de un hotel) o la proporción de votantes que apoyan un ranking específico.

El desafío central identificado es que las Funciones de Bienestar Social (FBS) clásicas, como la regla de Kemeny, el conteo de Borda y las reglas de tipo Condorcet, son inherentemente mayoritarias. Estas tienden a seleccionar el ranking de salida que minimiza la distancia respecto al ranking de entrada con mayor peso, ignorando efectivamente las preferencias de las minorías. Por ejemplo, si dos rankings inversos tienen pesos de 51% y 49%, las FBS estándar a menudo simplemente devuelven el ranking del 51%, fallando en representar al grupo del 49%. El artículo busca diseñar FBS que garanticen una representación proporcional, asegurando que cada ranking de entrada influya en la salida en proporción a su peso.

Metodología y Marco de Trabajo

Los autores formalizan la proporcionalidad definiendo la utilidad de un ranking de entrada $\succ$ para un ranking de salida $\triangleright$ como el número de acuerdos de pares entre ellos:
$$u(\succ, \triangleright) = |\{(x, y) \in C^2 : x \succ y \text{ y } x \triangleright y\}|$$
Dado que hay $\binom{m}{2}$ comparaciones de pares en total para $m$ candidatos, un ranking de entrada con un peso $\alpha$ debería idealmente obtener una utilidad de al menos $\lfloor \alpha \binom{m}{2} \rfloor$.

El artículo introduce una jerarquía de axiomas de proporcionalidad inspirados en la votación de comités basada en aprobación y el presupuesto participativo:

1. Representación Justificada Unánime (uJR): Un debilitamiento que requiere que cualquier ranking de entrada con un peso $\ge 1/\binom{m}{2}$ obtenga al menos un acuerdo de par.
2. Representación Justificada Proporcional Unánime (uPJR): El axioma central que requiere que un ranking de entrada con un peso $\alpha$ obtenga una utilidad de al menos $\lfloor \alpha \binom{m}{2} \rfloor$.
3. Representación Justificada Proporcional Fuerte (sPJR): Un fortalecimiento que extiende la garantía a grupos de rankings. Si un subperfil $S$ tiene un peso total $\alpha$, la salida debe estar de acuerdo con al menos $\lfloor \alpha \binom{m}{2} \rfloor$ comparaciones de pares de la unión de los rankings en $S$.

Para lograr estos axiomas, los autores adaptan el concepto de capacidad de fijación de precios (priceability) del presupuesto participativo. Modelan la construcción del ranking de salida como un proceso de compra secuencial donde los candidatos (o pares de candidatos) son "comprados" utilizando los presupuestos de los rankings de entrada.

Contribuciones Claves y Resultados

1. Limitaciones de los Métodos Existentes

El artículo analiza primero la Regla de Kemeny al Cuadrado (propuesta por Lederer et al. [2024] para el ranking proporcional). Los autores demuestran que para $m \ge 5$, la Regla de Kemeny al Cuadrado falla incluso en el axioma más débil, uJR. Específicamente, construyen perfiles donde un ranking de entrada con un peso significativo recibe cero utilidad del ranking de salida de la Regla de Kemeny al Cuadrado, demostizando la necesidad de nuevos mecanismos.

2. La Regla de Borda Secuencial Proporcional (PSB)

Para satisfacer uPJR, los autores proponen la Regla de Borda Secuencial Proporcional (PSB).

• Mecanismo: La PSB opera de forma secuencial. En cada ronda, selecciona al candidato que maximiza la puntuación de Borda ponderada basándose en los presupuestos actuales. Luego, actualiza los presupuestos de los rankings de entrada proporcionalmente a su contribución a la puntuación del candidato seleccionado, efectivamente "pagando" por la posición del candidato.
• Garantía Teórica: Los autores introducen un axioma estructurado llamado rank-priceability (capacidad de fijación de precios de rango), que refleja la priceability en el presupuesto participativo. Demuestran que la rank-priceability implica uPJR.
• Resultado: El Teorema 4.5 establece que la PSB satisface la rank-priceability y, consecuentamente, uPJR.
• Garantía Cuantitativa: Más allá de la satisfacción axiomática, el Teorema 4.6 demuestra que la PSB garantiza a cada subperfil $S$ una utilidad promedio de al menos $\frac{|S|}{4}\binom{m}{2} - \frac{3}{16}$. Esto proporciona un límite inferior lineal de utilidad respecto al peso del grupo.

3. La Regla de Borda de Ajuste de Flujo (FB)

Los autores muestran que la PSB falla en sPJR porque su esquema de pago no protege adecuadamente a los grupos de rankings que actúan en conjunto. Para abordar esto, introducen la pair-priceability (capacidad de fijación de precios de pares), un axioma refinado donde los pagos se realizan para pares específicos de candidatos en lugar de solo rangos.

• Mecanismo: La Regla de Borda de Ajuste de Flujo (FB) es un refinamiento de la PSB. Al igual que la PSB, selecciona al ganador de Borda secuencialmente. Sin embargo, en lugar de un pago proporcional simple, la FB determina los pagos resolviendo un problema de flujo máximo en una red construida. Esta red asegura que la relación costo por utilidad se minimice mientras se respetan las restricciones de presupuesto y de pares.
• Resultado: El Teorema 5.5 demuestra que la FB satisface la pair-priceability, lo que a su vez implica sPJR (Teorema 5.3).
• Garantía Cuantitativa: El Teorema 5.6 muestra que la FB proporciona la misma garantía de utilidad promedio lineal que la PSB ($\frac{|S|}{4}\binom{m}{2} - \frac{3}{16}$), asegurando una fuerte equidad tanto para individuos como para grupos.

4. Variantes Adicionales

En el apéndice, los autores discuten el Método de Partes Iguales de Rangos (RMES), una variante inspirada en el Método de Partes Iguales (MES) del presupuesto participativo. Muestran que el RMES satisface la rank-priceability (y por tanto uPJR) y ofrece un perfil utilitario ligeramente diferente, seleccionando los primeros $\lfloor m/4 \rfloor$ candidatos puramente basados en las puntuaciones de Borda iniciales.

Significado y Reivindicaciones

El artículo afirma presentar las primeras Funciones de Bienestar Social verdaderamente proporcionales para la agregación de rankings. Su principal importancia radica en:

• Puente entre Campos: Transfiere con éxito resultados profundos de la votación de comités basada en aprobación y el presupuesto participativo (específicamente PJR y priceability) al dominio de la agregación de rankings.
• Resolución de un Problema Abierto: Resuelve el problema abierto de diseñar FBS que satisfagan uPJR y sPJR, algo que intentos previos (como la Kemeny al Cuadrado) no lograron alcanzar.
• Fortaleza Axiomática y Cuantitativa: Las reglas propuestas (PSB y FB) no solo se prueban capaces de satisfacer condiciones de equidad axiomática fuerte, sino que también proporcionan garantías cuantitativas robustas sobre la utilidad promedio para cualquier grupo de votantes, asegurando que las preferencias de las minorías no sean sistemáticamente ignoradas.

Los autores señalan que, aunque su trabajo se centra en el acuerdo de pares como la métrica de utilidad, este es un enfoque estándar en la literatura. Sugieren que trabajos futuros podrían explorar nociones de equidad más fuertes (como EJR o estabilidad del núcleo) y funciones de utilidad más generales que tengan en cuenta el valor variable de las distintas posiciones de ranking.