4

A while ago, I tried to help a fella to develop a mentorship matchmaking program given the answers of a questionnaire to match mentors and mentees according to their respective skills and available time slots:

A mentor is defined with:

  • Identifier (email, full name)
  • X Time slots (UTC)
  • How many mentees the mentor can take care of, weekly
  • N skills that the mentor can teach

and a mentee with:

  • Identifier (email, full name)
  • Y Time slots (UTC)
  • How many mentors the mentee can interact with, weekly
  • M skills the mentee is willing to learn

Heuristics:

  • A mentor should have the skills necessary to provide proper mentorship
  • Mentors and mentees time slots should overlap (once everything is converted to UTC)
  • If there is like a deadlock situation => order mentors and mentees by their questionnaire submission times

I've checked a few questions, but still not too sure which algorithm will fit the scenario I just described just above, any idea?

EDIT 1 - Author of the project

I can explain the algorithm that was used to develop the project. We're just looking for interesting ways to improve the pairings that it generates. Before going into the explanations, I should say that for a given skill, we provided a heuristic value to showcase how rare it is. Given two equal matches, the one with the rarest skill should therefore win.

From the infrastructure, we parse the data extracted from the questionnaire into two separate lists where each list represents mentees and mentors. From there, we try to get to find all potential pairings first. We do this by finding every mentee that matches a mentor's skill and has an overlapping schedule.

To create unique pairings, we're using sets as caches for the mentees and mentors who have been matched. As we go through the search space, if a mentor is at capacity or a mentee has already been matched, they go to one of the caches and we continue checking all potential matches.

The only way we quantify matches is by providing a heuristic to the rarity of the skill and we somewhat provide a heuristic for the overlapping schedule. What I mean by that is that we recurse into potential matches with the number of hours of overlap that we have. Technically, matches are checked from most hours of overlap to less. Then we go for rarest skill while mentees and mentors aren't matched.

From what I see in the answer, we're really not that far off.

6

There are methodologies to deal with problems that we do no know how to solve. Let us give it a try.

First of all, let us come up with an utility function. The idea is that we should be able to feed a possible solution to the problem to the utility function, and it will return a value that tells us an estimation of how good that solution is.

We will have an agent try to maximize this utility function. If you want to imagine it as if we were designing a video game for people to do it, that works too.

Coming up with a good utility function is about understanding the problem space. So, let us see…

A mentor should have the skills necessary to provide proper mentorship

The solution will have pairings of mentors and mentees. The mentee has a list of skills, and so does the mentor. For each skill that overlaps in a pair, grant some points. The utility function is the sum of the points.

Mentors and mentees time slots should overlap (once everything is converted to UTC)

Similarly, they have time slots. When they overlap grant some points.

How does this interact with the above rule? The mentor skills are of no use if the mentor can't interact with mentee. Similarly - at least, in this model - the mentor that has none of the skills the mentee is looking for, is no use, even if their time overlap.

Thus, I suggest to grant points proportional the overlapped time times the overlapped skills.

If there is like a deadlock situation => order mentors and mentees by their questionnaire submission times

Instead of an utility function, we can work with relative utility. That is, we would have a function that compares solutions and tells you which is best. We still need to worry about making sure the order does not result in a strange loop or similar. This deadlock rule can be used with that.

Yet, I think there is a simpler solutions: add points for good questionnaire submission time. However, more time is worst, right? I suggest to avoid penalties, so don't do it by removing points. Add the multiplicative inverse of the time, by some factor q. I don't know what the factor q is, but it should be small, given that this is meant to untie solutions, it should result in fractions of a point.

Thus, our utility function would look like this:

f(p) = p.overlapping_skills * p.overlapping_time + q/p.total_q_time
utility(s) = sum i=1->n {f(s[n])}

Now, we can design our agent. Remember that we must not exceed the maximum number of mentees per mentor, nor the maximum number of mentors per mentee. Thus, every time we pick a pair, it must be validated. Also, every time we pick a mentor or a mentee (or loop over them), we have a chance to prioritize by questionnaire time.

We can follow a deterministic approach: loop over every mentee, for each one pick the mentor that would give the most utility, and assign it. Loop until no mentor can take more mentees, or no mentee can take more mentors.

We can try something similar to simulated annealing: Starting with no pair assigned, pick a mentor an mentee at random. If the mentor is at capacity, we are considering replacing the mentee that contributes less utility. Similarly, if the mentee is at capacity, we are considering replacing the mentor that contributes less utility. See if the assigment results in more utility that before, if it does, keep it, otherwise drop it. Loop until you are done a large amount of iterations (or a large ammount of iterations with no improvement).

We can try a genetic algorithm. The list of pairs is the genome. We can start with a random population, cross them, mutate them, select the best, and repeat. Until we have done a large amount of iterations, or we see no improvement form a generation to the next.

We can try path finding. Use the inverse of the utility as heuristic of the distance. The better the solution, it would have better utility. And thus, the heuristic will be smaller. Which means it is closer to "the solution". Implement A* or similar heuristic path finder algorithm, where the nodes are the solution, and the vertex are each possible pairing you can do. This graph has a large branching factor, thus you will run into memory problems with A*, consider Iterative Deepening A* or Memory bounded A*.

Oh, and who said these agents have to be artificial? You could start by having people do it by hand, see what patterns emerge from what they do, automate those, repeat. You would end up with an expert system that can solve most of the case automatically, and let the humans handle the outliers.

Look, we can throw plenty of different kinds of agents to this problem. We have gone from "we have this problem with these restrictions" to "here is a bunch of things we can try to solve it". You can even imagine coming up with a large dataset, and testing which performs better.

Plus we probably can improve the utility function. I remind you that coming up with a good utility function is about knowing the problem space. And you know that better than me. For example: should we prefer that a mentor interacts with a mentee one at a time? Should we prefer only one mentor per skill the mentee wants? Should we prefer more or less mentors per mentee? Or should we prefer more or less mentees per mentor? I don't know.

5
  • 5
    The name of the discipline you are describing is "optimization", not "artificial intelligence" - AI is usually associated today with machine learning, which can be used as one optimization technique among many others, from which you mentioned some in your answer. Another glitch in terms: you surely meant "genetic algorithm", not "generic algorithm". – Doc Brown Oct 23 '20 at 5:30
  • +1 for showing that there is no single best solution. And of course, what @DocBrown said is right. – Hans-Martin Mosner Oct 23 '20 at 6:20
  • 1
    In your opinion, @Theraot, how should I generate a large dataset that has valid information? A questionnaire gets me at best ~120 applicants so 120 rows of data. What would you do generate a fake dataset and make sure the data can be matched on. Also when we get this dataset, how would evaluate which alg. performs better? Faster? Less memory hungry? I'm guessing we'd need to manually make pairs ourselves from the data to see which alg. provides correct answers, yes? – Kevin Avignon Oct 23 '20 at 13:20
  • 2
    @KevinAvignon make fake data, without the constraint of it being solvable. I do not know if there is a correct answer, but if you can score solutions, that would be the first metric to compare the algorithms. I would also care about which solution is faster, however, remember that the faster would be to pair nothing. As per memory, if it is too expensive, get rid of that one. But in general memory is cheap, So I won't worry too much about it. – Theraot Oct 23 '20 at 16:13
  • FYI, Matthew Crews has just written an amazing and fantastic article tackling our problem, right here matthewcrews.com/blog/… – Natalie Perret Dec 4 '20 at 5:34

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.