Golden Recursion Inc. logoGolden Recursion Inc. logo
Advanced Search
Tim Roughgarden

Tim Roughgarden

Tim Roughgarden is an American computer scientist, a professor of computer science at Columbia University, and the author and editor of several works in game theory and computer science.

All edits

Edits on 22 Dec, 2022
Jen English"remove data"
Jen English edited on 22 Dec, 2022
Edits made to:
Infobox (-1 properties)
Infobox
Known for
Contributions to Selfish Routing in the context of Computer Science
Edits on 30 May, 2022
Smetanina Alena"Edit from table cell"
Smetanina Alena edited on 30 May, 2022
Edits made to:
Infobox (+1 properties)
Infobox
Birthplace
Edits on 4 May, 2022
Tsvirkun Dmytro Vitaliyovych
Tsvirkun Dmytro Vitaliyovych edited on 4 May, 2022
Edits made to:
Infobox (+1 properties)
Infobox
Known for
Contributions to Selfish Routing in the context of Computer Science
Edits on 7 Jan, 2022
Jen English
Jen English edited on 7 Jan, 2022
Edits made to:
Infobox (+1/-1 properties)
Infobox
Doctoral students
Doctoral students
Golden AI"Infobox creation from: Wikidata data enrichment"
Golden AI approved a suggestion from Golden's AI on 7 Jan, 2022
Edits made to:
Infobox (+1 properties)
Infobox
Doctoral students
Jen English
Jen English edited on 7 Jan, 2022
Edits made to:
Infobox (-1 properties)
Infobox
Doctoral students
Amy Tomlinson Gayle
Amy Tomlinson Gayle edited on 7 Jan, 2022
Edits made to:
Description (+24/-24 characters)
Article (+111/-122 characters)
Topic thumbnail

Tim Roughgarden

Tim Roughgarden is an American computer scientist, a Professorprofessor of Computercomputer Sciencescience at Columbia University, and the author and editor of several works in game theory and computer science.

Article

Tim Roughgarden is a professor of computer science at Columbia University, where he is a member of the Data Science Institute. Previously he was a professor of computer science at Stanford University, where he taught until 2018. His research interests include computer science and economics, and the connections between them both; and the design, analysis, applications, and limitations of algorithms; especiallyalgorithms—especially as those concepts are applied to networks, auctions, and cryptocurrencies.

...

Roughgarden studied at Stanford University from 1993 to 1998, where he earned his Bachelor of Science (BS) in Applied Mathematics in 1997, and earned his Masters in Computer Science in 1998. Following his masters, Roughgarden attended Cornell University where he studied for his PhD in computer science, from 1998 to 2002. At Cornell University, Roughgarden received his PhD under the supervision of Éva Tardos. After earning his PhD at Cornell University, Roughgarden did a postdoc at University of California, Berkeley.

...
Research
Research
...
Selfish routing
Selfish routing

Tim Roughgarden's research in selfish routing is related to game theory, algorithms, networks, and combinatorial optimization. This has included the application of game theory concepts to networking, in his Selfish Routing and the Price of Anarchy. This work offered a technical examination of selfish routing, a concept with implications not only in the electronic traffic found online and within the pathways of computer and communication networks, but also in the world of travel and moving people. And he quantifies the price of anarchy - theanarchy—the worst-possible loss of social welfare from selfish routing - androuting—and also discusses several methods for improving the price of anarchy with centralized control.

...
Auction and mechanism design
Auction and mechanism design
...
Cryptocurrency
Cryptocurrency
Edits on 7 Jan, 2022
Golden AI"Infobox creation from: Wikidata data enrichment"
Golden AI approved a suggestion from Golden's AI on 7 Jan, 2022
Edits made to:
Infobox (+1 properties)
Infobox
Aleksander Holm
Aleksander Holm edited on 7 Jan, 2022
Edits made to:
Infobox (+1/-1 properties)
Infobox
Aleksander Holm
Aleksander Holm edited on 7 Jan, 2022
Edits made to:
Timeline (+4 events) (+371 characters)
Article (+24 rows) (+48 cells) (+2 images) (+5434 characters)
Table (+3 rows) (+11 cells) (+672 characters)
Table (+148 rows) (+592 cells) (+20624 characters)
Article
Tim Roughgarden teaching at Stanford University.
...

