What you are asking is no longer called "Stable Marriage Problem." In contrast, it's called "Stable Roommates Problem." According to Wikipedia:
In mathematics, especially in the fields of game theory and combinatorics, the stable roommate problem (SRP) is the problem of finding a stable matching — a matching in which there is no pair of elements, each from a different matched set, where each member of the pair prefers the other to their match. This is different from the stable marriage problem in that the stable roommates problem does not require that a set is broken up into male and female subsets. Any person can prefer anyone in the same set.
It is commonly stated as:
In a given instance of the Stable Roommates problem (SRP), each of 2n participants ranks the others in strict order of preference. A matching is a set of n disjoint (unordered) pairs of participants. A matching M in an instance of SRP is stable if there are no two participants x and y, each of whom prefers the other to his partner in M. Such a pair is said to block M, or to be a blocking pair with respect to M.
Wikipedia discusses the answer to your question. It says the stable case cannot be always found, yet, there exists an efficient algorithm, due Irving (1985), which will find such matching if there's one.
Several natural relaxations are conceivable to the SRP: Instead of requiring that "there are no two participants x and y, each of whom prefers the other to his partner in M," one can require that:
- At least some certain fraction of people be satisfied with their roommates. Here, satisfiability can be interpreted differently. For instance:
- A pair (x,y) is said to be satisfied if y is x's first choice, and vice versa.
- A pair (x,y) is said to be satisfied if one of x or y is another's first choice.
- A pair (x,y) is said to be unsatisfied if there exists a pair (z,w) such that x likes z more than y, and z likes x more than w.
- At most some certain fraction of people be unsatisfied with their roommates. (This requirement might be different that the above depending on the interpretation of satisfiability.)