Prophet Inequality for Bipartite Matching: Merits of Being Simple and Nonadaptive: Static Vertex Prices Earn One Third of the Prophet's Expected Matching ValueResearch Paper
A prophet inequality compares an online decision maker, who sees random values one at a time and must decide irrevocably, with a prophet who sees every value in advance. The classical single-item version (Krengel–Sucheston, Samuel-Cahn) shows that a single threshold earns half of the prophet's expected maximum. These guarantees are the analytic core of poste…