Mail to a friend · Print this article · Previous Columns Tony Phillips' Take on Math in the Media A monthly survey of math news

September 2004

The Math of Medical Marriages. "Tweaking the Math to Make Happier Medical Marriages" is the title of a piece by Sara Robinson in the August 24 2004 New York Times. "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. Here is how Robinson explains the algorithm:

 "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. 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. 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."

The Times diagrams a 3x3 example in which Adam and Eve, Romeo and Juliet, Tristan and Isolde end up paired even though Isolde was only Tristan's second choice to start with, and he was her third. [An interesting point about this algorithm, unfortunately obscured by the Times presentation (boys ask girls in the text, girls ask boys in the diagram) is that it favors the askers. The simplest example is with two boys and two girls.

 Suppose Romeo ranks Juliet #1 and Isolde #2, while Tristan ranks Isolde #1 and Juliet #2. And suppose Juliet ranks Tristan #1 and Romeo #2, while Isolde ranks Romeo #1 and Tristan #2. Following the Times text, Romeo invites Juliet and Tristan invites Isolde. Each girl has only one offer, and has to take it, so Romeo and Tristan get their wish, but Juliet and Isolde do not. Following the Times diagram, Juliet invites Tristan and Isolde invites Romeo; now the girls get their heart's desire, and the boys do not.

Hospitals used to do the asking. Even though cases like this are very rare (a 1996 analysis by August Colenbrander, MD, from which the example above was taken, estimates that in the residency match the chance of a discrepancy is less than 0.1%) the algorithm has been reversed since 1996 to make the students the askers. See also Mathias Lindemann's The Stable Marriage Problem. -TP] The algorithm is in the news because it is suspected of allowing hospitals to underpay residents.

Bird Logic. "Bigger than" is a transitive relation: if X is bigger than Y, and Y is bigger than Z, then we can infer, without comparing X to Z, that X is bigger than Z. "Pinion jays use transitive interference to predict social dominance," by Guillermo Paz-y-Miño C and three collaborators (Nature, August 12, 2004) shows how some birds apply this principle to their pecking order. The experimental setup involved three initially isolated groups of jays; in each group a dominance hierarchy had established itself: A > B > C > D > E > F, 1 > 2 > 3 > 4 > 5 > 6 and P > Q > R > S. In a typical run, bird-3 (the "observer") would watch, on three consecutive days, bird-2 defer to bird-B. Then bird-3 and bird-B were placed in a competitive encounter. If birds can use transitive inference then bird-3, having seen its dominator bird-2 defer to bird-B, should infer that B is its superior. And in fact: "During the first minute of the first encounter, observers displayed subordinance levels that were nearly four times as high as those of controls." Controls would have watched similar displays involving two birds with which they were not acquainted. Pinyon jays are "among the most social of North American corvids." They also are better than their less gregarious cousins the scrub jays, at applying transitive inference in experiments involving colored markers. The authors' closing remark: "This work ... supports the hypothesis that social complexity provided a crucial context for the evolution of cognitive abilities."

Calculus, the play (New End Theatre, London, until August 24) is reviewed in the August 12 2004 Nature by Philip Ball. The play, written by Carl Djerassi, "centres on the deliberations of a Royal Society committee appointed in 1712 to pronounce on the priority issue." The issue being whether or not Leibnitz had plagiarized Newton's discovery of calculus. Newton appears in a play within a play which allows his interlocutor "to anticipate the audience's dismay (and indeed I sensed such a response) at having to hear about the calculus." Ultimately, Ball finds that "there is just not quite enough at stake here to sustain the drama." He adds parenthetically: "I did, however, enjoy the portrayal of the eminent French mathematician Abraham de Moivre as a gluttonous reprobate." Calculus was also reviewed online by Rachel Thomas in +plus magazine.

-Tony Phillips
Stony Brook