Making Serial Dictatorships Fair

Este artículo demuestra que para minimizar los casos de envidia justificada en el mecanismo de dictadura serial, la ordenación óptima de los agentes debe basarse en una clasificación de Kemeny (o una versión ponderada) de sus prioridades, dependiendo de las características de las preferencias y las capacidades de los objetos.

Lo esencial

Imagina que eres el director de un gran festival de verano. Tienes n niños (los agentes) y n puestos de juegos (los objetos, como una montaña rusa, un carrusel o un juego de agua). Cada niño tiene sus propios gustos: a uno le encanta la montaña rusa, a otro el carrusel, etc.

Además, hay una regla estricta de prioridad: por ejemplo, los niños mayores tienen prioridad sobre los pequeños para elegir primero, o los que viven más cerca tienen prioridad.

El problema es que quieres ser justo y eficiente.

1. Eficiencia: Nadie debería quedarse con un juego que odia si otro niño lo quiere más y no le hace daño a nadie.
2. Justicia (Sin envidia justificada): Si el niño "A" quiere el juego que le tocó al niño "B", pero el niño "A" tiene más prioridad que "B" para ese juego, entonces "A" tiene una envidia justificada. Es como si "A" dijera: "¡Yo debería haberlo tenido porque soy más importante para esta regla!".

El Dilema: La "Dictadura en Serie"

La forma más simple y honesta de repartir los juegos es la Dictadura en Serie (SD). Imagina que pones a los niños en una fila. El primero elige su juego favorito, el segundo elige el mejor que queda, y así sucesivamente.

• Ventaja: Es muy fácil de entender y nadie puede hacer trampas mintiendo sobre lo que le gusta (es "estratégicamente seguro").
• Desventaja: Si pones a los niños en la fila al azar, podrías tener mucha injusticia. Imagina que el niño con la prioridad más alta (el "rey" de la fila) es el último en elegir. ¡Se quedará con el último juego que quede, aunque tenga derecho a elegir primero! Eso genera mucha envidia.

La pregunta del autor, Adam Hamdan, es: ¿Cómo debemos ordenar a los niños en la fila para que la injusticia sea la menor posible, sin saber exactamente qué juegos les gustan a cada uno?

La Solución: El "Ranking de Kemeny" (El Árbitro Perfecto)

El autor descubre que la mejor manera de ordenar la fila no es al azar, sino usando una fórmula matemática llamada Ranking de Kemeny.

La Analogía del "Juez de Paz":
Imagina que cada juego (montaña rusa, carrusel, etc.) tiene su propio "juez" que dice: "Para la montaña rusa, el niño 2 es el más importante, luego el 5, luego el 1...".

• La montaña rusa dice: "El niño 2 es el Rey".
• El carrusel dice: "El niño 1 es el Rey".
• El juego de agua dice: "El niño 2 es el Rey".

Si ordenas la fila al azar, ignoras a estos jueces. Si usas el Ranking de Kemeny, estás buscando el orden de la fila que menos contradice a todos los jueces a la vez. Es como buscar el orden que hace que todos los jueces estén "menos enojados" con la decisión final.

El autor demuestra que, si todos los niños tienen gustos similares (o si no sabemos sus gustos y asumimos que son aleatorios), el orden de Kemeny es la forma matemática perfecta de minimizar las quejas de "¡Yo debería haber ido antes!".

¿Qué pasa si las cosas se complican?

El paper explora tres situaciones más complejas y muestra que la solución se adapta, convirtiéndose en un "Ranking de Kemeny Ponderado" (como si los jueces tuvieran diferentes niveles de autoridad):

1. Si algunos juegos son más populares que otros:

   • Analogía: Si la montaña rusa es el juego más deseado por todos, es muy probable que se elija al principio de la fila.
   • Solución: El orden debe dar más peso a la prioridad de la montaña rusa. Si el niño X es el favorito de la montaña rusa, debería estar más arriba en la fila general, porque es más probable que ese juego se agote rápido.

2. Si los gustos son totalmente diferentes (cada niño es un mundo):

   • Analogía: Aquí la envidia no es segura. El niño 10 podría no envidiar al niño 1 si al niño 1 le tocó algo que al 10 no le interesa.
   • Solución: El sistema debe ser más estricto con las diferencias de prioridad al final de la fila. Si alguien está muy atrás, es más probable que se sienta envidioso de alguien que eligió mucho antes. El orden penaliza más las desviaciones de prioridad al final de la lista.

