Tim Roughgarden

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.

Roughgarden studied at Stanford University from 1993 to 1998, where he earned his Bachelor of Science (BS) in Applied Mathematics in 1997 and 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.

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.

Tim Roughgarden teaching at Stanford University.

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.

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.

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.

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.

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.

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.