Prophet Matching with General Arrivals

• 成果类型: Article
• 署名作者: Ezra, Tomer; Feldman, Michal; Gravin, Nick; Tang, Zhihao Gavin
• 署名单位: Tel Aviv University; Shanghai University of Finance & Economics
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2021.1152
• 发表日期: 2022
• 页码: 878-898
• 关键词: INEQUALITIES; algorithms; maximum

摘要

We provide prophet inequality algorithms for online weighted matching in general (nonbipartite) graphs, under two well-studied arrival models: edge arrival and vertex arrival. The weights of the edges are drawn froma priori known probability distribution. Under edge arrival, the weight of each edge is revealed on arrival, and the algorithm decides whether to include it in thematching or not. Under vertex arrival, theweights of all edges fromthe newly arriving vertex to all previously arrived vertices are revealed, and the algorithm decides which of these edges, if any, to include in the matching. To study these settings, we introduce a novelunified framework of batched-prophet inequalities that captures online settingswhere elements arrive in batches. Our algorithms rely on the construction of suitable online contention resolution scheme (OCRS). We first extend the framework of OCRS to batched-OCRS, we then establish a reduction from batched-prophet inequality to batched-OCRS, and finally we construct batched-OCRSs with selectable ratios of 0.337 and 0.5 for edge and vertex arrival models, respectively. Both results improve the state of the art for the corresponding settings. For vertex arrival, our result is tight. Interestingly, a pricing-based prophet inequality with comparable competitive ratios is unknown.