I work at a summer camp where one of the activities is called Speed Dating. It's a game where participants talk with each other for a fixed amount of time. At the end everyone has to list three people they liked the most.
I'm looking for an algorithm that would match participants based on their preferences. It seems like it's the Stable marriage problem that could be solved using Gale-Shapley algorithm. However every implementation of this algorithm I've seen assumes that the number of men and women is equal and every person has to rank everyone from the opposing gender.
So my question is:
How can I ensure that all "marriages" are stable given that:
- Participants are divided into two groups unequal in size
- Every participant provides a ranked list of only three people from the opposing group they like the most
- Some of the participants might list no people
- Not everyone has to be matched
- A "marriage" is stable only when two people have picked each other (regardless of their ranks)