Materia	Carrera	Plan	Año	Periodo
() MODELOS DE ASIGNACIÓN BILATERAL	LIC.EN CS.MAT.	09/17	2025	1° cuatrimestre

Docente	Función	Cargo	Dedicación
JUAREZ, NOELIA MARIEL	Prof. Responsable	P.Asoc Exc	40 Hs
MANASERO, PAOLA BELEN	Prof. Responsable	P.Asoc Exc	40 Hs
LUCERO QUEVEDO, ANDRES MAURICI	Responsable de Práctico	A.1ra Simp	10 Hs

En los modelos de asignación bilateral, o simplemente modelos de matching (ver Gale y Shapley, 1962), se analizan las asignaciones que, en un marco de equilibrio general, corresponden a los óptimos de mercados centralizados. La importancia de encontrar formas efectivas (es decir, computacionales) para resolver problemas de asignación es innegable. Estos modelos han sido ampliamente utilizados para estudiar problemas de asignación cuya característica fundamental es la división de los conjuntos de agentes en dos subconjuntos disjuntos. Uno de estos conjuntos incluye instituciones como empresas, hospitales, universidades, orquestas, escuelas, clubes, entre otros, mientras que el otro conjunto incluye individuos como trabajadores, médicos internos, estudiantes, músicos, niños, jugadores, etc. Cada agente en uno de los subconjuntos tiene preferencias sobre los agentes del otro subconjunto.
El caso en el que un lado del mercado tiene preferencias estrictas y el otro sigue un sistema de prioridades es conocido en la literatura como el problema de asignación de estudiantes a escuelas. En este contexto, nos referiremos a los agentes con preferencias estrictas como "estudiantes" y a aquellos con prioridades como "escuelas". La naturaleza del problema consiste en asignar a cada escuela un subconjunto de estudiantes y a cada estudiante una escuela.
Tradicionalmente, en la mayor parte del mundo, los estudiantes han sido asignados a escuelas según las zonas en las que residen. Sin embargo, desde la década de 1980, un número creciente de distritos en los Estados Unidos ha ofrecido a los padres la opción de elegir entre diferentes escuelas públicas, ampliando así el acceso de las familias a instituciones más allá de su área de residencia.
La forma en que se asignan los estudiantes es una parte integral de los programas de elección de escuelas. Abdulkadiroğlu y Sönmez (2003) abordan el problema de asignación de estudiantes a escuelas públicas desde la perspectiva de la teoría de diseño de mecanismos. Lo hacen mediante un modelo de asignación bilateral en el que los estudiantes tienen preferencias sobre las escuelas, mientras que las escuelas ordenan a los estudiantes de acuerdo con un sistema de prioridades.

El objetivo de este curso es introducir a los estudiantes en los modelos de asignación bilateral. Se busca que los participantes se familiaricen con los conceptos fundamentales y las propiedades básicas de estos modelos, así como con las áreas de estudio más activas y dinámicas dentro de este campo. Asimismo, se presentarán problemas abiertos que podrían resultar de interés para los asistentes al curso.

Unidad 1. Introducción a los modelos de asignación (matching) bilateral. Historia de mercados que se ajustan a estos modelos. Un enfoque desde la Teoría de Juegos.
Unidad 2. Modelo de matching uno a uno. Características. Definición de matching. Matchings individualmente racional y estables. Propiedades. Existencia de matchings estables. Algoritmo de Aceptación diferida. Matchings óptimos.
Unidad 3. Estructura del conjunto de matchings estables. Reticulado, operaciones binarias. Dualidad del reticulado. Contraposición de intereses. Teorema del Hospital Rural. Comportamiento estratégico. Modelo de matching uno a uno con indiferencias.
Unidad 4. Reducción de preferencias. Ciclos. Matching cíclico. Algoritmos para el cálculo de todos los matchings estables. Algoritmo de Irving y Leather. Algoritmo de McVitie y Wilson. Algoritmo de Gusfield. Aspectos computacionales entre los distintos algoritmos.
Unidad 5. Programación lineal. Caracterización de los matchings estables del modelo uno a uno como puntos extremos de un politopo convexo. Características. Comportamiento estratégico. Propiedades.
Unidad 6. El modelo de matching muchos a uno con preferencias responsivas. Estabilidad. Estabilidad por grupos. Características. Descomposición al modelo uno a uno. El Algoritmo de NIMP.
Unidad 7. El modelo de matching muchos a uno con preferencias sustituibles. Existencia de matchings estables. Orden de Blair. Ley de la Demanda Agregada. Estructura del conjunto de matchings
estables. Reticulado, operaciones binarias.

