Last week I spent all of my time at the iAGT workshop in Jerusalem that I organized together with Michal Feldman and my garduate student Tali Gutman (who really did everything). This workshop is part of the activities of of the Semester on Algorithmic Game Theory at the Institue of advanced studies at the Hebrew University, with additional funding from the Google grant on electronic markets and auctions, as well as from Microsoft. The worskhop was packed with over 100 registered participants, A great list of 35 speakers, a poster session, a panel on “future directions in AGT”, trips to Masada and the Jerusalem old city, and has ended with a party at Amos Fiat’s new 300-year-old house. As an organizer I think that the workshop went great, with a wide coverage of AGT, excellent talks, high energy levels, and real “community-building”. We are posting videos of all talks on the web, and currently we have three formats: .mov files, .flv files, and slowly we are uploading the talks to youtube.
Let me mention two talks that left an especially large impression on me (both from the first day, since as the workshop progressed my brain capacity was getting lower). Paul Goldberg talked about his paper “The Complexity of the Homotopy Method, Equilibrium Selection,and Lemke-Howson Solutions” with Papadimitriou and Savani. While I’ve seen this paper before, I needed Paul’s crystal-clear talk to really understand the point: while the problem of finding an arbitrary Nash equilibrium is PPAD-complete, the problem of finding the “natural Nash equilibrium” — which is found e.g. by the Lemke-Howson algorithm — is harder, i.e. is PSPACE-complete. This distinction is similar to the well-known one for the cannonical PPAD-complete problem which asks to find an “end-of-line” in an exponential sized graph defined by a given Boolean circuit: finding an arbitrary end-of-line, in addition to a given one, is PPAD-complete, while finding the end of line specifically at the other end of the given one is PSPACE-complete.
Nina Balcan talked about her paper “Learning submodular functions” with Harvey (re-titled “learning valuation functions” so as to fit the workshop theme more directly). The main technical result is a new construction of a family of matroids over m items . This family has the following property: there is a fixed collection of super-polynomially (in m) many sets such that for any assignment of low/high to each one of these sets, one of the matroids in this family has a polylogarithmic rank on all the “low” sets and a rank on all the “high” sets. This technical feat is useful for proving lower bounds on various tasks you may want to do for submodular functions (such as learning them in an approximate sense) since the matroid rank function is submodular so we get a rich new family of submodular functions to make our life hard. Even more surprising to me was a reamrk made by Nina after the talk that matroid rank functions actually belong to the even more restricted family of “(gross) substitutes”, so such lower bounds will also apply to this smaller calss as well.
An interesting theme I could see in several talks was that we continue to look at new notions for modeling the private information in mechanism design, and we are starting to address more sophisticated information structures than the simple privae-value setting. Early work by Computer Scientists embraced the notion of dominant strategies — a worst case notion that we like in CS — and shunned the standrad economic modeiling of Bayesian priors. Many of the new papers are trying to find some middle ground — starting now with the Bayesian models and attempting to take a step back as to make them “distribution free” ala the “Wilson doctrine” or at rely on less information. See the Wednesday morning session and the Thursday afternoon session for examples of such talks.
The panel discussion was quite lively, much of it focusing on Kevin Leyton Brown’s comment that the elephant in the room is that we are all working on theoretical models which we don’t believe that they reflect reality. (My brother who is a philosopher of science told me that this “modeling question” is highly discussed in his field.) The natural continuation was the question of whether and how should we be in touch with practitioners as to make sure that we don’t lead ourselves astray with worthless theoretical questions. Silvio Micali insisted that it is our duty to lead the practitioners and provide them with new notions and ideas that they can not even imagine today rather than to follow them and solve their current concerns, while many others talked about the reality-check that interactions with practitioners brings.
Much more was going on, of course, but I’ll stop now and start getting ready for FCRC next week.