Selfish Routing and the Price of Anarchy

Speaker: Dr. Tim Roughgarden, Stanford University
Abstract: The "price of anarchy"---the worst-case ratio between the social objective function value of an equilibrium and that of a social optimum---is an increasingly popular measure of the extent to which competition approximates cooperation. It is a rendezvous of the idea of an equilibrium, an idea fundamental to game theory, and the concept of approximation, which is ubiquitous in optimization and theoretical computer science. In this talk, I will survey results on the price of anarchy of "selfish routing"---a mathematical model of how noncooperative individuals route traffic in a congested network.
Biography: Tim Roughgarden received his BS and MS degrees from Stanford University in 1997 and 1998, and his PhD in from Cornell University in 2002. He joined Stanford's computer science faculty in September 2004. Dr. Roughgarden's research interests lie on the interface of combinatorial optimization and game theory. For his PhD work, he received SIGACT's Danny Lewin Best Student Paper Award, the Mathematical Programming Society's Tucker Prize, INFORM's Optimization Prize for Young Researchers, and an honorable mention for the ACM Doctoral Dissertation Award.
Presented On: Friday, April 22, 2005
Videotape: <Not available.>