Prior independent mechanisms via prophet inequalities with limited information

• 成果类型: Article
• 署名作者: Azar, Pablo D.; Kleinberg, Robert; Weinberg, S. Matthew
• 署名单位: Massachusetts Institute of Technology (MIT); Cornell University; Princeton University
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2018.05.006
• 发表日期: 2019
• 页码: 511-532
• 关键词: Game theory; Bargaining theory

摘要

Prophet inequalities have recently become a fundamental tool in the design of sequential and multi-dimensional mechanisms in Bayesian settings. However, existing mechanisms- as well as the underlying prophet inequalities behind their analysis-require sophisticated information about the distribution from which inputs are drawn. Our goal in this work is to design prior-independent sequential and multi-dimensional mechanisms. To this end, we first design prophet inequalities that require knowing only a single sample from the input distribution. These results come in two forms: the first is via a reduction from single-sample prophet inequalities to secretary algorithms. The second is via novel single-sample prophet inequalities for k-uniform matroids. Leveraging our new prophet inequalities, we construct the first prior-independent sequential mechanisms where the seller does not know the order in which buyers arrive, and buyers may have asymmetric value distributions. We also construct the first prior-independent multi-dimensional mechanism where buyers may have asymmetric value distributions. (C) 2018 Elsevier Inc. All rights reserved.