2
$\begingroup$

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)
Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

This is the problem of finding a matching in a bipartite graph. Each person is represented as a vertex in the graph, and you draw an edge between two people if they both have included each other on their rankings. Then any matching corresponds to a way to match people. There are standard algorithms that can find a maximum matching in a bipartite graph efficiently, so you'll even be able to find a pairing that maximizes the number of stable pairs created.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.