Abstract: A recent exciting line of work proposes using machine learning to automatically design high-revenue mechanisms (auctions, pricing schemes, etc.) from samples. We present some new approaches that stem from this idea---including algorithms for efficient learning, and learning when samples are not even available.
First, we tackle algorithmic challenges of learning high-revenue two-part tariff structures from samples. A two-part tariff is a pricing scheme consisting of an up-front lump-sum fee and a per-unit fee---real-world examples include gym memberships, cell phone plans, etc. We present practically-efficient algorithms for learning two-part tariff structures in various scenarios. We then show that situations involving market segmentation induce computational hardness, but show how to circumvent that hardness when buyers are identically distributed.
We then present some new approaches to the elusive problem of designing high-revenue multi-item, multi-bidder auctions for limited supply. While the first part of the talk dealt with "learning across instances", here we assume that the mechanism designer is faced with a single instance of bidders who show up. First, we present a new "learning within an instance" mechanism that generalizes and improves upon previous random-sampling mechanisms for unlimited supply, and prove strong revenue guarantees for this mechanism. Then, we show how to learn an auction that is robust to market shrinkage. If there is a fixed population of buyers known to the seller, but only some random (unknown) fraction of them participate in the market, how much revenue can the seller guarantee?
Joint work with Nina Balcan and Tuomas Sandholm