Newsletter of the Game Theory Society

(previously called "Bulletin")

Upcoming deadlines:

May 1, 2008: Last day of reduced-fee registration to the
GAMES 2008 congress (July 13-17, 2008, Evanston, Illinois, USA)

May 3, 2008: Submission deadline for
MATCH-UP: Matching Under Preferences - Algorithms and Complexity (July 6, 2008, Reykjavik, Iceland), dedicated to the memory of David Gale.

May 1/May 15, 2008: Submission deadline for clusters/abstracts for
CLAIO 2008 - Meeting on game theory in honor of Guillermo Owen on the occasion of his 70th birthday (September 9-12, 2008, Cartagena de Indias, Colombia)

May 20, 2008: Abstract submission deadline for
27th Arne Ryde Symposium on "Mechanism Design - Properties of Allocation Mechanisms and Voting Rules" (September 12-13, 2008, Lund, Sweden)

May 27, 2008: Game Theory Day at CWI (Amsterdam, The Netherlands)

David Gale (December 13, 1921 - March 7, 2008)

(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

Renew your membership

(mailed to GTS members by Eric van Damme on Thur, 6 March 2008)

Dear game theorist,

Many of you already renewed your membership to the Game Theory Society. Thanks! In case you did not yet do so, I would like to remind you of that possibility.

As a 2008 member of the GTS you benefit from a considerable discount to a subscription to GEB (Volumes 62 - 64; 6 issues) and/or IJGT (Volume 37; 4 issues), and you have unrestricted online access to all previous issues GEB and/or IJGT.

The IJGT is available for the low price of $45. GEB is available for $90. Both journals together (GEB and IJGT) cost $110. As in previous years, students and GTS-members from low-income countries pay $20 less. Those GTS members that are on the editorial board of GEB or IJGT can choose the "membership only" option. For registration or renewal, please visit our registration page. After your registration has been processed, you will receive details on how to access the journals on line.

Also, a member of the Game Theory Society will receive a $100 discount to the registration fee for the 3rd World Congress of the Game Theory Society at Evanston, Illinois, USA.

Registration to the Congress is open now. For GTS-members, the registration fee is $260; students pay $135. Please note that the fees after May 1st 2008 go up with $100.

We hope to receive your registration soon.

Outcome Council Elections 2008

(mailed to GTS members by Eric van Damme on Mon, 21 Jan 2008)

The elections were announced on December 19, 2007 and January 15, 2008 was the final day on which people could vote. 108 members of the GTS voted, which is 35% of the GTS members. (In 2005, 32% of the GTS members voted; in 2003, 45%.) The following 12 members of the Council ended their terms:

Ken Binmore, David Blackwell, Pradeep Dubey, Joe Halpern, Josef Hofbauer, Michael Maschler, Andreu Mas-Colell, Leon Petrosjan, Rob Porter, David Schmeidler, William Thomson, and Stef Tijs.

The officers of the GTS thank all of them for their services to the Society.

The officers had proposed a list of 19 candidates for participation in this election. Below you find the candidates that have been elected as well as the composition of the Council as of January 1, 2008. We welcome the new council members and thank all persons that have participated in this year's election, either as candidates or as voters.

Newly elected members:

Martin Cripps
Olivier Gossner
Vijay Krishna
Barton Lipman
Benny Moldovanu
Steve Morris
Barry O'Neill
Motty Perry
Philip Reny
Larry Samuelson
Joel Sobel
Yair Tauman

Call for nominations: Prize in Game Theory and Computer Science

(mailed to GTS members by Peyton Young on Mon, 21 Jan 2008)

At the recent conference in Jerusalem in honor of Ehud Kalai, a new Prize in Game Theory and Computer Science was announced by the Society in recognition of Ehud's role in promoting this exciting new area of research.

The prize will be awarded at each of the next three World Congresses to the person (or persons) who have published the best paper at the interface of game theory and computer science in recent years. Preference will be given to candidates who are 45 or less at the time of the Congress, but this is not a binding constraint. The amount of the Prize will be $2000 plus travel expenses to attend the Congress.

The Society invites nominations for the prize, which will be awarded for the first time at the upcoming World Congress at Northwestern University (July 13-17, 2008). Each nomination should include a full copy of the paper (in pdf format) plus an extended abstract, not exceeding two pages, that explains the nature and importance of the contribution.

Nominations should be emailed to the Society's Secretary-Treasurer, Eric van Damme (at gts@uvt.nl ), by 15 February 2008. The selection will be made by a committee appointed by the President, and the result will be announced in April 2008.