Critical Relaxed-Stable Matchings with Ties in the Many-to-Many Setting

Este trabajo demuestra que siempre existe un emparejamiento crítico y relajadamente estable en el escenario de muchos-a-muchos con empates y cuotas, y presenta un algoritmo de aproximación de $\frac{2}{3}$ en tiempo polinomial para maximizar su cardinalidad, a pesar de que encontrar el máximo es NP-duro.

Lo esencial

Imagina que estás organizando un gran festival de intercambio de talentos. Tienes dos grupos: Artistas (que buscan trabajo) y Escenarios (que buscan artistas).

El problema que resuelve este artículo es cómo emparejar a los artistas con los escenarios de la manera más justa y eficiente posible, pero con tres reglas complicadas que hacen que la tarea sea muy difícil:

1. Las "Listas de Preferencias con Empates": A veces, un escenario no sabe si prefiere al Artista A o al Artista B; para ellos, ambos son igual de buenos. Es como si un jefe dijera: "Me da igual contratar a Juan o a María, ambos son geniales".
2. Las "Cuotas Mínimas" (Lower Quotas): Algunos escenarios necesitan un mínimo de artistas para poder abrirse (por ejemplo, un escenario de rock necesita al menos 4 músicos para funcionar). Si no llegan a ese número, el escenario se queda vacío y el evento falla.
3. El "Múltiple": A diferencia de un matrimonio tradicional (uno a uno), aquí un escenario puede contratar a varios artistas, y un artista puede tocar en varios escenarios a la vez.

El Gran Dilema: ¿Qué es lo "Perfecto"?

En un mundo ideal, querríamos un emparejamiento que cumpla dos cosas:

• Estabilidad: Que nadie quiera cambiar de pareja. (Ejemplo: Que un escenario no diga "Ojalá contratara a ese otro artista en lugar de a este").
• Criticalidad (Cumplir las Cuotas): Que se llene la mayor cantidad posible de los "huecos obligatorios". Si un escenario necesita 4 músicos, queremos que tenga 4, no 2.

El problema: Los autores descubrieron que, cuando hay empates y cuotas mínimas, es imposible garantizar que exista un emparejamiento que sea perfectamente estable y que cumpla todas las cuotas al mismo tiempo. A veces, para llenar los huecos obligatorios, tienes que hacer un pequeño "truco" que rompe la estabilidad perfecta.

La Solución: La "Estabilidad Relajada"

Como la perfección absoluta no existe, los autores proponen una solución inteligente llamada "Estabilidad Relajada".

Imagina que el festival tiene un Director de Seguridad (el algoritmo). Este director sabe que no puede evitar que todos los participantes estén 100% felices, pero puede evitar los problemas graves.

La regla de la "Estabilidad Relajada" funciona así:

• Si un escenario quiere cambiar de artista, el Director de Seguridad dice: "¡Espera! Solo puedes cambiar si tu actual artista está de sobra (tiene más trabajo del necesario) o si el nuevo artista es realmente mejor".
• Si el escenario actual está "justito" (tiene exactamente el número mínimo de artistas que necesita), el Director dice: "No puedes cambiar, porque si lo haces, tu escenario se quedará sin personal mínimo y se cerrará".

Básicamente, priorizamos no dejar a nadie desamparado (cumplir las cuotas mínimas) y permitimos pequeños cambios solo si no ponen en riesgo la supervivencia de nadie.

El Algoritmo: Una Danza de Propuestas

Los autores crearon un algoritmo (un conjunto de instrucciones para una computadora) que funciona como una danza de propuestas en varias rondas:

1. Ronda de Supervivencia (Niveles Bajos): Primero, los artistas solo pueden proponerse a los escenarios que necesitan gente urgente. El objetivo es llenar esos huecos mínimos obligatorios.
2. Ronda de Equilibrio (Nivel Medio): Una vez que se asegura lo básico, los artistas empiezan a proponerse a sus favoritos, incluso si hay empates. Aquí usan una técnica ingeniosa llamada "propuestas inciertas".
   • Analogía: Imagina que un artista le dice a un escenario: "Te propongo, pero no estoy seguro de que sea definitivo porque tengo otra opción igual de buena". El escenario acepta, pero sabe que si llega alguien mejor, puede cambiar. Esto permite que el sistema se mueva y encuentre un equilibrio sin bloquearse.
