1
$\begingroup$

I run a heterosexual matching making service. I have my male clients and my female clients. I need to pair each of my clients with their "soul mate" based on several attributes (age, interests, personality types, race, height,horoscope, etc.)

After I create all my pairings, there will be some sort of score to grade the quality of my matches.

I can't match a man with multiple women or vice versa. I also want to minimize the number of unmatched clients.

What's the best algorithm to come up with a way to match my clients based on their attributes?

Again, this is a toy example. My actual use case is completely different.

Edit:

The score is computed at the pair level and then summed. I can calculate how the score changes when I swap partners by looking at the new scores of two pairs. I do have access to the internals of the metric, but it's complicated. I don't have any constraints, other than I'd prefer it to be fast and simple for my own sanity.

Improve this question
$\endgroup$
5
  • $\begingroup$ Is the score only available in aggregate for the whole set? Do you have acess to the scoring metric? Quite important: Are you able to calculate changes to the score that occur when you swap partners between two or more pairs, faster than re-calculating the whole score? Also important: Are there any constraints on speed or other performance characteristics of the algorithm, or can the algorithm focus purely on the goal of optimising your score? $\endgroup$
    – Neil Slater
    Commented Aug 21, 2019 at 16:46
  • $\begingroup$ @NeilSlater see edit. $\endgroup$
    – Jack
    Commented Aug 21, 2019 at 17:18
  • $\begingroup$ Also would be useful to refine the performance metric - do you want to maximize the number of matches of have a score of at least X, or do you want to maximize the average score over all matches, or something else? There will be different algorithms and different results depending if you want to focus on optimal matches for a small group, or if you want "good enough" matches for a larger group. $\endgroup$
    – Nuclear Hoagie
    Commented Aug 21, 2019 at 17:33
  • $\begingroup$ @NuclearWang I kinda want both. but I'll settle for optimizing the number of good enough matches. $\endgroup$
    – Jack
    Commented Aug 21, 2019 at 18:03
  • $\begingroup$ @Jack: You can only optimise to a single metric. It doesn't have to be the sum of individual scores, your could do some other maths. But whatever it is has to capture the goals you have in a single number. As soon as you have more than one value - with different points at which they maximise - then there is no way to make a decision automatically. $\endgroup$
    – Neil Slater
    Commented Aug 22, 2019 at 7:53

2 Answers 2

Reset to default
3
$\begingroup$

Although you might find a way to apply machine learning (ML) to this optimisation problem, it does not look necessary, and is probably a distraction. ML might help if the scoring system was complex or if you had incomplete data for most matches, and needed to compute matching score estimates from some more limited set of attributes.

Instead here you seem to have a combinatorial optimisation problem. A well known example of this is the Travelling Salesman Problem.

There are many possible algorithms to attack these kinds of problem. Which to choose may depend on other traits of the data, such as how quickly you can calculate the scores - both for the whole set and for individual changes. If calculating for changes is fast enough, you can use optimisers that work from a complete (but not yet optimal) solution and make changes.

There is a free PDF/book called Clever Algorithms (Nature-Inspired Programming Recipes) covering selection choice amongst all the varied optimisers. This may allow you to find something optimal in terms of speed and reliability of algorithm.

Here's a simple thing you could try though

  • Create a "greedy" solution

    • Shuffle one set of items that need to be paired
    • For each item in turn, pair it with the best scoring partner
    • Calculate the score for this solution

  • Refine the solution

    • Sample some subset of pairs (e.g. 2, 3, 4, 5 pairs). You could do this deterministically for small enough dataset, or stochastically, or use some algorithm to filter to "at least has some chance of improving".
    • Find the best score amongst all permutations in this small subset (i.e. brute force all 24 pairings amongst 4 couples)
    • Put the best subset back into the solution
    • Repeat until no improvement found after some number of tests

This routine can be altered in various ways to take advantage of aspects of your problem. A nice thing in your case, making this easier that the Travelling Salesman Problem, is that you don't have any constraints on valid pairings. In TSP you care about making a single circuit, and not multiple separate loops which limits how you can make changes, whilst in your case each of your pairs is entirely separate.

One example of possible algorithm improvement: You could pre-calculate the scores for the top N matches for each person, and only search amongst those when considering local changes.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Awesome! Your idea inspired another thought: Apologies for the sexism. This is not my real use case. What if for each man, I record their top N women. Then I match every man with their top woman, ignoring potential polygamy. Then for each woman, if she is matched with multiple men, I match the "less optimal" man with his second choice woman, again ignoring potential polygamy. $\endgroup$
    – Jack
    Commented Aug 22, 2019 at 15:54
  • $\begingroup$ @Jack: That may work as a variation of the initial greedy algorithm. You will still need some kind of refinement stage if you want to get closer to fully optimised. How much of difference there is between an initial greedy algorithm and the improvements possible through local search depends very much on your data. $\endgroup$
    – Neil Slater
    Commented Aug 22, 2019 at 16:54
2
$\begingroup$

Gale–Shapley algorithm, also known as the SMP Stable Matching Problem.

Also see SRP Stable Roommates Problem when there's only one kind of item, not two sets.

Improve this answer
$\endgroup$

Your Answer

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

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