I’m currently on my way from EURO in Bonn to ICALP in Rhodes. Euro is the main Operations Research conference in Europe and I was invited to give a (semi-)keynote talk in it. I’ve never been in an OR conference before, and while I never totally understood what OR is, I always had the feeling that Algorithmic Game Theory should in principle fit squarely into OR, since these are the guys that anyway mix CS-ey optimization with economic considerations (and they’re really into LP to boot). Of course, in reality there has been very little contact between the Algorithmic Game Theory community and OR (well, yeh, Rakesh.) So, not only was I happy to give a talk, but I was also curious to find out everything about the OR field (spoiler: I failed).
Well, first the conference is huge: about 2,500 attendees (of which I personally only knew three…). The sessions are 45-way parallel. I understand that the North-American OR conference, INFORMS, is even larger. So, it seems that OR is thriving. The attendees looked about the same as I’m used to in TCS conferences, many of them young, the usual O(20%) female, dress-code more often casual than suited, but with very few North-Americans and a more varied European presence (including many from Spain, France and Turkey). The “opening session” was a pretty heavy event, starting with Beethoven’s Ode to Joy, several addresses by conference officials, as well as by the Mayor of Bonn (kudos to him for paying attention to a scientific conference), performance by an Opera singer (who’s getting a Ph.D. in OR), and the announcements of various awards. The most significant ones are the “Euro gold medal” awarded to Jacques Benders for his pioneering work in the 1960’s on decomposition in linear programming as well as to Frank Kelly for his work on networks, which had a strong influence on Algorithmic Game Theory too. Michael Trick’s blog post gives more details from an insider’s point of view.
The main keynote talks were by Reinhard Selten, a Nobel laureate economist, and by our own (?) Christos Papadimitriou. Selten described, in much detail, an economic experiment that studies “goal formation” in the sense of Herbert Simon. Christos gave the current version of his usual talk on the complexity of equilibria. While the title remains the same, the contents keep being updated as Christos obtains new results. (As Christos says, this is better than giving the same talk but with changing titles.) Since the last time that I heard this talk, the focus has moved from the basic PPAD-hardness impossibility results, to the various ways of dealing with them: approximation, special cases, and so on. Christos’s talk, as usual, was full of inspiring “one-liners”, some of which you can read in Michael Trick’s blog post. My favorite take home was the term “the third compromise”: approximation due to NP-hardness being the first compromise of CS, online algorithms due to partial information being the second, and equilibria due to non-cooperative behavior being the third. The last part of his talk was devoted to sexual optimization, somewhat off-topic but certainly entertaining.
Given 45 parallel tracks, I missed over 97% of all regular talks (well, ok, more than 98%), but a glance at the nicely colour-coded “master track schedule” can give some sense of what is OR today: many X-programming and X-optimization sessions, for X in {linear, non-linear, quadratic, convex, non-convex, mathematical, stochastic, boolean, semi-infinite, non-smooth, …}. Various applications in transportation, health-care, agriculture, finance, logistics, and more (but nothing I could find in advertsing). Scheduling gets several sessions, as well as data mining and knowledge discovery, supply chains, stochastic stuff (i’m not sure what), as well as various initials that I don’t understand: MCDA, DEA, AHP, and DSS. Well, that’s about what learned about OR this time.
Noam, regarding your statement, that there has been very little contact between AGT and OR: FYI, for the last 3 years, I have been Vice Chair of Informs for essentially CS representation there. I have been organizing 20 something sessions with 4 talks each. Many of these sessions/talks are on AGT. Come to San Diego in October this year.
Yes, you are right ofcourse, I am aware of the AGT sessions in INFORMS. I hope this grows into more interaction between communities.
I think you pretty much summer OR up in this post.
[…] Noam Nisan (see also his report on the EURO on his blog) gave a great talk about google’s tv ad business and how they allocate the slots […]