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?
While the question itself is not as hard and fast as Gale-Shapely, there are methods for finding a "stable-enough" matching. Similar to many approximate solutions to the traveling salesman problem, many times all we need is a good approximation.
The 1st and 3rd references above give that finding a stable matching is an NP-complete problem. As I discover more on the subject I will continue to update this answer perhaps.
But, for now, the simple answer is that finding a stable matching is an NP-complete problem.