Publications

Surveys and Theses

**Algorithms for Strategic Agents**

S. Matthew Weinberg.

PhD Thesis, 2014.

** George M. Sprowls Award (for best MIT doctoral theses in CS).**

**SIGecom Doctoral Dissertation Award.**

** Reducing Bayesian Mechanism Design to Algorithm Design**.

Yang Cai, Constantinos Daskalakis, S. Matthew Weinberg.

Encyclopedia of Algorithms, 2015.

Conference Publications

**Note:** I try to keep the following list up-to-date with pointers to current versions, but for very recent publications you may have better luck with dblp.

**Approximately Strategyproof Tournament Rules in the Probabilistic Setting**.

Kimberly Ding, S. Matthew Weinberg.

In *Proceedings
of the 12th Innovations in Theoretical Computer Science*
(ITCS), 2021.

**A Permutation-Equivariant Neural Network Architecture for Auction Design**.

Jad Rahme, Sami Jelassi, Joan Bruna, S. Matthew Weinberg.

In *Proceedings
of the 35th AAAI Conference on Artificial Intelligence*
(AAAI), 2021.

**Auction Learning as a Two-Player Game**.

Jad Rahme, Sami Jelassi, S. Matthew Weinberg.

In *Proceedings
of the 9th Annual International Colloquium on Learning Representation*
(ICLR), 2021.

**Asynchronous Majority Dynamics in Preferential Attachment Trees**.

Maryam Bahrani, Nicole Immorlica, Divyarthi Mohan, S. Matthew Weinberg.

In *Proceedings
of the 47th Annual International Colloquium on Automata, Languages, and Programming*
(ICALP), 2020.

**Credible, Truthful, and Two-Round (Optimal) Auctions via Cryptographic Commitments**.

Matheus V.X. Ferreira, S. Matthew Weinberg.

In *Proceedings
of the 21st ACM Conference on Economics and Computation*
(EC), 2020.

**Optimal Mechanism Design for Single-Minded Agents**.

Nikhil R. Devanur, Kira Goldner, Raghuvansh R. Saxena, Ariel Schvartzman, S. Matthew Weinberg.

In *Proceedings
of the 21st ACM Conference on Economics and Computation*
(EC), 2020.

**On the (in)-approximability of Bayesian Revenue Maximization for a Combinatorial Buyer**.

Natalie Collina, S. Matthew Weinberg.

In *Proceedings
of the 21st ACM Conference on Economics and Computation*
(EC), 2020.

**Separating the Communication Complexity of Truthful and Non-Truthful Combinatorial Auctions**.

Sepehr Assadi, Hrishikesh Khandeparkar, Raghuvansh R. Saxena, S. Matthew Weinberg.

In *Proceedings
of the 52nd ACM Symposium on Theory of Computation*
(STOC), 2020.

**Decentralized Reinforcement Learning: Global Decision-Making via Local Economic Transactions**.

Michael Chang, Sidhant Kaushik, S. Matthew Weinberg, Thomas L. Griffiths, Sergey Levine.

In *Proceedings
of the 37th International Conference on Machine Learning*
(ICML), 2020.

**Implementation in Advised Strategies: Welfare Guarantees from Posted-Price Mechanisms when Demand Queries are NP-hard**.

Linda Cai, Clayton Thomas, S.
Matthew Weinberg.

In *Proceedings
of the 11th Innovations in Theoretical Computer Science*
(ITCS), 2020.

**Optimal Single-Choice Prophet Inequalities from Samples**.

Aviad Rubinstein, Jack Z. Wang, S.
Matthew Weinberg.

In *Proceedings
of the 11th Innovations in Theoretical Computer Science*
(ITCS), 2020.

**New Query Lower Bounds for Submodular Function Minimization**.

Andrei Graur, Tristan Pollner, Vidhya Ramaswamy, S.
Matthew Weinberg.

In *Proceedings
of the 11th Innovations in Theoretical Computer Science*
(ITCS), 2020.

**Approximately Strategyproof Tournament Rules: On Large Manipulating Sets and Cover-Consistence**.

