Shahar Dobzinski reports from EC

Guest post by Shahar Dobzinski, reporting from EC:

EC took place last week at Stanford. For me EC is not necessarily the place to hear new results; I already read or heard talks about most of the papers that interest me in the program. The best thing about EC is that it is a meeting place for the algorithmic game theory community (with quite a few attendees that do not coauthor a paper in the proceedings).

The EC audience is quite diverse and consists mainly of Theory and AI people, but there are also some economists and attendees from other areas. Though it seems that everybody is quite happy with this diversity, I couldn’t avoid noticing that theory people tend to complain that there are too much AI papers, AI guys complain that there are too much theory papers, and both complain that there are too many computer scientists who are doing pure economics. Economists seem to be too polite to complain (at least when I am around). Optimists would interpret this as a sign that the mix of papers is correct.

One disappointing feature of this conference is the horrible meeting room. The room is huge, full with round tables. Hard to even hear hear the questions asked by the audience, so the poor session chair has to run with a microphone to the other side of the room whenever there is a question. I have never been to a wedding in the US, but in Israel this room could be a great wedding hall.

So what are the trends in EC? Adwords seems like a hot trend, although my feeling is that it was hotter last year. Many papers model different issues in selling ad auctions, and even more papers with adwords as their claimed motivation and inspiration. Adwords are an important application of algorithmic game theory, but in some sessions it looked as if this is the only application. On the other hand, relatively not too many equilibria computation papers were presented.  Price-of-anarchy type of results were not too popular either. Still, approximately 10 percent of the papers in the conference had the phrase “price of” in their title, and a few more have it in the abstract. Termed in 2001 by Papadimitriou, the “price of anarchy” is surely a great, catchy name. Unfortunately, by now it might be overused: an hypothetical list of the difference “prices” defined by now would probably be about the same size of Garey and Johnson’s NP-complete problems list. We should consider a definition freeze for at least a year or two.

Two papers won the outstanding paper award. Nicolas Lambert gave a very good talk on his paper with Yoav Shoam. The paper shows how to design payment schemes that motivate experts to answer truthfully multiple-choice questions. The expert is being asked, for example, ”what is the mean of a random variable X?” and is getting paid according to the realization of X.  They provide a complete characterization of the possible mechanisms. The paper also got the best student paper award.

The second winning paper was my joint paper with Itai Ashlagi and Ron Lavi. We considered the problem of truthful scheduling of jobs on unrelated machines to minimize the makespan, that was introduced by Nisan and Ronen in their “Algorithmic Mechanism Design” paper. We showed that no anonymous mechanism can provide a more-than-trivial approximation ratio (a mechanism is anonymous, if, roughly speaking, the names of the machines does not matter).

EC’10 will take place at Harvard, with  Moshe Tennenholtz and Chris Dellarocas as chairs. Hopefully it will be at least as good as EC’09.

Advertisement