Tuesday, April 01, 2008
David Gale, a wide-ranging mathematician who helped develop an algorithm for pairing individuals into couples died on March 7 in Berkeley, Calif.Dr. Gale’s interests included mathematical games and puzzles and the creation of economic models, but he was widely recognized for work on the so-called stable marriage algorithm, a concept he developed in the 1960s with the economist and mathematician Lloyd S. Shapley.The problem begins with the assumption that equal numbers of men and women are in search of potential partners.Born in New York, David Gale graduated from Swarthmore College in 1943 and earned his doctorate from Princeton in 1949. He taught at Princeton for a year and then on the Brown University faculty until he moved to UC Berkeley with a yearlong Miller Professorship in 1965. He joined the Cal faculty permanently as a full professor the following year.Professor Gale was a member of the National Academy of Sciences, a recipient of many awards and fellowships in his field, and the author of "The Theory of Linear Economic Models," a widely used reference work in what is known as linear optimization - a field that earned him a share in the coveted 1980 John von Neumann Theory Prize.Is it possible to pair the individuals in such a way that all achieve a satisfactory match? The solution developed by Dr. Shapley and Dr. Gale was to have each participant rank the members of the other sex in terms of desirability. The researchers then developed an algorithm that directed each participant to his or her next choice of partner, if rejected by the first or second choices. The stable marriage algorithm, due to D. Gale and H. S. Shapely, originally appeared in the American Mathematical Monthly in 1962 under the title ``College Admissions and the Stability of Marriage.He also developed an award-winning website (mathsite.math.berkeley.edu) to demonstrate mathematical concepts and allow hands-on participation by laymen.More recently, a form of the algorithm has been used to assign students to public high schools in New York City. As applied to medical students and their residencies, it has been criticized for not taking hospital salaries into consideration, potentially stifling competition and affecting the way the free market might raise pay for residents, an issue that is controversial among economists who study the matching process.