Ariel Schvartzman, S. Matthew Weinberg, Eitan Zlatin, Albert Zuo.

In *Proceedings
of the 11th Innovations in Theoretical Computer Science*
(ITCS), 2020.

**Subsidy Allocations in the Presence of Income Shocks**.

Rediet Abebe, Jon Kleinberg, S. Matthew Weinberg.

In *Proceedings
of the 34th AAAI Conference on Artificial Intelligence*
(AAAI), 2020.

**Approximation Schemes for a Buyer with Independent Items via Symmetries**.

Pravesh Kothari, Divyarthi Mohan, Ariel Schvartzman, Sahil Singla, S. Matthew Weinberg.

In *Proceedings
of the 60th Annual IEEE Symposium on Foundations of Computer Science*
(FOCS),
2019.

**Settling the Communication Complexity of Combinatorial Auctions with Two Subadditive Buyers**.

Tomer Ezra, Michal Feldman, Eric Neyman, Inbal Talgam-Cohen, S. Matthew Weinberg.

In *Proceedings
of the 60th Annual IEEE Symposium on Foundations of Computer Science*
(FOCS),
2019.

**Smoothed Analysis of Multi-Item Auctions with Correlated Values**.

Christos-Alexandros Psomas, Ariel Schvartzman, S. Matthew Weinberg.

In *Proceedings
of the 20th ACM Conference on Economics and Computation* (EC),
2019.

**Formal Barriers to Longest-Chain Proof-of-Stake Protocols**.

Jonah Brown-Cohen, Arvind Narayanan, Christos-Alexandros Psomas, S. Matthew Weinberg.

In *Proceedings
of the 20th ACM Conference on Economics and Computation* (EC),
2019.

**Multi-Armed Bandit Problems with Strategic Arms**.

Mark Braverman, Jieming Mao, Jon Schneider, S. Matthew Weinberg.

In *Proceedings
of the 32nd Conference on Learning Theory* (COLT),
2019.

**Optimal (and Benchmark-Optimal) Competition Complexity for Additive Buyers over Independent Items**.

Hedyeh Beyhaghi, S.
Matthew Weinberg.

In *Proceedings
of the 51st ACM Conference on Theory of Computation *(STOC),
2019.

**Selling a Single Item with Negative Externalities: to Regulate Production or Payments?**.

Tithi Chattopadhyay, Nick Feamster, Danny Huang, Matheus Venturyne, S.
Matthew Weinberg.

In *Proceedings
of the 28th Annual World Wide Web Conference*
(TheWebConf), 2019.

**Bitcoin: A Natural Oligopoly**.

Nick Arnosti, S.
Matthew Weinberg.

In *Proceedings
of the 10th Innovations in Theoretical Computer Science*
(ITCS), 2019.

**The Sample Complexity of Up-to-epsilon Multi-Dimensional Revenue Maximization**.

Yannai Gonczarowski, S.
Matthew Weinberg.

In *Proceedings
of the 59th Annual IEEE Symposium on Foundations of Computer Science*
(FOCS), 2018.

**
Selling to a No-Regret Buyer**

Mark Braverman, Jieming Mao, Jon Schneider, S. Matthew Weinberg.

In *Proceedings
of the 19th ACM Conference on Economics and Computation* (EC),
2018.

** Best Full Paper.**

** Best Paper with Student Lead Author.**

**
Arbitrum: Scalable Smart Contracts**

Harry Kalodner, Steven Goldfeder, Xiaoqi Chen, S. Matthew Weinberg, Edward W. Felten.

In *Proceedings
of the 27th USENIX Security Symposium* (USENIX),
2018.

**
On Simultaneous Two-Player Combinatorial Auctions**

Mark Braverman, Jieming Mao, S. Matthew Weinberg.

In *Proceedings
of the 29th ACM-SIAM Symposium on Discrete Algorithms* (SODA),
2018.

**
The Menu Complexity of "One-and-a-half" Dimensional Mechanism Design**

Raghuvansh R. Saxena, Ariel Schvartzman, S. Matthew Weinberg.

In *Proceedings
of the 29th ACM-SIAM Symposium on Discrete Algorithms* (SODA),
2018.

