close
Jump to content

Tim Roughgarden

From Wikipedia, the free encyclopedia

Timothy Roughgarden
BERJAYA
Born
Timothy Avelin Roughgarden

(1975-07-20) July 20, 1975 (age 51)
Education
Known forContributions to algorithms and game theory in the context of computer science
Awards
Scientific career
FieldsComputer science, Game theory
Institutions
ThesisSelfish routing (2002)
Éva Tardos
Websitetimroughgarden.org

Timothy Avelin Roughgarden (born July 20, 1975) is an American computer scientist whose research spans theoretical computer science, algorithmic game theory, mechanism design, and the economics of blockchain systems. He is a professor in the School of Mathematics at the Institute for Advanced Study and a professor of computer science at Columbia University. He is also the founding head of research at a16z crypto. He previously was a professor at Stanford University.

Education

[edit]

Roughgarden received a Bachelor of Science degree in applied mathematics from Stanford University in 1997 and a Master of Science degree in computer science from Stanford in 1998.[1] He received a Master of Science degree in mathematics and a PhD in computer science from Cornell University in 2002.[2] His doctoral dissertation was titled Selfish Routing.[3]

Academic career

[edit]

After completing his doctorate, Roughgarden was a postdoctoral researcher at Cornell University from 2002 to 2003 and at the University of California, Berkeley from 2003 to 2004.[4] He joined Stanford University in 2004 as an assistant professor of computer science, with a courtesy appointment in management science and engineering. He became an associate professor in 2011 and a professor in 2017.[5]

From 2017 to 2018, Roughgarden was a visiting professor in the Department of Mathematics at the London School of Economics.[6] He joined Columbia University as a professor of computer science in 2019.[1] In 2022, he became founding head of research at a16z crypto.[7]

In July, 2026, Roughgarden joined the Institute for Advanced Study as a professor in its School of Mathematics.[8]

Research

[edit]

Roughgarden's research is in theoretical computer science, algorithmic game theory, and the application of algorithmic methods to economic systems. His work has examined strategic behavior in networks, markets, and distributed systems, with particular emphasis on the efficiency of equilibria and the design of mechanisms and algorithms.[9]

In his early work on selfish routing and congestion games, Roughgarden studied how individual route choices affect overall network performance.[10] With Éva Tardos, he co-authored "How Bad Is Selfish Routing?", which analyzed the inefficiency that can arise when network users act independently.[10] This work used the concept of the price of anarchy to compare outcomes at equilibrium with socially optimal outcomes.[10] He later developed a smoothness-based approach to deriving price-of-anarchy bounds, including in "Intrinsic Robustness of the Price of Anarchy".[11]

Roughgarden has also worked in algorithmic mechanism design, including auction theory, cost-sharing mechanisms, and the design of markets with incomplete information.[12] His publications have addressed optimal and approximately optimal auctions, prior-independent mechanisms, combinatorial auctions, and fair division.[13][14][15] With Jason D. Hartline, he studied optimal mechanism design and auction design;[16][17] later work with other collaborators examined revenue maximization from samples, contracts, and the computational aspects of mechanism design.[18][19]

Another area of his research concerns alternatives to traditional worst-case analysis in algorithms.[20] His work in this area has included data-driven algorithm design, learning-based approaches to choosing algorithms and mechanisms, and distribution-free models of networks and social graphs.[21][22][23] He edited the volume Beyond the Worst-Case Analysis of Algorithms, which surveys analytical frameworks that incorporate input distributions, resource augmentation, and other approaches beyond standard worst-case guarantees.[24]

Roughgarden's more recent research has addressed the economics and design of blockchain systems.[9] He has studied transaction-fee mechanisms, permissionless consensus, mining pools, and automated market makers used in decentralized finance.[25][26][27][28] His work on transaction-fee mechanism design considered incentive and implementation issues in blockchain protocols,[25] while later work with collaborators examined automated market making, arbitrage, and loss-versus-rebalancing.[28]

Teaching

[edit]

Roughgarden has developed teaching materials on algorithms, algorithmic game theory, mechanism design, and related areas of theoretical computer science.[29] Since 2011, he has taught open online courses on algorithms through Coursera, which were later organized as a four-course Algorithms specialization.[29][30][31] He has also made lecture notes and course videos available online, covering topics including algorithms, game theory, mechanism design, and blockchain economics.[29]

Awards and honors

[edit]

Books

