Monday, June 18, 2007

Listen up ladies...

Back in my undergraduate days, I studied theoretical computer science...you know, algorithms and such. I have to admit that I don't use most of what I learned, and much of it is in fact very fuzzy by now. That said, there are random concepts that come forth as still being relevant. For example, market design has become an increasingly popular topic in economics, and what better market to study than the dating market? Consider the following algorithm:

First, a definition...a stable match is an assignment where there are no rogue couples, i.e. that no individual has another person that they like better than their current mate that also likes them better than the person they are with. Intuitively, we could say that there isn't going to be any adultery or something like that.
Now, the process:
1. Each male and female comes up with a rank ordering of all of the members of the opposite sex. (This matching becomes more complicated if we consider same sex couples.)
2. Each day, the girls go out and stand on the balconies of their apartments. Each guy goes and stands beneath the balcony of the girl that he likes best that hasn't rejected him yet. (In other words, the guys work progressively down their lists until they don't get rejected any more.)
3. The girls take a look at the guys below their balconies, and each picks the highest ranked one and tells him to come back the next day (which by construction he will). She rejects all of the other guys.
4. This process repeats. If there are an equal number of men and women, the process will repeat until each girl has exactly one guy at her balcony, and she will marry that guy.

This process results in a stable matching of partners. Now, this seems great for the girls, right? Not quite...
Another definiton: a person's realm of possibility is the set of people that the person could be paired with in a stable matching.
Not surprisingly, each guy gets matched with the highest ranked girl in his realm of possibility, since he just works his way down the list in order. In technical terms, the resulting matching is optimal for guys. However, the matching is also pessimal for girls! Furthermore, girls (but not guys) could do better by lying about their preferences. So the algorithm is also not strategy-proof for the girls.

Clearly, the context of this algorithm could be extended to college admissions, medical resident matches, etc. Nevertheless, it is an important less to you ladies out there to not just sit there and wait for guys to come to your balcony!

For a more rigorous treatment, see here.

I find it interesting that this algorithm assumes that men and women have perfect information about all the members of the opposite sex and that their preferences don't change over time. What would happen if these assumptions were relaxed? Stay tuned, perhaps...

5 comments:

Angad said...

"a stable match is an assignment where there are no rogue couples, i.e. that no individual has another person that they like better than their current mate that also likes them better than the person they are with."

You are starting from the wrong place. The first thing for a good micro model would be to look at how are individual "incentives" affected by the model.


In this case your definition is so limiting that it destroys the usefulness of the model. This is how: If there is a girl for a boy in another relationship who the boy likes better than his current girlfriend, he has a incentive to improve himself to be more appealing to the new partner. This is more predictive of reality and should lead to a better model.

Another thought, if supposedly the guy is able to improve upon his appeal enough to attract the new girl, his original girlfriend will have incentive to improve her appeal or use some coercive power to retain the guy.


The math is fancy, but the model is bad. Cheers!

Angad said...

"I find it interesting that this algorithm assumes that men and women have perfect information about all the members of the opposite sex and that their preferences don't change over time. What would happen if these assumptions were relaxed? Stay tuned, perhaps..."



okay, I think I jumped the gun in the last comment. I overlooked this paragraph. Sorry!

Jodi Beggs said...

Just to be clear, this is not my model. It is a typical model taught in various subjects to illustrate one way to generate one of possibly many stable matchings.

Angad said...

I didn't think it was your model, but you appeared to be quite keen about it. And I didn't mean to attack you personally either, if thats what you thought. Sorry, my blogging ettiquettes aren't very honed.

Since no one has commented on your blog yet I decided to take the initiative. I found out about your blog via Mankiw's blog and thought you looked cute.

Thanks for pointing out the context of the stability issue. I guess this was meant for a abstract discussion among harvard students.

Since you do agree that the assumptions are rather restrictive, I guess you also agree that its useless to generate any meaningful predictions about the real world like most economic models. Good luck!

Anonymous said...

Reading these kind of posts reminds me of just how technology truly is ever-permeating in this day and age, and I am fairly confident when I say that we have passed the point of no return in our relationship with technology.


I don't mean this in a bad way, of course! Societal concerns aside... I just hope that as the price of memory decreases, the possibility of downloading our brains onto a digital medium becomes a true reality. It's a fantasy that I dream about almost every day.


(Posted on Nintendo DS running [url=http://knol.google.com/k/anonymous/-/9v7ff0hnkzef/1]R4 SDHC[/url] DS QDos)