Matching Algorithms

August 28, 2023 6:10 PM

I'm working through the CS course on Brilliant. I'm currently on the section on algorithms. The one they are presenting now is The Stable Matching Problem. I'm having trouble getting it, but I don't know why.

Basically, are there any good (preferably free) resources out there that can break it down further for me.

posted by kathrynm to Computers & Internet (6 answers total)

Best answer: I think it is more traditionally called the “stable marriage problem” and has been recently renamed due to the somewhat problematic implications of the original name. If you search under the older name, you should find plenty of resources.
posted by A Blue Moon at 6:33 PM on August 28, 2023 [4 favorites]

Best answer: Jeff Erickson at the University of Illinois has a pretty good textbook and lecture notes he developed for his algorithms classes. It's all available freely online, and you can purchase a paper copy of the textbook: https://jeffe.cs.illinois.edu/teaching/algorithms/

The textbook has a section on the stable matching problem: Section 4.5 in Chapter 4 on greedy algorithms.
posted by whatnotever at 10:03 PM on August 28, 2023 [2 favorites]

Best answer: Blue Moon probably has it. It's assigning seven brothers to seven sisters for marriage where there will be no cheating because every one will be assigned to the the match such that even if they preferred some other match, that other match prefers their match more than them and wouldn't switch. So the final selection is stable, everybody to the best they could.

This also transfers into the better than "draw names from a hat" of seating like kids in a summer program where they get to order the options they want. The goal is to make sure that the fewest/none end up in a program where there is an empty seat in a program that they would prefer. Everybody is as happy as possible.

I have an old AskMetafilter about this from just before COVID that is exactly that assign kids to multiple programs. There's algorithms to do this in various ways. There's even the "assign graduate student to program" that takes into account the teacher's preference and workload supporting multiple classes. "Stable Marriage" is probably still the thing you want to look up. You could also look up something like "graduate school program acceptance algorithm".

I was ready for the big "corner case issues" discussion and had code mostly ready to go when COVID hit and the whole idea of summer camp went poof!
posted by zengargoyle at 5:04 AM on August 29, 2023 [1 favorite]

Best answer: Best way to assign people to classes based on multiple choices? - randomdraws raffle preferences | Ask MetaFilter
posted by zengargoyle at 5:17 AM on August 29, 2023

Response by poster: They are actually using resident/hospital matching as their example.

That e-book looks great too. It's probably overkill for my needs right now, but I can't wait to dig into it.

Thanks!
posted by kathrynm at 10:33 AM on August 29, 2023

Came here after another unrelated search: Stable Marriage Problem - Numberphile - YouTube
posted by zengargoyle at 11:15 AM on August 31, 2023