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)
$\endgroup$
  • $\begingroup$ This is an interesting problem, but maybe this question is too broad (unless an algorithm already exists for your use-case). $\endgroup$ – nbro Jul 8 '18 at 15:32
  • 1
    $\begingroup$ Until you define what you mean by "best", this is not answerable -- it is not a question about computer science. If you know how to define precise what is the optimal matching, then it is a computer science question how to build an efficient algorithm to compute that optimal matching. But asking us how to define optimality in the first place is not a question of computer science; that's a matter of what you want, and only you know what you want. $\endgroup$ – D.W. Jul 9 '18 at 3:34
  • 1
    $\begingroup$ @D.W. My interpretation was that "What is the best way?" means "What is a good algorithm?", not "how should I define optimality?" $\endgroup$ – David Richerby Jul 9 '18 at 16:15
  • $\begingroup$ @DavidRicherby, that could be, but I don't see that the question defines optimality anywhere. In other words, I don't see anywhere where the question specifies what the desired output is -- it only lists what the inputs to the algorithms are, but not what the algorithm should output. $\endgroup$ – D.W. Jul 9 '18 at 16:17
  • 1
    $\begingroup$ It seems that you want an algorithm that gives a matching that is 'stable for all submitted preferences', similar to what you would get if you had complete lists of preferences and ran Gale-Shapely. Is that correct? If not please clarify what requirements you have on the resulting matching. $\endgroup$ – Discrete lizard Jul 9 '18 at 18:16
1
$\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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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