**Computing Exact Minimum Cuts Without Knowing the Graph**.

Aviad Rubinstein, Tselil Schramm, S. Matthew Weinberg.

In *Proceedings
of the 9th Innovations in Theoretical Computer Science Conference *(ITCS),
2018.

** A Simple and Approximately Optimal Mechanism for a Buyer with Complements**.

Alon Eden, Michal Feldman, Ophir Friedler, Inbal Talgam-Cohen, S. Matthew Weinberg.

In *Proceedings
of the 18th ACM Conference on Economics and Computation * (EC) 2017.

** The Competition Complexity of Auctions: A Bulow-Klemperer Result for Multi-Dimensional Bidders**.

Alon Eden, Michal Feldman, Ophir Friedler, Inbal Talgam-Cohen, S. Matthew Weinberg.

In *Proceedings
of the 18th ACM Conference on Economics and Computation * (EC) 2017.

** The Optimal Mechanism for Selling to a Budget Constrained Buyer: The General Case**.

Nikhil R. Devanur, S. Matthew Weinberg.

In *Proceedings
of the 18th ACM Conference on Economics and Computation * (EC) 2017.

** Discovering Valuations and Enforcing Truthfulness in a Deadline Aware Scheduler**.

Zhe Huang, S. Matthew Weinberg, Liang Zheng, Mung Chiang, Carlee Joe-Wong.

In *Proceedings
of the 37th IEEE Conference on Computer Communications * (INFOCOM), 2017.

**Condorcet-Consistent and Approximately Strategyproof Tournament Rules**.

Jon Schneider, Ariel Schvartzman, S. Matthew Weinberg.

In *Proceedings
of the 8th Innovations in Theoretical Computer Science Conference *(ITCS),
2017.

**On the Instability of Bitcoin without the Block Reward**.

Miles Carlsten, Harry Kalodner, S. Matthew Weinberg, Arvind Narayanan.

In *Proceedings
of the 23rd ACM Conference on Computer and Communications Security *(CCS),
2016.

Blog post by Arvind: **Bitcoin is Unstable without the Block Reward**.

**A Duality Based
Unified Approach to Bayesian Mechanism Design**.

Yang Cai, Nikhil Devanur, S. Matthew Weinberg.

In *Proceedings
of the 48th ACM Conference on Theory of Computation *(STOC),
2016.

** Invited to special issue of SIAM Journal on Computing (SICOMP). **

Short note in SIGecom Exchanges: **A Duality-Based Unified Approach to Bayesian Mechanism Design **.

**Parallel Algorithms for Select and
Partition with Noisy Comparisons**
.

Mark Braverman, Jieming Mao, S. Matthew Weinberg.

In *Proceedings
of the 48th ACM Conference on Theory of Computation *(STOC),
2016.

**
Interpolating Between Truthful and
non-Truthful Mechanisms for Combinatorial Auctions**

Mark Braverman, Jieming Mao, S. Matthew Weinberg.

In *Proceedings
of the 27th ACM-SIAM Symposium on Discrete Algorithms* (SODA),
2016.

**Simple Mechanisms for a Subadditive
Buyer and Applications to Revenue Monotonicity**.

Aviad Rubinstein, S. Matthew Weinberg.

In *Proceedings
of the 16th ACM Conference on Economics and Computation* (EC),
2015.

** Invited to special issue of Transactions on Economics and Computation (TEAC).**

**Simple Auctions
with Simple Strategies**.

Nikhil Devanur, Jamie Morgenstern, Vasilis
Syrgkanis, S. Matthew Weinberg.

In *Proceedings
of the 16th ACM Conference on Economics and Computation *(EC),
2015.

** Invited to special issue of Transactions on Economics and Computation (TEAC). **

**Revenue Maximization and Ex-Post Budget
Constraints**.

Constantinos Daskalakis, Nikhil Devanur, S. Matthew
Weinberg.

In *Proceedings
of the 16th ACM Conference on Economics and Computation* (EC),
2015.

** Invited to special issue of Transactions on Economics and Computation (TEAC). **

