# Newsletter of the Game Theory Society 2015

## Call for Papers

Submission for GAMES 2016, the Fifth World Congress of the Game Theory Society, is now open, and closes on February 15, 2016. The Congress takes place Sunday-Thursday 24-28 July, 2016 in Maastricht, the Netherlands. You can submit a paper (including an abstract of up to 150 words), and revise it until submission closes, after registering free of charge with the EasyChair conference system, as described in the submission instructions. Each participant can submit only one paper. Accepted papers will be selected for a contributed talk of 25 minutes (including discussion/questions) in a parallel session, or else a poster presentation (entered into a queue in case talk slots become available).The Congress is the main event of the Game Theory Society, which takes place every four years.

Participation at the Congress requires membership in the Game Theory Society in 2016 (which is inexpensive, see 2015 membership options including journal subscriptions and concessionary rates).

GAMES 2016 conference fee: Early 390 Euros, late (from May 16, 2016) 490 Euros. The fee includes access to all talks, refreshments and lunches, a conference dinner, and free local public transport. Students get a 50 percent discount. Inexpensive dormitory rooms will be available.

The Congress is co-located with the 17th ACM Conference on Economics and Computation (EC'16) which participants at GAMES 2016 are allowed to attend (as are EC participants at the Congress).

Maastricht is a beautiful medieval city in the heart of Europe. The Congress takes place in a single location at the university in the town center. Maastricht is in easy reach from airports at Brussels BRU, Cologne/Bonn CGN, Düsseldorf DUS, or Amsterdam AMS. Information on public transportation and shuttle services (in particular to BRU and DUS) will be provided on the conference website.

**Important dates:**

Submission deadline papers: February 15, 2016

Notification of decisions: March 15, 2016

Deadline for Early registrations: May 15, 2016

## 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 (at) maastrichtuniversity.nl , where " (at) " should be replaced by "@"). 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 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.