{"id":748,"date":"2009-07-07T07:13:07","date_gmt":"2009-07-07T11:13:07","guid":{"rendered":"http:\/\/mat.tepper.cmu.edu\/blog\/?p=748"},"modified":"2009-07-07T07:13:07","modified_gmt":"2009-07-07T11:13:07","slug":"ifors-distinguished-lecturer-christos-papadimitriou","status":"publish","type":"post","link":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/2009\/07\/07\/ifors-distinguished-lecturer-christos-papadimitriou\/","title":{"rendered":"IFORS Distinguished Lecturer Christos Papadimitriou"},"content":{"rendered":"

\"bonn09Christos Papadimitriou of UC Berkeley was the IFORS<\/a> Distinguished Lecturer at the EURO<\/a> 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).\u00a0\u00a0 The starting point for his lecture was to note that the internet has greatly increased interest in multi-player games.\u00a0\u00a0 Christos described the Internet as the first computational artifact that was never truly designed:\u00a0 it was formed by the selfish behavior of millions of agents.\u00a0 To quote Scott Shenker<\/a>:<\/p>\n

The Internet is an equilibrium, we just need to identify the game<\/p><\/blockquote>\n

But how do players in a game find an equilibrium?\u00a0 For simple zero-sum games, linear programming can find an equilibrium.\u00a0 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).<\/p>\n

This issue of finding equilibria often comes up in coffee conversations with my colleagues.\u00a0 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.\u00a0 As Christos quoted:<\/p>\n

if your laptop can’t find it, then neither can the market<\/p><\/blockquote>\n

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.\u00a0 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.\u00a0\u00a0 In fact, Christos has a theorem on price adjustment mechanisms that shows that sometimes these cannot clear markets in anything less than exponential time.<\/p>\n

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

Why do Simulated Annealing algorithms work, while Genetic Algorithms don’t?<\/p><\/blockquote>\n

Audible gasps came from the sizable group of GA researchers in the audience.\u00a0 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).<\/p>\n

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

Christos’ home page<\/a> has lots of the papers that underlie the talk (see, particularly, the “computing equilibria” and “biology” subsections).\u00a0 Highly recommended!<\/p>\n","protected":false},"excerpt":{"rendered":"

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).\u00a0\u00a0 The starting point for his lecture … Continue reading “IFORS Distinguished Lecturer Christos Papadimitriou”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[13,40,44],"tags":[],"class_list":["post-748","post","type-post","status-publish","format-standard","hentry","category-conferences","category-people","category-prizes"],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/748","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/comments?post=748"}],"version-history":[{"count":0,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/748\/revisions"}],"wp:attachment":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/media?parent=748"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/categories?post=748"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/tags?post=748"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}