3 ms·
I wonder if the Gale–Shapley algorithm[0] would work in this situation. That algorithm applies to the stable marriage problem: N men and N women need to be pai
by mabbo 8y ago
I wonder if the Gale–Shapley algorithm[0] would work in this situation.
That algorithm applies to the stable marriage problem: N men and N women need to be paired such that no two members in each set would both prefer to be with each other over their partners.
The algorithm has each person rank every member of the opposite gender in preferential order. Then, one side (let's presume the women) take turns picking from the other in order of their preferences. If the woman A's top choice is man X, but man X is already taken by woman B, then he will swap iff he prefers woman A over woman B. If he prefers woman B over woman A, then woman A moves down to her next choice in the list. If you follow this pattern to conclusion, everyone is paired and there will not exist a man and woman who both want to be with each other more than their current partners.
We could apply this to school selection. Every student ranks all schools from most to least preferred. All schools then 'rank' students via any criteria they want. Want to put students with siblings in the school ahead of all others? Easily done. For any equally-preferred students, sort randomly. The "women" translates to students, and the "men" translates to "spot in this school".
Might not stop strategizing, but it's a great way to handle pairings with preferences involved.
[0]https://en.wikipedia.org/wiki/Stable_marriage_problem#Solution https://en.wikipedia.org/wiki/Stable_marriage_problem#Soluti...
- niftich 8y agoIn the US, this algorithm is used to place medical graduates at teaching hospitals, by the National Resident Matching Program. And of course, college admissions was the topic of Gale and Shapley's 1962 paper, 'College Admissions and the Stability of Marriage' which publicized the algorithm [1]. [1] https://doi.org/10.2307%2F2312726 https://doi.org/10.2307%2F2312726
- dfee 8y agoThat’s definitely an option that satisfices, but would it reduce the amount of satisfaction by increasing the number of “acceptable” solutions while decreasing the number of “desired” solutions? Humans are greedy, and that’s where these algorithms seem to fall apart in the real world.
- VHRanger 8y agoEdit: the deferred acceptance algorithm they refer to in the article __is__ the Gale algorithm. Those sort of algorithms (actually refined versions) are starting to be deployed for those problems. It's being used to match kidney donors to recipients, and freshly minted doctors to residencies. School districts have more problems implementing it due to regional politics. I would encourage you to look into the research by people like Al Roth, Itai Ashlagi or Atila Abdulkadiroglu.
- egl2019 8y agoWith some exceptions such as siblings of current students, the schools are not strategic actors in the Amsterdam problem. If you meet the entrance requirements, you're eligible, and that's all the schools are allowed to say. In the stable marriage and the residency problems, both sides express preferences.