Question

Consider the Stable Roommates problem, in which there is a set S of 2n people who must be paired up to be roommates and each person has an ordered preference list of the other 2n-1 people in S. A roommate assignment consists of n pairs of people that partition S. An assignment is stable if there that does not exist any rogue couple (x,y) such that x and y prefer each other to their current assigned roommate.

Prove or disprove that, for any collection of preference lists, there is at least one stable roommate assignment.

Answer 1

No , it is not always possible. Consider an arrangement of 4 people A,B,C,D and their respective preference list.

A:(B,C,D)

B:(C,A,D)

C:(A,B,D)

D:(A,B,C)

where i:(j,k,l) means i prefers j more that k and k more than l.

In this scenerio D will be paired with any of A,B,C. We will show that whomever D is paired to ,we'll not get a stabe assignment.

Case 1. D is paired to A and remaining BC are paired toghether. This assignment is not stable since C prefers A more than B and A prefers B more than D.

case 2. D is paired with B and remaining AC are paired toghether. This is also not stable since A prefers D and B prefers C more than D.

case 3. D is paired with C and remaining AB are paired toghether. This is also not stable since D prefers A more and B prefers C .

Hence none of the pairings are stable.