No es un problema clásico en la combinatoria de tratar con la estabilidad de la vinculación entre un conjunto de hombres y un conjunto de las mujeres como esposas. (Gale-bien formada algoritmo) http://en.wikipedia.org/wiki/Stable_marriage_problem
Es que hay equivalente algoritmo para determinar la estabilidad de una pareja, donde las mujeres eligen a los hombres, los hombres eligen a los perros, y los perros de elegir a las mujeres? Se le garantiza llegar a un matching estable formada de un hombre, una mujer y un perro?
Voy a definir estable a decir que si tenemos dos triples $(m_1, w_1, d_1$) y ($m_2, w_2, d_2$), entonces no podemos tener ese $w_1$ deseos de estar con $m_2$ más que con $m_1$ $m_2$ deseos propios $d_1$ más de lo que él desea propia $d_2$. Ignoramos la preferencia de los perros en este caso. Así que la inestabilidad se define como un miembro de una triple, llamarlo $T_1$, de deseos, de otra asociación, y la persona o perro con el que deseen unirse también deseos de dejar su propia vinculación a unirse con el tercer miembro de $T_1$.
Parecería como encontrar un matching estable puede ser mucho más difícil que el original hombre mujer problema. ¿Hay pruebas de la imposibilidad de lo que sabemos?