3. Si hay varios asientos (capacidad múltiple):

   • Analogía: Imagina que la montaña rusa tiene 10 asientos, no solo uno. Si el niño 1 se sienta en la montaña rusa, el niño 2 también puede sentarse allí sin envidiarlo.
   • Solución: El orden debe calcular la probabilidad de que un juego se "llene". Si un juego tiene muchos asientos, no importa tanto el orden exacto de los primeros niños para ese juego específico, porque habrá espacio para todos. El sistema ajusta los pesos según cuántos asientos hay y cuándo es probable que se llenen.

En Resumen

Este paper nos dice que, aunque la "Dictadura en Serie" parece simple, el orden en que pones a la gente importa muchísimo.

No necesitas ser un genio matemático para entenderlo: es como organizar una fila para entrar a un concierto. Si tienes una lista de "prioridades" de los fans (quién es fanático de qué banda), no debes poner a la gente al azar. Debes usar una fórmula inteligente (el Ranking de Kemeny) que combine todas esas prioridades para crear una fila donde, estadísticamente, la menor cantidad de gente se sienta injustamente tratada.

Es una forma de usar la lógica de las elecciones políticas (cómo agrupar votos) para resolver problemas de justicia en la vida real, como asignar escuelas o viviendas sociales, manteniendo la simplicidad y la honestidad del sistema.

Resumen técnico

Resumen Técnico: Hacer Justas las Dictaduras en Serie

1. Planteamiento del Problema

El artículo aborda el problema de la asignación basada en prioridades (como la elección de escuelas, asignación de vivienda pública o órganos), donde un conjunto de objetos debe asignarse a agentes respetando sus preferencias y las prioridades de los objetos sobre los agentes.

• El Dilema: Existe una tensión fundamental entre dos principios normativos:

  1. Eficiencia: Ningún agente puede mejorar sin empeorar a otro.
  2. Justicia (Ausencia de Envidia Justificada): Ningún agente debe preferir la asignación de otro agente si tiene prioridad sobre ese agente para el objeto en cuestión.
  • Roth (1982) y Abdulkadiroğlu y Sönmez (2003) demostraron que no existe un mecanismo que satisfaga simultáneamente eficiencia, ausencia de envidia justificada y estrategia de verdad (strategyproofness).

• La Solución Existente y su Limitación: La Dictadura en Serie (SD) es un mecanismo ampliamente utilizado por ser eficiente, simple y estrategia-proof (los agentes no tienen incentivos para mentir sobre sus preferencias). Sin embargo, SD ignora las prioridades de los objetos al ordenar a los agentes, lo que genera envidia justificada.

• La Pregunta de Investigación: Dado que la SD es deseable por sus otras propiedades, ¿cómo debe ordenar el planificador a los agentes (basándose únicamente en las prioridades de los objetos, ya que las preferencias no pueden usarse sin romper la estrategia-proofness) para minimizar el número esperado de casos de envidia justificada?

2. Metodología y Marco Teórico

El autor modela el problema como un problema de agregación de rankings (rank aggregation).

• Supuestos Base:

  • Un conjunto de agentes $I$ y objetos $S$.
  • Prioridades estrictas de cada objeto sobre los agentes ($\succ_s$).
  • Preferencias de los agentes ($P$) que son desconocidas para el planificador al momento de fijar el orden serial $\rho$, pero siguen una distribución conocida.
  • El planificador elige un orden serial $\rho$ para minimizar el valor esperado de la función de pérdida $N(\mu)$, que cuenta los casos de envidia justificada.

• Conexión con la Teoría de la Elección Social:
  El núcleo metodológico del artículo es identificar que minimizar la envidia justificada en la SD es matemáticamente equivalente a encontrar el Ranking de Kemeny.

  • Ranking de Kemeny: Es la permutación que minimiza la suma de las discordancias pareadas (distancia de Kendall tau) respecto a un perfil de rankings individuales.
  • En este contexto, los "votantes" son los objetos (según sus prioridades) y el "resultado" es el orden serial de los agentes.

3. Contribuciones Clave y Resultados Principales

El artículo establece una conexión novedosa entre la literatura de asignación y la de agregación de rankings, demostrando que la regla de Kemeny (y sus variantes ponderadas) es óptima bajo diversas condiciones.

A. Resultado Central (Teorema 1): Preferencias Idénticas y Distribución Uniforme

