        \problemdata       % Takes 5 *mandatory* arguments
        {stable-buddy}             % latex-friendly label for the prob.
        {stable-marriages}  % The topic(s) of the problem content.
        {}               % Source (if known)
        {F01 tut6-4} %Usage (list ones you are aware of).
        {}        % Last revision info (author, date).

\begin{problem}
The Stable Buddy Problem is a variant of the Stable Marriage
Problem without the constraint that matched pairs must be boy with girl.

Namely, in the Buddy Problem, there is an even number of people, each with
their own preference ranking of all the other people.  The population is
supposed to be organized into separate pairs of people --- the two members
of a pair are called ``buddies''.  Such an assignment of buddies is
\emph{unstable} if there are two people who are not each other's buddies,
but who would prefer to be buddies with each other rather than being with
their assigned buddies.

In contrast to the Stable Marriage Problem, there are preference listings
where all buddy assignments are unstable.  Give an example of four people
and their preference rankings of the other three people for which there is
no stable way to assign buddies.

\solution{Let the buddy preferences of four men A, B, C, D be\\
A: BCD\\
B: CAD\\
C: ABD\\
D: $?\: ?\: ?$

Let Y and Z be any two among A, B, and C, and let X be the remaining one.
Notice that the first choices of A, B, C are arranged in a cycle, so that
X must be the first choice of either Y or Z.

Now for any matching into pairs, let Y and Z be the two among A, B, C who
are paired, and X be the one paired with D.  So one of Y and Z, say Y, has X
as his first choice.  But since A, B, C each rank D last, X prefers Y to
his own buddy, D.  So X, Y are a rogue couple.  Notice that the ranking of
A, B, C by D doesn't matter.
}

\end{problem}
