Timezone: »

 
Poster
Maximizing Revenue under Market Shrinkage and Market Uncertainty
Maria-Florina Balcan · Siddharth Prasad · Tuomas Sandholm

Wed Nov 30 02:00 PM -- 04:00 PM (PST) @ Hall J #303
in Poster Session 4 »

A shrinking market is a ubiquitous challenge faced by various industries. In this paper we formulate the first formal model of shrinking markets in multi-item settings, and study how mechanism design and machine learning can help preserve revenue in an uncertain, shrinking market. Via a sample-based learning mechanism, we prove the first guarantees on how much revenue can be preserved by truthful multi-item, multi-bidder auctions (for limited supply) when only a random unknown fraction of the population participates in the market. We first present a general reduction that converts any sufficiently rich auction class into a randomized auction robust to market shrinkage. Our main technique is a novel combinatorial construction called a winner diagram that concisely represents all possible executions of an auction on an uncertain set of bidders. Via a probabilistic analysis of winner diagrams, we derive a general possibility result: a sufficiently rich class of auctions always contains an auction that is robust to market shrinkage and market uncertainty. Our result has applications to important practically-constrained settings such as auctions with a limited number of winners. We then show how to efficiently learn an auction that is robust to market shrinkage by leveraging practically-efficient routines for solving the winner determination problem.

Keywords: revenue maximization · Shrinking markets · gross substitutes · market uncertainty · automated mechanism design · combinatorial auctions

Author Information

Maria-Florina Balcan (Carnegie Mellon University)
Siddharth Prasad (Computer Science Department, Carnegie Mellon University)
Tuomas Sandholm (CMU, Strategic Machine, Strategy Robot, Optimized Markets)

More from the Same Authors