[edit]
  • Selfish Routing and the Price of Anarchy (MIT Press, 2005)
  • Algorithmic Game Theory (co-editor, with Noam Nisan, Éva Tardos, and Vijay V. Vazirani; Cambridge University Press, 2007)
  • Communication Complexity (for Algorithm Designers) (2016)
  • Twenty Lectures on Algorithmic Game Theory (Cambridge University Press, 2016)
  • Algorithms Illuminated series (2017–2022)
  • Beyond the Worst-Case Analysis of Algorithms (editor; Cambridge University Press, 2021)
  • Complexity Theory, Game Theory, and Economics: The Barbados Lectures (Now Publishers, 2020)

References

[edit]
  1. 1 2 "Tim Roughgarden and David Knowles Join the Department". Columbia University. 2019.
  2. ↑ "Cornellians at the International Congress of Mathematicians". Department of Mathematics. Cornell University.
  3. ↑ Roughgarden, Tim (May 2002). Selfish Routing (PDF) (PhD thesis thesis). Cornell University.
  4. 1 2 "Tim Roughgarden". Columbia Engineering. Columbia University. Retrieved July 1, 2026.
  5. ↑ "Four Stanford faculty honored with Guggenheim Fellowships". Stanford Report. Stanford University. April 13, 2017.
  6. ↑ "News Archive September 2016–August 2017" (PDF). Department of Mathematics. London School of Economics and Political Science.
  7. ↑ "Tim Roughgarden". a16z crypto.
  8. ↑ "Algorithmic Game Theorist Tim Roughgarden Appointed to IAS Faculty". Institute for Advanced Study. July 1, 2026.
  9. 1 2 Young, Bernadette Ocampo (January 26, 2024). "Game Theory, Blockchain Expert Tim Roughgarden Elected as ACM Fellow". Columbia Engineering. Columbia University.
  10. 1 2 3 Roughgarden, Tim; Tardos, Éva (March 2002). "How Bad Is Selfish Routing?". Journal of the ACM. 49 (2): 236–259. doi:10.1145/506147.506153.
  11. ↑ Roughgarden, Tim (November 2, 2015). "Intrinsic Robustness of the Price of Anarchy". Journal of the ACM. 62 (5): 1–42. doi:10.1145/2806883.
  12. ↑ Roughgarden, Tim; Sundararajan, Mukund (June 2009). "Quantifying Inefficiency in Cost-Sharing Mechanisms". Journal of the ACM. 56 (4): Article 23.
  13. ↑ Dughmi, Shaddin; Roughgarden, Tim; Yan, Qiqi (September 2016). "Optimal Mechanisms for Combinatorial Auctions and Combinatorial Public Projects via Convex Rounding". Journal of the ACM. 63 (4): Article 30. doi:10.1145/2908735.
  14. ↑ Dhangwatnotai, Peerapong; Roughgarden, Tim; Yan, Qiqi (2015). "Revenue Maximization with a Single Sample". Games and Economic Behavior. 91: 318–333. doi:10.1016/j.geb.2014.03.011.
  15. ↑ Plaut, Benjamin; Roughgarden, Tim (2020). "Almost Envy-Freeness with General Valuations". SIAM Journal on Discrete Mathematics. 34 (2): 1039–1068. doi:10.1137/19M124397X.
  16. ↑ Hartline, Jason D.; Roughgarden, Tim (2008). "Optimal Mechanism Design and Money Burning". Proceedings of the 40th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery. pp. 75–84. doi:10.1145/1374376.1374390.
  17. ↑ Hartline, Jason D.; Roughgarden, Tim (2009). "Simple versus Optimal Mechanisms". Proceedings of the 10th ACM Conference on Electronic Commerce. Association for Computing Machinery. pp. 225–234. doi:10.1145/1566374.1566407.
  18. ↑ Cole, Richard; Roughgarden, Tim (2014). "The Sample Complexity of Revenue Maximization". Proceedings of the 46th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery. pp. 243–252. doi:10.1145/2591796.2591867.
  19. ↑ Dütting, Paul; Roughgarden, Tim; Talgam-Cohen, Inbal (2021). "The Complexity of Contracts". SIAM Journal on Computing. 50 (1): 211–254. doi:10.1137/20M132153X.
  20. ↑ Roughgarden, Tim (March 2019). "Beyond Worst-Case Analysis". Communications of the ACM. 62 (3): 88–96. doi:10.1145/3232535.
  21. ↑ Gupta, Rishi; Roughgarden, Tim (June 2020). "Data-Driven Algorithm Design". Communications of the ACM. 63 (6): 87–94. doi:10.1145/3394625.
  22. ↑ Gupta, Rishi; Roughgarden, Tim (2017). "A PAC Approach to Application-Specific Algorithm Selection". SIAM Journal on Computing. 46 (3): 992–1017. doi:10.1137/15M1050276.
  23. ↑ Fox, Jacob; Roughgarden, Tim; Seshadhri, C.; Wei, Fan; Wein, Nicole (2020). "Finding Cliques in Social Networks: A New Distribution-Free Model". SIAM Journal on Computing. 49 (2): 448–464. doi:10.1137/18M1210459.
  24. ↑ Roughgarden, Tim, ed. (2021). Beyond the Worst-Case Analysis of Algorithms. Cambridge University Press.
  25. 1 2 Roughgarden, Tim (August 2024). "Transaction Fee Mechanism Design". Journal of the ACM. 71 (4): 1–25. doi:10.1145/3674143.
  26. ↑ Lewis-Pye, Andrew; Roughgarden, Tim (2023). "Byzantine Generals in the Permissionless Setting". Financial Cryptography and Data Security. pp. 21–37. doi:10.1007/978-3-031-47754-6_2.
  27. ↑ Roughgarden, Tim; Shikhelman, Clara (2021). "Ignore the Extra Zeroes: Variance-Optimal Mining Pools". Financial Cryptography and Data Security. Springer. pp. 233–249. doi:10.1007/978-3-662-64331-0_12.
  28. 1 2 Milionis, Jason; Moallemi, Ciamac C.; Roughgarden, Tim; Zhang, Anthony Lee (2022). "Automated Market Making and Loss-Versus-Rebalancing". arXiv:2208.06046 [q-fin.MF].
  29. 1 2 3 Neumann, Stefan (June 2025). "Bringing Theoretical Computer Science to YouTube: A Conversation with Tim Roughgarden". Bulletin of the European Association for Theoretical Computer Science (146). Retrieved August 4, 2026.
  30. ↑ Warne, Henrik (February 3, 2015). "Course Review: Algorithms, Design and Analysis, Part 1 offered by Stanford on Coursera". Class Central. Retrieved August 4, 2026.
  31. ↑ "Online Course: Algorithms from Stanford University". Class Central. Retrieved August 4, 2026.
  32. ↑ "Danny Lewin Best Student Paper Award". ACM SIGACT.
  33. ↑ "Tim Roughgarden". Association for Computing Machinery.
  34. ↑ "2003 Tucker Prize Citation". Mathematical Programming Society.
  35. ↑ "Tim Roughgarden". INFORMS.
  36. ↑ "ICM Plenary & Invited Speakers". International Mathematical Union.
  37. ↑ "2006 Annual Report" (PDF). Alfred P. Sloan Foundation. p. 4.
  38. ↑ "White House Announces 2007 Awards for Early Career Scientists and Engineers". The White House. December 19, 2008.
  39. ↑ "ACM Awards Recognize Computer Scientists for Innovations That Have Real-World Impact". Association for Computing Machinery. March 30, 2010.
  40. ↑ "Gödel Prize". ACM SIGACT.
  41. ↑ "Vincent Conitzer Receives Social Choice and Welfare Prize". Duke University. June 19, 2014.
  42. ↑ "5th Congress 2016, Maastricht". Game Theory Society.
  43. ↑ Myers, Andrew (December 6, 2017). "Tau Beta Pi engineering honor society debuts its "Teaching Honor Roll"". Stanford University.
  44. ↑ "Tim Roughgarden". John Simon Guggenheim Memorial Foundation.
  45. ↑ "Tim Roughgarden". INFORMS.
  46. ↑ "Fellows". Game Theory Society.
  47. ↑ "FOCS Test of Time Award". IEEE Computer Society Technical Committee on Mathematical Foundations of Computing.
  48. ↑ "Economic Theory Fellows". Society for the Advancement of Economic Theory.
  49. ↑ "2023 ACM Fellows Celebrated for Contributions to Computing That Underpin Our Modern World". Association for Computing Machinery. January 24, 2024.
  50. ↑ "2026 New Member List". American Academy of Arts and Sciences.
[edit]
Retrieved from "https://en.wikipedia.org/w/index.php?title=Tim_Roughgarden&oldid=1367640988"