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

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.