Automated online mechanism design and prophet inequalities

Recent work on online auctions for digital goods has explored the role of optimal stopping theory — particularly secretary problems — in the design of approximately optimal online mechanisms. This work generally assumes that the size of the market (number of bidders) is known a priori, but that the mechanism designer has no knowledge of the distribu-tion of bid values. However, in many real-world applica-tions (such as online ticket sales), the opposite is true: the seller has distributional knowledge of the bid values (e.g., via the history of past transactions in the market), but there is uncertainty about market size. Adopting the perspective of automated mechanism design, introduced by Conitzer and Sandholm, we develop algorithms that compute an optimal, or approximately optimal, online auction mechanism given access to this distributional knowledge. Our main results are twofold. First, we show that when the seller does not know the market size, no constant-approximation to the optimum efficiency or revenue is achievable in the worst case, even un-der the very strong assumption that bid values are i.i.d. sam-ples from a distribution known to the seller. Second, we show that when the seller has distributional knowledge of the mar-ket size as well as the bid values, one can do well in sev-eral senses. Perhaps most interestingly, by combining dy-namic programming with prophet inequalities (a technique from optimal stopping theory) we are able to design and an-alyze online mechanisms which are temporally strategyproof (even with respect to arrival and departure times) and approx-imately efficiency(revenue)-maximizing. In exploring the in-terplay between automated mechanism design and prophet inequalities, we prove new prophet inequalities motivated by the auction setting