Welcome to the Website of the Game Theory Society

# GTS News

*(last updated on September 2, 2015)*

## In Memoriam: Herbert Scarf (1935-2015)

*posted by Rakesh Vohra, 17 November 2015*

Herbert Scarf, one of the towering figures of the field, passed away on November 15th, 2015. Like John Nash and Harold Kuhn he was a member of that cohort that was to revolutionize Economics and Operations Research. Scarf himself left a lasting mark in Economic Theory, Mathematical Programming, Operations Research and Game Theory. In many ways he was ahead of his time in working on problems at the intersection of Game Theory and Algorithms.

Scarf's interest in algorithms was long standing. The title of his magnum opus: `The Computation of Economic Equilibria' said as much. His interest in the problem of indivisibilities led to a sequence of papers in integer programming that introduced the notion of neighborhood systems. This anticipated the use of Groebner basis in integer programming.

The lemma that bears his name, has, in the last decade found many applications in combinatorics and computer science. That lemma showed that balancedness was a sufficient condition for non-emptiness of the core of a NTU game. It has received renewed attention as a powerful tool for proving a host of combinatorial results. In fact, it has been used recently to establish stability properties of a stylized version of the border gateway protocol (BGP). The BGP is the dominant interdomain routing protocol used to exchange routing information on the internet today.

He departs leaving us richer than we were before.

## Call for nominations - The Lloyd Shapley Lecture

The Lloyd Shapley Lecture is given at each World Congress of the Game Theory Society by a distinguished game theorist aged 40 or under at the time of the Lecture.The Game Theory Society is currently inviting nominations for the Lloyd Shapley Lecture at GAMES 2016 - Fifth World Congress of the Game Theory Society, July 24-28, 2016, Maastricht, The Netherlands.

Each nomination letter should include a short summary, not exceeding two pages, that explains the nature and importance of the contributions of the candidate.

Nominations for the Lloyd Shapley Lecture should be emailed to the Society's Secretary-Treasurer, Jean-Jacques Herings (at gts-sbe@maastrichtuniversity.nl) by October 31, 2015. The selection will be made by a committee appointed by the President consisting of

Ehud Kalai (Northwestern University, USA)

Andy McLennan (University of Queensland, Australia)

Abraham Neyman, chair (Hebrew University, Israel)

Marilda Sotomayor (USP, Brazil)

Nicolas Vieille (HEC, France)

## Call for nominations - Prize in Game Theory and Computer Science

The Prize in Game Theory and Computer Science of the Game Theory Society in Honour of Ehud Kalai was established in 2008 by a donation from Yoav Shoham in recognition of Ehud Kalai's role in promoting the connection of the two research areas. The Prize will be awarded at the Fifth World Congress of the Game Theory Society, July 24-28, 2016, Maastricht, The Netherlands.

The Prize will be awarded to the person (or persons) who have published the best paper at the interface of game theory and computer science in the last decade. Preference will be given to candidates of age 45 or less at the time of the award, but this is not an absolute constraint. The amount of the Prize will be USD 2,500 plus travel expenses of up to USD 2,500 to attend the Congress.

The Game Theory Society invites nominations for the Prize. 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, Jean-Jacques Herings (at gts-sbe@maastrichtuniversity.nl ) by September 30, 2015. The selection will be made by a committee appointed by the President consisting of

Preston McAfee (Microsoft)

David Parkes (Harvard)

Eva Tardos, chair (Cornell)

Bernhard von Stengel (LSE)

## John F. Nash and his wife Alicia Larde killed in car crash on May 23, 2015

*(posted May 24, 2015 by Rakesh Vohra)*

On Saturday May 23rd, 2015, a taxi bearing John Forbes Nash and Alicia Larde went out of control and hit a guard rail. Both were thrown from the vehicle and met their deaths. Nash was 86 and Larde was 82. Nash is survived by two sons, John Charles Martin Nash and John David Stier.

Nash is known to the wider world because of his struggles with schizophrenia in his youth, and Larde for the care and support she gave him. This was described in Sylvia Nasar's biography and popularized in a movie with Russell Crowe playing Nash and Jennifer Connelly playing Larde. With the passage of time it appeared that his schizophrenia faded. Nash once remarked that the voices in his head never went away. Rather, he had chosen to ignore them.

Nash was part of that remarkable cohort that passed through Princeton's Fine Hall in the 1950s. Shapley, Shubik, Tucker, Kuhn, names now familiar in our mouths as household words. Nash himself will be remembered for three things. The first is Nash equilibrium. Legend has it that von Neuman was unhappy with the concept because it gave up on the idea of finding a notion of value for non-zero-sum games. Nevertheless, it stuck as members of this society well know. To say more would be to gild a lilly that needs it not. For this contribution Nash was honored with the 1994 Nobel memorial prize in Economics.

The second is the Nash embedding theorem. It shows that every Riemannian manifold can be isometrically embedded into some Euclidean space. For this contribution, Nash was awarded the 2015 Abel prize. In fact, Nash and Larde were in Norway fours days prior to their deaths for the Abel prize award ceremony, and on their way home from the airport when the accident happened.