In research, Roughgarden's interests include the connections between computer science and economics; and the design, analysis, application, and limitation of algorithms. According to Google Scholar, in early 2022, Roughgarden's research and papers had been cited approximately 21714 times, while his work had been cited around 8245 times in the past five years. In 2007, he received the Presidential Early Career Award for Scientists and Engineers.

...

Textbooks

Title
Publication date

Algorithmic Game Theory (editor)

2007

Algorithms Illuminated: Part 1: The Basics

2017

Algorithms Illuminated: Part 2: Graph Algorithms and Data Structures

2018

Algorithms Illuminated: Part 3: Greedy Algorithms and Dynamic Programming

2019

Algorithms Illuminated: Part 4: Algorithms for NP-Hard Problems

2020

Monographs

Title
Publication

"Communication Complexity (for Algorithm Designers)"

Foundations and Trends in Theoretical Computer Science, 2016

"Complexity Theory, Game Theory, and Economics (The Barbados Lectures)"

Foundations and Trends in Theoretical Computer Science, 2020

Selfish Routing and the Price of Anarchy

MIT Press, 2005

...

Tim Roughgarden's research in selfish routing is related to game theory, algorithms, networks, and combinatorial optimization. This has included the application of game theory concepts to networking, in his Selfish Routing and the Price of Anarchy. This work offered a technical examination of selfish routing, a concept with implications not only in the electronic traffic found online and within the pathways of computer and communication networks, but also in the world of travel and moving people. And he quantifies the price of anarchy - the worst-possible loss of social welfare from selfish routing - and also discusses several methods for improving the price of anarchy with centralized control.

Cover image of Tim Roughgarden's Selfish Routing and the Price of Anarchy.

He further describes two important examples that motivate the problems that follow. The first, Pigou's Example, demonstrates that selfish behavior need not generate a socially optimal outcome. While the second, Braess's Paradox, offers an example that network improvements can degrade network performance. From this Roughgarden develops techniques for quantifying anarchy. And he describes Stackelberg routing, which improves the price of anarchy using a modest degree of central control.

In his review of Roughgarden's Selfish Routing and the Price of Anarchy for the American Scientist, Brian Hayes remarked that "'Selfish routing' is the process of choosing a path based strictly on one's own interests, without regard for how that choice may affect anyone else; 'the price of anarchy' is the penalty that may have to be paid for this oblivious individualism." While he goes on to say that Roughgarden works to provide careful, quantitative estimates of how much people have to pay for the privilege of choosing routes without regard of the commonweal.

Hayes conceptualized the problem in terms of a daily commute. If an individual is offered two routes, one along Main Street and the other along a freeway, and Main Street is not crowded, but has stoplights and other distractions mean the trip takes an hour; while the freeway provides a higher speed limit and, if traffic is light, offers a half-hour commute, most individuals will choose the Freeway. Even when the freeway experiences heavy traffic that results in an hour long trip, same as Main Street, individuals choose the freeway as it promises a shorter trip at best, and at worst the same trip as Main Street. All while Main Street remains deserted and, perhaps, the better option.

Auction and mechanism design

As a specific case study of how computer science can influence economics, one of Roughgarden's research areas, he has cited the 2016 to 2017 Federal Communications Commission (FCC) auction to free up traditional broadcast licenses for broadband development. This auction offered a real-world application of game-theoretic algorithms.

