Speaker: Christos Papadimitriou University of California,Berkeley
Time: 2011-04-22 14:00-2011-04-22 15:30
Venue: FIT1-222
Download: Click!

Abstract:

The advent of the Internet brought parallel paradigm shifts to both Economics and Computer Science. Computer scientists realized that large-scale performing systems can emerge from the interaction of selfish agents, while economists saw that the default platforms of economic transactions are computational and interconnected. Algorithmic Economics (or Algorithmic Game Theory) is a subdiscipline that emerged from this turmoil, revisiting some of the most important problems in Economics and Game Theory from a computational and network perspective, but also bringing in new computational insights and models. In this series of seminars I will survey some of the major results and challenges in this fascinating field. In the first seminar (April 21) I will talk about the complexity of computing equilibria: The intractability of Nash equilibrium, tractable cases, and the complexity class CLS. In the second talk (April 22) I will discuss briefly the price of anarchy, and focus on recent work on an emerging swarm of problems, on algorithms for optimal Bayesian auctions. No prior knowledge of Game Theory is required.

Short Bio:

Christos H. Papadimitriou is C. Lester Hogan Professor of Computer Science at UC Berkeley. Before joining Berkeley in 1996 he taught at Harvard, MIT, Athens Polytechnic, Stanford, and UCSD. He has written five textbooks and many articles on algorithms and complexity, and their applications to optimization, databases, AI, economics, evolution, and the Internet. He holds a PhD from Princeton, and honorary doctorates from ETH (Zurich), the Universities of Macedonia (Thessaloniki), Athens, Cyprus, and Patras. He is a member of the National Academy of Sciences, the American Academy of Arts and Sciences and of the National Academy of Engineering, and a fellow of the ACM. His second novel "Logicomix" has been translated in over 20 languages.