Revenue maximization and prophet inequalities

Speaker  Balasubramanian Sivan

Host  Yuval Peres

Affiliation  MSR

Duration  00:42:31

Date recorded  19 September 2013

Consider the problem faced by a seller desiring to maximize revenue with m items, in a market with n unit-demand buyers (interested in buying at most one item). The valuation of buyer i for item j is independently drawn from distribution Fij. The design of revenue optimal mechanisms is well understood in the special case of m=1 item. However, the general problem had been open for long. In this talk, I will begin with the special case of 1 buyer and m items, and discuss the design and proof of an approximately revenue optimal mechanism. Emphasis will be on the proof and connection to prophet inequalities. I will discuss the extension to multiple buyers, and a recent generalization of prophet inequalities that has been used to approximate revenue maximization problems with matroidal feasibility constraints. The resulting mechanisms in all cases are simple posted price mechanisms. No prior knowledge of mechanism design will be assumed.

©2013 Microsoft Corporation. All rights reserved.
> Revenue maximization and prophet inequalities