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

Tim Roughgarden is a Professor of Computer Science at Columbia University and a winner of the Gödel Prize, which is often considered as “the Nobel Prize of theoretical computer science.” His research interests include the many connections between computer science and economics, as well as the design, analysis, applications, and limitations of algorithms. We’ll also talk about his most recent research in the cryptocurrency space, EIP-1559, and the future of Ethereum.

Prof. Roughgarden has been awarded the ACM Grace Murray Hopper Award, the Presidential Early Career Award for Scientists and Engineers, the Kalai Prize in Computer Science and Game Theory, the Social Choice and Welfare Prize, the Mathematical Programming Society's Tucker Prize, and the Gödel Prize in theoretical computer science. He was an invited speaker at the 2006 International Congress of Mathematicians, the Shapley Lecturer at the 2008 World Congress of the Game Theory Society, and a Guggenheim Fellow in 2017. He has written or edited ten books and monographs, and is regarded by many students as one of the best educators in algorithmic game theory.

We start by discussing Prof. Roughgarden’s early work that helped lay the foundations for algorithmic game theory and won him the Gödel Prize. He takes us back to the late 90’s and talks us through the history of the field and the key researchers and papers that helped kick it off. He unpacks the price of anarchy, a formal measure of the extent to which selfishly acting individuals (thus ideally acting according to a Nash equilibrium) can harm collective welfare. A well-known example of this phenomenon is the prisoner’s dilemma. He then explains his work on selfish routing, examining the price of anarchy in the particular case of network routing and finding that in this setting the excess cost due to individuals acting selfishly is at most 33%.

Prof. Roughgarden then discusses his later work on revenue-optimal auctions, an ongoing area of research in mechanism design. Here a seller wants to sell some number of items to some bidders that each have different values for different items, and wants to make as much money as possible. How should they structure their auction if they don’t have a strong guess for how much the bidders would be willing to pay for each item? Along the way, he describes his approach to research, choosing problems to work on in a way that builds on previous work, remains relevant to practical settings, and lends significant insight.

We then turn to Prof. Roughgarden’s most recent work in the cryptocurrency space, particularly EIP-1559. He outlines the current cryptocurrency landscape for us, likening it to the Internet shortly after its inception. He explains the different layers of abstraction at which cryptocurrency technologies can operate, from peer-to-peer networks to consensus protocols to applications such as smart contracts, along with the vast array of computer science problems that comes with them. Cryptocurrency protocols are especially difficult mechanisms to design because these mechanisms are being directly executed by self-interested miners rather than a benevolent centralized authority.

Prof. Roughgarden then shares with us his work on the soon to be implemented EIP-1559 proposal for Ethereum. Instead of the previous method where participants bid to have each transaction included in the blockchain, EIP-1559 proposes to internally compute an appropriate price for each transaction. Moreover, the transaction fee is burnt instead of awarded to miners in an effort to counteract the naturally inflationary tokenomics of Ethereum. Prof. Roughgarden’s role in the project was to closely analyze the game-theoretic properties of this new protocol. He notes the growing appetite in the blockchain community for formal academic analysis of protocols.

Finally, Prof. Roughgarden reflects on what might be necessary in order for cryptocurrencies to flourish in the future. He speculates that it will need to become easier for people to participate in blockchains without much prior knowledge, much as anyone can use a mobile phone to interact without needing to know the mechanics of how it transmits and receives signals. He comments on his journey learning about cryptocurrencies and intends to share what he has learned with other academics as he goes along. This fall, he will be teaching a class at Columbia University titled “Foundations of Blockchains”.

Tim Roughgarden