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!

## { 8 } Comments

Thank you for blogging about this talk. I also want to let you know that I enjoyed your talk on sports scheduling. It was really entertaining!

“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”Can you write a post about that? My experience with GAs and TSP was a homework exercise (solve Symmetric TSPs of ~300 cities using GAs, mutation, crossover and stuff).

Mike, thanks for posting all these info. I am not sure that I agree with Papadimitriou point of view on SA (and genetics)

but I want to read more carefully his papers.

Adamo: I might write a longer post, but my point is that Concorde (the TSP solver at Georgia Tech) can solve to provable optimality TSPs of size 300 in about 3 seconds (on the NEOS server). Lin-Kernighen is a really fast heuristic for finding really good solutions even more quickly. If you want to say you are “helping solve TSPs”, then that is is your comparison set. And GAs (that I have seen) are no where near close to competitive for the pure TSP.

Lin-Kernighan is the reason that I ask the question. Reaging page 2 (499 in the paper) the brief description of the algorithm reminded me of a genetic algorithm. But can one consider L-K to be a GA? (Holland’s book was published in 1975 and L-K in 1973).

Thank you.

Well, if you want to see a GA in L-K, you are welcome to. I don’t see it (it looks like a local improvement heuristic to me), but we all use different glasses to see the world.

Checking the literature a bit more, I see from http://users.informatik.uni-halle.de/~jaegerg/publ/halifax.pdf that Nguyen has had some records with a “parallel hybrid genetic algorithm” http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=4067083 that combines GA with L-K so I was wrong in disparaging all GA for TSP. I have just received a few too many papers to review where people have applied GAs to small (under 1000 node) TSPs or even tiny (a thorough study of how things work on 30 node TSPs) without seeming to realize that this is not the game to be playing (if your goal is to improve solving of TSPs).

Ha! Score one for your Google visibility. An algorithm for sex…hm…seems ironic.

Eric wrote:

> An algorithm for sex…hm…seems ironic.

Warning: juvenile humor below.

A number of Unix distributions once had a man page for it (warning: content is a bit racy, as if you wouldn’t have guessed).

That seems to not be part of standard distributions so much these days, as *nix tries to go “corporate”.

So now if you type the command ‘man sex’, the response is “No manual entry for sex”.

Somebody on one of the Linux mailing lists I’m on had a signature that included a sequence of Unix commands piped together that was all double entendre. I can’t lay my hands on it just now, but I think it started with ‘date’, moved on to ‘talk’, ‘touch’, ‘unzip’, ‘strip’, and ‘mount’ and culminated with ‘fsck’, which is by now a standard Unix euphemism for the real interjection. At the end was ‘sleep’.

Now back to your regularly scheduled OR blog…

## { 5 } Trackbacks

[…] highly recommend the post by Mike about Christos talk – including the details on Christos question Why do Simulated Annealing algorithms work, […]

[…] 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 […]

[…] Of course a number of people are searching for “sex market” or some such, and hit a post from my past entries that includes those words. In fact, now that I have included that phrase here, they may end up on this page. If so, the […]

[…] really think that 300 cities is a good lower bound for exact work on the TSP (see Concorde, and the discussion given in a previous post). If someone has a bacterial technique that might work on 10 cities, how will it work on a system […]

[…] If your laptop cannot find the solution, neither can the market. […]

## Share Your Views!