Tim Roughgarden

Last updated
Timothy Avelin Roughgarden
Born(1975-07-20)July 20, 1975
Alma mater
Known forContributions to Selfish Routing in the context of Computer Science
Scientific career
Fields Computer Science, Game Theory
Thesis Selfish routing  (2002)
Doctoral advisor Éva Tardos
Website http://timroughgarden.org/

Timothy Avelin Roughgarden is an American computer scientist and a professor of Computer Science at Columbia University. [1] Roughgarden's work deals primarily with game theoretic questions in computer science.


Roughgarden received his Ph.D. from Cornell University in 2002, under the supervision of Éva Tardos. [2] He did a postdoc at University of California, Berkeley in 2004. From 2004 to 2018, Roughgarden was a professor at the Computer Science department at Stanford University working on algorithms and game theory. Roughgarden teaches a four-part algorithms specialization on Coursera. [3]

He received the Danny Lewin award at STOC 2002 for the best student paper. He received the Presidential Early Career Award for Scientists and Engineers in 2007, [4] the Grace Murray Hopper Award in 2009, [5] and the Gödel Prize in 2012 for his work on routing traffic in large-scale communication networks to optimize performance of a congested network. [6] [7] He received a Guggenheim Fellowship in 2017 [8] [9] and the Kalai Prize in 2016.

Roughgarden is a co-editor of the 2016 textbook Algorithmic Game Theory, as well as the author of two chapters (Introduction to the Inefficiency of Equilibria and Routing Games). [10] [11]

Selected publications

Related Research Articles

The Gödel Prize is an annual prize for outstanding papers in the area of theoretical computer science, given jointly by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Interest Group on Algorithms and Computational Theory. The award is named in honor of Kurt Gödel. Gödel's connection to theoretical computer science is that he was the first to mention the "P versus NP" question, in a 1956 letter to John von Neumann in which Gödel asked whether a certain NP-complete problem could be solved in quadratic or linear time.

<span class="mw-page-title-main">Daphne Koller</span> Israeli-American computer scientist

Daphne Koller is an Israeli-American computer scientist. She was a professor in the department of computer science at Stanford University and a MacArthur Foundation fellowship recipient. She is one of the founders of Coursera, an online education platform. Her general research area is artificial intelligence and its applications in the biomedical sciences. Koller was featured in a 2004 article by MIT Technology Review titled "10 Emerging Technologies That Will Change Your World" concerning the topic of Bayesian machine learning.

<span class="mw-page-title-main">Éva Tardos</span> Hungarian mathematician

Éva Tardos is a Hungarian mathematician and the Jacob Gould Schurman Professor of Computer Science at Cornell University.

<span class="mw-page-title-main">Christos Papadimitriou</span> American computer scientist

Christos Harilaos Papadimitriou is a Greek theoretical computer scientist and the Donovan Family Professor of Computer Science at Columbia University.

<span class="mw-page-title-main">Knuth Prize</span>

The Donald E. Knuth Prize is a prize for outstanding contributions to the foundations of computer science, named after the American computer scientist Donald E. Knuth.

<span class="mw-page-title-main">Dan Boneh</span>

Dan Boneh is an Israeli-American professor in applied cryptography and computer security at Stanford University.

Omer Reingold is an Israeli computer scientist. He is the Rajeev Motwani professor of Computer Science in the Computer Science Department at Stanford University and the director of the Simons Collaboration on the Theory of Algorithmic Fairness. He received the 2005 Grace Murray Hopper Award for his work in finding a deterministic logarithmic-space algorithm for st-connectivity in undirected graphs. He, along with Avi Wigderson and Salil Vadhan, won the Gödel Prize (2009) for their work on the zig-zag product. He became a Fellow of the Association for Computing Machinery in 2014 "For contributions to the study of pseudorandomness, derandomization, and cryptography."

Algorithmic mechanism design (AMD) lies at the intersection of economic game theory, optimization, and computer science. The prototypical problem in mechanism design is to design a system for multiple self-interested participants, such that the participants' self-interested actions at equilibrium lead to good system performance. Typical objectives studied include revenue maximization and social welfare maximization. Algorithmic mechanism design differs from classical economic mechanism design in several respects. It typically employs the analytic tools of theoretical computer science, such as worst case analysis and approximation ratios, in contrast to classical mechanism design in economics which often makes distributional assumptions about the agents. It also considers computational constraints to be of central importance: mechanisms that cannot be efficiently implemented in polynomial time are not considered to be viable solutions to a mechanism design problem. This often, for example, rules out the classic economic mechanism, the Vickrey–Clarke–Groves auction.

Algorithmic game theory (AGT) is an area in the intersection of game theory and computer science, with the objective of understanding and design of algorithms in strategic environments.

<span class="mw-page-title-main">Rajeev Motwani</span> Indian computer scientist (1962–2009)

