Tuesday, September 14, 2004

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.


At 9/14/2004 12:41:00 PM,

That's cool stuff, but i have some questions. So does that mean everyone is supposedly "satisfied" with their pairing? How does this work in societies, like in some places in China and India, where there are more boys than girls? And, this being a Mormon blog, how would things go with polygamy or polyandry?

At 9/14/2004 12:57:00 PM,

This comment has been removed by a blog administrator.

At 9/14/2004 01:01:00 PM,

Here's a good example of what I mentioned above, that creates problems for more than Game Theorists (Sorry so long):

Valerie Hudson, BYU professor of political science, authored a new book on the potential instability parts of Asia may face because of its overwhelmingly male population.

A new book by a Brigham Young University professor warns that by 2020, China's government will be forced to contend with a potentially unruly and unrooted population of 30 million surplus young adult males with no hope of marriage.

"Bare Branches: The Security Implications of Asia's Surplus Male Population" is published by the MIT Press as part of Harvard's Belfer Center series on international security. Historical and sociological evidence gathered for the book predicts that excess males in China, India and Pakistan portend instability and more authoritarian states.

The root of the problem is a growing disparity between the number of boys and girls born in Asian societies, which place a special value on sons. Well-deserved attention has been paid to the tens of millions of missing women in Asia, but the book is the first to examine a consequence of the dearth of women – legions of young men with no hopes of marriage, and therefore, its author says, prone to violence and unrest.

"We stand at the threshold of a time in which these young, surplus males will increasingly figure into the deliberations of Asian governments," says Valerie Hudson, professor of political science at BYU. "Not only the nations of Asia, but the nations of the world will want to pay close attention to the ramifications of Asia's spiraling sex ratios and the policy choices they force upon Asian governments."

The work of Hudson and her co-author, Andrea den Boer, a lecturer at the University of Kent and former graduate student of Hudson, is already attracting attention.

"'Bare Branches' reveals a largely overlooked but important variable correlated with war and peace: high ratios of males to females," said Jessica Stern, lecturer in public policy at Harvard's Kennedy School of Government. "All those who hope to understand the causes of war – in academe as well as in government – will have to be aware of these findings."

A normal sex ratio at birth is between 105 and 107 males born for every 100 females. Gathering data from many sources, the authors assessed the current birth sex ratio in China as 120 males per 100 females.

Hudson and den Boer determined that such rates mean that in 2020 China will have 29 to 33 million surplus males between the ages of 15 and 34 and India will have 28 to 32 million.

According to the study, about 97 percent of all unmarried people age 28 to 49 in China are male, and 74 percent of unmarried males failed to graduate from high school. Most are migrants. India and other Asian countries demonstrate similar trends.

At 9/14/2004 01:14:00 PM,

My wife is in the process of applying for residency so this was a very interesting post for me to read. Thanks! I hope she gets her first choice! :)


At 9/14/2004 01:51:00 PM,

This seems to be one of those situations where it SHOULD work but probably doesn't bc people are irrational. Let me try to explain why it should work. Let's say you don't get paired with your 1st or 2nd or even 3rd choice, and end up with your 4th choice. The rationale behind this algorithm is that bc your higher choices are already taken, the 4th pick is the best you can do. Essentially, its take the best available under the circumstances. As far as whether or not they are happy, that may or may not be the case, depending on their point of view. While some people may be disappointed bc they did not get what they wanted, others will be content with the knowledge that they got the best available to them. (We're talking about people, right? hahahaha) It's a matter of perspective.

At 9/15/2004 09:58:00 AM,

If you'll indulge me, I'd like to throw a monkey wrench into the works, i.e., the economic concept of scarce information.

Let's say I'm one of the players in this game and am asked to make a ranking of the girls I'd like to date. I rank Girl A first, Girl B second, etc. However, having not dated any of them previously, I don't know enough about them (let alone how well we will get along together) to be extremely confident in my rankings.

So if Girl A accepts my offer for a date, but as I get to know her better I realize that I don't want to be around her that much, then the system breaks down. Even if I do like her as much as I thought I would, she may decide that she likes me less and less the more she gets to know me. Assuming multiple rounds of dating, I may end up realizing I should have been with Girl C all along, which does me no good because she may already have married Boy C even though she would have preferred me all along.

The same analogy can be made with universities, residency programs, etc. As I write this I can think of plenty of instances where Girl A or School A turned out to be a dud for me. And I'm not even going to introduce the idea of the shifting priorities and fickleness of womankind (okay, of mankind as well, I suppose ;)) which of course reduces our model to a quivering puddle of refuse.

Ain't social sciences fun?

At 9/15/2004 12:30:00 PM,

I like your example although I'm pretty sure that the rankings wouldn't be made blindly. Who, except for me, applied to a bunch of random schools and then chose at random amongst the ones to which he was accepted? I'm willing to bet that nobody did that. The way I see it, if you make uninformed decisions, especially when the situations are as important as the ones we are talking about, then you deserve what you get and you should know that.

And yes, social sciences are fun, though pretty wishy-washy most of the time.

At 9/15/2004 01:00:00 PM,

I know, the Social Sciences are nothing like the solid ground the humanities have to offer...




<< Home