In order to repurpose the wireless spectrum, the FCC initially hosted a reverse auction, which used a descending clock option algorithm in which each broadcaster was offered a buyout price that decreased over time in each round. If the broadcaster declined the offer, they would be exited from the auction and retain the original license without government compensation. If the broadcaster accepted the offer, they would move to the next round of the auction with an expectation that the government would buy back their license and pay the most recent lower offer.

According to Roughgarden, the problem with the auction format was a classic theory problem. The FCC needed to buy a certain number of licenses nationwide to be successful, but those that remained needed to have channels the government could reassign to them, or a classical mathematical repacking problem. The solution was an NP-complete problem, graph coloring, which assigns labels or colors to graph verticals to ensure no two adjacent verticals share a color. And the auction required solving thousands of graph coloring problems within a second, which could be solved with a satisfiability algorithm, which Roughgarden suggesting the best method for solving this being a reverse greedy algorithm, which delete edges from graphs.

In the forward auction, the FCC needed to sell broadband licenses, and relied on the computer science concept of proof of anarchy to prove that simple auctions can work well without complements, with Roughgarden noting that without techniques from computer science, the government could not have used the auction format they did.

Cryptocurrency

More recently, Roughgarden has worked on and conducted research into cryptocurrencies, which has included his work on the EIP-1559 proposal for the Ethereum cryptocurrency and blockchain. Instead of previous methods, where participants have bid to have each transaction included in the blockchain, EIP-1559 proposes to compute an appropriate price for each transaction internally. As well, the transaction fee is burnt instead of awarded to miners in an effort to counteract the naturally inflationary tokenomics of Ethereum. Roughgarden's research into the proposition included the close analysis of the game-theoretic properties of the new protocol, and includes what he sees as a growing appetite in the blockchain community for formal academic analysis of existing protocols.

Further, when asked what about what would be needed for cryptocurrency to flourish in the future, Roughgarden has suggested it would need to become easier for people to participate in blockchains without prior knowledge, similar to the way people use a mobile phone without needing to know the mechanics of how it transmits and receives a signal.

Surveys

Title
Publication

Algorithmic Game Theory

Published in Communications of the ACM, July 2010

Approximately Optimal Mechanism Design (with Inbal Talgam-Cohen)

Published in Annual Reviews of Economics in 2019

Approximately Optimal Mechanism Design: Motivation, Examples, and Lessons Learned

Published in SIGEcom Exchanges, 2014

Beyond Worst-Case Analysis

Published in Communications of the ACM, 2019

Computing Equilibria: A Computational Complexity Perspective

Invited by Economic Theory, 2010

Table

Title
Author
Link
Type
Date

Professor Tim Roughgarden Delivers Distinguished Lecture on How CS Solved One of the Hardest Government Auction Problems

Web

October 11, 2018

Tim Roughgarden: Gödel Prize Winner and Trailblazer from Algorithmic Game Theory to EIP-1559 -- Policy Punchline

Web

July 8, 2021

Tim Roughgarden: The Price of Anarchy - IT University of Copenhagen

Web

Table

Title
Date
Link

A Field Guide to Algorithm Design (Epilogue to the Algorithms Illuminated book series)

June 11, 2020

A Second Course in Algorirthms (Lecture 8: Linear Programming Duality --- Part 1)

January 29, 2016

A Second Course in Algorithms (Lecture 1: Course Goals and Introduction to Maximum Flow)

January 11, 2016

A Second Course in Algorithms (Lecture 10: The Minimax Theorem & Algorithms for Linear Programming)

February 8, 2016

A Second Course in Algorithms (Lecture 11: Online Learning and the Multiplicative Weights Algorithm)

February 11, 2016

...
Timeline

May 2005

Selfish Routing and the Price of Anarchy is published.

2002

Tim Roughgarden earns his Doctor of Philosophy (PhD) in Computer Science from Cornell University. He writes his dissertation on Selfish Routing.

1998

Tim Roughgarden earns his Masters of Computer Science from Stanford University.

