Game Theory and Computer Science Prize

OK, it's the main reason I attended the conference, since it was awarded to Constantinos Daskalakis, myself and Christos Papadimitriou for our paper “The Complexity of Computing a Nash Equilibrium”, which first appeared at STOC in 2006. The plan is to award this prize once every world congress of the Game Theory Society (so, every 4 years) for a recent CS/game theory paper. It's an encouraging sign of the interest that the game theory community has for work going on in CS.

Constantinos Daskalakis gave the talk; in the audience was John Nash himself (Nash equilibrium was named after him since he was the one to prove (back in 1950!) that any game has one (at least one, to be more precise.)) Nash is now 80 years old, so he was 22 when he obtained that famous result.

Other bits and pieces: I attended a very nice talk at a session on "Roommate and Marriage Models", given by Thayer Morrill, on "The Roommates Problem Revisited". From memory, here's the idea. The problem with looking for a solution to the Stable Roommates Problem (in contrast with the Stable Marriage Problem) is that for some instances of the problem, any proposed solution may have at least one blocking pair. (That is, a pair of participants who prefer each other to the partners to which they have been assigned.) So, what we need is, a new solution concept. Morrill notes that shared rooms are scarce - the members of a blocking pair typically cannot go off together and move in with each other unilaterally. Instead, a solution should be deemed stable, essentially if there is no group of participants who can re-distribute the keys to their rooms in such a way that they are all happier than before. A solution should be Pareto optimal in this sense. Given this notion of what it means to be a solution, there is a simple algorithm that finds solutions efficiently, called something like "iterated random dictator", in which at each step, a participant is chosen, who gets to select his/her roommate; those two are paired off and we continue with the remaining participants.

Another session I attended was on "Algorithms and Games", where I got to attend talks by COMSOC invited speakers Tuomas Sandholm and Rohit Parikh. (It clashed with a session on "War", which I was sorry to miss.)

Outgoing president of the Game Theory Society, Peyton Young, gave a great plenary talk about viewing the search for a Nash equilibrium as an iterative learning process in which a player should interact with the other players solely by trying to improve his own payoff and not by attempting to model the behaviour of the other players. The wonderful thing about this talk, as far as I'm concerned, is how much it overlaps (coincides?) with my own research agenda. It is great to hear that the mainstream game theory community is very interested in these issues. I hope to talk to him later in more detail, but already I have some very interesting literature to look into, and will certainly write my next research proposal with that much more conviction.

This evening I got to attend a dinner hosted by Ehud Kalai; I came away feeling slightly star-struck by all the eminent game theorists who were in attendance...