Friday, July 18, 2008

GAMES and Computer Science

About 30 computer scientists attended the recent GAMES (Game Theory Congress), a tiny fraction of the participants but a noticeable force including several theory heavyweights from a variety of backgrounds: Joe Halpern (Logic), Silvio Micali (Cryptography), Noam Nisan (Complexity) and Éva Tardos (Algorithms). There we also a few AI researchers shuttling between GAMES and AAAI.

The game theory community has made some efforts to welcome the computer scientists. There is now a Game Theory and Computer Science Prize given to The Complexity of Computing a Nash Equilibrium with a lecture given by Constantinos Daskalakis and co-authored by Paul Goldberg and Christos Papadimitriou (noticeably missing from GAMES). Goldberg also has several posts on his blog about the award and the conference.

The Shapley lecture, given each congress by a researcher under 40, was given this year by computer scientist Tim Roughgarden. Afterwords there was a CS-Game Theory lovefest between Tim and Ehud Kalai, one of the leaders of the game theory community. It doesn't hurt that Ehud's son, Adam, is one of our own.

On Monday the conference had a panel by recent Nobel prize winning game theorists Eric Maskin, Robert Aumann and Roger Myerson on the recent history and future of the field. Mostly the expected preaching to the choir but at the end Aumann did talk about the importance of computer science in games in the areas of crypto, games played on computers, auctions and real-time algorithms. He followed up with a memorable take on the future by singing the chorus of Que Sera Sera.

Sergiu Hart, new president of the Game Theory Society, gave an invited talk on his paper with Yishay Mansour showing exponential lower bounds for convergence to a Nash equilibrium in certain models. A nice result but he unfortunately picked up the CS habit of using "natural" as shorthand for "the set of assumptions needed to prove the main theorem."

Computer science showed up in several other presentations. For example, Iter Sher uses max-flow to analyze persuasion. Nearly every topic in game theory hits on CS issues and many (though not all) game theorists seem welcome to have computer scientists work on their problems. There are still many language, technical and cultural issues to overcome to have true collaborations but I foresee a bright future between our fields. So go talk to a game theorist. They don't bite.

Not CS related by on Wednesday we had lunch-time entertainment presentation by Yoram Bauman, self-proclaimed stand-up economist. He opened the talk with his translation of the 10 Principles of Economics which you can watch yourself in this video.


  1. What does "lovefest" mean in this context?

  2. Lovefest: Tim said how great it was that a CS person was chosen for the Shapley lecture, then Ehud mentioned how great it was that CS people were using their tools in Econ and Tim said it was a 2-way street. All that was missing was the group hug.

  3. what are the language, technical and cultural issues to overcome? As I see CS is pretty much connected to games

  4. about language and cultural differences: the easiest way to see them is to go to any game theory seminar at your local economics department. i expect you'd find them significant.

  5. THE PLAYING of violent video games makes teens more emotional according to a report produced by the Indiana University School of Medicine.
    Not to sure what you are trying to say..I mean is it or is it not.

    Anyhow I know I am rambling but try to see it from someone reading it the first time without thinking about it first.
    Luwow Goldman - Luwow Goldman