3. Ronda de Último Esfuerzo (Niveles Altos): Si alguien sigue sin tener trabajo suficiente, sube a un nivel superior y sigue proponiéndose hasta que se llena o se queda sin opciones.

¿Qué logran con esto?

El resultado es un emparejamiento que:

1. Es Crítico: Llena la mayor cantidad posible de las cuotas mínimas obligatorias. Nadie se queda "desnudo" si se podía evitar.
2. Es Relajadamente Estable: No hay caos. Los cambios solo ocurren si no perjudican a nadie que esté en una situación crítica.
3. Es Rápido y Eficiente: Aunque encontrar la solución perfecta (la más grande posible) es matemáticamente imposible de calcular en tiempo razonable (es un problema "NP-duro"), su algoritmo encuentra una solución que es al menos un 66% (2/3) tan buena como la mejor solución posible, y lo hace muy rápido.

En resumen

Este paper es como un manual para organizar un festival caótico donde todos tienen gustos similares y necesidades urgentes. En lugar de buscar la utopía imposible (donde todos estén 100% felices y todo esté lleno), proponen un sistema inteligente que asegura que nadie se quede sin trabajo esencial y que, aunque no sea perfecto, es lo suficientemente bueno y justo para que el evento funcione sin desastres.

Es una demostración de que, en la vida real (y en la informática), a veces la mejor solución no es la perfecta, sino la robusta y realista.

Resumen técnico

1. Introducción y Definición del Problema

El artículo aborda el problema de emparejamiento bipartito muchos-a-muchos en un entorno donde coexisten dos características complejas que a menudo se estudian por separado:

1. Empates en las preferencias: Los agentes pueden ser indiferentes entre varios vecinos (no tienen un orden estricto).
2. Cuotas inferiores (Lower Quotas): Cada vértice tiene una cuota mínima ($q^-$) y una cuota máxima ($q^+$). Un emparejamiento debe asignar al menos $q^-$ vecinos a cada vértice para ser considerado "factible".

El Desafío Principal:
En presencia de empates y cuotas inferiores en ambos lados de la partición, un emparejamiento que sea simultáneamente crítico (minimiza la deficiencia total respecto a las cuotas inferiores) y estable (en el sentido de estabilidad débil) puede no existir. Además, decidir si existe tal emparejamiento es un problema NP-completo.

Objetivo:
Encontrar un emparejamiento que sea:

• Crítico: Satisface las cuotas inferiores en la mayor medida posible.
• Relajadamente Estable (Relaxed-Stable): Una noción de estabilidad generalizada que permite ciertas "pares bloqueantes" justificadas, específicamente aquellas que involucran a agentes que no están cumpliendo sus cuotas inferiores o que están excediendo sus cuotas mínimas de manera necesaria.

2. Metodología y Algoritmo Propuesto

Los autores proponen un algoritmo polinómico basado en propuestas que combina y extiende dos marcos teóricos existentes:

1. El algoritmo de Király (2013) para emparejamientos estables de tamaño máximo con empates (escenario muchos-a-uno sin cuotas).
2. El algoritmo de Nasre et al. (2024) para emparejamientos críticos populares con cuotas inferiores (escenario muchos-a-muchos sin empates).

Componentes Clave del Algoritmo:

• Estructura de Niveles (Multi-level Framework):
  El algoritmo utiliza un sistema de niveles ($0$a$s+t$) para gestionar las propuestas.

  • **Niveles $0$a$t-1$:** Se enfocan en satisfacer las cuotas inferiores del lado$B$. Los vértices del lado$A$solo proponen a vértices de$B$ que tienen cuotas inferiores.
  • Nivel $t$: Implementa la adaptación del algoritmo de Király para manejar los empates. Aquí se introducen conceptos clave como "propuestas inciertas" (uncertain proposals) y "vecino favorito" (favorite neighbor).
  • Niveles $t+1$ a $s+t$: Se enfocan en satisfacer las cuotas inferiores del lado $A$ si aún quedan deficientes.

• Propuestas Inciertas (Uncertain Proposals):
  Una propuesta se etiqueta como "incierta" si un vértice propone a un vecino de rango $k$ y existe otro vecino del mismo rango $k$ que aún no ha sido propuesto y está sub-suscrito. Esto permite manejar la ambigüedad de los empates sin descartar opciones prematuramente, garantizando que el algoritmo no pierda estabilidad.

