Real-life Applications of Stable Matching, maybe in FWS (First-Year Writing Seminar) enrollment
In our class discussion on matching markets, we explored the example of matching students and rooms as well as the stable marriage problem which is an example of matchings with preferences. To further my understanding on stable matching and the polynomial-time algorithm given by David Gale and Lloyd Shapley, I found [this website made for a CS Final Project on the Theory of Stable Allocations and Market Design by Ha Cao and Hening Zheng](https://jcrouser.github.io/CSC250/projects/hospitals-and-residents.html).
To define stable matching, we need to first define instability or unstable pairs. Given one or several groups with a preference list of possible matches, an unstable pair is “a pair of agents who prefer each other to their assigned partners” while a stable matching is “a solution which provides a matching with no unstable pair”(Cao and Zheng, 2018). In 1962, David Gale and Lloyd Shapley developed an algorithm that can output a stable matching to solve the marriage problem for an equal number of men and women as long as each agent is treated as an independent individual (Cao and Zheng, 2018).
In addition to the explanation and implementation of the Gale-Shapley algorithm in pseudocode (which may be fascinating for CS students), the final project website also includes several applications of the stable matching algorithm which are relevant to what we talked about in Networks as well as our homework such as the National Resident Matching Program, matching students and high schools, and matching kidneys with patients.
One key take-aways from this research project is that many problems in real life such as hospital/residents matching and kidneys/patients matching may sound like different problems but with reductions, it may be possible to solve all problems with the same algorithm or some variations of one algorithm (Cao and Zheng, 2018). For example, most first-year students at Cornell are required to take two FWS (First-Year Writing Seminar). However, getting into a FWS you are interested in can be challenging with the unbreakable enrollment cap at 17 students per seminar. Have you ever casted FWS ballots? Well, for Fall 2021, the Knight Writing Institute has decided not to use a ballot system and instead decide enrollment on a first-come, first-served basis. On [the FWS website](https://knight.as.cornell.edu/fws-guidelines) it says, “Please be aware that the university has increased the size of the class of 2025. The supply of available seminars is limited. A significant number of students may be unable to find a seminar in Fall 2021.” In this case, there cannot be perfect matching because the students would form a constricted set. Also, like medical resident-hospital matching, for FWS enrollment, the decision was binding since students cannot be registered for more than one FWS at a time. Since there are much more students than available seats in FWS, and students each have a preference over the course topic and schedule, it is important to perhaps offer a course selection tool. The Course Crafter developed by the Future of Learning Lab at Cornell may help students discover courses. However, the official Scheduler or Course Roster might not provide adequate information and support for students given their preferences. I’d like to end my post with a question: how can we design a better matching algorithm and perhaps course selection ecosystem from both the student and instructor perspectives to provide more accessible and equitable education for anyone, any study?
Reference:
CSC 250 – Final Project: Theory of Stable Allocations and Market Design
Ha Cao, Hening Zheng
5/6/2018
https://jcrouser.github.io/CSC250/projects/hospitals-and-residents.html
Video:
How the NRMP Matching Algorithm Works
National Resident Matching Program
https://www.youtube.com/watch?v=kvgfgGmemdA