Note on the size of a stable matching

Resumen Técnico: Nota sobre el Tamaño de un Emparejamiento Estable

Planteamiento del Problema
El artículo investiga la relación entre el tamaño de un emparejamiento estable y el tamaño del mayor emparejamiento individualmente racional (máximo) en un mercado de emparejamiento de dos lados uno a uno (trabajadores y empresas con una sola posición). Si bien el marco de Gale-Shapley garantiza la existencia de emparejamientos estables, no garantiza que estos maximicen el número de trabajadores empleados o de posiciones ocupadas. Los autores abordan la siguiente cuestión: dado un mercado donde el mayor emparejamiento individualmente racional contiene $n$ pares, ¿cuál es el límite inferior en el número de pares en cualquier emparejamiento estable? Además, buscan caracterizar las estructuras de preferencias específicas que fuerzan a los emparejamientos estables a ser lo más pequeños posible en relación con el máximo, y analizan el solapamiento entre los pares estables y los pares máximos.

Metodología
Los autores emplean un enfoque de teoría de grafos para modelar el mercado de emparejamiento, utilizando formulaciones de grafos tanto no dirigidos como dirigidos.

1. Formulación de Grafo No Dirigido: El mercado se modela como un grafo bipartito $G = (W, F; E)$, donde las aristas representan pares aceptables. Los autores utilizan las propiedades de los emparejamientos maximales y máximos para establecer límites.
2. Formulación de Grafo Dirigido (Digrafo): Para caracterizar las estructuras de preferencias, los autores adoptan la formulación de digrafo de emparejamiento propuesta por Maffaffray (1992). En este digrafo $D = (V, A)$, los vértices representan pares aceptables $(w, f)$, y las arcos representan clasificaciones de preferencia (por ejemplo, un arco de $(w, f)$ a $(w, f')$ indica que el trabajador $w$ prefiere $f'$ a $f$).
3. Eliminación Iterativa de Alternativas Poco Atractivas (IDUA): Los autores utilizan el procedimiento IDUA (Balinski y Ratier, 1997; Gutin et al., 2023) para reducir el mercado a su "forma normal". Este proceso elimina iterativamente los pares que no pueden pertenecer a ningún emparejamiento estable (por ejemplo, pares donde un participante está emparejado con un socio menos preferido mientras que su socio más preferido no está emparejado).
4. Caracterización Constructiva: Los autores definen clases específicas de mercados ($G_n$ y $F_n$) mediante la construcción de perfiles de preferencias que extienden un mercado base con un emparejamiento estable máximo, añadiendo nuevos participantes cuyas preferencias están estructuradas para ser "poco atractivas" para los participantes estables existentes.

Contribuciones Clave y Resultados

• Teorema 1 (Límite de Tamaño): El resultado principal establece que en cualquier mercado donde el mayor emparejamiento individualmente racional tiene tamaño $n$, cada emparejamiento estable debe tener un tamaño de al menos $\lceil n/2 \rceil$.

  • Lógica de la Demostración: La demostración se basa en dos hechos: (i) un emparejamiento estable es un emparejamiento maximal (no existe un par aceptable donde ambas partes estén sin emparejar), y (ii) cualquier emparejamiento maximal en un grafo es al menos la mitad del tamaño de un emparejamiento máximo.
  • Implicación: La tasa de empleo de equilibrio nunca puede caer por debajo del 50% del empleo máximo alcanzable, siempre que el emparejamiento máximo sea individualmente racional.

• Teorema 2 (Caracterización de Preferencias Extremas): El artículo caracteriza la clase de perfiles de preferencias ($F_n$) que alcanzan este límite inferior.

  • Un mercado alcanza el límite (tamaño estable = $\lceil n/2 \rceil$, tamaño máximo = $n$) si y solo si pertenece a la clase $F_n$.
  • Propiedad Estructural: En estos mercados, los participantes que no aparecen en ningún emparejamiento estable (los "no emparejados" en el equilibrio) deben encontrarse mutuamente como inaceptables. Si se encontraran aceptables, formarían un par de bloqueo, aumentando el tamaño del emparejamiento estable.
  • Acuerdo en la Cúspide: Una subclase natural de estos mercados exhibe "acuerdo en la cúspide" (agreement at the top), donde los participantes en el núcleo estable clasifican a todos los nuevos participantes no estables por debajo de su socio estable menos preferido.

• Teorema 3 (Solapamiento y Sacrificio): Los autores analizan la intersección entre el conjunto de pares en un emparejamiento estable ($\mu^*$) y un emparejamiento máximo ($\mu$).

  • Sea $r$ el número de pares comunes. El teorema establece que: $|\mu^*| \geq (|\mu| + r) / 2$.
  • Implicación: Cuando el emparejamiento estable se minimiza (es decir, $|\mu^*| = \lceil |\mu|/2 \rceil$), el solapamiento $r$ debe ser cero. Esto significa que, si el mercado está estructurado de tal manera que los emparejamientos estables son lo más pequeños posible, ninguno de los pares en el emparejamiento estable aparece en el emparejamiento máximo.
  • Costo de la Estabilidad: Maximizar el empleo (llenar todas las vacantes) puede requerir "sacrificar" todos los emparejamientos de equilibrio que de otro modo existirían en una configuración estable más pequeña.

Significancia y Alcance
El artículo enmarca su análisis como una exploración del "costo de la estabilidad". Cuantifica la compensación entre la estabilidad y la eficiencia (medida por el tamaño del emparejamiento). Los autores señalan que, si bien la estabilidad asegura que no haya pares de bloqueo, puede resultar en una reducción significativa del número de trabajadores empleados en comparación con el máximo teórico, específicamente en mercados con las estructuras de preferencia identificadas en el Teorema 2.

Los autores limitan explícitamente el alcance de sus resultados a mercados de emparejamiento de dos lados uno a uno. Reconocen que, aunque el marco es ampliamente aplicable (por ejemplo, estudiante-colegio, médico-hospital), los límites específicos y las caracterizaciones derivadas aquí no se extienden automáticamente a entornos más complejos, tales como mercados de muchos a uno, mercados con parejas, o problemas de "compañeros" (roommate) de un solo lado. El artículo no propone nuevos algoritmos o aplicaciones experimentales, sino que proporciona un límite teórico y una caracterización estructural de los escenarios de peor caso para las tasas de empleo en equilibrios estables.