Revenue maximization and prophet inequalities

  • Balasubramanian Sivan | MSR

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.

Speaker Details

Balasubramanian Sivan completed his PhD at the University of Wisconsin-Madison advised by Prof. Shuchi Chawla, and is presently a post-doc in the theory group. His interests include approximation and online algorithms with stochastic input, prior robust/independent optimization, algorithmic game theory, and mechanism design in particular.

    • Portrait of Balasubramanian Sivan

      Balasubramanian Sivan

    • Portrait of Jeff Running

      Jeff Running

Series: Microsoft Research Talks