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.
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.