# Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities

arXiv: https://arxiv.org/abs/2102.10261 · HTML: https://mlsanity.com/paper/2102.10261/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Feb 2021.

## Built on by (most cited first, 3 of 3)

- [Bandit Algorithms for Prophet Inequality and Pandora's Box](https://mlsanity.com/paper/2211.08586/) (2022)
- [MAGNOLIA: Matching Algorithms via GNNs for Online Value-to-go Approximation](https://mlsanity.com/paper/2406.05959/) (2024)
- [The Competition Complexity of Prophet Inequalities with Correlations](https://mlsanity.com/paper/2409.06868/) (2024)

## Abstract (arXiv)

The rich literature on online Bayesian selection problems has long focused on so-called prophet inequalities, which compare the gain of an online algorithm to that of a "prophet" who knows the future. An equally-natural, though significantly less well-studied benchmark is the optimum online algorithm, which may be omnipotent (i.e., computationally-unbounded), but not omniscient. What is the computational complexity of the optimum online? How well can a polynomial-time algorithm approximate it? We study the above questions for the online stochastic maximum-weight matching problem under vertex arrivals. For this problem, a number of 1/2-competitive algorithms are known against optimum offline. This is the best possible ratio for this problem, as it generalizes the original single-item prophet inequality problem. We present a polynomial-time algorithm which approximates the optimal online algorithm within a factor of 0.51 -- beating the best-possible prophet inequality. In contrast, we show that it is PSPACE-hard to approximate this problem within some constant α < 1.