Tim Roughgarden

research

∙ 07/04/2023

Transaction Fee Mechanism Design with Active Block Producers

The incentive-compatibility properties of blockchain transaction fee mec...

0 Maryam Bahrani, et al. ∙

research

∙ 06/29/2023

When Bidders Are DAOs

In a typical decentralized autonomous organization (DAO), people organiz...

0 Maryam Bahrani, et al. ∙

research

∙ 04/28/2023

Permissionless Consensus

Blockchain protocols typically aspire to run in the permissionless setti...

0 Andrew Lewis-Pye, et al. ∙

research

∙ 03/01/2023

A Myersonian Framework for Optimal Liquidity Provision in Automated Market Makers

In decentralized finance ("DeFi"), automated market makers (AMMs) enable...

0 Jason Milionis, et al. ∙

research

∙ 02/22/2023

Complexity-Approximation Trade-offs in Exchange Mechanisms: AMMs vs. LOBs

This paper presents a general framework for the design and analysis of e...

0 Jason Milionis, et al. ∙

research

∙ 05/25/2022

Formalizing Preferences Over Runtime Distributions

When trying to solve a computational problem we are often faced with a c...

5 Devon R Graham, et al. ∙

research

∙ 02/22/2022

No-Regret Learning with Unbounded Losses: The Case of Logarithmic Pooling

For each of T time steps, m experts report probability distributions ove...

1 Eric Neyman, et al. ∙

research

∙ 11/04/2021

Are You Smarter Than a Random Expert? The Robust Aggregation of Substitutable Signals

The problem of aggregating expert forecasts is ubiquitous in fields as w...

15 Eric Neyman, et al. ∙

research

∙ 09/10/2021

How Does Blockchain Security Dictate Blockchain Implementation?

Blockchain protocols come with a variety of security guarantees. For exa...

0 Andrew Lewis-Pye, et al. ∙

research

∙ 09/03/2021

Strictly Proper Contract Functions Can Be Arbitrage-Free

We consider mechanisms for truthfully eliciting probabilistic prediction...

0 Eric Neyman, et al. ∙

research

∙ 06/02/2021

Transaction Fee Mechanism Design

Demand for blockchains such as Bitcoin and Ethereum is far larger than s...

0 Tim Roughgarden, et al. ∙

research

∙ 02/16/2021

Smoothed Analysis with Adaptive Adversaries

We prove novel algorithmic guarantees for several online problems in the...

8 Nika Haghtalab, et al. ∙

research

∙ 02/14/2021

From Proper Scoring Rules to Max-Min Optimal Forecast Aggregation

This paper forges a strong connection between two seemingly unrelated fo...

0 Eric Neyman, et al. ∙

research

∙ 01/18/2021

Byzantine Generals in the Permissionless Setting

Consensus protocols have traditionally been studied in a setting where a...

0 Andrew Lewis-Pye, et al. ∙

research

∙ 12/01/2020

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

EIP-1559 is a proposal to make several tightly coupled additions to Ethe...

0 Tim Roughgarden, et al. ∙

research

∙ 09/20/2020

A General Framework for the Security Analysis of Blockchain Protocols

Blockchain protocols differ in fundamental ways, including the mechanics...

0 Andrew Lewis-Pye, et al. ∙

research

∙ 07/30/2020

Distribution-Free Models of Social Networks

The structure of large-scale social networks has predominantly been arti...

0 Tim Roughgarden, et al. ∙

research

∙ 07/26/2020

Beyond the Worst-Case Analysis of Algorithms (Introduction)

One of the primary goals of the mathematical analysis of algorithms is t...

21 Tim Roughgarden, et al. ∙

research

∙ 07/26/2020

Distributional Analysis

In distributional or average-case analysis, the goal is to design an alg...

0 Tim Roughgarden, et al. ∙

research

∙ 07/26/2020

Resource Augmentation

This chapter introduces resource augmentation, in which the performance ...

0 Tim Roughgarden, et al. ∙

research

∙ 07/19/2020

FPT Algorithms for Finding Dense Subgraphs in c-Closed Graphs

Dense subgraph detection is a fundamental problem in network analysis fo...

0 Edin Husic, et al. ∙

research

∙ 07/07/2020

Mathematical Foundations for Social Computing

Social computing encompasses the mechanisms through which people interac...

0 Yiling Chen, et al. ∙

research

∙ 06/18/2020

Resource Pools and the CAP Theorem

Blockchain protocols differ in fundamental ways, including the mechanics...

0 Andrew Lewis-Pye, et al. ∙

research

∙ 06/17/2020

Smoothed Analysis of Online and Differentially Private Learning

Practical and pervasive needs for robustness and privacy in algorithms h...

9 Nika Haghtalab, et al. ∙

research

∙ 02/27/2020

The Complexity of Contracts

We initiate the study of computing (near-)optimal contracts in succinctl...

0 Paul Duetting, et al. ∙

research

∙ 09/23/2019

An Axiomatic Approach to Block Rewards

Proof-of-work blockchains reward each miner for one completed block by a...

0 Xi Chen, et al. ∙

research

∙ 12/31/2018

Approximately Optimal Mechanism Design

Optimal mechanism design enjoys a beautiful and well-developed theory, a...

0 Tim Roughgarden, et al. ∙

research

∙ 08/10/2018

Simple versus Optimal Contracts

We consider the classic principal-agent model of contract theory, in whi...

0 Paul Dütting, et al. ∙

research

∙ 07/03/2018

On the Computational Power of Online Gradient Descent

We prove that the evolution of weight vectors in online gradient descent...

0 Vaggos Chatziafratis, et al. ∙

research

∙ 06/26/2018

Beyond Worst-Case Analysis

In the worst-case analysis of algorithms, the overall performance of an ...

0 Tim Roughgarden, et al. ∙

research

∙ 06/08/2018

An Optimal Algorithm for Online Unconstrained Submodular Maximization

We consider a basic problem at the interface of two fundamental fields: ...

0 Tim Roughgarden, et al. ∙

research

∙ 05/24/2018

Optimal Algorithms for Continuous Non-monotone Submodular and DR-Submodular Maximization

In this paper we study the fundamental problems of maximizing a continuo...

0 Rad Niazadeh, et al. ∙

research

∙ 04/30/2018

The idemetric property: when most distances are (almost) the same

We introduce the idemetric property, which formalises the idea that most...

0 George Barmpalias, et al. ∙

research

∙ 04/20/2018

Finding Cliques in Social Networks: A New Distribution-Free Model

We propose a new distribution-free model of social networks. Our definit...

0 Jacob Fox, et al. ∙

research

∙ 01/02/2018

Complexity Theory, Game Theory, and Economics

This document collects the lecture notes from my mini-course "Complexity...

0 Tim Roughgarden, et al. ∙

research

∙ 11/11/2017

Communication Complexity of Discrete Fair Division

We initiate the study of the communication complexity of fair division w...

0 Benjamin Plaut, et al. ∙

research

∙ 07/26/2016

The Price of Anarchy in Auctions

This survey outlines a general and modular theory for proving approximat...

0 Tim Roughgarden, et al. ∙

research

∙ 09/19/2014

Tight Error Bounds for Structured Prediction

Structured prediction tasks in machine learning involve the simultaneous...

0 Amir Globerson, et al. ∙

Tim Roughgarden

Featured Co-authors