# Prophet inequality for bipartite matching: merits of being simple and non adaptive

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

## Key facts

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

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

- [Improved Regret and Contextual Linear Extension for Pandora's Box and Prophet Inequality](https://mlsanity.com/paper/2505.18828/) (2025)
- [The Competition Complexity of Prophet Inequalities with Correlations](https://mlsanity.com/paper/2409.06868/) (2024)
- [Optimal No-Regret Learning for Repeated Prophet Inequality](https://mlsanity.com/paper/2609.23265/) (2026)

## Abstract (arXiv)

We consider Bayesian online selection problem of a matching in bipartite graphs, i.e., online weighted matching problem with edge arrivals where online algorithm knows distributions of weights, that corresponds to the intersection of two matroids in [Kleinberg and Wienberg STOC 12] model. We consider a simple class of non adaptive vertex-additive policies that assign static prices to all vertices in the graph and accept each edge only if its weight exceeds the sum of the prices of the edge's endpoints. We show existence of a vertex-additive policy with the expected payoff of at least one third of the prophet's payoff and present gradient decent type algorithm that quickly converges to the desired vector of vertex prices. This improves the adaptive online policy of [Kleinberg and Wienberg STOC 12] for the intersection of two matroids in two ways: our policy is non adaptive and has better approximation guarantee of 3 instead of previous guarantee of 5.82 against the prophet. We give a complementary lower bound of 2.25 for any online algorithm in the bipartite matching setting.