**Bayesian Truthful Mechanisms for Job
Scheduling from Bi-criterion Approximation Algorithms**.

Constantinos Daskalakis, S. Matthew Weinberg.

In *Proceedings
of the 26th ACM-SIAM Symposium on Discrete Algorithms* (SODA),
2015.

**Game Theory based
Peer Grading Mechanisms for MOOCs**
.

Constantinos Daskalakis, Nicolaas Kaashoek, Christos
Tzamos, S. Matthew Weinberg, William Wu.

In* Proceedings
of the 2nd ACM Conference on Learning at Scale *(L@S), 2015. Work
in Progress paper.

**A Simple and Approximately Optimal
Mechanism for an Additive Buyer**.

Moshe Babaioff, Nicole Immorlica, Brendan Lucier, S.
Matthew Weinberg.

In *Proceedings
of the 55th Annual IEEE Symposium on Foundations of Computer Science*
(FOCS), 2014.

Short note in SIGecom Exchanges: **A Simple and Approximately Optimal Mechanism for an Additive Buyer**.

**Reaching Consensus via non-Bayesian
Asynchronous Learning in Social Networks**

Michal Feldman, Nicole Immorlica, Brendan Lucier, S.
Matthew Weinberg.

In *Proceedings
of the 17th International Workshop on Approximation Algorithms for
Combinatorial Optimization Problems* (APPROX), 2014.

**Prophet Inequalities with Limited Information**.

Pablo D. Azar, Robert Kleinberg, S. Matthew
Weinberg.

In *Proceedings
of the 25th ACM-SIAM Symposium on Discrete Algorithms* (SODA),
2014.

** Invited to special issue of Games and Economic Behavior (GEB). **

**Understanding Incentives: Mechanism Design Becomes Algorithm Design**.

Yang Cai, Constantinos Daskalakis, S. Matthew
Weinberg.

In *Proceedings
of the 54th Annual IEEE Symposium on Foundations of Computer Science
*(FOCS), 2013.

**Reducing Revenue to Welfare Maximization:
Approximation Algorithms and other Generalizations**.

Yang Cai, Constantinos Daskalakis, S. Matthew
Weinberg.

In *Proceedings
of the 24th ACM-SIAM Symposium on Discrete Algorithms* (SODA),
2013.

**Optimal and
Efficient Parametric Auctions**.

Pablo D. Azar, Constantinos Daskalakis, Silvio
Micali, S. Matthew Weinberg.

In *Proceedings
of the 24th ACM-SIAM Symposium on Discrete Algorithms* (SODA),
2013.

**Optimal Multi-Dimensional Mechanism Design: Reducing Revenue to Welfare Maximization**.

Yang Cai, Constantinos Daskalakis, S. Matthew
Weinberg.

In *Proceedings
of the 53rd Annual IEEE Symposium on Foundations of Computer Science*
(FOCS), 2012.

**Symmetries and Optimal Multi-Dimensional Mechanism Design**
.

Constantinos Daskalakis and S. Matthew Weinberg.

In *Proceedings
of the 13th ACM Conference on Electronic Commerce* (EC), 2012.

** Best Student
Paper Award.**

Short note in SIGecom Exchanges: **On Optimal
Multi-Dimensional Mechanism Design**.

**Matroid Prophet Inequalities**.

Robert Kleinberg, S. Matthew Weinberg.

In *Proceedings
of the 44th ACM Conference on Theory of Computation *(STOC),
2012.

**Accepted to special issue of Games and Economic
Behavior (GEB): ** **Matroid Prophet Inequalities and Applications to Multi-Dimensional Mechanism Design**.

**An Algorithmic Characterization of
Multi-Dimensional Mechanisms**.

Yang Cai, Constantinos Daskalakis, S. Matthew
Weinberg.

In *Proceedings of the 44th ACM Conference on Theory of Computation *(STOC), 2012.

**Pricing Randomized Allocations**.

Patrick Briest, Shuchi Chawla, Robert Kleinberg, S.
Matthew Weinberg.

In *Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms* (SODA), 2010.

**Accepted to special issue of Journal of Economic
Theory (JET): ****Pricing Lotteries**.