Hacker News new | ask | show | jobs
by sachinag 3637 days ago
I assume this is using the same or similar algorithm as the NRMP algorithm uses for U.S. residency match day?
4 comments

Yeah, the Stable Marriage problem provides a solution for matching these ordered preferences between two sets of people/elements: https://en.wikipedia.org/wiki/Stable_marriage_problem
Very close. It's many:many with multiple iterations until a stable solution is found.
Could you write up the differences? I'd really enjoy reading that.
We plan to in the near future.
Almost definitely. Stable matching is a very well understood problem, and as far as I can tell investor day is a textbook example of it.
I assume so as well.

This algorithm is outlined by the stable marriage problem for those that are interested.

It's not quite the stable marriage problem, because in the stable marriage problem you're trying to find an optimal 1:1 pairing. It's also not the NRMP problem because in that case, residents are only matched with one hospital in a year. Here companies are matched with multiple investors, and investors are matched with multiple companies.

But regardless, I believe the algorithm is roughly the same as the NRMP algorithm: you run through multiple rounds where you look at each combination of company and investor. If both sides would prefer that they meet with each other, rather than the people they're already paired with, then you reassign them. Once you've done that several times you arrive at a stable state.

Yes you are on the money. There are also some additional constraints, e.g., we don't want to match startups with multiple investors from the same fund.
In the NRMP there is a N:1 matching between residents and hospitals, where N <= the number of open positions in the hospital.

If the meetings are time sliced, let's say by hour, then run the algorithm for each time slice.

Well, with the constraint that no startup wants to have multiple visits with the same investor (and vice versa) - so you need to rerun the algorithm with the earlier matches removed from a preference list.