# Newsletter of the Game Theory Society 2008

Separate link: Changes in the editorial structure of the IJGT

## Game Theory and Computer Science Prize of the Game Theory Society 2008

Following the call for nominations for the prize in February 2008 from the Society President, Peyton Young, Ehud Kalai chaired, at the request of Peyton Young, the prize committee that included Silvio Micali of MIT and Yoav Shoham of Stanford, to determine the Prize winner(s), and reports (July 21, 2008):Chairing the prize committee was not an easy task. Not because of the people on the committee, they were wonderful to work with, and not because there were no good submissions, but because there were so many outstanding submissions.

#### The Decision of the committee reads as follows:

We are pleased to announce that the winner of the 2008 prize is "The Complexity of Computing a Nash Equilibrium," by Constantinos Daskalakis, Paul W. Goldberg and Christos H. Papadimitriou (2006).

This paper made key conceptual and technical contributions in an illustrious line of work on the complexity of computing Nash equilibrium, e.g., Gilboa and Zemel (1989), Conitzer and Sandholm (2003) and Chen and Deng (2006). It also highlights the necessity of constructing practical algorithms that compute equilibria efficiently on important subclasses of games, e.g., Govindan and Wilson (2004), Bárány, Vempala and Vetta (2005) and Porter, Nudelman and Shoham (2008).

We are also pleased to include honorable mentions to "How Bad is Selfish Routing" by Roughgarden and Tardos (2002), an outstanding example of the measurement of the inefficiency of Nash equilibrium, and to "Program Equilibrium" by Tennenholtz (2004), which uses computer-science concepts to substantially enrich standard game-theoretic modeling.

Signed by the members of the committee:

Ehud Kalai Silvio Micali Yoav Shoham

#### References

- Bárány, I., S. Vempala and A. Vetta, "Nash Equilibria in Random Games," Foundations of Computer Science, 2005.
- Chen, X., and X. Deng, "Settling the Complexity of 2-Player Nash-Equilibrium," Foundations of Computer Science, 2006.
- Conitzer, V. and T. Sandholm, "Complexity Results about Nash Equilibria", Proceedings of IJCAI, 2003.
- Daskalakis, C., P. W. Goldberg and C. H. Papadimitriou, "The Complexity of Computing a Nash Equilibrium," The Symposium on the Theory of Computing, 2006.
- Gilboa, I. and E. Zemel, "Nash and Correlated Equilibria: Some Complexity Results," Games and Economic Behavior, 1989.
- Govindan S. and R. Wilson, "Computing Nash equilibria by iterated polymatrix approximation," Journal of Economic Dynamics and Control, 2004.
- Porter, R. W., E. Nudelman and Y. Shoham, "Simple Search Methods for Finding a Nash Equilibrium," Games and Economic Behavior, forthcoming 2008.
- Roughgarden, T. and E. Tardos, "How Bad is Selfish Routing," Journal of the ACM, 2002.
- Tennenholtz, M., "Program Equilibrium," Games and Economic Behavior, 2004.

### Call for papers - A special issue of the IJGT in honor of Michael Maschler

Professor Michael Maschler passed away on July 20, 2008. A professor in the department of Mathematics and a member of the Center for the Study of Rationality at the Hebrew University in Jerusalem, Israel, Michael Maschler belonged to the small and select group of first generation game theorists who created the discipline,by developing new frameworks of analysis, proposing original solutions and discovering new fields of application. For over fifty years he played a central role in our community, and his name is decisively associated with the development of cooperative game theory and the theory of games with incomplete information. Maschler was among the founders of the International Journal of Game Theory and a member of its advisory board till now. He was also one of the founders of the Game Theory Society and took an active part in all its important activities, in particular the world conferences in Bilbao and Marseille and the international conferences in Stony Brook, one of which he organized.

The International Journal of Game Theory is planning a special issue in honor of Michael Maschler. Papers on any field of game theory are within the scope of the issue, in accordance with Maschler's view of the discipline as a whole. However, we expect that most contributions would be centered around those fields where he contributed most: cooperative game theory, games with incomplete information, coalition formation, bargaining problems, cost sharing, network games etc. Authors who wish their papers considered for this issue should submit no later than January 31, 2009, as we expect the publication of the special issue by July 2009. All papers will be refereed by the standards of the IJGT. In consideration to all authors who might want to join this homage, papers should preferably be no longer than 15 pages.

Submissions are made online
here or at the IJGT site
selecting *article type* as *special issue:
Maschler*.

Shmuel Zamir (Editor of the IJGT)

Salvador Barbera (Editor of the special issue)

### Michael Maschler (1927 - 2008)

*(mailed to GTS members by Peyton Young on Wednesday, 30 July 2008)*

With great sadness we report that, after a long illness, Michael Maschler of the Hebrew University of Jerusalem passed away on July 20, in Jerusalem, at the age of 81. He was a wonderful colleague, researcher, and teacher, and served as a member of the First Council of the Game Theory Society. Michael Maschler will be greatly missed by the game theory community at large.

Professor Michael Maschler was a major architect of the theory of games as we know it. He originated the Bargaining Set for cooperative games, whose conceptual offspring include the kernel and the nucleolus, and did many deep studies of their properties in a wide variety of applications; as a result, the Bargaining Set "family" today constitutes one of the three major approaches to cooperative game theory, together with the core and the Shapley value. His pioneering work on repeated games of incomplete information became the cornerstone of a very extensive literature on the subject, which continues to expand rapidly. He was one of the earliest to do experimental work on the theory of games in general, and in cooperative games in particular. He also contributed importantly to the dynamics of elections, to the theory of extensive games, to network games, and to various other topics in game theory.

Maschler was known as an excellent and much-beloved teacher and lecturer, and a willing citizen of the game theory community. He will be sorely missed, and his memory will be cherished.

Bob Aumann

### Outcome of 2008 Election for Officers of the GTS

*(mailed to GTS members by Eric van Damme on Wed, 21
May 2008)*

Dear Members of the Game Theory Society,

According to the Bylaws of our Society, elections for the Officers of the Society have to be held every two years. The Officers (the President, the past President, the Executive Vice-President, the Vice President for Communications, and the Secretary/Treasurer) are responsible for the ongoing operations of the Society. New officers are elected by the members of the Council, upon a proposal drawn up by the existing officers, using the system of approval voting.

This month the elections took place and we would like to inform you of the outcome.

The candidates proposed were:

For President: Sergiu Hart (to succeed Peyton Young)

For Executive Vice president: Eric Maskin (to succeed Sergiu Hart)

For Vice President for Communications: Bernhard von Stengel (to continue another term)

For Secretary and Treasurer: Federico Valenciano (to succeed Eric van Damme)

Peyton Young had indicated that he did not want to continue for another term; Eric van Damme had served as Secretary-Treasurer of the Society for four terms, which is the maximum allowable under the Bylaws.

In the election 32 Council members (out of 36) voted, and all candidates received very large support, hence, were elected. The newly elected officers will take up their positions on August 1, 2008.

We thank all the people who contributed their effort towards this election, and wish the new officers best of luck in fulfilling their duties.

With kind regards,

Peyton Young

Current President of the Game Theory Society

Ehud Kalai

Past President of the Game Theory Society

### 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 Internet**ional 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)*

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)*

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)*

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.