Archive for March, 2011
The March 2011 issue of SigEcom exchanges has been published. SigEcom Exchanges is the official newsletter of the ACM special interest group on E-commerce, and despite its “official” status contains interesting AGT-related articles. Yiling Chen is now replacing Vincent Conitzer as the editor. Thanks to Vince for his work and Wishes of success to Yiling.
The AGT semester at the institute of advanced studies of the Hebrew University is gearing up with a sequence of AGT talks being given at various forums here. What I liked about the last few talks that I heard is that each of them really advances an agenda by exhibiting a result, rather than just showing a result.
Christos Papadimitriou gave a special seminar with his usual title Games, Algorithms, and the Internet. While the title remained fixed for quite some time (I have heard him talk with this title at least twice in the last few years), the technical content changes as the years pass, shifting to his most recent work (Christos remarks that this is better than keeping the content and changing the title, a not too unusual state of affairs). This talk is the mother of all AGT-as-a-way-to-study-the-Internet agenda setting talks. As usual the talk contained memorable one-liners, some that I’ve heard before (Scot Shenker: “The Internet is in Equilibrium, we just have to identify the game”), and some new to me (“If Game Theory is a beauty contest among modeling concepts, then Computational Complexity should be one of the judges”). A particularly lively discussion with the audience ensued when he offered the interpretation that NP-completeness implies “mathematical-nastiness”, and thus in some vague sense, (which I’d be happy to see made more precise,) proving that a certain problem is NP-hard means that “you’re not going to get nice mathematical theorems about it”. (The context was his recent paper with George Pierrakos on the difficulty of extending Myerson’s theorem to interdependent valuations.)
Tim Roughgarden talked in our group’s Computation and Economics seminar and his agenda was the possibility of designing “distribution-free” mechanisms. The idea is that you want to design a mechanism that does not depend on the prior distribution of valuations (“detail free” as the “Wilson doctrine” would call it), and still is competitive with an optimal algorithm designed for a specific distribution; and for this to happen for all prior distributions. Amazingly, this is possible, with the classic example being the Klemperer-Bulow result showing that, in a single item auction, having an additional single bidder and having no reserve price (and thus being detail-free) always gets at least as much revenue as using the optimal Myerson reserve price (which depends on the distribution). Tim and his co-authors, Peerapong Dhangwatnotai and Qiqi Yan, were able to get competitive detail-free auctions for more complex settings and without adding an extra bidder.
Kevin Leyton-Brown actually gave two talks, the first in the rationality seminar, and the second in the CS colloquium. While the “proof of concept” in both talks were actual software systems that he built, they served to demonstrate his agendas. In the first talk he advocated modeling and analyzing games computationally, for which a good “language” to describe games is needed. Such a language should be succinct and yet amenable to efficient computation, and he suggested — and provided software for — the language of “action graph games“. In the second talk he advocated “meta-algorithmic” optimization techniques: taking existing algorithms and automatically combining them and/or optimizing their parameters using learning-like methods on a given data-set. He built several systems along these lines, the most impressively demonstrated of which is SATzilla which won several medals in SAT solving competitions.
Google has awarded a grant to a group of 20 PIs (including myself) from three universities in Israel for the study of “electronic markets and auctions”. It is defined rather widely from basic Algorithmic Game Theory type issues to more applied ad-auction questions and spans a spectrum of researchers from CS, AI, GT, EE, IE, math, economics, and business. The crucial point is that this is academic non-Google-specific research and its results will be normally academically published.
The list of PIs is:
- Hebrew University: Danny Dolev, Jeffrey S. Rosenschein, Noam Nisan (Computer Science and Engineering); Liad Blumrosen, Alex Gershkov, Eyal Winter (Economics); Michal Feldman and Ilan Kremer (Business). The last six are also members of the Center for the Study of Rationality.
- Tel Aviv University: Yossi Azar, Amos Fiat, Haim Kaplan, and Yishay Mansour (Computer Science); Zvika Neeman (Economics); Ehud Lehrer and Eilon Solan (Mathematics); and Gal Oestreicher (Business).
- Technion: Seffi Naor (Computer Science); Ron Lavi (Industrial Engineering); Shie Mannor and Ariel Orda (Electrical Engineering).
Many observers are curios about Google’s motives in such a grant. It seems that Google is simply trying to support basic research in an area which is crucial for it, while strengthening its ties with researchers, students, and the academia in this area.
- NetEcon 2011 — 6th workshop on Economics of Networks, Systems, and Computation. June 6th. Submission deadline: March 25th.
- Workshop on Bayesian Mechanism Design. June 5th. Submission deadline: April 15th.
- Workshop on Implementation Theory. June 6th. Submission deadline: April 3rd.
- 7th Ad Auction Workshop. June 5th. Submission deadline April 15th.
- Workshop on Social Computing and User Generated Content. June 5th. Submission deadline: April 15th.
The Center of Rationality at the Hebrew University of Jerusalem is announcing five postdoc positions in game theory and rationality for the coming academic year. This is certainly one of the best places in the world for interdisciplinary research involving game theory, with a large number of excellent researchers in Economics, Computer Science, Mathematics, Psychology, and other disciplines, all interested in Game Theory and Rationality. The areas open this year are:
- Game Dynamics. Host: Sergiu Hart
- Algorithmic Game Theory. Hosts: Liad Blumrosen and Noam Nisan
- Game Theoretic Approaches to Financial Economics. Host: Ilan Kremer
The positions carry unusually high Stipends. The final deadline for application is May 31, 2011, but strong applications received by March 31, may get an early reply. For details see the poster.