Rajeev Motwani was an Indian American professor of Computer Science at Stanford University whose research focused on theoretical computer science. He was an early advisor and supporter of companies including Google and PayPal, and a special advisor to Sequoia Capital. He was a winner of the Gödel Prize in 2001.

Shang-Hua Teng is a Chinese-American computer scientist. He is the Seeley G. Mudd Professor of Computer Science and Mathematics at the University of Southern California. Previously, he was the chairman of the Computer Science Department at the Viterbi School of Engineering of the University of Southern California.

The Annual ACM Symposium on Theory of Computing (STOC) is an academic conference in the field of theoretical computer science. STOC has been organized annually since 1969, typically in May or June; the conference is sponsored by the Association for Computing Machinery special interest group SIGACT. Acceptance rate of STOC, averaged from 1970 to 2012, is 31%, with the rate of 29% in 2012.

<span class="mw-page-title-main">Gábor Tardos</span> Hungarian mathematician

Gábor Tardos is a Hungarian mathematician, currently a professor at Central European University and previously a Canada Research Chair at Simon Fraser University. He works mainly in combinatorics and computer science. He is the younger brother of Éva Tardos.

<span class="mw-page-title-main">Joseph S. B. Mitchell</span> American computer scientist and mathematician

Joseph S. B. Mitchell is an American computer scientist and mathematician. He is Distinguished Professor and Department Chair of Applied Mathematics and Statistics and Research Professor of Computer Science at Stony Brook University.

<span class="mw-page-title-main">Noam Nisan</span> Israeli computer scientist

Noam Nisan is an Israeli computer scientist, a professor of computer science at the Hebrew University of Jerusalem. He is known for his research in computational complexity theory and algorithmic game theory.

The Computer Science Department at Stanford University in Stanford, California, is a leading school for computer science. It was founded in 1965 and has consistently been ranked as one of the top computer science programs in the world. Its location in Silicon Valley makes it unique among computer science programs.

Michael Kearns is an American computer scientist, professor and National Center Chair at the University of Pennsylvania, the founding director of Penn's Singh Program in Networked & Social Systems Engineering (NETS), the founding director of Warren Center for Network and Data Sciences, and also holds secondary appointments in Penn's Wharton School and department of Economics. He is a leading researcher in computational learning theory and algorithmic game theory, and interested in machine learning, artificial intelligence, computational finance, algorithmic trading, computational social science and social networks. He previously led the Advisory and Research function in Morgan Stanley's Artificial Intelligence Center of Excellence team, and is currently an Amazon Scholar within Amazon Web Services.

<span class="mw-page-title-main">Mohammad Hajiaghayi</span> American computer scientist

Mohammad Taghi Hajiaghayi is a computer scientist known for his work in algorithms, game theory, social networks, network design, graph theory, and big data. He has over 200 publications with over 185 collaborators and 10 issued patents.

The Prize in Game Theory and Computer Science in Honour of Ehud Kalai is an award given by the Game Theory Society. The prize is awarded for outstanding articles at the interface of game theory and computer science. Following the eligibility rules of the Gödel Prize, preference is given to authors who are 45 years old or younger at the time of the award. It was established in 2008 by a donation from Yoav Shoham in honor of the Ehud Kalai's contributions in bridging these two fields.


  1. "Tim Roughgarden's Homepage". theory.stanford.edu. Retrieved 6 July 2015.
  2. "Tim Roughgarden's Profile - Stanford Profiles". soe.stanford.edu. Stanford University. Archived from the original on 17 July 2012. Retrieved 6 July 2015.
  3. "Algorithms Specialization". coursera.org. Coursera Inc. Retrieved 17 May 2017.
  4. "White House Announces 2007 Awards for Early Career Scientists and Engineers". The George W. Bush White House Archives (Press release). Washington, D.C.: Office of Science and Technology Policy. 19 December 2008. Retrieved 19 January 2020.
  5. "ACM Awards Recognize Computer Science Innovation". acm.org (Press release). Association for Computing Machinery. 31 March 2010. Retrieved 19 January 2020.
  6. "The Gödel Prize 2012 - Laudatio". European Association for Theoretical Computer Science. 2012. Retrieved 19 January 2020.
  7. "ACM Gödel Prize for Seminal Papers in Algorithmic Game Theory". Game Theory Society. 3 June 2012. Retrieved 19 January 2020.
  8. "Tim Roughgarden: Fellow, Awarded 2017". gf.org. John Simon Guggenheim Memorial Foundation. 2017. Retrieved 19 January 2020.
  9. Knowles, Hannah (17 April 2017). "Four professors named Guggenheim fellows". The Stanford Daily . Retrieved 19 January 2020.
  10. Hrsg., Nisan, Noam (24 September 2007). Algorithmic game theory. ISBN   978-0-521-87282-9. OCLC   870638977.
  11. "Tim Roughgarden's Books and Surveys". timroughgarden.org. Retrieved 2021-04-07.