Potential Functions and the Inefficiency of Equilibria

Date: 
Friday, March 2, 2012 - 4:21pm

UCSB COMPUTER SCIENCE AND CENTER FOR GEOMETRIC COMPUTING PRESENTS:

Tuesday, March 6, 2012
10:00 – 11:00 AM
Computer Science Conference Room, Harold Frank Hall Rm. 1132

HOST: Subhash Suri

SPEAKER: Tim Roughgarden
Computer Science, Stanford University

Title: Potential Functions and the Inefficiency of Equilibria

Abstract:

We survey some methods for proving worst-case bounds on the inefficiency
of equilibria, including potential functions and variational inequalities.

Bio:

Tim Roughgarden received his Ph.D. from Cornell University in 2002 and
joined the Stanford CS department in 2004, where he is currently an
associate professor. His research interests are in theoretical computer
science, especially its interfaces with game theory and networks. He
wrote the book “Selfish Routing and the Price of Anarchy” (MIT Press,
2005) and co-edited the book “Algorithmic Game Theory”, with Nisan,
Tardos, and Vazirani (Cambridge, 2007). His significant awards include
the 2002 ACM Doctoral Dissertation Award (Honorable Mention), the 2003
Tucker Prize,the 2003 INFORMS Optimization Prize for Young Researchers,
speaking at the 2006 International Congress of Mathematicians, 2007
PECASE Award, the 2008 Shapley Lectureship of the Game Theory Society,
and the 2009 ACM Grace Murray Hopper Award. He’s currently developing a
free online course on the design and analysis of algorithms, which has
over 50,000 students.