Random Matching with Minimums

Resumen Técnico: Emparejamiento Aleatorio con Mínimos

Enunciado del Problema
Este artículo aborda problemas de asignación estocástica de objetos donde los objetos están sujetos tanto a restricciones de capacidad máxima ($c_j$) como a restricciones de requisito mínimo ($m_j$). Si bien los mecanismos estándar de asignación aleatoria (como la Dictadura Serial Aleatoria o el mecanismo de Consumo Probabilístico) manejan las restricciones de capacidad, no logran garantizar asignaciones implementables cuando existen cuotas mínimas. El desafío central es construir un mecanismo de asignación aleatoria que:

1. Produzca una asignación aleatoria implementable (aquella que puede descomponerse en una lotería sobre asignaciones deterministas factibles que satisfacen todas las $m_j$ y $c_j$).
2. Logre eficiencia de Dominancia Estocástica (DE) (eficiencia de Pareto bajo dominancia estocástica de primer orden).
3. Mantenga propiedades de equidad (ausencia de envidia y anonimato).
4. Preserve la incentivabilidad débil en el escenario de demanda unitaria.

La literatura existente enfrenta un compromiso: mecanismos como el Consumo Probabilístico Generalizado (GPS) de Budish et al. (2013) manejan restricciones bijerárquicas (máximos únicamente) pero no pueden representar mínimos. Por el contrario, el Consumo Probabilístico Constrained Generalizado (GCPS) de Balbuzanov (2022) maneja restricciones arbitrarias pero requiere enumerar todas las asignaciones deterministas permitidas para caracterizar el politopo factible. Esta enumeración tiene complejidad factorial, lo que hace que el GCPS sea computacionalmente intratable incluso para tamaños de problema modestos.

Metodología
Los autores proponen el mecanismo de Consumo Probabilístico Mínimo (MPS). La metodología procede en dos etapas principales:

1. Caracterización del Politopo Factible:
   En lugar de enumerar el conjunto de asignaciones deterministas $D$ (lo cual es computacionalmente prohibitivo), los autores caracterizan directamente el conjunto de asignaciones aleatorias implementables, denotado $\Delta_D$, utilizando un sistema de desigualdades lineales positivas.

   • Para el caso de demanda unitaria ($d=1$), derivan un sistema específico de desigualdades (Proposición 3) que define el conjunto de contorno inferior $lcs(\Delta_D)$. Este sistema incluye:
     • Restricciones de demanda unitaria ($\sum_j \mu_{ij} \leq 1$).
     • Restricciones de capacidad ($\mu_j \leq c_j$).
     • Un nuevo conjunto de restricciones (Min-III) que asegura que, para cualquier subconjunto de objetos $S$ con mínimos, la probabilidad total asignada a objetos fuera de $S$ no exceda la capacidad restante de los agentes para satisfacer los mínimos de $S$.
   • Esta caracterización se simplifica ulteriormente a una forma compacta (Proposición 4) que involucra $\sum_j \max\{m_j, \mu_j\} \leq N$, lo cual facilita una implementación algorítmica.
   • Para demanda general ($d > 1$), proporcionan un sistema más complejo de desigualdades (Proposición 5) derivado utilizando el teorema de existencia de Hoffman para circulaciones en redes.

2. Diseño del Mecanismo y Algoritmo:

   • Definición de Tiempo Continuo: El mecanismo MPS se define como un proceso de "consumo" en tiempo continuo (análogo al Consumo Probabilístico) donde los agentes consumen su objeto disponible más preferido a una velocidad uniforme. Un objeto es "disponible" solo si consumirlo no viola las desigualdades lineales derivadas.
   • Algoritmo de Tiempo Discreto: Aprovechando la estructura específica de las desigualdades de demanda unitaria, los autores construyen el Algoritmo 1, un algoritmo discreto de tiempo polinomial. El algoritmo procede en pasos donde los agentes consumen objetos hasta que una restricción se vuelve vinculante. Crucialmente, el algoritmo identifica un tiempo crítico $\tau$ donde las restricciones globales mínimas se vuelven vinculantes. En $\tau$, cualquier objeto que haya cumplido su requisito mínimo se cierra a un consumo posterior, asegurando que los agentes restantes se vean obligados a satisfacer los mínimos de otros objetos.

Resultados Clave
El artículo establece las siguientes propiedades teóricas para el mecanismo MPS:

• Eficiencia DE: El mecanismo MPS produce asignaciones que son eficientes en Dominancia Estocástica. Ninguna otra asignación aleatoria implementable es preferida por todos los agentes mediante dominancia estocástica de primer orden.
• Equidad: El mecanismo es anónimo (invariante ante la reindexación de agentes) y sin envidia (ningún agente prefiere estrictamente la lotería de otro agente).
• Incentivabilidad: En el caso de demanda unitaria, MPS es débilmente incentivable. Los agentes no pueden lograr una asignación estocásticamente dominante reportando incorrectamente sus preferencias. La prueba se basa en demostrar que manipular las preferencias para alterar el tiempo crítico $\tau$ o los tiempos de cierre de los objetos nunca genera un beneficio neto para el que reporta incorrectamente.
  • Nota: Para demanda general ($d > 1$), el mecanismo permanece eficiente en DE, anónimo y sin envidia, pero se pierde la incentivabilidad débil, lo cual es consistente con los hallazgos de Kojima (2009b).
• Implementación: La asignación aleatoria resultante está garantizada para ser implementable. Dado que las restricciones son bijerárquicas (en el sentido de Budish et al., 2013), el teorema de Birkhoff-von Neumann (o su generalización en BCKM13) asegura que la asignación aleatoria puede descomponerse en una lotería sobre asignaciones deterministas factibles.

Significado y Afirmaciones
El artículo afirma cerrar la brecha entre los mecanismos teóricos de asignación aleatoria y las aplicaciones prácticas que involucran cuotas mínimas (por ejemplo, clubes escolares, equipos de proyectos, selección de jurados).

• Viabilidad Computacional: La contribución principal es proporcionar el primer algoritmo factible para el emparejamiento aleatorio con mínimos. Al evitar la complejidad factorial de enumerar asignaciones deterministas y la complejidad exponencial del problema de enumeración de facetas (FEP) requerido por Balbuzanov (2022), los autores proporcionan un algoritmo de tiempo polinomial para el caso de demanda unitaria.
• Preservación de Incentivos: A diferencia del mecanismo GCPS más general, que pierde la incentivabilidad débil, el mecanismo MPS preserva esta propiedad en el escenario de demanda unitaria.
• Extensión Teórica: El trabajo generaliza el mecanismo de Consumo Probabilístico a entornos con límites inferiores, demostrando que la eficiencia y la equidad pueden mantenerse incluso cuando la estructura de restricciones impide el uso de marcos estándar bijerárquicos de solo máximos.

Los autores declaran explícitamente que, aunque proporcionan un algoritmo de tiempo polinomial para la demanda unitaria, la descripción algorítmica para la demanda general ($d > 1$) sigue siendo una pregunta abierta para futuras investigaciones debido a la mayor complejidad del sistema de desigualdades.