Prophet Matching with General Arrivals

Tomer Ezra (), Michal Feldman (), Nick Gravin () and Zhihao Gavin Tang ()
Additional contact information
Tomer Ezra: Blavatnik School of Computer Science, Tel Aviv University, Tel Aviv 6997801, Israel
Michal Feldman: Blavatnik School of Computer Science, Tel Aviv University, Tel Aviv 6997801, Israel; Microsoft Research, Herzliya 4672415, Israel
Nick Gravin: Institute of Theoretical Computer Science, Shanghai University of Finance and Economics, Shanghai 200433, China
Zhihao Gavin Tang: Institute of Theoretical Computer Science, Shanghai University of Finance and Economics, Shanghai 200433, China

Mathematics of Operations Research, 2022, vol. 47, issue 2, 878-898

Abstract: 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 from a 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 the matching or not. Under vertex arrival, the weights of all edges from the 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 novel unified framework of batched-prophet inequalities that captures online settings where 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.

Keywords: Primary: 68W27; secondary: 90C27; 68Q87; prophet inequality; online matching; online stochastic matching; online contention resolution scheme (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2021.1152 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:47:y:2022:i:2:p:878-898

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().