7 papers
On Infinite Separations Between Simple and Optimal Mechanisms
C. Alexandros Psomas, Ariel Schvartzman, S. Matthew Weinberg
We consider a revenue-maximizing seller with heterogeneous items for sale to a single additive buyer, whose values are drawn from a known, possibly correlated prior $\mathcal{D…
Optimal Mechanism Design for Single-Minded Agents
Nikhil Devanur, Kira Goldner, Raghuvansh Saxena +2
We consider revenue-optimal mechanism design in the interdimensional setting, where one dimension is the 'value' of the buyer, and one is a 'type' that captures some auxiliary info…
Approximately Strategyproof Tournament Rules: On Large Manipulating Sets and Cover-Consistence
Ariel Schvartzman, S. Matthew Weinberg, Eitan Zlatin +1
We consider the manipulability of tournament rules, in which teams play a round robin tournament and a winner is (possibly randomly) selected based on the outcome of all $\bino…
Approximation Schemes for a Unit-Demand Buyer with Independent Items via Symmetries
Pravesh Kothari, Divyarthi Mohan, Ariel Schvartzman +2
We consider a revenue-maximizing seller with items facing a single buyer. We introduce the notion of symmetric menu complexity of a mechanism, which counts the number of distin…
Smoothed Analysis of Multi-Item Auctions with Correlated Values
Christos-Alexandros Psomas, Ariel Schvartzman, S. Matthew Weinberg
Consider a seller with m heterogeneous items for sale to a single additive buyer whose values for the items are arbitrarily correlated. It was previously shown that, in such settin…
The menu complexity of "one-and-a-half-dimensional" mechanism design
Raghuvansh R. Saxena, Ariel Schvartzman, S. Matthew Weinberg
We study the menu complexity of optimal and approximately-optimal auctions in the context of the "FedEx" problem, a so-called "one-and-a-half-dimensional" setting where a single bi…