Matroid prophet inequalities and applications to multi-dimensional mechanism design

• 成果类型: Article
• 署名作者: Kleinberg, Robert; Weinberg, S. Matthew
• 署名单位: Cornell University; Massachusetts Institute of Technology (MIT)
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2014.11.002
• 发表日期: 2019
• 页码: 97-115
• 关键词: Multi-dimensional mechanism design; Auction theory; revenue; online optimization; stochastic optimization

摘要

Consider a gambler who observes a sequence of independent random numbers and is allowed to stop at any time, claiming reward equal to the most recent observation. The famous prophet inequality of Krengel, Sucheston, and Garling asserts that a gambler who knows the distribution of each random variable can achieve half as much reward, in expectation, as a prophet who knows the sampled values and can choose the largest one. We generalize this result to settings in which the gambler and the prophet are allowed to make multiple selections, subject to a matroid constraint, showing that the gambler can still achieve half as much reward as the prophet. Our results imply improved bounds on the ability of sequential posted-price mechanisms to approximate optimal mechanisms in single-parameter and multi-parameter Bayesian settings. In particular, we provide the first efficiently computable constant-factor approximations to the Bayesian optimal revenue in certain multi-parameter settings. (C) 2014 Published by Elsevier Inc.