El modelo del matrimonio con indiferencias: Un enfoque desde la programación lineal

NOELIA MARIEL JUAREZ; PABLO NEME; JORGE OVIEDO

Mendoza

Congreso; Reunión anual de la UMA; 2019

Unión Matemática Argentina, Universidad Nacional de Cuyo

En este trabajo estudiamos el modelo de asignación bilateral (matching) uno-a-uno con indiferencias. Últimamente han surgido problemas donde se muestra la necesidad de estudiar el modelo con indiferencias. Un ejemplo es el ingreso de alumnos de nivel inicial (o medio) a las escuelas (ver Referencias), estas priorizan a los alumnos con algún criterio (cercanía o zona de influencia, notas, etc.) sin embargo puede haber indiferencias en estos ordenes de prioridad, mientras que los estudiantes tienen un orden de preferencia (estricto) sobre las escuelas a las que quieren asistir. El objetivo es asignar estudiantes (en forma estable o robusta) a las escuelas. El modelo con indiferencias es una generalización del modelo sin indiferencias o modelo clásico, este último ha sido muy estudiado. Hay ejemplos del modelo con indiferencias donde no se pueden generalizar los resultados del modelo clásico. Vande Vate (1989) y Rothblum (1992) estudiaron el modelo de asignación bilateral uno-a-uno con preferencias estrictas utilizando como herramienta programación lineal. Introdujeron un sistema de inecuaciones lineales que generaron un poliedro convexo. Demostraron que las asignaciones estables del modelo uno-a-uno eran exactamente los puntos extremos de este poliedro convexo. En este trabajo, caraterizamos las asignaciones estables del modelo con indiferencias, como soluciones enteras de un sistema de inecuaciones lineales generalizando así el resultado de Vande Vate (1989) y Rothblum (1992). En el modelo de asignación uno-a-uno con preferencias estrictas , Gale y Shapley (1962) mostraron la existencia de las asignaciones estables óptimas para el conjunto de hombres y de mujeres μ_{M} y μ_{W} respectivamente. La asignación μ_{M} es estable óptima en el sentido de que no existe otra asignación estable μ que da a cada hombre m un resultado μ(m) que prefiera estrictamente a μ_{M}(m), de manera similar ocurre con μ_{W}. Al permitir indiferencias en las preferencias las asignaciones estables óptimas podrían no ser únicas. Mostramos, un programa lineal entero que calcula una asignación estable optimal para el conjunto de hombres (mujeres).