Revenue maximization and prophet inequalities

Опубликовано 27 июля 2016, 2:07

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 F_{ij}. 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.