S. Matthew Weinberg

research

∙ 09/18/2023

Simple and Optimal Online Contention Resolution Schemes for k-Uniform Matroids

We provide a simple (1-O(1/√(k)))-selectable Online Contention Resolutio...

0 Atanas Dinev, et al. ∙

research

∙ 09/13/2023

Undetectable Selfish Mining

Seminal work of Eyal and Sirer (2014) establishes that a strategic Bitco...

0 Maryam Bahrani, et al. ∙

research

∙ 07/09/2023

Selling to Multiple No-Regret Buyers

We consider the problem of repeatedly auctioning a single item to multip...

0 Linda Cai, et al. ∙

research

∙ 04/04/2023

q-Partitioning Valuations: Exploring the Space Between Subadditive and Fractionally Subadditive Valuations

For a set M of m elements, we define a decreasing chain of classes of no...

0 Kiril Bangachev, et al. ∙

research

∙ 01/19/2023

Tight Bounds on 3-Team Manipulations in Randomized Death Match

Consider a round-robin tournament on n teams, where a winner must be (po...

0 Atanas Dinev, et al. ∙

research

∙ 11/08/2022

On the cut-query complexity of approximating max-cut

We consider the problem of query-efficient global max-cut on a weighted ...

0 Orestis Plevrakis, et al. ∙

research

∙ 09/12/2022

An Improved Lower Bound for Matroid Intersection Prophet Inequalities

We consider prophet inequalities subject to feasibility constraints that...

0 Raghuvansh R. Saxena, et al. ∙

research

∙ 07/16/2022

Optimal Strategic Mining Against Cryptographic Self-Selection in Proof-of-Stake

Cryptographic Self-Selection is a subroutine used to select a leader for...

0 Matheus V. X. Ferreira, et al. ∙

research

∙ 05/29/2022

Credible, Strategyproof, Optimal, and Bounded Expected-Round Single-Item Auctions for all Distributions

We consider a revenue-maximizing seller with a single item for sale to m...

0 Meryem Essaidi, et al. ∙

research

∙ 05/25/2022

On Infinite Separations Between Simple and Optimal Mechanisms

We consider a revenue-maximizing seller with k heterogeneous items for s...

0 C. Alexandros Psomas, et al. ∙

research

∙ 11/07/2021

Formal Barriers to Simple Algorithms for the Matroid Secretary Problem

Babaioff et al. [BIK2007] introduced the matroid secretary problem in 20...

0 Maryam Bahrani, et al. ∙

research

∙ 07/08/2021

Proof-of-Stake Mining Games with Perfect Randomness

Proof-of-Stake blockchains based on a longest-chain consensus protocol a...

0 Matheus V. X. Ferreira, et al. ∙

research

∙ 03/02/2021

Prior-free Dynamic Mechanism Design With Limited Liability

We study the problem of repeatedly auctioning off an item to one of k bi...

0 Mark Braverman, et al. ∙

research

∙ 01/10/2021

Approximately Strategyproof Tournament Rules in the Probabilistic Setting

We consider the manipulability of tournament rules which map the results...

0 Kimberly Ding, et al. ∙

research

∙ 11/19/2020

Optimal Multi-Dimensional Mechanisms are not Local

Consider the problem of implementing a revenue-optimal, Bayesian Incenti...

0 S. Matthew Weinberg, et al. ∙

research

∙ 11/14/2020

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

We provide the first separation in the approximation guarantee achievabl...

0 Sepehr Assadi, et al. ∙

research

∙ 07/10/2020

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

We consider a revenue-maximizing single seller with m items for sale to ...

0 Natalie Collina, et al. ∙

research

∙ 07/05/2020

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

This paper seeks to establish a framework for directing a society of sim...

0 Michael Chang, et al. ∙

research

∙ 06/10/2020

Auction learning as a two-player game

Designing an incentive compatible auction that maximizes expected revenu...

0 Jad Rahme, et al. ∙

research

∙ 04/03/2020

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

We consider the sale of a single item to multiple buyers by a revenue-ma...

0 Matheus V. X. Ferreira, et al. ∙

research

∙ 04/03/2020

Credible, Truthful, and Bounded-Round Mechanisms via Cryptographic Commitments

We consider the sale of a single item to multiple buyers by a revenue-ma...

0 Matheus V. X. Ferreira, et al. ∙

research

∙ 03/02/2020

A Permutation-Equivariant Neural Network Architecture For Auction Design

Designing an incentive compatible auction that maximizes expected revenu...

23 Jad Rahme, et al. ∙

research

∙ 02/25/2020

Binary Scoring Rules that Incentivize Precision

All proper scoring rules incentivize an expert to predict accurately (re...

0 Eric Neyman, et al. ∙

research

∙ 02/15/2020

Optimal Mechanism Design for Single-Minded Agents

We consider revenue-optimal mechanism design in the interdimensional set...

0 Nikhil Devanur, et al. ∙

research

∙ 02/15/2020

When to Limit Market Entry under Mandatory Purchase

We study a problem inspired by regulated health insurance markets, such ...

0 Meryem Essaidi, et al. ∙

research

∙ 11/18/2019

Optimal Single-Choice Prophet Inequalities from Samples

We study the single-choice Prophet Inequality problem when the gambler i...

0 Aviad Rubinstein, et al. ∙

research

∙ 11/15/2019

New Query Lower Bounds for Submodular Function MInimization

We consider submodular function minimization in the oracle model: given ...

0 Andrei Graur, et al. ∙

research

∙ 10/10/2019

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

State-of-the-art posted-price mechanisms for submodular bidders with m i...

0 Linda Cai, et al. ∙

research

∙ 09/23/2019

Persuasion and Incentives Through the Lens of Duality

Lagrangian duality underlies both classical and modern mechanism design....

0 Shaddin Dughmi, et al. ∙

research

∙ 07/12/2019

Asynchronous Majority Dynamics in Preferential Attachment Trees

We study information aggregation in networks where agents make binary de...

0 Maryam Bahrani, et al. ∙

research

∙ 06/07/2019

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

We consider the manipulability of tournament rules, in which n teams pla...

0 Ariel Schvartzman, et al. ∙

research

∙ 05/13/2019

Approximation Schemes for a Buyer with Independent Items via Symmetries

We consider a revenue-maximizing seller with n items facing a single buy...

0 Pravesh Kothari, et al. ∙

research

∙ 02/26/2019

Selling a Single Item with Negative Externalities

We consider the problem of regulating products with negative externaliti...

0 Tithi Chattopadhyay, et al. ∙

research

∙ 12/05/2018

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

The Competition Complexity of an auction setting refers to the number of...

0 Hedyeh Beyhaghi, et al. ∙

research

∙ 12/04/2018

A Duality-Based Unified Approach to Bayesian Mechanism Design

We provide a unified view of many recent developments in Bayesian mechan...

0 Yang Cai, et al. ∙

research

∙ 11/29/2018

Smoothed Analysis of Multi-Item Auctions with Correlated Values

Consider a seller with m heterogeneous items for sale to a single additi...

0 Christos-Alexandros Psomas, et al. ∙

research

∙ 11/24/2018

Complement-Free Couples Must Communicate: A Hardness Result for Two-Player Combinatorial Auctions

We study the communication complexity of welfare maximization in combina...

0 Tomer Ezra, et al. ∙

research

∙ 11/21/2018

Bitcoin: A Natural Oligopoly

Although Bitcoin was intended to be a decentralized digital currency, in...

0 Nick Arnosti, et al. ∙

research

∙ 09/18/2018

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

The security of most existing cryptocurrencies is based on a concept cal...

0 Jonah Brown-Cohen, et al. ∙

research

∙ 08/07/2018

The Sample Complexity of Up-to-ε Multi-Dimensional Revenue Maximization

We consider the sample complexity of revenue maximization for multiple b...

0 Yannai A. Gonczarowski, et al. ∙

research

∙ 11/25/2017

Selling to a No-Regret Buyer

We consider the problem of a single seller repeatedly selling a single i...

0 Mark Braverman, et al. ∙

research

∙ 11/08/2017

Computing exact minimum cuts without knowing the graph

We give query-efficient algorithms for the global min-cut and the s-t cu...

0 Aviad Rubinstein, et al. ∙

research

∙ 11/06/2017

The menu complexity of "one-and-a-half-dimensional" mechanism design

We study the menu complexity of optimal and approximately-optimal auctio...

0 Raghuvansh R. Saxena, et al. ∙

research

∙ 06/27/2017

Multi-armed Bandit Problems with Strategic Arms

We study a strategic version of the multi-armed bandit problem, where ea...

0 Mark Braverman, et al. ∙

S. Matthew Weinberg

Featured Co-authors