(mailed to GTS members by Bernhard von Stengel on Monday, 17 March 2008)
UC Berkeley Press release and Obituary (March 18, 2008)
David Gale, a charter member of the Game Theory Society, died on March 7, 2008, following a heart attack, in Berkeley, California. He was 86 and very active until the day of his heart attack.
David Gale was among the founders of game theory in Princeton. He received his PhD in Princeton in 1949 with a dissertation on “Finite solutions of two-person games”. His advisor was Albert Tucker, who also supervised John Nash and Lloyd Shapley. David Gale, Harold Kuhn and Albert Tucker won the von Neumann Theory Prize in 1980 for their seminal role in laying the foundations of game theory, linear and non-linear programming.
In game theory, one of his seminal contributions was his joint paper with Lloyd Shapley, “College admissions and the stability of marriage”, American Mathematical Monthly 69 (1962), pp. 9-15, which started a whole research area on stable matchings and their applications.
A collection of papers dedicated to David Gale on the occasion of his 85th birthday is forthcoming in the International Journal of Game Theory, Volume 36, Numbers 3-4, March, 2008, and accessible online to GTS members. This volume is edited by Marilda Sotomayor, who had also organized a scientific day in David’s honour during the 18th Summer Festival on Game Theory in Stony Brook, July 12/13, 2007. The preface to the IJGT volume summarizes many other fundamental contributions of David Gale to mathematical economics. See also the letter by Marilda Sotomayor on David Gale’s work below.
David Gale’s work is of astonishing breadth and full of mathematical beauty. Less known to game theorists are probably his contributions to geometry. To name some that bear his name, the Gale transform and the Gale diagram allow to describe and visualize polytopes in high dimension which do not have too many vertices. The Gale evenness condition characterizes the “cyclic polytopes”, which, for example, have any number of vertices in dimension four so that any two of them are connected by an edge on the outside of the polytope. In the familiar dimension three, this cannot happen with more than four vertices, nor does it apply to a cube in dimension four, and it shows how our imagination goes astray in higher dimensions.
An excellent article that summarizes his work is http://en.wikipedia.org/wiki/David_Gale
David Gale wrote a Mathematical Entertainments column for the Mathematical Intelligencer from 1991 through 1997. The book “Tracking the Automatic Ant” (1998) collects these columns.
In 2004 David Gale developed MathSite, a pedagogic website that uses interactive exhibits to illustrate important mathematical ideas. MathSite won the 2007 Pirelli Internetional Award for Science Communication in Mathematics.
David Gale is survived by his partner, Sandra Gilbert, his three daughters, and his grandchildren.
Letter from Marilda Sotomayor on David Gale’s work to Bernhard von Stengel, from March 12 (on the web March 20), 2008:
On Monday [March 10, 2008], I received a message from Katherine, Gale’s daughter, telling the sad knews. I still have David’s e-mails from last December…
Over the last fifty years David Gale played a leading role in developing some of the themes of fundamental importance to economic theory. An example is matching theory which he introduced to me in 1983. We wrote several papers together. From this time on I used to send to him my manuscripts, before submitting them. He always used to read them and to make comments and suggestions. The Gale’s Feast I organized at Stony Brook was a way to thank him for everything I received from him. I also edited a special issue in honor to him for the International Journal of Game Theory, which was published these days. I think David did not see the publication, but I gave to him during the dinner of the Gale’s Feast, as a symbolic gift, a compilation of the copies of all 17 papers. You can find a paper of mine there too: The Stability Of The Equilibrium Outcomes In The Admission Games Induced By Stable Matching Rules. This special issue is on David’s work but most of them are on matching. Probably we will also have a book published by Springer.
There is some thing that I am sure you can tell in your appreciation on Gale’s work. Once, in 1975, when David finished a talk about the stable marriage problem, some physician, who had attended the talk, approached him and told him that the Gale-Shapley algorithm was very similar to the one that was being used by the National Resident Matching Program in Illinois. Then, he wrote a letter to the NRMP asking them about that. They answered David and from the description of the algorithm used by the NRMP he could see that it was mathematically equivalent to the Gale-Shapley algorithm, but in the reverse: instead of producing the optimal stable matching for the students it produced the optimal stable matching for the hospitals. This fact was spread orally. When I arrived in Berkeley, February of 1983, there were papers on the walls of the Department of Mathematics congratulating David for having been elected for the National Academy of Sciences. In these papers it was written that David Gale had discovered an algorithm which was being used to make the allocation of the interns and hospitals in the United States. At this time, there was a colloquium in the Department of Mathematics and David gave a talk about the stable marriage problem. I attended such a talk. Then he talked about the mathematical equivalence of the two algorithms and made clear that the Gale-Shapley algorithm was independently discovered 11 years after the discovery of the NRMP.
These facts were reported in the second paper David wrote about the stable marriage problem, in 1983, co-authored with me: Some remarks on the stable matching problem, Discrete Applied Mathematics. This paper was only published in 1985 and was very important for the developing of the theory of the discrete matchings. In my opinion this was, , after the first one by Gale and Shapley, the most important paper that was written on this subject. It presents a concise theory whose results and arguments used in the proofs have been used by the authors until nowadays. The existent theory only considered special cases of the marriage model (the same number of men and women and/or complete preference lists of acceptable partners). Our paper presents the general marriage model where the lists of acceptable partners do not need to be complete and we may have any number of agents in each side of the model. Then the paper generalizes all existent results, presents new proofs with different arguments, and also new results. Almost all results have two proofs: one by making use of the algorithm and another one without the algorithm, by only using the theory that is constructed in the paper. A new and very short proof of the non-manipulability theorem by Dubins and Freedman allows to teach this result in only one class. The original proof had 20 pages. This theorem opened space for investigation on the strategic aspects of the Gale-Shapley algorithm. This was done in the following paper by us, also written in 1983 and published in 1985: Ms. Machiavelli and the stable matching problem, American Math. Monthly.
His first work on continuous matching models was with Gabrielle Demange: The strategy structure of two-sided matching markets, Econometrica, 1985. This is a very precious paper because it allowed to us to use the similarities and differences between several results for the marriage model and for the continuous model to understand better the structure of the matching models.
Another important work on the continuous matching models was written with me and Demange: Multi-item auctions, Journal of Political Economy. It is about two dynamic auction mechanisms to produce the minimum competitive equilibrium price for the case where buyers have quasi-linear utilities and only wish one object and each seller owns one object.
An important thing to be written about David Gale is that all his works reflect his extraordinary creativity, his ability to combine precision and rigour with an elegant style of exposition and to provide simpler alternatives to complicated proofs. An example is the paper of Shapley and Scarf (1974), where he presented a short and simple proof of the non-emptiness of the core of the Housing market, as an alternative to the more complicated proof of the authors. His proof is done by means of the well-known “Top trading cycles algorithm” which has been applied to allocation problems of students to schools and of kidneys to patients. Another example is the suggestion to John Nash to demonstrate the existence of Nash equilibria using the Kakutani Fixed Point Theorem to simplify his proof.
Do not hesitate to contact me for any further information you need about my work with David Gale.
Best, Marilda