The Stable Matching Algorithm - Examples and Implementation
Вставка
- Опубліковано 14 січ 2017
- Please support me on Patreon: / thesimpleengineer
/ thesimpengineer / schachte
ryan-schachte.com
Don't forget to subscribe! ➨ Website -
➨ New Video! - • Docker Client, Images ...
➨ / the-simple-engineer-80...
➨ Github - github.com/schachte
---------------------------------------------------------------
Click Expand to View All Code and Related Links..
Code:
github.com/Schachte/stable-ma...
NRMP Example:
www.nrmp.org/wp-content/upload...
NRMP Website:
www.nrmp.org/
Wikipedia:
en.wikipedia.org/wiki/Stable_...
Sorority Rush Research:
www.uibk.ac.at/economics/bbl/...
NYC High School Stable Matching:
dash.harvard.edu/bitstream/ha...
This is a video talking about the background involving gayle and shapley's marriage proposal algorithm. Also known as the propose and reject algorithm. I walk through coding the implementation in python, the background, step-by-step example and some applications of the GS algorithm. - Навчання та стиль
Amazing explanation. My mind was blown by the fact that you get the same outcome regardless of starting from the top or bottom.
Great video!! Excellent explanations and meaningful code!!
Perfect. IT could not be better than this. Thank you for sharing this video with us.
Thanks for the explanation! I really find it useful.
As a Ryan, the example was a nice boost to morale
Ama-f*cking-zing !! Loved it !! Thank you so much buddy ! GBU.
thats the cleanest and best best structure of dictionary damn
I love it! appreciate so much!!!
YOU ARE THE BEST! MORE THAN JUST A THANK YOU!!!
Hey, great video but i have a question for the example. Could you elaborate on what does it actually mean that the proposee gets the worst possible match, since lizzy gets the best pick for him. Thanks
Great video! Is there an algorithm to determine ranking of preference for each individual based on say, interests, age, etc?
Very informative and explained. How can I DM you pls? I have a question on something that I'm currently thinking of setting up a start up with matching algorithm.
Thanks, Its really helps me. Love it
I'm you're biggest fan! Your vids are so cool you must be so smart and have so many cool friends. Also, your voice is so smooth and deep it's so attractive...
Me too. very clear
This is still stable because simple engineer doesn't prefer spencer over his woman 2.
Hi.
Can Irving's algorithm be used to build a roommate recommendation system?
P.s: any response is good.
What happens in the 3 couples case?
thanks for the video, but for the possibility existing singles?
there cant be singles, the algorithm wouldn't work.
that's a silly question
can there be multiple stable matches ???
I'm trying to incorporate this code into a website that I'm working on. Anybody have any idea how to do that?
can u help me with which algorithm should i use for a match making according to the matching requirements that male gives which matches with women's requirement which women gives herself and vice versa. hoping for quick response
Can you please make a video on the hospitals/residents problem (aka college/students problem aka admissions problem). This is where you can accept more than one match, for example, a college can accept 10 students and each student has a ranking of their preferred college, etc.
All you need to be is keep the same code -- just have another data structure storing the values of the maximum vacancy (quota) for each hospital, and iterate the matching until the quota is 0 (we reduce the quota by 1 when a matching occurs and increase it by one when an already matched student trades up/changes to a higher priority hospital/valid match)
@@bizzey2714 hey , can please write the code for it it will really help a lot . thank you
@@abbadmed2667 I can’t share the code bc it falls under disclosure/publication rules (for me), but I don’t mind helping you out with your code or something
@@bizzey2714 ok thank you ,
So, this is my code and I want to write a program that oriented student to their specialty in university , and each specialty can take multiple student (in this case cnm =1 , dsi=2 , rss=2),and the number of student can be more than the number of places (in this case one student not gonna have a place because there is only 5 places ).
The program run with out a problem but the output is not correct .(and I couldn’t know why )
.
The output for this example should be ((a,cnm),(c,rss),(b,dsi),(e,dsi),(f,rss))
If you could help me out I would really appreciate it.
Thank you in advance
this is mycode
students = {
'A': ['CNM', 'DSI', 'RSS'],
'B': ['CNM', 'DSI', 'RSS'],
'C': ['DSI', 'CNM', 'RSS'],
'D': ['DSI', 'RSS', 'CNM'],
'E': ['RSS', 'DSI', 'CNM'],
'F': ['RSS', 'CNM', 'DSI']
}
choices = {
'DSI': ['C', 'E','D', 'B','F','A'],
'RSS': ['B','F','A', 'E', 'D','C'],
'CNM': ['A', 'B','C', 'D','E','F']
}
rss=2
cnm = 1
dsi=2
results = []
students_with_out_choice =[]
for student in students:
students_with_out_choice.append(student)
while (len(students_with_out_choice) > 0 ):
for i in range (3):
for student in students_with_out_choice:
for choice in students[student]:
if ((choice == "DSI" and dsi != 0) or (choice == "RSS" and rss != 0) or (choice == "CNM" and cnm != 0)):
results.append([student, choice])
students_with_out_choice.remove(student)
if (choice == "DSI"):
dsi -= 1
if (choice == "RSS"):
rss -= 1
if (choice == "CNM"):
cnm -= 1
break
else:
for key, value in results:
if choice == value:
a= key
etudiant_actuel = choices[choice].index(a)
etudiant_proposer = choices[choice].index(student)
if (etudiant_actuel >etudiant_proposer):
students_with_out_choice.remove(student)
students_with_out_choice.append(a)
a = student
break
elif(i==2):
students_with_out_choice.remove(student)
break
print(results)
Can someone please help me understand how to extend gate shapely algo when e.g 1 man doesnt wanna marry woman x under any circumstances
Then he simply wouldn't enter the marriage pool at all. It would be analogous to a medical student who elects not to rank any residency programs at which he interviewed and sit out the Match instead.
shouldnt the code keep track of the men's already proposed woman?
File "E:\ClassWork\3.1\CSE 4591 DM\Assignment5_TMA_plussix\stable.py", line 44, in begin_matching
for woman in preferred_rankings_men[man]:
TypeError: unhashable type: 'list'
Can't find the reason for this problem, nor how to solve it.
I use Python3 and this is written on Spyder.
C++ code if anyone interested - not the most optimised (Too lazy to make changes)
std::set getMatching(std::map men,
std::map women) {
std::set match;
std::unordered_map menCurrMatch;
std::unordered_map womenCurrMatch;
std::unordered_map womenMatchReverseLookup;
std::set matchedMen;
while (1) {
bool change = false;
for (auto& curr : men) {
if (matchedMen.find(curr.first) != matchedMen.end()) {
// Dont bother matched men
continue;
}
std::string currMan = curr.first;
std::string currWomen("");
std::string nextWomen("");
int startWomenIndex = 0;
if (menCurrMatch.find(currMan) != menCurrMatch.end()) {
startWomenIndex = menCurrMatch[currMan].second + 1;
}
for (int i = startWomenIndex; i < men[currMan].size(); i++) {
currWomen = men[currMan][i];
std::cout
It was good but you should of scrolled up man, the youtube bar gets on the way when I pause for examination
ok, you did scrolled down a little
19:10 But, in this example, women got better results then men.
Men got 1-3-1-3
Women got 1-2-1-2
When we are saying best and worst, do we mean best/worst in all possible stable matchings? If so, I wouldn't say it's best to be in the left set.
He gave an odd example since in his example the outcome is always the same regardless of whether the males or the females do the proposing. When he says the men get their best options, he means that in no other stable matching would the men get better results.
@@joestewart7150 That is not true. Stable Matching problem is beneficial for man/man optimal because the man always proposes (in the order of women in their pref list) while women can only trade-up/reject a proposal.
Bizzey Joe Dangelewicz is right! If you calculate the final engagements when you let the women propose, the exact same 4 couples will be created. This is only because of the sets of preferences chosen in this example. With other preferences, there will be 2 different stable outcomes: depending on which gender is assigned to propose. If you compare the outcomes, the men will have a better result in the algorithm where they proposed, and the women have a better result in the algorithm where they proposed.
only algorithm I don't enjoy learning ; :
saying guaranteed after already stating that it is 100% is redundant