My favorite math professor has, over the course of two semesters, introduced his classes to many prominent mathematicians through brief stories about their lives. Each recounting reminded us of the importance of the scientist and the frailty of their existence. From mild psychosis to paranoia, from greed to altruism, from lives filled with joy and happiness to those wrecked by tragedy and sadness, we have learned that the perfection of mathematics springs from the imperfection of the human condition. The question is not why, but how.
So, it is to be expected that I am alert for translations to the highest sphere…..
David Gale (1921 – 2008)
Mathematician Who Loved Games Helped Unknot a Pairing-Up Puzzle
This spring’s medical-school graduates have just completed the nerve-wracking “match day,” in which they rank the hospitals where they would like to do their residencies and bite their fingernails until they find out where they will be placed.
Few realize that the algorithm pairing them with a teaching hospital was developed by a game-loving University of California, Berkeley, mathematics professor, David Gale.
Enamored of recreations from sudoku to the roller derby, Mr. Gale, who died March 7 at age 86, was a game-theory specialist often mentioned alongside a onetime collaborator, Nobel laureate John Nash, as a giant in the field.
Mr. Gale’s best-known contribution came as a solution to the “stable-marriage problem,” the question of how best to pair up an equal number of men and women, each of whom has his or her own preferences for a mate.
In a 1962 paper written with University of California, Los Angeles, professor Lloyd Shapley, Mr. Gale proposed a multistage process beginning with each man asking his top choice whether she will have him. Women with multiple offers tell one of the suitors “maybe” and all the others “no.” The rejected men move on to make offers to other women. If a woman gets a new offer from someone she likes better, she gives him a “maybe” and tells the earlier “maybe” that he is now a “no.”
After many rounds, as the rejected men turn to women who didn’t get any offers at first, everyone has paired up. Then each woman turns to her man and says “yes.”
Although offered as an academic solution to a theoretical problem, Mr. Gale’s paper proved a remarkably fertile contribution to real-world cases of “two-sided matching” such as the medical-residency example, where hospitals are choosing students at the same time as students are choosing hospitals. A related algorithm is used by school systems in Boston and New York to allocate slots in high schools.
“David’s work will be remembered for generations to come,” says Alvin E. Roth, a professor of economics at Harvard. Mr. Roth helped design the school-choice systems and has lately been working to apply the theory to the allocation of scarce kidney donations.
Mr. Gale inspired headlines as recently as last year when he challenged studies reporting that men had more lifetime heterosexual partners than women, a situation he labeled a logical impossibility.
Mr. Gale studied math at Princeton, where he was a doctoral candidate alongside Mr. Nash. He was known for devising elegant puzzles and games. Among these was Chomp, in which players take cookies from a board until a final, poison cookie must be removed by the loser. Simple enough for a preschooler to master, the game turns out to have mathematical subtleties that have inspired dozens of academic papers.
At dinner time, says his daughter, Katharine Gale, “he would ask us if we all toasted, how many clinks would there be. He would write matrices all over napkins.”
Once, in a flash of inspiration, “he wrote all over an airplane ticket. The airline refused to honor it and he had to buy a new one,” she says.
“He thought math was beautiful, and he wanted people to understand that,” Ms. Gale says.
Thank you, Professor Gale.