• Manejo de la Indiferencia y Reasignación:
  A diferencia de algoritmos anteriores que borran vecinos de las listas de preferencias al ser rechazados, este algoritmo utiliza un sistema de marcado. Si una propuesta es rechazada pero es "incierta", el vértice receptor queda marcado, permitiendo futuras re-proposiciones bajo ciertas condiciones para mantener la estabilidad.

• Construcción del Grafo Clonado ($G_M$):
  Para probar la corrección, los autores construyen un grafo clonado donde cada vértice original se divide en múltiples clones (uno por cada posición de su cuota). Esto transforma el problema muchos-a-muchos en uno de uno-a-uno, facilitando el análisis de caminos alternantes y la demostración de propiedades de optimalidad.

3. Contribuciones Clave

1. Generalización de la Estabilidad Relajada:
   Extienden la definición de estabilidad relajada (anteriormente solo para el problema de Hospitales/Residentes con listas estrictas) al escenario muchos-a-muchos con empates y cuotas inferiores en ambos lados. Demuestran que un emparejamiento Crítico Relajadamente Estable (CRITICAL-RSM) siempre existe en este modelo generalizado.

2. Refinamiento del Algoritmo de Király:
   Identifican y corrigen un problema técnico en la definición original de "propuesta incierta" de Király (que requería que el proponente estuviera totalmente suscrito, lo cual podía llevar a inestabilidad). Proponen una definición corregida y la extienden al escenario muchos-a-muchos, donde un vértice puede estar involucrado en múltiples propuestas inciertas simultáneamente.

3. Algoritmo de Aproximación:
   Presentan un algoritmo que calcula un emparejamiento CRITICAL-RSM en tiempo polinómico.

4. Resultados Principales

• Existencia: Se demuestra teóricamente que siempre existe al menos un emparejamiento que es crítico y relajadamente estable en el modelo propuesto.
• Dureza Computacional: El problema de encontrar el emparejamiento CRITICAL-RSM de tamaño máximo es NP-duro. Esto se debe a que, incluso sin cuotas inferiores, maximizar el tamaño de un emparejamiento estable con empates es NP-duro.
• Factor de Aproximación:
  El algoritmo propuesto logra un factor de aproximación de $2/3$ respecto al tamaño del emparejamiento CRITICAL-RSM máximo posible.
  • Teorema 1: Existe un algoritmo de tiempo polinómico que computa una aproximación de $2/3$ para el tamaño máximo de un emparejamiento crítico relajadamente estable.
  • Este factor es óptimo bajo la Hipótesis de Expansión de Conjuntos Pequeños (Small Set Expansion Hypothesis), coincidiendo con los mejores resultados conocidos para el problema de emparejamiento estable con empates sin cuotas.

5. Significado e Impacto

Este trabajo es significativo por varias razones:

• Unificación de Modelos: Es uno de los primeros trabajos que integra simultáneamente empates, cuotas inferiores en ambos lados y el escenario muchos-a-muchos. Modelos anteriores solían restringir uno de estos aspectos (ej. solo cuotas en un lado, o sin empates).
• Aplicabilidad Práctica: El modelo es altamente relevante para problemas del mundo real como:
  • Asignación de estudiantes a cursos (donde los cursos tienen mínimos de inscritos y los estudiantes tienen mínimos de créditos).
  • Asignación de trabajadores a empresas (donde las empresas necesitan un mínimo de personal y los trabajadores pueden tener preferencias grupales).
• Viabilidad de Implementación: A pesar de la complejidad teórica, el algoritmo es una extensión directa del clásico algoritmo de Gale-Shapley, lo que lo hace factible de implementar en sistemas reales.
• Compromiso Óptimo: Dado que la estabilidad estricta y la criticidad no pueden garantizarse simultáneamente, la noción de "estabilidad relajada" ofrece un compromiso práctico y teóricamente sólido, asegurando que las cuotas se satisfagan lo mejor posible sin crear inestabilidades injustificadas.

En resumen, el artículo establece un nuevo estándar teórico para el emparejamiento bipartito con restricciones complejas, proporcionando un algoritmo eficiente con garantías de rendimiento sólidas ($2/3$) en un escenario que antes se consideraba intratable para encontrar soluciones óptimas.