Third is his anticipation by at least a decade the notion of computational complexity and trapdoor functions in cryptography. These ideas are outlined in a handwritten letter by Nash to the U.S. National Security Agency in 1955. This letter was declassified in 2012. A succinct summary can be found here as well as a link to a copy of the letters themselves.

In the period after the award of the Nobel, Nash was
much concerned with the notion of `ideal money.' The
underlying question was formulated in 1903 by Charles Conant
as follows:
``Can a better form of standard money be devised than silver and gold? Is a
more equitable means attainable of conducting exchanges than by the use of
coined money?''

Nash's views on the subject can be found here
and are interesting to read in light of current discussions
about bitcoin and other alternatives to money.

It should not be forgotten, but probably will, that Nash developed the board game Hex (also invented independently by Piet Hein). It is an example of a connection game played on a board of equal length and width where the game spaces are hexagonal. The players play at perpendicular angles to each other, and the goal of each is to connect from his side to the opposite side.

Further obituaries: New York Times, Guardian, BBC World Service.

## 2015 Abel prize awarded to John F. Nash and Louis Nirenberg

On March 25th of this year the Norwegian Academy of Sciences announced that John Nash along with Louis Nirenberg were awarded the Abel prize in Mathematics. The prize is named in honor of Niels Hendrik Abel, whose name graces commutative groups (with a pun involving grapes) and certain integrals and functions in the complex plane related to elliptic curves. Nash is being honored for what is now called the Nash embedding theorem which states that every Riemannian manifold can be isometrically embedded into some Euclidean space. The official citation states Nash's "striking and seminal contributions to the theory of nonlinear partial differential equations and its applications to geometric analysis" in its press release. In 2012, Harold Kuhn conducted an interview of Nash on his discoveries and his early years at Princeton.Nash is the first Nobel laureate to have won the Abel prize but not the first prize winner to have made contributions to Game Theory. In 2011, the Abel prize was awarded to John Milnor.

## Award of the 2015 Michael B. Maschler Prize of the Israeli Chapter of the Game Theory Society

Alex Frug, a Ph.D. student in Economics at Tel Aviv University, is the winner of the 2015 Maschler Prize. The Michael B. Maschler Prize is an annual prize awarded by the Israeli chapter of the Game Theory Society to an outstanding research student in game theory and related topics in Israel. See the Maschler prize website.## In Memoriam: Harold W. Kuhn (1925-2014)

*posted by Rakesh Vohra, 27 January 2015*

Harold Kuhn passed away July 2nd, 2014. Members of the Society will recognize the name because of the integral role he played in the development of Game Theory. Robert Aumann, former president of the Society, writes:

"One can't call him game theory's father and mother - those were von Neumann and Morgenstern (respectively). But continuing with the family analogy, one might liken him to a particularly family-minded older brother. Not only did he make fundamental research contributions which continue to shape the field to this day, he contributed greatly - and very importantly - to the social fabric of the discipline."

Born in 1925, he came of age in the Princeton mathematics department when Giants, one is reliably informed, roamed the earth. Among his fellow students were John Nash, David Gale, Martin Shubik and Lloyd Shapley, John Milnor and John McCarthy. Genius, as plentiful as weeds.

Kuhn is famous for his contributions to both game theory and mathematical programming. I will recall three of them here. First, the paper with William Tucker and David Gale establishing the connection between the duality theorem of linear programming and equilibria of zero sum games. Second, Kuhn invented extensive form games with information sets and established the equivalence between behavior strategies and mixed strategies in extensive form games with perfect recall. Like the first result, Kuhn's Theorem (published in 1953) is so much a part of our mental furniture that it is a staple of homework sets in Game Theory classes. Third, the Kuhn-Tucker-Karush theorem for optimality. Members of the Society will recall that Karush's name did not always grace this theorem even though he had arrived at it in 1939 (Kuhn-Tucker is from 1951). How Kuhn responded is an example to us all. He wrote Karush:

"In March I am talking at an AMS Symposium on 'Nonlinear Programming - A Historical View.' Last summer I learned through reading Takayama's Mathematical Economics of your 1939 Master's Thesis and have obtained a copy. First, let me say that you have clear priority on the results known as the Kuhn-Tucker conditions (including the constraint qualification). I intend to set the record as straight as I can in my talk."

The letter closes with this paragraph:

"Dick Cottle, who organized the session, has been told of my plans to rewrite history and says 'you must be a saint' not to complain about the absence of recognition. Al Tucker remembers you from RAND, wonders why you never called this to his attention and sends his best regards."

Karush's reply, 6 days later, equally gracious:

"Thank you for your most gracious letter. I appreciate your thoughtfulness in wanting to draw attention to my early work. If you ask why I did not bring up the matter of priority before, perhaps the answer lies in what is now happening - I am not only going to get credit for my work, but I am going to be crowned a "saint".'

Interestingly, one of Kuhn's contributions to optimization was the Hungarian algorithm for the assignment problem (1955). This algorithm anticipated later primal-dual methods for optimization and was inspired by the work of Kőnig and Egerváry (hence Hungarian). It was discovered quite recently that Carl Jacobi (1890, posthumously) had derived the same algorithm. No doubt Harold Kuhn, wherever he might be, is setting the record straight.

## Congratulations

to Jean Tirole for receiving The Sveriges Riksbank Prize in Economic Sciences in Memory of Alfred Nobel 2014 "for his analysis of market power and regulation".Jean Tirole |
---|

"The progress in these areas largely reflects two methodological breakthroughs: game theory and the theory of mechanism design."

As this is the 75th anniversary of the publication of von Neumann and Morgenstern's seminal book, it is interesting to reflect on the introductory paragraph in Chapter 1:

"It is well known what considerable and in fact unsurmounted difficulties this task involves given even a limited number of typical situations, as, for example, in the case of the exchange of goods, direct or indirect, between two or more persons, of bilateral monopoly, of duopoly, of oligopoly, and of free competition."

With the award to Tirole, the Nobel committee has now honored work that has advanced our understanding of each and every one of the topics that von Neumann and Morgenstern listed in their introduction.

## Call for Papers - Journal of Dynamics and Games, Special Issue on Matching: Theory and Applications

*(posted September 30, 2014)*

The *Journal of Dynamics and Games* (IJGT)
is pleased to invite paper submissions for
**Matching: Theory and Applications**,
a Special Issue dedicated to Marilda Sotomayor on the occasion of her 70th
birthday.

Marilda Sotomayor is a foundational figure in the development of matching
theory and applications in economics with seminal contributions on the
structural, game theoretic and mechanism design aspects of the basic model
and its extensions. Her volume **Two-Sided Matching** (1992), co-authored
with 2012 Nobel laureate Roth is the singular textbook in the area, which was
awarded the prestigious Frederick W. Lanchester Prize.
Papers are welcome on all aspects of matching games and markets,
theoretical as well as applied, including the analysis and design of
institutions or marketplaces, e.g. for jobs or school choice, for houses or
organ exchange.

Please submit your paper directly to one of the invited editors using their email:

**Ahmet Alkan**

Sabanci University, Turkey, Email: alkan@sabanciuniv.edu

**Jesús David Pérez Castrillo**

Universitat Autònoma de Barcelona, Spain,
Email: David.Perez@uab.cat

**Myrna Wooders**

Vanderbilt University, USA,
Email: myrna.wooders@vanderbilt.edu

**John Wooders **

University of Technology, Australia,
Email: John.Wooders@uts.edu.au

**28 February 2015**

Journal webpage:

http://aimsciences.org/journals/home.jsp?journalID=26

## Call for Papers - IJGT Special Issue in Honor of Abraham Neyman

*(posted May 29, 2014)*

The *International Journal of Game Theory* (IJGT)
is pleased to announce a
special issue in honor of Professor Abraham Neyman, in recognition of his
important contributions to game theory and on the occasion of his 66th
birthday in 2015.

We solicit papers for the special issue within the entire scope of IJGT and
in particular within the research interests of Abraham Neyman. The deadline
for submission of papers is December 1, 2014. Authors submitting their work
to the special issue should indicate in the cover letter that the
submission is for the special issue in honor of Abraham Neyman. Submissions
will be subject to normal refereeing procedures and to the usual standards
of the IJGT.

Olivier Gossner, Ori Haimanko and Eilon Solan are the editors of the
special issue.

## Israeli Chapter of the Game Theory Society - Elections

*(posted April 9, 2014)*

The Israeli Chapter of the Game Theory Society elected Abraham Neyman as the President for the years 2014-2016, and re-elected Eilon Solan as the Executive Officer for a second (and last) term.

## Game Theory Software

*(posted April 9, 2014)*

Try out the Game Theory Explorer software for the interactive creation and equilibrium analysis of (currently two-player) games in extensive and strategic form.

See also our resources on algorithms for game theory; further suggestions welcome!

## GAMES 2016 in Maastricht, The Netherlands, 24-28 July 2016

*(mailed to GTS members by Roger Myerson, President of the Game Theory Society on Monday, 19 August 2013)*

Dear members of the Game Theory Society,

the Fifth World Congress of the Game Theory Society is scheduled for
Sunday-Thursday **24-28 July 2016**, to be held in **Maastricht, The Netherlands**. Please mark these dates in your calendar!

Scholars can meet for such global exchanges of ideas only with the help and support of major academic institutions. Our Society was fortunate this year to receive an offer to host GAMES 2016 from Maastricht University as well as from several other outstanding institutions. Let us all plan to help make the 2016 World Congress an important event that will mark the progress of our field from 2012.

### Check out our book listing (and send suggestions) - new book:

Michael Maschler, Eilon Solan, and Shmuel Zamir

2013 Cambridge University Press