The Competition Complexity of Prophet Inequalities

• 成果类型: Article; Early Access
• 署名作者: Brustle, Johannes; Correa, Jose; Dutting, Paul; Ezra, Tomer; Feldman, Michal; Verdugo, Victor
• 署名单位: Sapienza University Rome; Universidad de Chile; Harvard University; Tel Aviv University; Pontificia Universidad Catolica de Chile; Pontificia Universidad Catolica de Chile
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2024.0684
• 发表日期: 2025
• 关键词: Combinatorial auctions; mechanisms

摘要

We study the classic single-choice prophet inequality problem through a resource augmentation lens. Our goal is to bound the (1- E)-competition complexity of different types of online algorithms. This metric asks for the smallest k such that the expected value of the online algorithm on k copies of the original instance is at least a (1 - E)-approximation to the expected off-line optimum on a single copy. We show that block threshold algorithms, which set one threshold per copy, are optimal and give a tight bound of k = Theta(log log 1/E). This shows that block threshold algorithms approach the off-line optimum doubly exponentially fast. For single threshold algorithms, we give a tight bound of k = Theta(log 1/E), establishing an exponential gap between block threshold algorithms and single threshold algorithms. Our model and results pave the way for exploring resource-augmented prophet inequalities in combinatorial settings. In line with this, we present preliminary findings for bipartite matching with one-sided vertex arrivals as well as in XOS combinatorial auctions. Our results have a natural competition complexity interpretation in mechanism design and pricing applications.