¿Cómo cambia el bienestar social cuando las dos entidades no tienen el mismo número de individuos en ellas, de modo que no todos pueden ser emparejados?
El algoritmo funciona bien en este caso. La suposición importante sigue siendo que el grafo subyacente es bipartito (y que las preferencias son transitivas). Si permitimos que los miembros de un tipo determinado se propongan unos a otros, perdemos la convergencia. Supongamos que tenemos tres jugadores: $A, B, C$ . Tenemos $A$ Las preferencias de los usuarios son las siguientes $(B, C, A)$ ; $B$ Las preferencias de los usuarios son las siguientes $(C, A, B)$ y $C$ Las preferencias de los usuarios son las siguientes $(A, B, C)$ . Así que $A$ propone $B$ que acepta. Entonces $B$ propone $C$ que acepta. Esto desempata $A$ . Siguiente, $C$ propone $A$ que acepta. Esto desempata $B$ . Entonces repetimos.
¿Hay formas más rápidas de emparejar a los individuos entre sí (menor tiempo de ejecución?)
Gale-Shapley tiene una complejidad de ejecución de $\Theta(n^{2})$ . En la teoría de grafos, la mayoría de los algoritmos de emparejamiento bipartito toman $\Omega(|E| \sqrt{|V|})$ tiempo. En el peor de los casos, $|E| = |V|^{2}/4$ . Así que yo no apostaría por algo mejor.
Además, este no es un problema que se preste a un enfoque de divide y vencerás. Es realmente un problema de codicia. Es posible que se pueda reducir el tiempo de ejecución esperado seleccionando un orden aleatorio para las propuestas. Sin embargo, el análisis sería complicado.
Me parece un modelo de teoría de juegos muy extraño porque cuando leo la prueba de la validez del algoritmo, no parece que el problema sea "discreto"; es decir, optimizar quién se empareja con quién y encontrar un resultado eficiente de Pareto no puede resolverse mediante la maximización de una función continua.
En realidad, es un modelo discreto. En los campos más tradicionales de la economía, tenemos variables continuas. Así que la programación lineal tiene sentido. De hecho, podríamos formular un programa entero-lineal para el problema del matrimonio estable si lo miramos desde la perspectiva de la teoría de los gráficos. Los problemas de emparejamiento pueden formularse en el lenguaje de los flujos. Y podemos escribir los problemas de flujos como LPs. Las restricciones de flujo forman un politopo convexo. Si el grafo es bipartito, los vértices del politopo son los emparejamientos. El truco aquí es que tenemos que añadir restricciones adicionales para asegurarnos de que terminamos con el emparejamiento correcto (ya que el emparejamiento del algoritmo Gale-Shapley es único, independientemente del orden en el que se propongan los hombres).
Incluso si nos tomamos la molestia de formular el programa lineal, la resolución de un LP para este problema a mano o por ordenador es menos eficiente que el uso del algoritmo.
(Como pregunta al margen, ¿es la asignación de Gale-Shapley Pareto eficiente?)
La coincidencia generada por el algoritmo Gale-Shapely está en el núcleo. Una imputación perteneciente al núcleo satisface la propiedad de que ninguna coalición puede coludir sus dotaciones iniciales y mejorar los resultados de sus miembros. Una imputación es óptima de Pareto si ningún conjunto de agentes puede mejorar sus resultados sin que el resultado de otro jugador sea menos favorable. Por tanto, las imputaciones del núcleo son óptimas de Pareto.
Para más información sobre Gale-Shapley, consulte mi blog: https://michaellevet.wordpress.com/2015/05/22/algorithmic-game-theory-stable-marriage-problem/
