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...
share
research
∙
09/13/2023
Undetectable Selfish Mining
Seminal work of Eyal and Sirer (2014) establishes that a strategic Bitco...
research
∙
07/09/2023
Selling to Multiple No-Regret Buyers
We consider the problem of repeatedly auctioning a single item to multip...
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...
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...
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 ...
research
∙
09/12/2022
An Improved Lower Bound for Matroid Intersection Prophet Inequalities
We consider prophet inequalities subject to feasibility constraints that...
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...
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...
research
∙
05/25/2022
On Infinite Separations Between Simple and Optimal Mechanisms
We consider a revenue-maximizing seller with k heterogeneous items for s...
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...
research
∙
07/08/2021
Proof-of-Stake Mining Games with Perfect Randomness
Proof-of-Stake blockchains based on a longest-chain consensus protocol a...
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...
research
∙
01/10/2021
Approximately Strategyproof Tournament Rules in the Probabilistic Setting
We consider the manipulability of tournament rules which map the results...
research
∙
11/19/2020
Optimal Multi-Dimensional Mechanisms are not Local
Consider the problem of implementing a revenue-optimal, Bayesian Incenti...
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...
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 ...
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...
research
∙
06/10/2020
Auction learning as a two-player game
Designing an incentive compatible auction that maximizes expected revenu...
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...
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...
research
∙
03/02/2020
A Permutation-Equivariant Neural Network Architecture For Auction Design
Designing an incentive compatible auction that maximizes expected revenu...
research
∙
02/25/2020
Binary Scoring Rules that Incentivize Precision
All proper scoring rules incentivize an expert to predict accurately (re...
research
∙
02/15/2020
Optimal Mechanism Design for Single-Minded Agents
We consider revenue-optimal mechanism design in the interdimensional set...
research
∙
02/15/2020
When to Limit Market Entry under Mandatory Purchase
We study a problem inspired by regulated health insurance markets, such ...
research
∙
11/18/2019
Optimal Single-Choice Prophet Inequalities from Samples
We study the single-choice Prophet Inequality problem when the gambler i...
research
∙
11/15/2019
New Query Lower Bounds for Submodular Function MInimization
We consider submodular function minimization in the oracle model: given ...
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...
research
∙
09/23/2019
Persuasion and Incentives Through the Lens of Duality
Lagrangian duality underlies both classical and modern mechanism design....
research
∙
07/12/2019
Asynchronous Majority Dynamics in Preferential Attachment Trees
We study information aggregation in networks where agents make binary de...
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...
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...
research
∙
02/26/2019
Selling a Single Item with Negative Externalities
We consider the problem of regulating products with negative externaliti...
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...
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...
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...
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...
research
∙
11/21/2018
Bitcoin: A Natural Oligopoly
Although Bitcoin was intended to be a decentralized digital currency, in...
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...
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...
research
∙
11/25/2017
Selling to a No-Regret Buyer
We consider the problem of a single seller repeatedly selling a single i...
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...
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...
research
∙
06/27/2017