talks; return home

I return home yesterday, with a four-hour delay to my flight.

Let me mention 2 other good talks. Uri Zwick gave another nice one yesterday on a recent result he co-authored (on a deterministic sub-exponential algorithm for parity games). The hallmark of a great talk is to strip away the layers of definitions and notation that are needed for a precise paper, and to get to the heart of the fundamental idea, and make it look simple. It is hard to do this with one's own work; we do not like to make our own work look simple. I also liked Ronald Peeters' talk on homotopy methods on equilibrium computation - again, a simple idea: you want to compute an equilibrium of a game, so you start out with a game for which you know the equilibria (having the same number of players and strategies) and you gradually move all the numbers that define that game, towards the numbers that define the game of interest. As you do so, try to keep track of one of the equilibria, which are themselves moving continuously as this process goes on. Apparently the Lemke-Howson algorithms can be thought of as this kind of process, which gives me a new way of thinking about the L-H algorithm.

One thing this workshop has done for me is, give me an impression of the interesting and varied ways that people have tried to implement algorithms for computing Nash equilibria in practice - my own work has just been on the analysis of algorithms in the abstract.