1997

Tim Roughgarden earns his Bachelor of Science in Applied Mathematics from Stanford University.
Aleksander Holm
Aleksander Holm edited on 7 Jan, 2022
Edits made to:
Infobox (+4 properties)
Description (+186/-18 characters)
Article (+4517 characters)
Table (+1 rows) (+4 cells) (+157 characters)
Table (+1/-1 rows) (+4/-4 cells) (+127/-125 characters)
Topic thumbnail

Tim Roughgarden

Computer scientist

Tim Roughgarden is an American computer scientist, a Professor of Computer Science at Columbia University, and the author and editor of several works in game theory and computer science.

Article
Overview

Tim Roughgarden is a professor of computer science at Columbia University, where he is a member of the Data Science Institute. Previously he was a professor of computer science at Stanford University, where he taught until 2018. His research interests include computer science and economics, and the connections between them both; and the design, analysis, applications, and limitations of algorithms; especially as those concepts are applied to networks, auctions, and cryptocurrencies.

Education

Roughgarden studied at Stanford University from 1993 to 1998, where he earned his Bachelor of Science (BS) in Applied Mathematics in 1997, and earned his Masters in Computer Science in 1998. Following his masters, Roughgarden attended Cornell University where he studied for his PhD in computer science from 1998 to 2002. At Cornell University, Roughgarden received his PhD under the supervision of Éva Tardos. After earning his PhD at Cornell University, Roughgarden did a postdoc at University of California, Berkeley.

In 2002, Roughgarden presented his dissertation on Selfish Routing for his PhD at Cornell University, which looked at the degradation of network performance from selfish and uncoordinated network user behavior, while also offering algorithms for building and managing networks to direst selfish behavior towards desirable outcomes. In the same year, Roughgarden received the Danny Lewin award at STOC for the best student paper.

Academic career

In 2004, Tim Roughgarden's academic career began at Stanford University where he was given a position as a professor in the Computer Science department, and where he taught until 2018. While there he held the Chambers Faculty Scholarship development chair. While teaching at Stanford University, he taught on algorithms and game theory, and received consistently positive reviews from his students both for the relative complexity of his courses, and for the way in which he taught.

From September 2017 to August 2018, he worked as a visiting professor at The London School of Economics and Political Science (LSE). And in 2019, Roughgarden began teaching at Columbia University in New York. Besides his academic work, Roughgarden founded Parallel Lines Consulting, LLC, a consulting firm in legal and expert work in algorithms, game theory, mechanism design, and blockchain technology. As well, he was hired on at Andreessen Horowitz starting in February 2021, where he works as a research partner on the Andreessen Horowitz Crypto team.

Roughgarden also teaches a four part course on algorithms on Coursera, a two part course on algorithm design and analysis on edX, and he has published series of his lectures on topics such as blockchain, cryptocurrencies, auctions, and algorithms on YouTube.

Research

In research, Roughgarden's interests include the connections between computer science and economics; and the design, analysis, application, and limitation of algorithms. In 2007, he received the Presidential Early Career Award for Scientists and Engineers.

In 2009, he received the Association for Computing Machinery (ACM) Grace Murray Hopper award for introducing novel techniques that quantify lost efficiency with the uncoordinated behavior of network users acting in their own self-interest.

And in 2012, Roughgardenwon the European Association for Theoretical Computer Science (EATCS) Gödel Prize for his paper "How Bad Is Selfish Routing?" co-written with Éva Tardos published in the Journal of ACM in 2002. This paper explored the "price of anarchy" concept, providing mathematical results on the relationship between centralized optimization and "selfish routing" in network traffic.

...

Other awards Roughgarden has earned for his research has included the Kalai Prize in Computer Science and Game Theory, the Shapley Lectureship of the Game Theory Society, the Social Choice and Welfare Prize, INFORM's Optimization Prize for Young Researchers, the Mathematical Programming Society's Tucker Prize, and a Guggenheim Fellowship.

