Category: Prizes

Christos Papadimitriou of UC Berkeley was the IFORS Distinguished Lecturer at the EURO Meeting yesterday (in the fuzzy picture, he is getting his award from IFORS President Elise del Rosario), and gave a very fine lecture on “Computing Equilibria” (and Sex, though that was not in the formal title).   The starting point for his lecture was to note that the internet has greatly increased interest in multi-player games.   Christos described the Internet as the first computational artifact that was never truly designed:  it was formed by the selfish behavior of millions of agents.  To quote Scott Shenker:

The Internet is an equilibrium, we just need to identify the game

But how do players in a game find an equilibrium?  For simple zero-sum games, linear programming can find an equilibrium.  For non-zero sum games, John Nash in 1950 proved an equilibrium exists, but his proof is nonconstructive (and is essentially equivalent to Brouwer’s fixed point theorem).

This issue of finding equilibria often comes up in coffee conversations with my colleagues.  Economists love the beauty of their theorems, but I get frustrated when they claim what they do has real-world relevance when their actors have super-real capabilities.  As Christos quoted:

if your laptop can’t find it, then neither can the market

But, they complain, it is really a bunch of different actors, so perhaps the quote should be “if a million laptops can’t find it, then neither can the market”, but that doesn’t affect things very much.  Given the lack of computational methods for finding equilibrium in any but the simplest games and markets, it seems reasonable to worry about the advisability of relying on the assumption that people in real markets can magically find equilibria.   In fact, Christos has a theorem on price adjustment mechanisms that shows that sometimes these cannot clear markets in anything less than exponential time.

After the romp through computational methods for finding equlibria, Christos moved on to Sex (that should increase my google visibility!).  Why do creatures have sex?  What is the advantage?  Biologists have looked at this problem but don’t have a really satisfactory solution to it.  Christos was motivated by his experience with computational methods for optimization:

Why do Simulated Annealing algorithms work, while Genetic Algorithms don’t?

Audible gasps came from the sizable group of GA researchers in the audience.  I’ll remind readers this is Christos’ view not mine (though I certainly believe that anyone doing work on GAs for the traveling salesman problem, as an example, who believes they are helping solve TSPs is misguided, but I have seen applications where GAs seem the right approach).

Christos’ fundamental point is that perhaps selection under recombination does not maximize fitness.  Instead, it favors “mixability” (or genetic tolerance).  And this mixability accelerates speciation, and accelerates evolution.   There is a paper in the Proceedings of the National Academy of Science that explains this all in more detail.

Christos’ home page has lots of the papers that underlie the talk (see, particularly, the “computing equilibria” and “biology” subsections).  Highly recommended!

I am in Bonn, Germany for the EURO Conference. Tons of people here (2200+) but the organizers seem to be coping very well. Last night was a nice reception in a beer garden nearby. It has been a long time since I was at a conference with unlimited free beers. This morning was a little … slow.

The opening plenary session today included the announcement and talks of this year’s EURO Gold Medal winners: Jacques Benders, Eindhoven, and Frank Kelly, University of Cambridge. I missed most of the session (thanks, Graham Rand, for letting me know the winners), and I am really kicking myself for missing Benders’ talk: his work has a huge influence on my own current research. Benders’ Decomposition is one of the fundamental tools of operations research. Recently, people like John Hooker have breathed new life into the approach by introducing logical Benders’ decomposition (or combinatorial Benders decomposition).

Benders’ decomposition works as follows: take an optimization problem with two types of variables, x and y. First, solve the problem using only constraints that include just the x variables (this is the master problem). Give a solution x* to the master problem, now solve for the optimal y (the subproblem). We now have a candidate solution (x*,y*). The key step is to now generate a constraint on the x variables that says: “If you want a better x, it has to satisfy this constraint”. In classical Benders decomposition, that constraint is formed from the dual solution to the subproblem. In logical Benders, techniques such as constraint programming can be used to identify appropriate constraints. This iterates until the master problem (with the additional constraints) shows there is no better x than the ones already generated.

This approach can be radically faster than solving the overall (x,y) problem as one monolithic optimization. As the introduction to a reprinting of Benders’ original work says:

The real importance of the introduced algorithm is more evident today than ever before. It has had a profound seminal influence on the development of new generation of algorithms that enable us to solve ever larger and more complex from a wide spectrum.

I did get to the last half of Kelly’s talk. This was a very nice talk on modeling network routing, including issues of fairness. This happens a lot in internet routing of course, where routers try to figure out where things should go, and try to let everything through (eventually at least!). It would be rather annoying if one line through a router had a permanent “stop sign” while other traffic was sent through. Frank is famous enough to have a Wikipedia page.

Congrats to both Jacques and Frank, and no more missing plenary sessions for me!