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.
Turing's Invisible Hand 
Leave a Reply