August 19, 2003

"As moonlight unto sunlight, and as water unto wine"

From Matilde's comment on Invisible Adjunct, I was led to a history and summary of the algorithm used to match residents to hospital slots. Nice to have these things clear - or "Clearing", as the UK system for getting into college seems to call it. The algorithm is easy to understand; the old and basic example is stated in terms of boys proposing to girls who keep an eye out for better engagements. Still, startling to find so blunt a summary of old-fashioned sexual mores and politics:

Gale and Shapley also showed that the match achieved in this manner has a remarkable property: It is "boy-optimal" and "girlpessimal," meaning that each boy is matched to the best girl he can get in any stable matching, while each girl ends up with the worst possible guy. (I leave this as an easy exercise for the reader's morning commute.) Of course, the corresponding algorithm that has the girls proposing achieves the opposite, prompting some reflection on real-life dating conventions.

Another exercise is to show that it's possible for those on the side that's not proposing to "game the system." By lying about her preferences, a girl can do better in the male-proposing algorithm than she would otherwise.

I need to tidy up whatever is preventing this blog from having several categories for one post, because it's not all that often I can categorize something at once as math and 19th c. fiction.

Locksley Hall gave me my title.

So wrote clew in Fiction (19th c.). , Math. | TrackBack
And thus wrote others:
TrackBacks turned off...