<html><head><style type='text/css'>p { margin: 0; }</style></head><body><div style='font-family: arial,helvetica,sans-serif; font-size: 12pt; color: #000000'><b>Porting the Computer Science Toolbox to Game Theory and Economics</b>
<br>
<b><a href="http://theory.stanford.edu/%7Etim/">Tim Roughgarden</a></b>, <a href="http://www.stanford.edu/">Stanford University</a>
<br>
<b><a name="2012-02-08">Wednesday, February 8, 2012</a>, 4:30 PM - 5:30 PM</b>
<br><a href="http://www.princeton.edu/%7Epumap/index.html?id=167">Computer Science</a> Small Auditorium (Room 105)
<br><br>Theoretical computer science has brought new ideas and techniques to
game and economic theory. A primary signature of the computer science
approach is {em approximation} --- the idea of building credibility for a
proposed solution by proving that its performance is always within a
small factor of an ideal (and typically unimplementable) solution. We
explain two of our recent contributions in this area, one motivated by
networks and one by auctions.<br><br><p>
We first discuss the "price of anarchy": how well does decentralized (or
"selfish") behavior approximates centralized optimization? This
concept has been analyzed in many applications, including network
routing, resource allocation, network formation, health care, and even
models of basketball. We highlight a new theory of robust price of
anarchy bounds, which apply even to systems that are not in equilibrium.
</p><p>
Second, we consider auction design: for example, what selling procedure
should be used to maximize the revenue of a seller? On the analysis
side, we highlight a new framework that explicitly connects average-case
(i.e., Bayesian) analysis, the dominant paradigm in economics, with the
worst-case analysis approach common in computer science. On the design
side, we provide a distribution-independent auction that performs, for
a wide class of input distributions, almost as well as the
distribution-specific optimal auction.
</p>
<br>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, a 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.
<br><br><div><span name="x"></span><br><br><br><br><span name="x"></span><br></div><br></div></body></html>