¿Conoces algún código disponible públicamente en python o R (o cualquier otro lenguaje de alto nivel libre) que devuelva todo los emparejamientos estables para cualquier problema de emparejamiento uno a uno?
Nota : Esto está relacionado pero es diferente de ¿Código disponible para calcular las soluciones de los algoritmos de correspondencia? .
En esta otra pregunta, pedía código que implementara mecanismos famosos como el de la aceptación diferida. Algunos de estos mecanismos encuentran un la coincidencia estable, entre otros. Aquí estoy buscando un código que encuentre todo coincidencias estables.
He inspeccionado los paquetes recomendados en las respuestas que obtuve a ¿Código disponible para calcular las soluciones de los algoritmos de correspondencia? y no encontré nada que hiciera el trabajo.
0 votos
En un entorno de emparejamiento bipartito, sólo hay dos emparejamientos estables: el emparejamiento estable óptimo del proponente y el emparejamiento estable óptimo del aceptante. Si se ejecuta Gale-Shapley para ambos casos, se obtendrá el resultado deseado.
1 votos
@ml0105 : No debemos tener el mismo modelo en mente. En el escenario de emparejamiento bipartito que tengo en mente (el del artículo original de Gale y Shapley de 1962), puede haber un gran número de emparejamientos estables (y se ha escrito mucho sobre ellos, especialmente sobre su estructura de red cuando se emparejan con la relación binaria apropiada). Para un ejemplo sencillo, véase, por ejemplo, el ejemplo 3.7 en Klaus, B., y Klijn, F. (2006). "Median Stable Matching for College Admissions" que presenta 3 emparejamientos estables (lo siento si no puedes acceder a él, quería reproducirlo aquí pero es demasiado largo para un comentario).
0 votos
Me corrijo (¡y pido disculpas por la información errónea!)