Sesión Matemática Discreta y Teoría de JuegosEstabilidad y pseudo-estabilidad en mercados de matching muchos-a-muchos con preferencias responsivas
Paola B. Manasero
Universidad Nacional de San Luis - Instituto de Matemática Aplicada San Luis, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Estudiamos el problema de calcular matchings estables en mercados de matching muchos-a-muchos con preferencias responsivas. Para ello, construimos un mercado de matching auxiliar uno-a-uno aplicando de manera independiente la clásica construcción por copias a cada lado del mercado. Sin embargo, a diferencia del caso muchos-a-uno, la noción clásica de estabilidad en el mercado auxiliar uno-a-uno no caracteriza los matchings estables del mercado original muchos-a-muchos. Para superar esta dificultad, introducimos la noción de matching pseudo-estable, que proporciona el concepto adecuado de estabilidad para el mercado auxiliar uno-a-uno y establece el vínculo teórico con los matchings estables del mercado original. Demostramos que todo matching pseudo-estable induce un matching estable en el mercado original y que todo matching estable es inducido por al menos un matching pseudo-estable. A partir de esta caracterización, desarrollamos una versión modificada del algoritmo de Aceptación Diferida (Deferred Acceptance Algorithm), que calcula matchings pseudo-estables en el mercado auxiliar uno-a-uno y, en consecuencia, produce matchings estables en el mercado original muchos-a-muchos. Nuestro enfoque extiende la correspondencia clásica entre mercados muchos-a-uno con preferencias responsivas y sus mercados auxiliares uno-a-uno al contexto de mercados muchos-a-muchos.
Trabajo en conjunto con: Noelia Juárez (Universidad Nacional de San Luis, Instituto de Matemática Aplicada San Luis) y Jorge Oviedo (Instituto de Matemática Aplicada San Luis (CONICET - UNSL)).