Game Theory at its finest
I decided that I should post more so I figured I would start with a topic I know well. That being math. Some of you may have read this in the New York Times, it was also posted on the American Mathematical Society website. I thought it was interesting, also Lloyd Shapley was a professor at UCLA and probably one of the most prominent figures in Game Theory other than John Nash.
"Medical marriages" refers to the process by which the National Residency Match Program assigns medical students to residency positions. Residency Match uses an algorithm that turns out to be equivalent to the "marriage algorithm" devised in 1962 by the mathematicians David Gale and Lloyd Shapley, who proved that it converges:
1. Each boy ranks all the girls in order of his preference, and each girl does the same. Then, each boy asks his first choice for a date. Each girl with one or more offers dates her favorite and says "no" to the rest.
2. In the next round, the boys who were rejected move on to their second-choice girl. The girls again date their favorites, possibly throwing over their date from the earlier round for someone better.
3. Continuing in this way, the mathematicians showed, the dating frenzy eventually subsides into a stable situation where each girl has only one boy, and there is no boy and girl who prefer each other to the people they are dating. That is, every time a boy does not get his first choice, he has no hope of getting anything better. Each of the girls he prefers is paired with someone she prefers to him. The same is true for a girl.