In the original paper introducing the Gale$$Shapley algorithm, the authors framed the stable matching

problem in terms of men and women $$rank$[$ing$]$ those of the opposite sex in accordance with his or

her preferences for a marriage partner$.$ In $1962,$ when this paper was published, society$$s views on

marriage were more conservative than they are today. So let$$s bring the problem into the modern era:

what happens if we no longer marry men and women, but instead marry anybody to anybody?

Suppose we have a group of n people, where n is even. Each person ranks the other n$1$ people in order

of preference, and we want to find a stable matching. Note the difference in this problem formulation:

we are no longer matching members of one group $($e$.$g$.,$ men$)$ to members of another group $($e$.$g$.,$ women$),$

but instead all members belong to the same single group $($e$.$g$.,$ people$).$

Unfortunately, with this variant of the problem, a stable matching is not always guaranteed to exist!

Show that this is the case by giving a counterexample of people and preference lists where no stable

matching exists.

Hint. Matching two people is easy. What about four people?