# Man, Woman, Dog, seeking stable relationship.

There is a classic problem in combinatorics dealing with a stable pairing between a set of men and a set of women as spouses. (Gale-Shapely algorithm) http://en.wikipedia.org/wiki/Stable_marriage_problem

Is there are equivalent algorithm for determining the stability of a pairing where women choose men, men choose dogs, and dogs choose women? Are we guaranteed to arrive at a stable matching consisting of a man, a woman, and a dog?

I will define stable to mean that if we have two triples $(m_1, w_1, d_1$) and ($m_2, w_2, d_2$), then we cannot have that $w_1$ desires to be with $m_2$ more than with $m_1$ and $m_2$ desires to own $d_1$ more than he desires to own $d_2$. We ignore the preference of the dogs in this case. So instability is defined to mean that a member of one triple, call it $T_1$, desires another partnering, and the person or dog with whom they wish to join also desires to leave their own pairing to join with the third member of $T_1$.

It would seem like finding a stable matching may be much more challenging than the original man woman problem. Are there any proofs of impossibility that we know of?

• If we add the constraint that the third member of the triple must also concur with the change, that would no doubt make obtaining a stable matching easier. Commented Oct 18, 2013 at 23:16
• dcs.gla.ac.uk/~pbiro/papers/BMcD08comsoc_final.pdf provides a paper discussing this subject. Commented Nov 5, 2013 at 20:37
• sciencedirect.com/science/article/pii/S1389128612003520 is another article delving into the subject. Commented Nov 5, 2013 at 20:44
• Thanks for the references. You can answer a question yourself, you know. ;) Commented Dec 4, 2013 at 11:30
• If you want a stable matching, shouldn't you use horses instead of dogs? Commented Dec 4, 2013 at 20:58