• Supuestos: Todos los agentes comparten la misma preferencia ordinal (idéntica), esta preferencia se dibuja uniformemente al azar, y los objetos tienen capacidad unitaria (1 asiento).
• Hallazgo: El orden serial que minimiza la envidia justificada esperada es exactamente el Ranking de Kemeny de las prioridades de los agentes.
• Intuición: Con preferencias idénticas, la envidia es inevitable. El objetivo es minimizar la parte "justificada" de la envidia. Dado que cada objeto es igualmente probable de ser elegido en cualquier posición, se debe dar el mismo peso a la prioridad de cada objeto. El Ranking de Kemeny logra esto al minimizar las violaciones de las preferencias pareadas de todos los objetos por igual.

B. Extensión 1: Preferencias No Uniformes (Proposición 1)

• Escenario: Los agentes tienen preferencias idénticas, pero la distribución de estas preferencias no es uniforme (ciertos objetos son sistemáticamente más deseables).
• Resultado: El orden óptimo es un Ranking de Kemeny Ponderado.
• Mecanismo: Las discordancias de prioridad se ponderan por la probabilidad de que un objeto aparezca en una posición específica de la preferencia. Si un objeto es muy deseable (probabilidad alta de ser elegido temprano), sus prioridades tienen un peso mayor en la determinación del orden serial para evitar envidias tempranas.

C. Extensión 2: Preferencias Independientes (Proposición 2)

• Escenario: Los agentes tienen preferencias independientes y uniformemente distribuidas (no idénticas).
• Resultado: El orden óptimo es un Ranking de Kemeny Ponderado, pero con una estructura de pesos diferente.
• Intuición: La probabilidad de que un agente en la posición $t'$ sienta envidia hacia un agente en la posición $t$ aumenta con la brecha $(t' - t)$. Por lo tanto, el mecanismo asigna un peso mayor a las discordancias de prioridad que ocurren entre agentes con posiciones muy separadas en la secuencia, y penaliza más las violaciones en la parte inferior de la clasificación donde la probabilidad de envidia es mayor.

D. Extensión 3: Capacidades No Unitarias (Proposición 3)

• Escenario: Los objetos tienen múltiples copias (capacidades $q_s > 1$), como escuelas con múltiples plazas.
• Resultado: El orden óptimo sigue siendo un Ranking de Kemeny Ponderado, pero los pesos ahora capturan dos factores dinámicos:
  1. La probabilidad de que el agente en la posición $t$ sea asignado al objeto $s$.
  2. La probabilidad de que el objeto $s$ alcance su capacidad total entre el paso $t$ y el paso $t'$.
• Detalle Técnico: Si un objeto tiene múltiples copias, el agente siguiente no sentirá envidia inmediata. Los pesos se ajustan para reflejar cuándo es probable que un objeto se agote, lo que desencadena la envidia justificada para los agentes posteriores.

4. Significado e Implicaciones

• Puente Teórico: El artículo es pionero en aplicar la regla de Kemeny (tradicionalmente usada en teoría de la elección social y biología computacional) a problemas de emparejamiento con prioridades.
• Mejora Práctica: Proporciona una guía concreta para diseñar mecanismos de asignación (como la asignación de escuelas o dormitorios universitarios) que mantengan la simplicidad y la estrategia-proofness de la Dictadura en Serie, pero que sean significativamente más justos (menos envidia justificada) que un orden aleatorio o arbitrario.
• Relación con RSD (Dictadura en Serie Aleatoria): El autor muestra que la SD con un orden óptimo es una generalización de la RSD. En problemas sin prioridades (asignación de casas), el Ranking de Kemeny coincide con todas las permutaciones posibles, y elegir uno al azar recupera la RSD. En problemas con prioridades, el orden óptimo rompe la simetría para minimizar la injusticia ex-post.
• Robustez: Los resultados sugieren que, incluso cuando las suposiciones ideales (preferencias idénticas, capacidades unitarias) se relajan, la estructura óptima sigue siendo una versión ponderada de la regla de Kemeny, lo que indica una robustez conceptual del enfoque.

5. Conclusión

Hamdan demuestra que la minimización de la envidia justificada en la Dictadura en Serie no es un problema ad hoc, sino un problema clásico de agregación de rankings. Al utilizar el Ranking de Kemeny (o sus variantes ponderadas) para determinar el orden de los agentes basándose en las prioridades de los objetos, los planificadores pueden lograr la asignación más justa posible dentro del conjunto de mecanismos eficientes y estrategia-proof. Esto ofrece una solución práctica al compromiso histórico entre eficiencia y equidad en la asignación de recursos escasos.