[Computational Complexity] 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 collaboration between our fields 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.
Posted By Lance to Computational Complexity at 7/18/2008 06:36:00 AM