Selfish routing

Tim Roughgarden's research in selfish routing is related to game theory, algorithms, networks, and combinatorial optimization. This has included the application of game theory concepts to networking, in his Selfish Routing and the Price of Anarchy. This work offered a technical examination of selfish routing, a concept with implications not only in the electronic traffic found online and within the pathways of computer and communication networks, but also in the world of travel and moving people.

Table

Title
Author
Link
Type
Date

Transaction Fee Mechanism Design for the Ethereum Blockchain: An Economic Analysis of EIP-1559

Tim Roughgarden

December 1, 2020

Table

Title
Date
Link

Incentives in Computer Science (Lecture 6.1: Bitcoin Transactions)

April 4, 2021

Incentives in Computer Science (Lecture 6.2: The Bitcoin Blockchain)

April 4, 2021

Infobox
Also known as
Timothy Avelin Roughgarden
Location
Nationality
Occupation
Edits on 6 Jan, 2022
Aleksander Holm
Aleksander Holm edited on 6 Jan, 2022
Edits made to:
Infobox (+2 properties)
Infobox
Aleksander Holm
Aleksander Holm edited on 6 Jan, 2022
Edits made to:
Infobox (+1 properties)
Infobox
Current Employer
Aleksander Holm
Aleksander Holm edited on 6 Jan, 2022
Edits made to:
Infobox (+4 properties)
Table (+1 rows) (+5 cells) (+91 characters)
Topic thumbnail

Tim Roughgarden

Tim Roughgarden is an American computer scientist, a professor of computer science at Columbia University, and the author and editor of several works in game theory and computer science.

Table

Title
Author
Link
Type
Date

Selfish Routing

Tim Roughgarden

Web

May 2002

Infobox
Aleksander Holm
Aleksander Holm edited on 6 Jan, 2022
Edits made to:
Table (+59/-60 characters)
Table

Title
Date
Link

Incentives in Computer Science (Lecture 6.56.3: ForkingBitcoin AttacksMining)

April 4, 2021

Aleksander Holm
Aleksander Holm edited on 6 Jan, 2022
Edits made to:
Table (+1/-1 rows) (+4/-4 cells) (+120/-134 characters)
Table

Title
Date
Link

Beyond Worst-Case Analysis (IGAFIT Algorithmic Colloquium, March 25, 2021)

April 17, 2021

Incentives in Computer Science (Lecture 6.5: Forking Attacks)

April 4, 2021

Golden AI"Infobox creation from: Wikidata data enrichment"
Golden AI approved a suggestion from Golden's AI on 6 Jan, 2022
Edits made to:
Infobox (+3 properties)
Infobox
Doctoral advisor
Doctoral students
Google Scholar ID
Aleksander Holm
Aleksander Holm edited on 6 Jan, 2022
Edits made to:
Table (+5 rows) (+20 cells) (+574 characters)
Table

Title
Date
Link

Beyond Worst-Case Analysis (IGAFIT Algorithmic Colloquium, March 25, 2021)

April 17, 2021

Incentives in Computer Science (Lecture 6.1: Bitcoin Transactions)

April 4, 2021

Incentives in Computer Science (Lecture 6.5: Forking Attacks)

April 4, 2021

Incentives in Computer Science (Lecture 6.6: Selfish Mining)

April 4, 2021

Teaching Backward

April 6, 2021

Edits on 24 May, 2020
Golden AI"Wikidata import from WikidataImport2"
Golden AI edited on 24 May, 2020
Edits made to:
Infobox (+1 properties)
Infobox
Wikidata entity ID
Q7804199
Edits on 28 Jan, 2019
Golden AI
Golden AI edited on 28 Jan, 2019
Edits made to:
Infobox (+1 properties)
Infobox
Is a
Golden logo
By using this site, you agree to our Terms & Conditions.