Re:Why a Dutch court stopped high school students from swapp...
by niftich on Saturday May 19, 2018 @12:04PM
(#17108432)
In 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].
Re:Why a Dutch court stopped high school students from swapp...
by VHRanger on Saturday May 19, 2018 @12:14PM
(#17108468)
Edit: 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.
Re:Why a Dutch court stopped high school students from swapp...
by egl2019 on Saturday May 19, 2018 @07:28PM
(#17110293)
With 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.
Re:Why a Dutch court stopped high school students from swapp...
by dfee on Saturday May 19, 2018 @12:08PM
(#17108448)
That’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.
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#Soluti...