Tim Roughgarden

Assistant professor in the Computer Science and (by courtesy) Management Science and Engineering Departments at Stanford University.
Research interests: Algorithms, Network and Combinatorial Optimization, Game Theory.

News:

My book Algorithmic Game Theory, co-edited with Noam Nisan, Eva Tardos, and Vijay Vazirani, will be published by Cambridge University Press in October 2007.
Thanks to our progressive-minded publisher, you can read the entire book online by clicking here (username=agt1user, password=camb2agt).
Errata from the first printing.

Teaching (2007-2008)

Winter '08: CS161, Design and Analysis of Algorithms
Winter '08: CS369, Advanced Graph Algorithms
Fall '07: CS364B, Foundations of Sponsored Search
Archived graduate courses

Local Theory Events

Bay Algorithmic Game Theory Symposium (BAGT), Google, April 11, 2008.
Bay Area Theory Symposium (BATS), Microsoft, November 30, 2007.
AFLB (i.e., the Stanford CS Theory Seminar), roughly every other Tuesday at 4 PM.

Some Recent Papers

J. D. Hartline and T. Roughgarden, Optimal Mechanism Design and Money Burning, STOC '08.
S. Dobzinski, A. Mehta, T. Roughgarden, and M. Sundararajan, Is Shapley Cost Sharing Optimal?, SAGT '08.
S. Chawla and T. Roughgarden, Bertrand Competition in Networks, SAGT '08.
H. Chen, T. Roughgarden, and G. Valiant, Designing Networks with Good Equilibria, SODA '08.
R. Krauthgamer and T. Roughgarden, Metric Clustering via Consistent Labeling, SODA '08.

Selected Older Publications (Full chronological list)

A. Mehta, T. Roughgarden, and M. Sundararajan, Beyond Moulin Mechanisms, full version of EC '07 paper.
T. Roughgarden and M. Sundararajan, Quantifying Inefficiency in Cost-Sharing Mechanisms, full version of STOC '06 paper.
C. H. Papadimitriou and T. Roughgarden, Computing Correlated Equilibria in Multi-Player Games, JACM to appear.
A. Gupta, A. Kumar, M. Pal, and T. Roughgarden, Approximation Via Cost Sharing, JACM '07.
T. Roughgarden. Selfish Routing and the Price of Anarchy, MIT Press, 2005.
T. Roughgarden, The Price of Anarchy is Independent of the Network Topology, JCSS '03.
T. Roughgarden, Designing Networks for Selfish Users is Hard, JCSS '06.
T. Roughgarden and E. Tardos, How Bad is Selfish Routing?, JACM '02.

Music

Back in the Stone Age I DJed at KZSU 90.1 FM.
Top two reasons to live in the Bay Area: #1; #2.

Tim Roughgarden

Stanford University

Computer Science Department

462 Gates Building

353 Serra Mall

Stanford, CA 94305

P:(650)724-9147

F:(650)725-4671

"first name"@cs.stanford.edu

Admin:

Wendy Cardamone

Stanford University

Computer Science Department

461 Gates Building

353 Serra Mall

Stanford, CA 94305

P:(650)725-2340

F:(650)725-4671

"first name + first letter of last name"@cs.stanford.edu