Los trabajos prácticos consistirán en la resolución de ejercicios en las horas destinadas a tal fin, y resolución de ejercicios propuestos fuera del horario establecido que luego podrán ser consultados.

Evaluación:
Promoción sin examen final: Se llevará a cabo a través de una evaluación continua con entrega de ejercicios escritos. La entrega total de ejercicios debe estar aprobado con al menos un 70%. Además, cada estudiante deberá realizar al menos 3 exposiciones orales a lo largo del cuatrimestre, referido a los ejercicios entregados. Se requerirá al menos del 80% de asistencia a clases. El estudiante que cumpla con los requisitos detallados obtendrá la condición de estudiante promocionable. Quienes hayan obtenido esta condición deberán rendir un examen integrador oral.
Regularidad: Se llevará a cabo a través de una evaluación continua con entrega de ejercicios escritos. La entrega total de ejercicios debe estar aprobado con al menos un 60%. Además, cada estudiante deberá realizar al menos 3 exposiciones orales a lo largo del cuatrimestre referido a los ejercicios entregados. Se requerirá al menos del 70% de asistencia a clases. El estudiante que cumpla con los requisitos detallados obtendrá la condición de estudiante regular. Quienes hayan obtenido esta condición deberán rendir un examen final en las fechas establecidas por calendario
académico.

[1] Roth, A. and M. Sotomayor (1990): Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis, Cambidge University Press, Cambridge.

[1] • Alkan, A. (2002): “A class of multipartner matching markets with a strong lattice structure,”
[2] Economic Theory, 19, 737–746.
[3] • Bonifacio, A., Guinazu, N., Juarez, N., Neme, P., & Oviedo, J. (2021). The lattice of worker-quasistable
[4] matchings. arXiv preprint arXiv: 2103.16330.
[5] • Blair, C. (1988): “The lattice structure of the set of stable matchings with multiple partners,”
[6] Mathematics of Operations Research, 13, 619–628.
[7] • Blum, Y., A. Roth, and U. Rothblum (1997): “Vacancy chains and equilibration in senior-level
[8] labor markets,” Journal of Economic theory, 76, 362–411.
[9] • Echenique, F. and J. Oviedo (2004): “Core many-to-one matchings by fixed-point methods,”
[10] Journal of Economic Theory, 115, 358–376.
[11] • Fleiner, T. (2003): “A fixed-point approach to stable matchings and some applications,”
[12] Mathematics of Operations Research, 28, 103–126.
[13] • Gale, D. and L. Shapley (1962): “College admissions and the stability of marriage,” The American
[14] Mathematical Monthly, 69, 9–15.
[15] • Gusfield, D. and R. W. Irving (1989): The stable marriage problem: structure and algorithms, MIT
[16] press.
[17] • Irving, R. and P. Leather (1986): “The complexity of counting stable marriages,” SIAM Journal on
[18] Computing, 15, 655–667.
[19] • Juarez, N., Neme, P. A., and Oviedo, J. (2021). Marriage market with indifferences: A linear
[20] programming approach. Journal of the Operations Research Society of China, 1-24.

El objetivo de este curso es introducir a los estudiantes en los modelos de asignación bilateral.

Se estudian modelos de asignación (matching) bilateral desde la Teoría de Juegos, aplicables a distintos mercados. Se analiza el modelo uno a uno, con conceptos clave como estabilidad y racionalidad, y se presentan algoritmos para encontrar matchings estables.

Luego se explora la estructura matemática de los matchings, incluyendo reticulados y comportamiento estratégico. Se revisan algoritmos clásicos y aspectos computacionales.

Se introduce la programación lineal para caracterizar matchings estables como puntos extremos de politopos. Finalmente, se abordan los modelos muchos a uno, primero con preferencias responsivas y luego con preferencias sustituibles, incluyendo condiciones de estabilidad y estructuras del conjunto de matchings.

 

Email de contacto noemjuarez@gmail.com